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

作     者：王小明 朱松平 陈庆新 毛宁 WANG Xiaoming;ZHU Songping;CHEN Qingxin;MAO Ning

作者机构：广东工业大学广东省计算机集成制造重点实验室广东广州510006 

出 版 物：《计算机集成制造系统》 (Computer Integrated Manufacturing Systems)

年 卷 期：2024年第30卷第6期

页      面：2044-2055页

核心收录：

学科分类：081203[工学-计算机应用技术] 08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

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

主　　题：设计项目 随机返工 紧急插单 可抢占调度 次优策略 

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