Improved Genetic Programming Algorithm for RCMPSP

doi:10.3969/j.issn.1004-132X.2021.10.010

Abstract

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.

Key words: genetic programming, hyper-heuristic, multi-objective optimization, resource constrained multi-project scheduling problem(RCMPSP), non-dominated sorting genetic algorithm Ⅱ

摘要： 针对优先级规则调度不具备优化能力的缺陷，提出了一种应用于资源受限多项目调度的改进超启发式遗传规划算法以进化出更理想的优先级规则。通过分析现有优先级规则构建出适用多项目调度的归一化属性集和顶层判别编码方式，并结合NSGA-Ⅱ虚拟适应度分配方法对种群进行评估以实现多目标优化。设计了一种多样性种群更新方式，以避免传统遗传规划易陷入局部最优的缺陷和提高搜索能力。通过基于标准数据集PSPLIB所构造的算例和飞机总装装配线的生产实例验证了该方法的有效性和可行性。

关键词: 遗传规划, 超启发式, 多目标优化, 资源受限多项目调度, NSGA-Ⅱ

CLC Number:

TP182

CHEN Haojie, DING Guofu, ZHANG Jian, YAN Kaiyin. Improved Genetic Programming Algorithm for RCMPSP[J]. China Mechanical Engineering, 2021, 32(10): 1213-1221.

陈浩杰, 丁国富, 张剑, 阎开印. 求解资源受限多项目调度的改进遗传规划算法[J]. 中国机械工程, 2021, 32(10): 1213-1221.

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.

[1]	LI Meng-Lei, GU Yo-Qin, ZHANG Hua-Liang, LIU Li-Qin, DU Juan, WEN Chu-Hua, LAN Guo-Sheng. Parallel Mechanism Structure Optimization Design Based on Multi-objective Differential Evolution Algorithm [J]. J4, 201016, 21(16): 1915-1920.
[2]	HU Fuqing, SUN Jianghong, SUN Yingjie, SUN Yutong, MA Chao, ZHOU Fuqiang, . Design and Parameter Optimization of Slicing Machines Based on New Rotary-straight Line Reciprocating Mechanisms [J]. China Mechanical Engineering, 2024, 35(04): 614-623，635.
[3]	WEI Shupeng, TANG Hongtao, LI Xixing, YANG Guanyu, ZHANG Jian. Dual-resource Constrained Flexible Machining Workshop Inverse Scheduling Problem [J]. China Mechanical Engineering, 2024, 35(03): 457-471.
[4]	LIU Yi, YI Wangmin, YAO Jiantao, WANG Xingda, YU Peng, ZHAO Yongshen. Design and Research of Heavy-duty Posture-adjusting Assembly Robots in Narrow Space [J]. China Mechanical Engineering, 2024, 35(02): 324-336.
[5]	QU Ligang, SU Yan, XIN Yufei. Automatic Layout Method of Aircraft Tank Pipelines Based on SHO-NSGA Hybrid Algorithm [J]. China Mechanical Engineering, 2023, 34(15): 1864-1872.
[6]	ZHANG Weicun, GU Hongyu. Job-shop Scheduling Problems Considering Similar Learning Effect in One-worker and Multiple-machine Partterns [J]. China Mechanical Engineering, 2023, 34(14): 1701-1709.
[7]	PENG Xiang, JIANG Haohao, GUO Yuliang, LI Jiquan, YI Bing, JIANG Shaofei, . Collaborative Optimization of Stacking Sequence and Material Distribution for Wing Skins [J]. China Mechanical Engineering, 2023, 34(12): 1415-1424,1435.
[8]	CHEN Xiren, YE Wenhua, ZHANG Chaohong, CUI Kunkun, LENG Sheng, YE Liukang. NURBS Curve-based Multi-objective Aerodynamic Optimization Design for Ultra-high-speed Elevator Fairings [J]. China Mechanical Engineering, 2023, 34(12): 1436-1445,1464.
[9]	TIAN Ying, SHAO Wenting, WANG Taiyong. Energy Footprint Modeling and Parameter Optimization in Workshop Manufacturing Processes [J]. China Mechanical Engineering, 2022, 33(21): 2547-2553.
[10]	ZHANG Hongliang, XU Gongjie, BAO Qiang, PAN Ruilin. Distributed Flexible Job Shop Green Scheduling with Transportation Time [J]. China Mechanical Engineering, 2022, 33(21): 2554-2563,2645.
[11]	WANG Qiulian, DUAN Xinghao. Scheduling of Flexible Job Shop Based on High-dimension and Multi-objective Migrating Bird Optimization Algorithm [J]. China Mechanical Engineering, 2022, 33(21): 2601-2612.
[12]	BAO Hong, YANG Jing, KE Qingdi, LI Hongzhen, YAO Yongzheng, . An Energy Efficiency Optimization Model of Fused Filament Fabrication 3D Printing Based on Support Vector Regression [J]. China Mechanical Engineering, 2022, 33(18): 2215-2226.
[13]	RONG Yu, DOU Tianci, ZHANG Xingchao, ZHANG LeiZ, HAO Jingyu. A Real-time Control Method for Optimal Overall Performances of Planar Redundant Robots [J]. China Mechanical Engineering, 2022, 33(16): 1928-1939.
[14]	LI Hao, XU Zhiling, XU Yong, ZHAO Youwei. Grouping Selective Assembly Method for Mechanical Products Based on Local Search Strategy for NSGA-Ⅱ [J]. China Mechanical Engineering, 2022, 33(09): 1127-1133.
[15]	SHANG Zuen, ZHAO Lijuan, LIU Xionghao, JIN Xin. Deployable Waterbomb Wheel Structure Analysis and Optimization of Mine Rescue Robots [J]. China Mechanical Engineering, 2021, 32(24): 2924-2933.