Please wait a minute...
浙江大学学报(工学版)
浙江大学学报(工学版)
计算机技术﹑电信技术     
抢占式资源受限项目调度问题的遗传算法
寿涌毅, 彭晓峰, 李菲, 赖昌涛
浙江大学 管理学院, 浙江 杭州 310058
Genetic algorithms for the preemptive resource-constrained project scheduling problem
SHOU Yong-yi, PENG Xiao-feng, LI Fei, LAI Chang-tao
School of Management, Zhejiang University, Hangzhou 310058, China
 全文: PDF(829 KB)   HTML
摘要：

要: 针对抢占式资源受限项目调度问题中任意活动只被允许抢占最多1次的子问题,在经典的活动列表和优先权值编码方案基础上,引入抢占点概念,设计2种新的二维编码方案,并设计相应的解码方法.在4种编码方案基础上,采用不同的选择算子、交叉算子及变异概率,并对各种遗传算法的参数设置进行系统的实验测试,确定各方案的最佳参数设置.基于标准PSPLIB数据集设计大规模计算实验.结果表明,在资源受限项目调度问题中引入抢占能够显著缩短项目工期,采用优先权值编码方案的遗传算法在抢占式资源受限项目调度问题上有良好的求解效果,当问题规模扩大时采用活动列表编码方案的遗传算法也表现良好.
Abstract:

In order to solve a subproblem of the preemptive resource-constrained project scheduling problem in which each activity is allowed to be exempted once only, a new concept of preemption point was introduced to design two new encoding schemes based on the classic encoding schemes such as the activity list and priority values. Decoding schemes were designed for all encoding schemes respectively. Based on different encoding and decoding schemes, four genetic algorithms were proposed with different configurations of selection operators, crossover operators, and mutation probabilities. Systematic tests were carried out to determine the optimal parameter configurations. A large-scale computational experiment was designed using the standard PSPLIB problem sets. Computational results show that preemption helps shorten the duration of resource-constrained projects and the genetic algorithm based on priority values is most effective in handling preemptive resource-constrained project scheduling problems whereas the genetic algorithm based on activity lists is competitive for problems with more activities.
出版日期: 2014-08-01
:  F 224.3  
基金资助:

国家自然科学基金资助项目(71072119)；浙江省杰出青年科学基金资助项目(R7100297).
作者简介: 寿涌毅(1974—)，男，副教授，从事项目管理与运营管理研究.E-mail: yshou@zju.edu.cn
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　

引用本文:

寿涌毅, 彭晓峰, 李菲, 赖昌涛. 抢占式资源受限项目调度问题的遗传算法[J]. 浙江大学学报(工学版), 10.3785/j.issn.1008-973X.2014.08.017.

SHOU Yong-yi, PENG Xiao-feng, LI Fei, LAI Chang-tao. Genetic algorithms for the preemptive resource-constrained project scheduling problem. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 10.3785/j.issn.1008-973X.2014.08.017.

链接本文:

http://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2014.08.017    或    http://www.zjujournals.com/eng/CN/Y2014/V48/I8/1473

［1］ LINO P. Planificación de proyectos en diagramas de precedencias ［D］. Valencia: Universidad de Valencia, 1997.
［2］ BALLESTIN F, VALLS V, QUINTANILLA S. Pre-emption in resource-constrained project scheduling ［J］. European Journal of Operational Research, 2008, 189(3): 1136-1152.
［3］ KAPLAN L A. Resource-constrained Project Scheduling with Preemption of Jobs ［D］.Ann Arbor: University of Michigan, 1988.
［4］ DEMEULEMEESTER E L, HERROELEN W S. An efficient optimal solution procedure for the preemptive resource-constrained project scheduling problem ［J］. European Journal of Operational Research, 1996, 90(2): 334-348.
［5］ BALLESTIN F, VALLS V, QUINTANILLA S. Scheduling projects with limited number of preemptions ［J］. Computers & Operations Research, 2009, 36(11): 2913-2925.
［6］ BUDDHAKULSOMSIRI J, KIM D S. Properties of multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting ［J］. European Journal of Operational Research, 2006, 175(1): 279-295.
［7］ DAMAY J, QUILLIOT A, SANLAVILLE E. Linear programming based algorithms for preemptive and non-preemptive RCPSP ［J］. European Journal of Operational Research, 2007, 182(3): 1012-1022.
［8］ VAN PETEGHEM V, VANHOUCKE M. A genetic algorithm for the preemptive and non-preemptive multi-mode resource-constrained project scheduling problem ［J］. European Journal of Operational Research, 2010, 201(2): 409-418.
［9］ ZHANG H, HENG L, TAM C M. Particle swarm optimization for preemptive scheduling under break and resource-constraints ［J］. Journal of Construction Engineering and Management, 2006, 132(3): 259-267.
［10］ BRUCKER P, DREXL A, MOHRING R, et al. Resource-constrained project scheduling: Notation, classification, models, and methods ［J］. European Journal of Operational Research, 1999, 112: 341.
［11］ HARTMANN S. A competitive genetic algorithm for resource-constrained project scheduling ［J］. Naval Research Logistics, 1998, 45(7): 733-750.
［12］ KOLISCH R, HARTMANN S. Experimental investigation of heuristics for resource-constrained project scheduling: An update ［J］. European Journal of Operational Research, 2006, 174(1): 23-37.
［13］ VALLS V, BALLESTIN F, QUINTANILLA S. A hybrid genetic algorithm for the resource-constrained project scheduling problem ［J］. European Journal of Operational Research, 2008, 185(2): 495-508.
［14］ CHENG R, GEN M. Resource constrained project scheduling problem using genetic algorithms ［J］. International Journal of Intelligent Automation and Soft Computing, 1997, 3(3): 273-286.
［15］ MUTH J F, THOMPSON G L. Industrial scheduling ［M］. Englewood Cliffs, NJ: Prentice-Hall, 1963: 347-365.
［16］ KOLISCH R. Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation ［J］. European Journal of Operational Research, 1996, 90(2): 320-333.
［17］ TORMOS P, LOVA A. A competitive heuristic solution technique for resource-constrained project scheduling ［J］. Annals of Operations Research, 2001, 102(1): 65-81.
［18］ VALLS V, BALLESTIN F, QUINTANILLA S. Justification and RCPSP: A technique that pays ［J］. European Journal of Operational Research, 2005, 165(2): 375-386.
［19］ KOLISCH R, SPRECHER A, DREXL A. Characterization and generation of a general class of resource-constrained project scheduling problems ［J］. Management Science, 1995, 41(10): 1693-1703.
No related articles found!