混合工作日历下资金受限工程项目工期最短化任务指派方法
|
摘要
针对一类混合工作日历下资金受限工程项目工期最短化任务指派问题,提出了一种基于遗传算法的优化方法。对混合工作日历下资金受限工程项目工期最短化任务指派问题进行了描述,并设计了遗传算法对问题进行求解。提出了基于承包商工作日历的时间推算机制,设计了时间推算函数作为混合工作日历下工程项目工期推算的基础;算法采用"基于承包商号的整数编码方式"对个体进行编码和"拒绝策略"产生初始可行种群,使用"交叉算子改进策略"和"两点交叉方式"进行交叉以保证交叉后子个体可行,采用"拒绝策略"和"单点变异方式"进行变异以保证变异后子个体可行,解码过程中基于"关键路径法"和"正向推算函数FC"推算项目工期。通过案例分析验证了所提方法的有效性。
This paper presents an optimization method using a genetic algorithm to solve the task assignment problem of achieving the shortest project duration for an engineering project with capital limit under mixed work calendars.Firstly,the problem was described.Then,agenetic algorithm was designed to solve the researched problem.A time reckoning mechanism based on the contractor's work calendar was proposed and related time reckoning functions were designed as the basis of calculating project duration for an engineering project under mixed work calendars.An integer coding method based on contract number was used to encode the chromosome.The refusal strategy was used in the population initialization to ensure the feasibility of chromosomes.To ensure the feasibility of offspring chromosomes,an improved crossover operator was used in the crossover operation based on the two-point crossover method,and a refusal strategy was used in the mutation operation based on the single-point mutation method.Finally based on the critical path method,the forward reckoning function FC was used to get the shortest project duration.The effectiveness of the proposed method was verified by a case study.
This paper presents an optimization method using a genetic algorithm to solve the task assignment problem of achieving the shortest project duration for an engineering project with capital limit under mixed work calendars.Firstly,the problem was described.Then,agenetic algorithm was designed to solve the researched problem.A time reckoning mechanism based on the contractor's work calendar was proposed and related time reckoning functions were designed as the basis of calculating project duration for an engineering project under mixed work calendars.An integer coding method based on contract number was used to encode the chromosome.The refusal strategy was used in the population initialization to ensure the feasibility of chromosomes.To ensure the feasibility of offspring chromosomes,an improved crossover operator was used in the crossover operation based on the two-point crossover method,and a refusal strategy was used in the mutation operation based on the single-point mutation method.Finally based on the critical path method,the forward reckoning function FC was used to get the shortest project duration.The effectiveness of the proposed method was verified by a case study.
引文
[1]寿涌毅,彭晓峰,李菲,等.抢占式资源受限项目调度问题的遗传算法[J].浙江大学学报(工学版),2014,48(8):1473-1480.SHOU Yongyi,PENG Xiaofeng,LI Fei,et al.Genetic algorithm for the preemptive resource-constrained project scheduling problem[J].Journal of Zhejiang University(Engineering Science),2014,48(8):1473-1480.(in Chinese)
[2]靳金涛,聂兰顺,战德臣,等.基于人工蜂群的空间资源受限项目调度算法[J].计算机集成制造系统,2014,20(5):1088-1098.JIN Jintao,NIE Lanshun,ZHAN Dechen,et al.Spatial-resource constrained project scheduling algorithm based on artificial bee colony[J].Computer Integrated Manufacturing Systems,2014,20(5):1088-1098.(in Chinese)
[3]Besikci U,BilgeU,Ulusoy G.Multi-mode resource constrained multi-project scheduling and resource portfolio problem[J].European Journal of Operational Research,2015,240(1):22-31.
[4]Almeida B F,Correia I,Saldanha-Da-gama F.Priority-based heuristics for the multi-skill resource constrained project scheduling problem[J].Expert Systems with Applications,2016,57:91-103.
[5]何立华,张连营.基于资源波动成本的工程项目资源均衡优化[J].管理工程学报,2015,29(2):167-174.HE Lihua,ZHANG Lianying.Resource leveling optimization based on resource fluctuation cost in construction projects[J].Journal of Industrial Engineering and Engineering Management,2015,29(2):167-174.(in Chinese)
[6]张连营,岳岩.工期:成本:质量的模糊均衡优化及其Pareto解[J].同济大学学报(自然科学版),2013,41(2):303-308,316.ZHANG Lianying,YUE Yan.Fuzzy trade-off of time-cost-quality in construction project and pareto solution[J].Journal of Tongji University(Natural Science),2013,41(2):303-308,316.(in Chinese)
[7]Chakrabortty R K,Sarker R A,Essam D L.Multi-mode resource constrained project scheduling under resource disruptions[J].Computers&Chemical Engineering,2016,88:13-29.
[8]Kuhn H W.The Hungarian method for the assignment problem[J].Naval Research Logistics Quarterly,1955,2(1-2):83-97.
[9]周良泽.削高排除法求解指派问题[J].系统工程学报,1992,7(2):97-105.ZHOU Liangze.Solving assignment problem with the method of cutting top and exclusion[J].Journal of Systems Engineering,1992,7(2):97-105.(in Chinese)
[10]丁文仁.缩阵分析法——求解指派问题的新方法[J].系统工程理论与实践,1988,8(3):38-86.DING Wenren.New method to solve assignment problem-reduced matrix analyzing method[J].Systems Engineering theory&Practice,1988,8(3):38-86.
[11]Zhu H B,Liu D N,Zhang S Q,et al.Solving the Many to Many assignment problem by improving the Kuhn-Munkres algorithm with backtracking[J].Theoretical Computer Science,2016,618:30-41.
[12]周莉,张维华,徐射雕.求解指派问题的一次性分配算法[J].计算机工程与应用,2011,47(18):135-138,152.ZHOU Li,ZHANG Weihua,XU Shediao.One-time assignment algorithm to solve assignment problem[J].Computer Engineering and Applications,2011,47(18):135-138,152.(in Chinese)
[13]赵洪刚,杨竹君,孟庆华,等.指派问题新解法:目标值子矩阵法[J],浙江大学学报(理学版),2010,37(5):501-504.ZHAO Honggang,YANG Zhujun,MENG Qinghua,et al.New method of solving assignment problem-target value submatrix method[J].Journal of Zhejiang University(Science Edition),2010,37(5):501-504.(in Chinese)
[14]李珍萍,王亮.最短时限缺省指派问题的一种解法[J].运筹与管理,2000,9(2):55-61.LI Zhenping,WANG Liang.The absent assignment problem to the shortest time limit and its algorithm[J].Operations Research and Management Science,2000,9(2):55-61.(in Chinese)
[15]Mazzola J B,Neebe A W.Resource-constrained assignment scheduling[J].Operations Research,1986,34(4):560-572.
[16]郭强.人数少于任务数的全指派问题的迭代算法[J].计算机工程与应用,2007,43(24):91-93,103.GUO Qiang.Iterative algorithm of total assignment problem on persons less than jobs[J].Computer Engineering and Applications,2007,43(24):91-93,103.(in Chinese)
[17]Choi K,Kim G,Suh Y,et al.Assignment of collaborators to multiple business problems using genetic algorithm[J].Information Systems and e-Business Management,2017,15(4):877-895.
[18]Myszkowski P B,Skowroński M E,OlechP,et al.Hybrid ant colony optimization in solving multi-skill resourceconstrained project scheduling problem[J].Soft Computing,2015,19(12):3599-3619.
[19]Myszkowski P B,Skowroński M E,OlechP,et al.Hybrid ant colony optimization in solving multi-skill resourceconstrained project scheduling problem[J].Soft Computing,2015,19(12):3599-3619.
[20]王维博,冯全源.基于改进粒子群算法的工程项目综合优化[J].西南交通大学学报,2011,46(1):76-83.WANG Weibo,FENG Quanyuan.Synthesis optimization for construction project based on modified particle swarm optimization algorithm[J].Journal of SouthWest JiaoTong University,2011,46(1):76-83.(in Chinese)
[21]Gon9alves J F,Mendes J J M,Resende M G C.A genetic algorithm for the resource constrained multi-project scheduling problem[J].European Journal of Operational Research,2008,189(3):1171-1190.
[22]Ma W M,Che Y Y,Huang H,et al.Resource-constrained project scheduling problem with uncertain durations and renewable resources[J].International Journal of Machine Learning and Cybernetics,2016,7(4):613-621.
[2]靳金涛,聂兰顺,战德臣,等.基于人工蜂群的空间资源受限项目调度算法[J].计算机集成制造系统,2014,20(5):1088-1098.JIN Jintao,NIE Lanshun,ZHAN Dechen,et al.Spatial-resource constrained project scheduling algorithm based on artificial bee colony[J].Computer Integrated Manufacturing Systems,2014,20(5):1088-1098.(in Chinese)
[3]Besikci U,BilgeU,Ulusoy G.Multi-mode resource constrained multi-project scheduling and resource portfolio problem[J].European Journal of Operational Research,2015,240(1):22-31.
[4]Almeida B F,Correia I,Saldanha-Da-gama F.Priority-based heuristics for the multi-skill resource constrained project scheduling problem[J].Expert Systems with Applications,2016,57:91-103.
[5]何立华,张连营.基于资源波动成本的工程项目资源均衡优化[J].管理工程学报,2015,29(2):167-174.HE Lihua,ZHANG Lianying.Resource leveling optimization based on resource fluctuation cost in construction projects[J].Journal of Industrial Engineering and Engineering Management,2015,29(2):167-174.(in Chinese)
[6]张连营,岳岩.工期:成本:质量的模糊均衡优化及其Pareto解[J].同济大学学报(自然科学版),2013,41(2):303-308,316.ZHANG Lianying,YUE Yan.Fuzzy trade-off of time-cost-quality in construction project and pareto solution[J].Journal of Tongji University(Natural Science),2013,41(2):303-308,316.(in Chinese)
[7]Chakrabortty R K,Sarker R A,Essam D L.Multi-mode resource constrained project scheduling under resource disruptions[J].Computers&Chemical Engineering,2016,88:13-29.
[8]Kuhn H W.The Hungarian method for the assignment problem[J].Naval Research Logistics Quarterly,1955,2(1-2):83-97.
[9]周良泽.削高排除法求解指派问题[J].系统工程学报,1992,7(2):97-105.ZHOU Liangze.Solving assignment problem with the method of cutting top and exclusion[J].Journal of Systems Engineering,1992,7(2):97-105.(in Chinese)
[10]丁文仁.缩阵分析法——求解指派问题的新方法[J].系统工程理论与实践,1988,8(3):38-86.DING Wenren.New method to solve assignment problem-reduced matrix analyzing method[J].Systems Engineering theory&Practice,1988,8(3):38-86.
[11]Zhu H B,Liu D N,Zhang S Q,et al.Solving the Many to Many assignment problem by improving the Kuhn-Munkres algorithm with backtracking[J].Theoretical Computer Science,2016,618:30-41.
[12]周莉,张维华,徐射雕.求解指派问题的一次性分配算法[J].计算机工程与应用,2011,47(18):135-138,152.ZHOU Li,ZHANG Weihua,XU Shediao.One-time assignment algorithm to solve assignment problem[J].Computer Engineering and Applications,2011,47(18):135-138,152.(in Chinese)
[13]赵洪刚,杨竹君,孟庆华,等.指派问题新解法:目标值子矩阵法[J],浙江大学学报(理学版),2010,37(5):501-504.ZHAO Honggang,YANG Zhujun,MENG Qinghua,et al.New method of solving assignment problem-target value submatrix method[J].Journal of Zhejiang University(Science Edition),2010,37(5):501-504.(in Chinese)
[14]李珍萍,王亮.最短时限缺省指派问题的一种解法[J].运筹与管理,2000,9(2):55-61.LI Zhenping,WANG Liang.The absent assignment problem to the shortest time limit and its algorithm[J].Operations Research and Management Science,2000,9(2):55-61.(in Chinese)
[15]Mazzola J B,Neebe A W.Resource-constrained assignment scheduling[J].Operations Research,1986,34(4):560-572.
[16]郭强.人数少于任务数的全指派问题的迭代算法[J].计算机工程与应用,2007,43(24):91-93,103.GUO Qiang.Iterative algorithm of total assignment problem on persons less than jobs[J].Computer Engineering and Applications,2007,43(24):91-93,103.(in Chinese)
[17]Choi K,Kim G,Suh Y,et al.Assignment of collaborators to multiple business problems using genetic algorithm[J].Information Systems and e-Business Management,2017,15(4):877-895.
[18]Myszkowski P B,Skowroński M E,OlechP,et al.Hybrid ant colony optimization in solving multi-skill resourceconstrained project scheduling problem[J].Soft Computing,2015,19(12):3599-3619.
[19]Myszkowski P B,Skowroński M E,OlechP,et al.Hybrid ant colony optimization in solving multi-skill resourceconstrained project scheduling problem[J].Soft Computing,2015,19(12):3599-3619.
[20]王维博,冯全源.基于改进粒子群算法的工程项目综合优化[J].西南交通大学学报,2011,46(1):76-83.WANG Weibo,FENG Quanyuan.Synthesis optimization for construction project based on modified particle swarm optimization algorithm[J].Journal of SouthWest JiaoTong University,2011,46(1):76-83.(in Chinese)
[21]Gon9alves J F,Mendes J J M,Resende M G C.A genetic algorithm for the resource constrained multi-project scheduling problem[J].European Journal of Operational Research,2008,189(3):1171-1190.
[22]Ma W M,Che Y Y,Huang H,et al.Resource-constrained project scheduling problem with uncertain durations and renewable resources[J].International Journal of Machine Learning and Cybernetics,2016,7(4):613-621.