计算机工程 ›› 2020, Vol. 46 ›› Issue (1): 279-285.doi: 10.19678/j.issn.1000-3428.0054247

• 开发研究与工程应用 • 上一篇    下一篇

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

刘尧, 宋元斌, 李云祥   

  1. 上海交通大学 船舶海洋与建筑工程学院, 上海 200240
  • 收稿日期:2019-03-15 修回日期:2019-05-04 出版日期:2020-01-15 发布日期:2019-04-29
  • 作者简介:刘尧(1992-),男,硕士研究生,主研方向为建筑信息模型、项目调度;宋元斌,高级工程师;李云祥,硕士。
  • 基金项目:
    国家自然科学基金"施工计划中的复杂时间关系表述及施工顺序优化"(71271137);上海市自然科学基金"大型复杂工程项目计划中的复杂时间关系表述及调度算法研究"(12ZR1415100)。

Genetic Algorithm for Project Scheduling with Logical Relation

LIU Yao, SONG Yuanbin, LI Yunxiang   

  1. School of Naval Architecture, Ocean and Civil Engineering, Shanghai Jiao Tong University, Shanghai 200240, China
  • Received:2019-03-15 Revised:2019-05-04 Online:2020-01-15 Published:2019-04-29

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

关键词: 项目调度, 逻辑关系, 顺序编码, 遗传算法, 混合整数线性规划

Abstract: 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.

Key words: project scheduling, logical relation, sequential coding, genetic algorithm, mixed integer linear programming

中图分类号: