融入逻辑关系的项目调度遗传算法

Genetic Algorithm for Project Scheduling with Logical Relation

为解决复杂施工项目中存在的模型表述和计算问题,研究互斥、共存、依赖3种逻辑关系在调度计划表述模型中的应用,建立复杂施工调度问题的混合整数线性规划模型,并设计一种改进的遗传算法以快速求解模型。基于布尔变量划分的顺序编码方式,将染色体分为独立变量和半独立变量编码基因段,以最短工期的倒数为适应度函数进行最优解的启发式求解。在遗传操作后进行冲突检测,消除由种群初始化、交叉和变异操作生成的违反约束规则的个体,保证算法的有效性。工程案例计算结果表明,与传统精确式算法相比,该算法能有效缩短大型工程项目工期的求解时间。

In order to solve the problems of model expression and calculation in complex construction projects,this paper conducts a study on the application of three logical relations,including mutual exclusion,coexistence and dependence in the scheduling project expression model.On this basis,a mixed integer linear programming model for complex construction scheduling problem is proposed and an improved genetic algorithm is designed to quickly solve the model.Based on the sequential coding manner of Boolean variable division,the chromosome is divided into independent variable and semi-independent variable coding gene segments,and the reciprocal of the shortest duration is used as the fitness function to search the optimal solution in a heuristic approach.Then,the conflict detection is performed after genetic operations,so as to eliminate individuals who violate constraint rules generated by population initialization,crossover,and mutation operations,thus ensuring the effectiveness of the algorithm.The calculation results of project cases show that compared with the traditional precision algorithm,the proposed algorithm can effectively shorten the solution procedure of construction period in large construction projects.