Improved Genetic Programming Algorithm for RCMPSP

Expand
  • Institute of Advanced Design and Manufacturing, School of Mechanical Engineering, Southwest Jiaotong University, Chengdu,610031

Received date: 2020-04-08

  Online published: 2021-05-26

Abstract

Aiming at the lack of optimization ability for priority rule scheduling, an improved hyper-heuristic genetic programming algorithm for the RCMPSP was proposed to evolve better priority rules. By analyzing the existing priority rules, a normalized attribute set and a top-level discriminant coding method for multi-project scheduling were constructed, and the NSGA-Ⅱ virtual fitness allocation method was applied to evaluate the population for achieving multi-objective optimization. A diversity population updating method was designed to enhance the search ability and avoid the defects that the traditional genetic programming was easy to fall into local optimum. The validity and feasibility of the proposed method were verified by the calculation experiments based on benchmark data set PSPLIB and the aircraft assembly line production instance.

Cite this article

CHEN Haojie, DING Guofu, ZHANG Jian, YAN Kaiyin . Improved Genetic Programming Algorithm for RCMPSP[J]. China Mechanical Engineering, 2021 , 32(10) : 1213 -1221 . DOI: 10.3969/j.issn.1004-132X.2021.10.010

References

[1]方晨, 王凌. 资源约束项目调度研究综述[J]. 控制与决策, 2010, 25(5): 641-650.
FANG Chen, WANG Ling. Survey of Study on Resource Constrained Project Scheduling[J]. Control and Decision, 2010, 25(5):641-650.
[2]HARTMANN S, BRISKORN D. A Survey of Variants and Extensions of the Resource-constrained Project Scheduling Problem[J]. European Journal of Operational Research, 2010, 207(1): 1-14.
[3]BLAZEWICZ J, LENSTRA J K,KAN A H G. Scheduling Subject to Resource Constraints: Classification and Complexity[J]. Discrete Applied Mathematics, 1983, 5(1): 11-24.
[4]ZHENG H, WANG L, ZHENG X. Teaching–learning-based Optimization Algorithm for Multi-skill Resource Constrained Project Scheduling Problem[J]. Soft Computing, 2017, 21(6): 1537-1548.
[5]CHENG J, FOWLER J, KEMP K, et al. Multi-mode Resource-constrained Project Scheduling Problems with Non-preemptive Activity Splitting[J]. Computers & Operations Research, 2015, 53: 275-287.
[6]张沙清,陈新度,陈庆新,等.基于改进多目标微粒群算法的模具多项目反应调度[J].中国机械工程,2011,22(10):1173-1179.
ZHANG Shaqing, CHEN Xindu, CHEN Qingxin, et al. Reactive Scheduling for Multiple Mould and Die Projects Based on Improved Multi-objective Particle Swarm Optimization[J].China Mechanical Engineering, 2010,22(10): 1173-1179.
[7]WAUTERS T, KINABLE J,SMET P, et al. The Multi-mode Resource-constrained Multi-project Scheduling Problem[J]. Journal of Scheduling, 2016, 19(3): 271-283.
[8]HOMBERGER J, FINK A. Generic Negotiation Mechanisms with Side Payments:Design, Analysis and Application for Decentralized Resource-constrained Multi-project Scheduling Problems[J]. European Journal of Operational Research, 2017, 261(3): 1001-1012.
[9]PAYNE J H. Management of Multiple Simultaneous Projects: a State-of-the-art Review[J]. International Journal of Project Management, 1995, 13(3): 163-168.
[10]XIN S H U, SU Q, WANG Q, et al. Optimization of Resource-constrained Multi-project Scheduling Problem Based on the Genetic Algorithm[C]//15th International Conference on Service Systems and Service Management (ICSSSM). Hangzhou, 2018: 1-6.
[11]ZHENG Z, GUO Z, ZHU Y, et al. A Critical Chains Based Distributed Multi-project Scheduling Approach[J]. Neurocomputing, 2014, 143: 282-293.
[12]TIAN M, LIU R J, ZHANG G J. Solving the Resource-constrained Multi-project Scheduling Problem with an Improved Critical Chain Method[J]. Journal of the Operational Research Society, 2020,71(8):1243-1258 .
[13]PREZ E, POSADA M, LORENZANA A. Taking Advantage of Solving the Resource Constrained Multi-project Scheduling Problems Using Multi-modal Genetic Algorithms[J]. Soft Computing, 2016, 20(5): 1879-1896.
[14]BROWNING T R, YASSIN A A. Resource-constrained Multi-project Scheduling: Priority Rule Performance Revisited[J]. International Journal of Production Economics, 2010, 126(2): 212-228.
[15]WANG Y, HE Z, KERKHOVE L P, et al. On the Performance of Priority Rules for the Stochastic Resource Constrained Multi-project Scheduling Problem[J]. Computers & Industrial Engineering, 2017, 114: 223-234.
[16]CHEN H J, DING G, ZHANG J, et al. Research on Priority Rules for the Stochastic Resource Constrained Multi-project Scheduling Problem with New Project Arrival[J]. Computers & Industrial Engineering, 2019, 137: 106060.
[17]CHEN Z, DEMEULEMEESTER E,BAI S, et al. Efficient Priority Rules for the Stochastic Resource-constrained Project Scheduling Problem[J]. European Journal of Operational Research, 2018, 270(3): 957-967.
[18]VILLAFA'N~EZ F, POZA D, LOPEZ-PAREDES A, et al. A Generic Heuristic for Multi-project Scheduling Problems with Global and Local Resource Constraints (RCMPSP)[J]. Soft Computing, 2019, 23(10): 3465-3479.
[19]BURKE E K, HYDE M, KENDALL G, et al. A Classification of Hyper-heuristic Approaches[M]//GENDREAU M, POTVIN J Y.Handbook of Metaheuristics. Boston:Springer, 2010: 449-468.
[20]聂黎. 基于基因表达式编程的车间动态调度方法研究[D].武汉:华中科技大学,2011.
NIE Li. Research on Methods Based on Gene Expression Programming for Dynamic Scheduling[D]. Wuhan:Huazhong University of Science and Technology, 2011.
[21]NIE L, GAO L, LI P G,et al. Reactive Scheduling in a Job Shop Where Jobs Arrive Over Time[J]. Computers & Industrial Engineering, 2013, 66(2):389-405.
[22]NIE L, GAO L, LI P G, et al. A GEP-based Reactive Scheduling Policies Constructing Approach for Dynamic Flexible Job Shop Scheduling Problem with Job Release Dates[J]. Journal of Intelligent Manufacturing, 2013, 24(4):763-774.
[23]JIA Y, LI J H. Scheduling Rules Based on Gene Expression Programming for Resource-constrained Project Scheduling Problem[J].Journal of Donghua University(English Edition),2015,32(1):91-96.
[24]CHAND S, HUYUH Q, SINGH H, et al. On theUse of Genetic Programming to Evolve Priority Rules for Resource Constrained Project Scheduling Problems[J]. Information Sciences, 2018, 432: 146-163.
[25]CHAND S, SINGH H, RAY T. Evolving Heuristics for the Resource Constrained Project Scheduling Problem with Dynamic Resource Disruptions[J]. Swarm and Evolutionary Computation, 2019, 44: 897-912.
[26]LIN J, ZHU L, GAO K. A Genetic Programming Hyper-heuristic Approach for the Multi-skill Resource Constrained Project Scheduling Problem[J]. Expert Systems with Applications, 2020, 140: 112915.
[27]TUKYILMAZ A, 瘙塁ENVAR , NAL I·, et al. A Research Survey: Heuristic Approaches for Solving Multi Objective Flexible Job Shop Problems[J]. Journal of Intelligent Manufacturing, 2020:1-35.
[28]KOLISCH R. Efficient Priority Rules for the Resource-constrained Project Scheduling Problem[J]. Journal of Operations Management, 1996, 14(3): 179-192.
[29]HILDEBRANDT T, HEGER J, SCHOLZ-REITER B. Towards Improved Dispatching Rules for Complex Shop Floor Scenarios: a Genetic Programming Approach[C]//Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation. Portland, 2010: 257-264.
[30]DEB K, PRATAP A, AGARWAL S, et al. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.
[31]LUKE S, PANAIT L. A Comparison of Bloat Control Methods for Genetic Programming[J]. Evolutionary Computation, 2006, 14(3): 309-344.
[32]KOLISCH R, SPRECHER A. PSPLIB—a Project Scheduling Problem Library: OR Software—ORSEP Operations Research Software Exchange Program[J]. European Journal of Operational Research, 1996, 96(1): 205-216.
Outlines

/

〈 〉