Mathematics, Vol. 13, Pages 2672: A Random Forest-Enhanced Genetic Algorithm for Order Acceptance Scheduling with Past-Sequence-Dependent Setup Times

Mathematics doi: 10.3390/math13162672

Authors:
Yu-Yan Zhang
Shih-Hsin Chen
Yen-Wen Wang
Chia-Hsuan Liao
Chen-Hsiang Yu

This study developed a simple genetic algorithm (SGA) enhanced by a random forest (RF) surrogate model, namely SGARF, to solve the permutation flow-shop scheduling problem with order acceptance under the conditions of limited capacity, weighted-tardiness, and past-sequence-dependent (PSD) setup times (PFSS-OAWT with PSD). To the best of our knowledge, this is the first study to investigate this problem. Our proposed algorithm increases the setup time for each successive job by a constant proportion of the cumulative processing time of preceding jobs to capture the progressive slowdown that often occurs on real production lines. In the developed algorithm with maximum 105 fitness evaluations, the RF surrogate model predicts objective function values and guides crossover and mutation. On the PFSS-OAWT with PSD benchmark (up to 500 orders and 20 machines, 160 instances), SGARF represents improvements of 0.9% over SGA, 0.8% over SGALS, and 5.6% over SABPO. Although the surrogate incurs additional runtime, the gains in both profit and order-acceptance rates justify its use for high-margin, offline planning. Overall, the results of this study suggest that integrating evolutionary search into data-driven prediction is an effective strategy for solving complex capacity-constrained scheduling problems.

Source link

Yu-Yan Zhang www.mdpi.com