基于关键链改进搜索的遗传算法求解分布式多项目调度

针对基于多代理系统求解分布式多项目调度问题的不足, 开发了一种适应性的遗传算法ccm_GA。ccm_GA的独特性体现为两点:第一, 修正的串行调度过程分两个阶段分别消除全局资源和本地资源冲突; 第二, 在满足两类资源约束的调度方案中, 识别出关键链并改变关键活动在活动序列编码中的位置以增加解的多样性从而提高搜索效率。设计并实施大规模数值实验测试算法性能, 与现有文献中的六种算法作对比, 结果表明:ccm_GA在50%的算例集上获得的测试指标都好于六种算法, 且对于资源约束越紧的算例集, ccm_GA的求解效果越好。

An Adapted Genetic Algorithm Based on the Critical Chain with Improving Search to Solve the Decentralized Resource-constrained Multi-project Scheduling Problem

Aimed at the deficiency of solving decentralized multi-project scheduling problem based on multi-agent system,an adapted genetic algorithm ccm_GA is developed.The uniqueness of the ccm_GA is reflected in two aspects.First,the amended serial scheduling process eliminatesboth global and local resource conflicts in two stages.Second,in scheduling schemes that satisfy two types of resource constraints,the critical chain is identified and the position of the critical activity in the activity sequence coding is changed to increase the diversity of the solution so as to improve the search efficiency.Numerical experiments are designed and carried out to test the performance of the algorithm,and the results are compared with the six algorithms in the existing literature.The results show that:ccm_GA has better test indexes than the other six algorithms in 50%of the example sets.And the tighter the resource constraints are,the better the solution results of ccm_GA are.