资源转移视角下分布式多项目调度的启发式规则设计及评估  

Design and evaluation of heuristic rules for decentralized multi-project scheduling from a resource transferring perspective

作　　者：刘婉君 张静文[1] 刘翠方 丁文静 LIU Wanjun;ZHANG Jingwen;LIU Cuifang;DING Wenjing(School of Management,Northwestern Polytechnical University,Xi'an 710072,China)

机构地区：[1]西北工业大学管理学院,西安710072

出　　处：《系统工程理论与实践》2024年第10期3418-3433,共16页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(71971173,72201209);西北工业大学博士论文创新基金(CX2023069,SOMBC202203)。

摘　　要：鉴于优先规则启发式算法求解多项目调度的优势,基于带有全局资源转移时间的分布式多项目调度问题,设计多种启发式算法及优先规则并针对不同优化目标评估其性能.首先,基于最小化多项目组合延迟百分比和最小化平均子项目延迟时间两种目标构建问题的混合整数规划模型.其次,设计改进的单项目、coupled和decoupled启发式三种类型的优先规则启发式算法求解问题;针对每种启发式算法,分别改进传统求解资源约束型项目调度的串行和并行机制以适应新问题的全局资源转移时间特征,梳理现有用于求解单项目和多项目问题的优先规则,并根据全局资源特性设计新的规则;根据在调度机制中的不同作用,每种启发式算法下的优先规则被分类和组合并应用于改进的调度机制中,从而共获得4080种可求解新问题的启发式优先规则组合方案.最后,提出一种基于子项目位置分布的资源转移时间生成方法,结合MPSPLIB算例库中的分布式多项目算例构造测试算例;针对三种启发式算法及嵌入的4080种优先规则组合设计评估方案和指标并开展数值实验.研究结果表明:针对两种不同的优化目标,单项目启发式和decoupled启发式各有优势,但coupled启发式表现较差;与现有优先规则相比,提出的新优先规则可以更有效地优化两种目标;全局资源转移时间对多项目的两种目标均有重要影响.In view of the advantages of the priority rule-based heuristics in solving multi-project scheduling,various heuristics and priority rules were designed for the decentralized multi-project scheduling problem with global resource transfer times and their performance on different objectives was evaluated.Firstly,a mixed integer programming model was constructed based on the two objectives portfolio percentage delay and average project delay.Secondly,three improved priority rule-based heuristics,single-project,coupled and decoupled heuristics,were designed to solve the problem.For each heuristic,the traditional serial and parallel schedule schemes for multi-project scheduling were improved to adapt to the global resource transfer time characteristics of the new problem;the existing priority rules for solving single project and multi-project problems were sorted out,and new rules were proposed according to the global resources characteristics.According to the different roles in the schedule schemes,the priority rules under each heuristic method were classified and combined and applied to the improved schedule schemes,so that a total of 4080 priority rule combinations that can solve the new problem were obtained.Finally,a resource transfer time generation mechanism based on project location distribution was proposed,and test instances were constructed based on the MPSPLIB dataset;the evaluation schemes and indicators were designed for three heuristics and the corresponding 4080 combination schemes,based on which numerical experiments were carried out.The results showed that the single-project heuristic and the decoupled heuristic had their own advantages for different objectives,but the coupled heuristic performed poorly;the new priority rules proposed in this paper performed better than the existing rules;global resource transfer time had a significant impact on both objectives of the multi-project.

关 键 词：全局资源转移时间 分布式多项目 decoupled启发式 优先规则性能 改进的调度生成机制 

分 类 号：C935[经济管理—管理学] F224.33