求解柔性资源受限项目调度问题的多种群遗传算法

Multi-population Genetic Algorithm for Multi-skill Resource-constrained ProJect Scheduling Problem

柔性资源普遍存在于制造业生产制造的各个环节中,提高了资源利用率和生产效益。以柔性资源为研究对象,建立了以最小化项目完成工期为目标的柔性资源受限项目调度问题的数学模型。针对现有标准遗传算法过早地收敛从而使整个遗传搜索无法求解出全局最优值的缺陷,提出了一种改进的多种群遗传算法来求解该问题模型。算法对作业优先级列表编码,引入交叉移民算子实现多种群间的协同进化,在解码过程中运用一种启发式柔性资源技能分配算法为作业分配资源,同时通过改进的串行调度生成方案对作业调度。最后通过标准算例库PSPLIB进行数值试验,验证了所提算法求解该问题的有效性。

Multi-skill resource resource is popularly existing in the process of production and manufacturing,which improves resource utilization and production efficiency.This paper makes the multi-skill resource as the obJect and presents a mathematical model of multi-skill resource-constrained proJect scheduling problem(MSRCPSP)with the obJective of minimizing the makespan of the proJect.In order to solve the disadvantage that the existing genetic algorithm converges prematurely and the whole algorithm cannot solve the global optimal value,an improved multi-population genetic algorithm is proposed to solve the problem model.The algorithm is designed to code Job priority list and introduced the cross immigration operator to promote the co-evolution of different groups.In the decoding process,a heuristic flexible resource skill allocation algorithm is used to allocate resources for Jobs,and an improved serial scheduling generation scheme is used to schedule Jobs.Finally,numerical experiments are carried out with standard case library PSPLIB to verify the effectiveness of the proposed algorithm in solving MSRCPSP.