Multiobjective Dynamic Flexible Job Shop Scheduling with Biased Objectives via Multitask Genetic Programming
Breakthrough Research in Multiobjective Dynamic Flexible Job Shop Scheduling: An Innovative Approach to Optimize Biased Objectives via Multitask Learning in Genetic Programming
Background Introduction
Dynamic Flexible Job Shop Scheduling (DFJSS) is an essential combinatorial optimization problem with extensive real-world applications in areas such as manufacturing and warehousing. For example, it is used to optimize task allocation in production processes or order picking in warehouses. The core challenge lies in making flexible machine assignments and operation sequencing decisions in dynamic environments, aiming to maximize efficiency metrics or minimize time costs. However, the problem’s complexity is extremely high, especially when tasks dynamically arrive or machines experience breakdowns. Traditional optimization methods often face shortcomings, such as high computational complexity and poor real-time performance.
In recent years, Genetic Programming (GP), as a hyper-heuristic approach, has been widely used to generate scheduling heuristic rules for DFJSS. These rules, as priority functions, efficiently support real-time decisions. However, researchers have discovered that in learning these scheduling heuristic rules, the rule size (the number of nodes in the rule) and the rule effectiveness often present conflicting objectives: larger and more complex rules usually exhibit higher effectiveness, while smaller rules are easier to understand, computationally efficient, but may not produce desirable scheduling outcomes.
Traditional dominance-based multiobjective optimization algorithms, such as NSGA-II (Nondominated Sorting Genetic Algorithm II), tend to favor objectives that are easier to optimize—in this case, rule size. This bias results in the retention of small but ineffective rules, while effective large rules are often discarded during the evolutionary process. This challenge, known as “multiobjective optimization with biased objectives,” is a significant hurdle in the field.
To address these challenges, the authors of this paper introduced a novel multiobjective genetic programming algorithm that leverages a multitask learning mechanism. This approach employs knowledge-sharing techniques to simultaneously improve rule effectiveness and usability, thus achieving breakthrough advancements in dynamic scheduling.
Paper Source
This research was conducted by Fangfang Zhang (corresponding author), Gaofeng Shi, Yi Mei, and Mengjie Zhang. The authors are affiliated with the Centre for Data Science and Artificial Intelligence at Victoria University of Wellington and Emerson Company. The paper was published in IEEE Transactions on Artificial Intelligence (January 2025, Vol. 6) and represents a significant contribution to the fields of multiobjective optimization and genetic programming.
Research Design and Workflow
The research design can be summarized into the following key steps:
1. Problem Modeling and Background
The study started by formulating a multiobjective optimization problem for DFJSS that includes two conflicting objectives: rule size (number of nodes) and rule effectiveness. Using widely adopted benchmarking instances, the research designed an optimization environment with three primary effectiveness-related objectives: maximum flowtime (max-flowtime), mean flowtime (mean-flowtime), and mean weighted tardiness (mean-weighted tardiness). The mathematical definitions of these objective functions were clearly provided, alongside detailed simulations of dynamic task arrivals and machine resource constraints.
2. Algorithm Framework and Innovative Design
The authors proposed a novel algorithm called “VMT_αNSGP” (Variable Multi-task α-Nondominated Sorting Genetic Programming). The specific workflow of the algorithm is as follows:
Task Division and Subpopulation Design: The algorithm divides the population into two subpopulations to handle two tasks:
- Main Task: Optimize DFJSS’s effectiveness and rule size using α-dominance-based multiobjective optimization.
- Auxiliary Task: Utilize traditional dominance relations for optimization, with a bias towards smaller rules.
α-Dominance Relation: By dynamically adjusting α values, the algorithm balances biased objectives, giving more attention to effectiveness. This approach significantly improves search performance in scenarios where effectiveness and rule size are uneven.
Knowledge Sharing Mechanism: A range-based rule size selection strategy was designed for knowledge sharing. During evolution, individuals with similar rule sizes across subpopulations exchange genetic material via crossover operations, improving the effectiveness of smaller rules.
Diversity Control and Exploration-Exploitation Trade-Off: Entropy was employed to evaluate population diversity. The algorithm ensures high diversity in the early stages for exploration and maintains moderate diversity in the later stages for exploitation.
3. Experimental Design
The study simulated dynamic environments involving 5000 jobs and 10 machines under different utilization levels (e.g., 0.75, 0.85, 0.95). Nine combinations of objectives were used to evaluate algorithm performance. Training and testing were conducted separately, with independent random seeds generating new instances for validation. Metrics such as Hypervolume (HV) and Inverted Generational Distance (IGD) were used to evaluate multiobjective performance.
Major Research Results
Optimization Performance: Across nine scenarios, VMT_αNSGP significantly outperformed NSGP, αNSGP_A, and other comparison algorithms in terms of HV and IGD. The performance improvement was particularly notable in highly complex scenarios.
High-Quality Pareto Fronts: The Pareto fronts generated by VMT_αNSGP effectively covered the conflict space between rule effectiveness and rule size, showing clear advantages over competing algorithms.
Rule Simplicity and Interpretability: Compared to traditional large rules, the algorithm enhanced the effectiveness of small rules. Despite the slight increase in rule complexity, the learned rules remained interpretable and computationally efficient.
Diversity and Stability: VMT_αNSGP maintained higher population diversity in the early evolutionary stages and gradually converged, effectively balancing exploration and exploitation.
Research Conclusions and Implications
The paper proposed an innovative multiobjective genetic programming algorithm that leverages multitask learning mechanisms to address the optimization challenges in dynamic scheduling. This study is the first to demonstrate how task separation and knowledge-sharing mechanisms can directly improve the effectiveness of small rules without the need for complex archive maintenance. This is a significant theoretical contribution to multiobjective optimization and heuristic rule learning while offering an efficient and interpretable optimization method for practical scheduling problems.
Research Highlights
- Innovative Framework: The combination of task separation and multitask learning provides a groundbreaking approach to addressing biased objective optimization.
- Efficiency and Interpretability: The algorithm achieves an efficient balance between effectiveness and usability of rules.
- Wide Applicability: The approach can be extended to other dynamic optimization problems, such as arc routing and warehouse management.
Future Outlook
Future research could explore more complex objective structures, such as three-objective optimization scenarios, and further analyze the detailed relationships between the sizes of routing and sequencing rules. Additionally, the multitask learning mechanism has potential for applications in various other domains.