基于遗传算法的多模式资源约束项目调度问题研究*

为解决多模式资源约束项目调度问题，提出了一种混合遗传算法的求解方法。该算法采用二维编码方法来表示问题的解，基因的值表示任务的优先权和执行模式，每条染色体对应一个满足逻辑关系约束的可行任务排序，根据染色体所对应的任务调度顺序和执行模式序列可以获得一个满足资源约束的项目调度方案。应用该编码方法进行选择、交叉和变异等遗传操作，能够使搜索范围遍及整个问题解空间。实际应用表明，该算法能快速求得问题的最优解或近似最优解。

Research of Multi Mode Resource Constrained Project Scheduling Problem Based on Genetic Algorithm

This paper developes a hybrid genetic algorithm for solving Multi-Mode Resource-Constrained Project Scheduling Problem(MRCPSP).The objective is to determine a mode and a start time for each activity such that all constraints are observed and the project duration is minimized.A two-dimensional encoding is used in the algorithm.Each gene represents the priority and execution mode of an activity.A feasible activity sort meeting precedence constraints can be generated from a given chromosome.It can construct a scheduling meeting resource constraints by selecting the activities and their execution mode in order of their appearance in the activity sort.Using the encoding the algorithm can get all possible schedulings through genetic operators: selection,crossover,mutation.Results show that the algorithm can get near-optimal solutions of MRCPSP rapidly.