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]	LI Yi, TANG Qian, LIULianchao, PENG Xiaogang, YAN Xianhong. An Improved ACO Algorithm for Automobile Mixed-flow Assembly Scheduling Problems#br# [J]. China Mechanical Engineering, 2021, 32(09): 1126-1133.
[3]	WENG Jian, ZHUANG Kejia, PU Donglin, DING Han, . Plunge Milling of Titanium Alloys Based on Machine Learning and Multi-objective Optimization [J]. China Mechanical Engineering, 2021, 32(07): 771-777.
[4]	NI Hengxin, YAN Chunping, CHEN Jianlin, HOU Yuehui, CHEN Liang. Multi-objective Optimization and Decision-making Method of High Speed Dry Gear Hobbing Processing Parameters [J]. China Mechanical Engineering, 2021, 32(07): 832-838.
[5]	LIU Feng, , LI Jiquan, PENG Xiang, JIANG Shaofei. Optimization of RHCM Mould Electric Heating Systems for Constrainted Heating Pipe Layout [J]. China Mechanical Engineering, 2020, 31(22): 2699-2707.
[6]	JIAO Dongfeng;LIU Zhifeng. Precision Optimization of Driving Axle Parts for Low Cost and Low Noise [J]. China Mechanical Engineering, 2020, 31(20): 2505-2511.
[7]	TONG Zheming1；CHEN Yao1；TONG Shuiguang1；YU Yue1；LI Jinfu2；HAO Guoshuai3. Multi-objective Optimization Design of Low Specific Speed Centrifugal Pumps Based on NSGA-Ⅲ Algorithm [J]. China Mechanical Engineering, 2020, 31(18): 2239-2246.
[8]	LIU Shihao, LIN Mao. Research on Status and Prospects of Optimization Design Method of High-speed CNC Turntables [J]. China Mechanical Engineering, 2020, 31(13): 1629-1637.
[9]	LI Yibing1,2;HUANG Weixing1;WU Rui1. Research on Multi-objective Green Flexible Job-shop Scheduling Based on Improved ABC Algorithm [J]. China Mechanical Engineering, 2020, 31(11): 1344-1350,1385.
[10]	DING Xiaohong;ZHANG Jun;ZHANG Heng. Multi-objective Design Optimization of Pad-iron Positions for Three-point Supporting T-shaped Bed Machine Tools [J]. China Mechanical Engineering, 2019, 30(21): 2615-2621.
[11]	YING Fuqiang;MA Liangliang;WANG Neili. Design and Optimization of Forklift Steering Mechanisms with Horizontal Hydro-cylinder [J]. China Mechanical Engineering, 2019, 30(19): 2329-2334,2341.
[12]	CAI Ning;ZHANG Zeqiang;ZHANG Ying;ZHU Lixia. Modeling and Improved SFLA for Disassembly Line Balancing under Resource Constraints [J]. China Mechanical Engineering, 2019, 30(17): 2091-2099.
[13]	HUA Ertian1,2;ZHOU Meng1;LI Shenghui1;LU Hao1. Evolutionary Design of Mechanism Kinematics Chain of Genetic Programming [J]. China Mechanical Engineering, 2019, 30(16): 1916-1924.
[14]	XIE Miao;LI Xiaojing. Multi-objective Optimization Design of Support Cylinders for Excavation and Anchor Combined Units [J]. China Mechanical Engineering, 2019, 30(16): 1976-1981.
[15]	LUO Ju;GUO Fushui. Study on Multi-disciplinary Design Optimization on Civil Turbofan Engines [J]. China Mechanical Engineering, 2019, 30(15): 1813-1820.