多模式资源受限项目调度问题的混合遗传算法

多模式资源受限项目调度问题是一种NP难的组合优化问题.提出了与基于关键链的启发式算法相结合的二层混合遗传算法对该问题进行求解.在由上层算法确定的调度顺序下,下层遗传算法结合基于关键链的启发式算法,对系统资源重新优化配置,使算法加速向最优解区域收敛,并在下层设计了随迭代代数增加的可变变异概率,以避免早熟收敛.利用标准问题库对算法进行测试,分析问题参数与算法参数对算法结果的影响,发现实验结果的绩效随迭代数的增加而提高,算法耗时随任务数和迭代数的增加而增加.数值测试结果验证了算法的可行性和可靠性.

Hybrid genetic algorithm for multi-mode resource-constrained project scheduling problems

The multi-mode resource-constrained project scheduling problem is a kind of NP-hard combination optimization problem.To solve it a bi-level hybrid genetic algorithm combined with a critical chain-based heuristic is proposed.Under the given project scheduling specified by the upper-level algorithm,combined with a critical chain-based heuristic,the lower-level genetic algorithm reallocates the resources to shorten the project duration so that the rate of converging to the global optimum district is improved,and a variable mutation probability is developed to avoid premature convergence.Finally,a computational study for a standard set of project instances is carried out to test the validity of the algorithm,and the effects of the problem parameters and algorithm parameters on the results are analyzed.It can be found that the performance of the experimental results improves with the increment of the generations,and the algorithm takes more CPU time when the task numbers or the generations increase.Numerical examples testify the feasibility and reliability of the algorithm.