Importance-Aware Genetic Programming for Automated Scheduling Heuristics Learning in Dynamic Flexible Job Shop Scheduling

被引:4
|
作者
Zhang, Fangfang [1 ]
Mei, Yi [1 ]
Nguyen, Su [2 ]
Zhang, Mengjie [1 ]
机构
[1] Victoria Univ Wellington, Sch Engn & Comp Sci, POB 600, Wellington 6140, New Zealand
[2] La Trobe Univ, Ctr Data Analyt & Cognit, Bundoora, Vic, Australia
来源
PARALLEL PROBLEM SOLVING FROM NATURE - PPSN XVII, PPSN 2022, PT II | 2022年 / 13399卷
关键词
Importance-aware scheduling heuristics learning; Genetic programming; Hyper-heuristic; Dynamic flexible job shop scheduling;
D O I
10.1007/978-3-031-14721-0_4
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
Dynamic flexible job shop scheduling (DFJSS) is a critical and challenging problem in production scheduling such as order picking in the warehouse. Given a set of machines and a number of jobs with a sequence of operations, DFJSS aims to generate schedules for completing jobs to minimise total costs while reacting effectively to dynamic changes. Genetic programming, as a hyper-heuristic approach, has been widely used to learn scheduling heuristics for DFJSS automatically. A scheduling heuristic in DFJSS includes a routing rule for machine assignment and a sequencing rule for operation sequencing. However, existing studies assume that the routing and sequencing are equally important, which may not be true in real-world applications. This paper aims to propose an importance-aware GP algorithm for automated scheduling heuristics learning in DFJSS. Specifically, we first design a rule importance measure based on the fitness improvement achieved by the routing rule and the sequencing rule across generations. Then, we develop an adaptive resource allocation strategy to give more resources for learning the more important rules. The results show that the proposed importance-aware GP algorithm can learn significantly better scheduling heuristics than the compared algorithms. The effectiveness of the proposed algorithm is realised by the proposed strategies for detecting rule importance and allocating resources. Particularly, the routing rules play a more important role than the sequencing rules in the examined DFJSS scenarios.
引用
收藏
页码:48 / 62
页数:15
相关论文
共 50 条
  • [41] Dynamic flexible job shop scheduling based on deep reinforcement learning
    Yang, Dan
    Shu, Xiantao
    Yu, Zhen
    Lu, Guangtao
    Ji, Songlin
    Wang, Jiabing
    He, Kongde
    PROCEEDINGS OF THE INSTITUTION OF MECHANICAL ENGINEERS PART B-JOURNAL OF ENGINEERING MANUFACTURE, 2024,
  • [42] Dynamic heuristics for the generalized job-shop scheduling problem
    Ghedjati, Fatima
    Portmann, Marie-Claude
    2009 IEEE INTERNATIONAL CONFERENCE ON SYSTEMS, MAN AND CYBERNETICS (SMC 2009), VOLS 1-9, 2009, : 2562 - +
  • [43] Energy-Aware Flexible Job Shop Scheduling Using Mixed Integer Programming and Constraint Programming
    Ham, Andy
    Park, Myoung-Ju
    Kim, Kyung Min
    MATHEMATICAL PROBLEMS IN ENGINEERING, 2021, 2021
  • [44] Integrating genetic programming into job shop scheduling problem
    Chin, JF
    Meeran, S
    ADVANCES IN MANUFACTURING TECHNOLOGY - XVII, 2003, : 415 - 421
  • [45] Introduction to automated design of scheduling heuristics with genetic programming
    Durasevic, Marko
    Jakobovic, Domagoj
    Mei, Yi
    Su Nguyen
    Zhang, Mengjie
    PROCEEDINGS OF THE 2022 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE COMPANION, GECCO 2022, 2022, : 1506 - 1526
  • [46] Enhancing Genetic Programming based Hyper-Heuristics for Dynamic Multi-objective Job Shop Scheduling Problems
    Su Nguyen
    Zhang, Mengjie
    Tan, Kay Chen
    2015 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC), 2015, : 2781 - 2788
  • [47] Sampling Heuristics for Multi-objective Dynamic Job Shop Scheduling Using Island Based Parallel Genetic Programming
    Karunakaran, Deepak
    Mei, Yi
    Chen, Gang
    Zhang, Mengjie
    PARALLEL PROBLEM SOLVING FROM NATURE - PPSN XV, PT II, 2018, 11102 : 347 - 359
  • [48] A Further Investigation to Improve Linear Genetic Programming in Dynamic Job Shop Scheduling
    Huang, Zhixing
    Mei, Yi
    Zhang, Fangfang
    Zhang, Mengjie
    2022 IEEE SYMPOSIUM SERIES ON COMPUTATIONAL INTELLIGENCE (SSCI), 2022, : 496 - 503
  • [49] Automatic Design of Dispatching Rules with Genetic Programming for Dynamic Job Shop Scheduling
    Shady, Salama
    Kaihara, Toshiya
    Fujii, Nobutada
    Kokuryo, Daisuke
    ADVANCES IN PRODUCTION MANAGEMENT SYSTEMS: THE PATH TO DIGITAL TRANSFORMATION AND INNOVATION OF PRODUCTION MANAGEMENT SYSTEMS, PT I, 2020, 591 : 399 - 407
  • [50] Investigating a Machine Breakdown Genetic Programming Approach for Dynamic Job Shop Scheduling
    Park, John
    Mei, Yi
    Nguyen, Su
    Chen, Gang
    Zhang, Mengjie
    GENETIC PROGRAMMING (EUROGP 2018), 2018, 10781 : 253 - 270