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

来源：计算机集成制造系统杂志2024年第6期北京时间：

作者：王小明, 朱松平, 陈庆新, 毛宁

单位：广东工业大学广东省计算机集成制造重点实验室

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

关键词：设计项目,随机返工,紧急插单,可抢占调度,次优策略

基金资助：国家自然科学基金资助项目(71972053,61973089,51505090)。