IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v13y2025i16p2672-d1728010.html

A Random Forest-Enhanced Genetic Algorithm for Order Acceptance Scheduling with Past-Sequence-Dependent Setup Times

Author

Listed:
  • Yu-Yan Zhang

    (Department of Information Management, Cheng Shiu University, Kaohsiung City 833, Taiwan
    Current address: ChungPeng Intelligence Services Co., New Taipei City 220017, Taiwan.)

  • Shih-Hsin Chen

    (Department of Computer Science and Information Engineering, Tamkang University, New Taipei City 251, Taiwan)

  • Yen-Wen Wang

    (Department of Industrial Engineering and Management, Minghsin University of Science and Technology, Hsinchu County 304, Taiwan)

  • Chia-Hsuan Liao

    (Graduate Institute of Educational Psychology and Counseling, Tamkang University, New Taipei City 251, Taiwan)

  • Chen-Hsiang Yu

    (Multidisciplinary Graduate Engineering, College of Engineering, Northeastern University, Boston, MA 02115, USA)

Abstract

This study developed a simple genetic algorithm (SGA) enhanced by a random forest (RF) surrogate model, namely S G A R F , 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 10 5 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), S G A R F represents improvements of 0.9% over SGA, 0.8% over S G A L S , 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.

Suggested Citation

  • Yu-Yan Zhang & Shih-Hsin Chen & Yen-Wen Wang & Chia-Hsuan Liao & Chen-Hsiang Yu, 2025. "A Random Forest-Enhanced Genetic Algorithm for Order Acceptance Scheduling with Past-Sequence-Dependent Setup Times," Mathematics, MDPI, vol. 13(16), pages 1-23, August.
    • Handle: RePEc:gam:jmathe:v:13:y:2025:i:16:p:2672-:d:1728010
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/13/16/2672/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/13/16/2672/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Seung Jae Lee & Byung Soo Kim, 2025. "An Optimization Problem of Distributed Permutation Flowshop Scheduling with an Order Acceptance Strategy in Heterogeneous Factories," Mathematics, MDPI, vol. 13(5), pages 1-19, March.
    2. Chen, Shih-Hsin & Chen, Min-Chih, 2013. "Addressing the advantages of using ensemble probabilistic models in Estimation of Distribution Algorithms for scheduling problems," International Journal of Production Economics, Elsevier, vol. 141(1), pages 24-33.
    3. Archer, Kellie J. & Kimes, Ryan V., 2008. "Empirical characterization of random forest variable importance measures," Computational Statistics & Data Analysis, Elsevier, vol. 52(4), pages 2249-2260, January.
    4. Shih-Hsin Chen & Yeong-Cheng Liou & Yi-Hui Chen & Kun-Ching Wang, 2019. "Order Acceptance and Scheduling Problem with Carbon Emission Reduction and Electricity Tariffs on a Single Machine," Sustainability, MDPI, vol. 11(19), pages 1-16, September.
    5. Esmaeilbeigi, Rasul & Charkhgard, Parisa & Charkhgard, Hadi, 2016. "Order acceptance and scheduling problems in two-machine flow shops: New mixed integer programming formulations," European Journal of Operational Research, Elsevier, vol. 251(2), pages 419-431.
    6. Tang, Lixin & Liu, Jiyin & Rong, Aiying & Yang, Zihou, 2000. "A multiple traveling salesman problem model for hot rolling scheduling in Shanghai Baoshan Iron & Steel Complex," European Journal of Operational Research, Elsevier, vol. 124(2), pages 267-282, July.
    7. Wang, Xiuli & Xie, Xingzi & Cheng, T.C.E., 2013. "Order acceptance and scheduling in a two-machine flowshop," International Journal of Production Economics, Elsevier, vol. 141(1), pages 366-376.
    8. Koulamas, Christos & Kyparisis, George J., 2008. "Single-machine scheduling problems with past-sequence-dependent setup times," European Journal of Operational Research, Elsevier, vol. 187(3), pages 1045-1049, June.
    9. Lei, Deming & Guo, Xiuping, 2015. "A parallel neighborhood search for order acceptance and scheduling in flow shop environment," International Journal of Production Economics, Elsevier, vol. 165(C), pages 12-18.
    10. Wang, Xiuli & Xie, Xingzi & Cheng, T.C.E., 2013. "A modified artificial bee colony algorithm for order acceptance in two-machine flow shops," International Journal of Production Economics, Elsevier, vol. 141(1), pages 14-23.
    11. V. Mani & Pei-Chann Chang & Shih-Hsin Chen, 2011. "Single-machine scheduling with past-sequence-dependent setup times and learning effects: a parametric analysis," International Journal of Systems Science, Taylor & Francis Journals, vol. 42(12), pages 2097-2102.
    12. Li, Chuan & Tao, Ying & Ao, Wengang & Yang, Shuai & Bai, Yun, 2018. "Improving forecasting accuracy of daily enterprise electricity consumption using a random forest based on ensemble empirical mode decomposition," Energy, Elsevier, vol. 165(PB), pages 1220-1227.
    13. Ruiz, Ruben & Maroto, Concepcion & Alcaraz, Javier, 2005. "Solving the flowshop scheduling problem with sequence dependent setup times using advanced metaheuristics," European Journal of Operational Research, Elsevier, vol. 165(1), pages 34-54, August.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Li, Xin & Ventura, Jose A., 2020. "Exact algorithms for a joint order acceptance and scheduling problem," International Journal of Production Economics, Elsevier, vol. 223(C).
    2. Chen, Wenchong & Feng, Pengwei & Luo, Xinggang & Nie, Libing, 2024. "Task-service matching problem for platform-driven manufacturing-as-a-service: A one-leader and multi-follower Stackelberg game with multiple objectives," Omega, Elsevier, vol. 129(C).
    3. Esmaeilbeigi, Rasul & Charkhgard, Parisa & Charkhgard, Hadi, 2016. "Order acceptance and scheduling problems in two-machine flow shops: New mixed integer programming formulations," European Journal of Operational Research, Elsevier, vol. 251(2), pages 419-431.
    4. Shih-Hsin Chen & Yeong-Cheng Liou & Yi-Hui Chen & Kun-Ching Wang, 2019. "Order Acceptance and Scheduling Problem with Carbon Emission Reduction and Electricity Tariffs on a Single Machine," Sustainability, MDPI, vol. 11(19), pages 1-16, September.
    5. Naderi, Bahman & Roshanaei, Vahid, 2020. "Branch-Relax-and-Check: A tractable decomposition method for order acceptance and identical parallel machine scheduling," European Journal of Operational Research, Elsevier, vol. 286(3), pages 811-827.
    6. Wang, Xiuli & Cheng, T.C.E., 2015. "A heuristic for scheduling jobs on two identical parallel machines with a machine availability constraint," International Journal of Production Economics, Elsevier, vol. 161(C), pages 74-82.
    7. Wang, Xiuli & Zhu, Qianqian & Cheng, T.C.E., 2015. "Subcontracting price schemes for order acceptance and scheduling," Omega, Elsevier, vol. 54(C), pages 1-10.
    8. Tarhan, İstenç & Oğuz, Ceyda, 2022. "A matheuristic for the generalized order acceptance and scheduling problem," European Journal of Operational Research, Elsevier, vol. 299(1), pages 87-103.
    9. Baruch Mor & Gur Mosheiov, 2018. "A note: minimizing total absolute deviation of job completion times on unrelated machines with general position-dependent processing times and job-rejection," Annals of Operations Research, Springer, vol. 271(2), pages 1079-1085, December.
    10. Wang, Sheng-yao & Wang, Ling & Liu, Min & Xu, Ye, 2013. "An effective estimation of distribution algorithm for solving the distributed permutation flow-shop scheduling problem," International Journal of Production Economics, Elsevier, vol. 145(1), pages 387-396.
    11. Mohamadreza Dabiri & Mehdi Yazdani & Bahman Naderi & Hassan Haleh, 2022. "Modeling and solution methods for hybrid flow shop scheduling problem with job rejection," Operational Research, Springer, vol. 22(3), pages 2721-2765, July.
    12. Lei, Deming & Guo, Xiuping, 2015. "A parallel neighborhood search for order acceptance and scheduling in flow shop environment," International Journal of Production Economics, Elsevier, vol. 165(C), pages 12-18.
    13. R. Micale & C. M. La Fata & M. Enea & G. La Scalia, 2021. "Regenerative scheduling problem in engineer to order manufacturing: an economic assessment," Journal of Intelligent Manufacturing, Springer, vol. 32(7), pages 1913-1925, October.
    14. Chen, Wenchong & Gong, Xuejian & Rahman, Humyun Fuad & Liu, Hongwei & Qi, Ershi, 2021. "Real-time order acceptance and scheduling for data-enabled permutation flow shops: Bilevel interactive optimization with nonlinear integer programming," Omega, Elsevier, vol. 105(C).
    15. Allahverdi, Ali, 2015. "The third comprehensive survey on scheduling problems with setup times/costs," European Journal of Operational Research, Elsevier, vol. 246(2), pages 345-378.
    16. Binh Thai Pham & Chongchong Qi & Lanh Si Ho & Trung Nguyen-Thoi & Nadhir Al-Ansari & Manh Duc Nguyen & Huu Duy Nguyen & Hai-Bang Ly & Hiep Van Le & Indra Prakash, 2020. "A Novel Hybrid Soft Computing Model Using Random Forest and Particle Swarm Optimization for Estimation of Undrained Shear Strength of Soil," Sustainability, MDPI, vol. 12(6), pages 1-16, March.
    17. Esmaeilbeigi, Rasul & Mak-Hau, Vicky & Yearwood, John & Nguyen, Vivian, 2022. "The multiphase course timetabling problem," European Journal of Operational Research, Elsevier, vol. 300(3), pages 1098-1119.
    18. Zhen Song & Håkan Schunnesson & Mikael Rinne & John Sturgul, 2015. "Intelligent Scheduling for Underground Mobile Mining Equipment," PLOS ONE, Public Library of Science, vol. 10(6), pages 1-21, June.
    19. Bai, Yun & Deng, Shuyun & Pu, Ziqiang & Li, Chuan, 2024. "Carbon price forecasting using leaky integrator echo state networks with the framework of decomposition-reconstruction-integration," Energy, Elsevier, vol. 305(C).
    20. Kong, Xiangyu & Li, Chuang & Wang, Chengshan & Zhang, Yusen & Zhang, Jian, 2020. "Short-term electrical load forecasting based on error correction using dynamic mode decomposition," Applied Energy, Elsevier, vol. 261(C).

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:13:y:2025:i:16:p:2672-:d:1728010. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager The email address of this maintainer does not seem to be valid anymore. Please ask MDPI Indexing Manager to update the entry or send us the correct address (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.