考虑随机返工与紧急插单的可抢占设计项目群调度

Preemptive scheduling of design projects with random rework and urgent tasks

鉴于多项目并行以及因随机返工和紧急插单而导致的任务抢占特征,使设计项目群调度问题难以求解,而传统随机动态规划方法因维数灾难只能获得小规模问题的最优策略,为构造面向大规模问题的高效近似方法,提出将原随机调度问题近似分解为各个状态下的确定性调度子问题,从而获得原问题的次优策略。建立了确定性调度子问题的混合整数规划模型,并提出基于元启发式算法和优先规则的求解方法。基于标准测试集PSPLIB设计了多组计算实验,在不同调度环境下验证了所构建模型和算法的有效性。实验结果表明,元启发式算法不但在单项目平均拖期比目标下较最优规则提升了12%以上,而且具有较高的计算效率,能够满足实际决策需求。

The design projects scheduling problem is hard due to multiple concurrent projects,as well as preemptions caused by random rework and urgent tasks.Although an optimal policy of this problem can be theoretically obtained by traditional stochastic dynamic programming,it is computationally intractable due to the curse of dimensionality.To construct efficient approximation methods for large-scale problem instances,the original stochastic scheduling problem was approximately decomposed into deterministic scheduling sub-problems in each state to obtain a suboptimal policy.A mixed-integer programming model for the deterministic scheduling sub-problems was established and the solution methods based on meta-heuristics and priority rules were proposed.Computational experiments were conducted based on benchmark PSPLIB,which validated the effectiveness of the model and algorithm in different scheduling environments.Computational results showed that the meta-heuristics was improved by more than 12% under the objective of individual projects′average percent delay compared with the best priority rule.The meta-heuristics were practical because of their high computational efficiency.