IDEAS home Printed from https://ideas.repec.org/a/eee/matcom/v234y2025icp169-193.html
   My bibliography  Save this article

Solving the permutation flow shop scheduling problem with sequence-dependent setup time via iterative greedy algorithm and imitation learning

Author

Listed:
  • Du, Zhao-sheng
  • Li, Jun-qing
  • Song, Hao-nan
  • Gao, Kai-zhou
  • Xu, Ying
  • Li, Jia-ke
  • Zheng, Zhi-xin

Abstract

In recent years, the application of learning-based methods in flow shop scheduling problem has gained considerable attention. However, there are gaps in the quality of their solution due to the difficulty of fully exploring the huge search space faced by learning-based methods and the difficulty of reward function design. In this paper, a hybrid approach of meta-heuristic algorithm and imitation learning (IL) is proposed to solve the permutation flow shop scheduling problem with sequence-dependent setup times (PFSP-SDST). Firstly, jobs are treated as nodes, and the processing time and setup times of PFSP-SDST are considered as features of the nodes, respectively. Secondly, a graph neural network based on an attention feature fusion (AFF) mechanism is designed as an encoder to embed the feature information of the problem. Finally, an iterative greedy algorithm based on critical path is proposed to provide high-quality expert solutions for the IL algorithm. The running results on randomly generated datasets and benchmark datasets demonstrate the effectiveness of the proposed method.

Suggested Citation

  • Du, Zhao-sheng & Li, Jun-qing & Song, Hao-nan & Gao, Kai-zhou & Xu, Ying & Li, Jia-ke & Zheng, Zhi-xin, 2025. "Solving the permutation flow shop scheduling problem with sequence-dependent setup time via iterative greedy algorithm and imitation learning," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 234(C), pages 169-193.
    • Handle: RePEc:eee:matcom:v:234:y:2025:i:c:p:169-193
    DOI: 10.1016/j.matcom.2025.02.026
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378475425000692
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.matcom.2025.02.026?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to

    for a different version of it.

    References listed on IDEAS

    as
    1. Harvey M. Wagner, 1959. "An integer linear‐programming model for machine scheduling," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 6(2), pages 131-140, June.
    2. Imène Benkalai & Djamal Rebaine & Caroline Gagné & Pierre Baptiste, 2017. "Improving the migrating birds optimization metaheuristic for the permutation flow shop with sequence-dependent set-up times," International Journal of Production Research, Taylor & Francis Journals, vol. 55(20), pages 6145-6157, October.
    3. 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.
    4. Liu, Weibo & Jin, Yan & Price, Mark, 2017. "A new improved NEH heuristic for permutation flowshop scheduling problems," International Journal of Production Economics, Elsevier, vol. 193(C), pages 21-30.
    5. Brammer, Janis & Lutz, Bernhard & Neumann, Dirk, 2022. "Permutation flow shop scheduling with multiple lines and demand plans using reinforcement learning," European Journal of Operational Research, Elsevier, vol. 299(1), pages 75-86.
    6. Bengio, Yoshua & Lodi, Andrea & Prouvost, Antoine, 2021. "Machine learning for combinatorial optimization: A methodological tour d’horizon," European Journal of Operational Research, Elsevier, vol. 290(2), pages 405-421.
    7. Sioud, A. & Gagné, C., 2018. "Enhanced migrating birds optimization algorithm for the permutation flow shop problem with sequence dependent setup times," European Journal of Operational Research, Elsevier, vol. 264(1), pages 66-73.
    8. Taillard, E., 1993. "Benchmarks for basic scheduling problems," European Journal of Operational Research, Elsevier, vol. 64(2), pages 278-285, January.
    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. V. Anjana & R. Sridharan & P. N. Ram Kumar, 2020. "Metaheuristics for solving a multi-objective flow shop scheduling problem with sequence-dependent setup times," Journal of Scheduling, Springer, vol. 23(1), pages 49-69, February.
    2. Brammer, Janis & Lutz, Bernhard & Neumann, Dirk, 2022. "Permutation flow shop scheduling with multiple lines and demand plans using reinforcement learning," European Journal of Operational Research, Elsevier, vol. 299(1), pages 75-86.
    3. Meenakshi Sharma & Manisha Sharma & Sameer Sharma, 2022. "Desert sparrow optimization algorithm for the bicriteria flow shop scheduling problem with sequence-independent setup time," Operational Research, Springer, vol. 22(4), pages 4353-4396, September.
    4. Ruiz, Ruben & Stutzle, Thomas, 2007. "A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem," European Journal of Operational Research, Elsevier, vol. 177(3), pages 2033-2049, March.
    5. Libralesso, Luc & Focke, Pablo Andres & Secardin, Aurélien & Jost, Vincent, 2022. "Iterative beam search algorithms for the permutation flowshop," European Journal of Operational Research, Elsevier, vol. 301(1), pages 217-234.
    6. Bahman Naderi & Rubén Ruiz & Vahid Roshanaei, 2023. "Mixed-Integer Programming vs. Constraint Programming for Shop Scheduling Problems: New Results and Outlook," INFORMS Journal on Computing, INFORMS, vol. 35(4), pages 817-843, July.
    7. Fernandez-Viagas, Victor & Talens, Carla & Framinan, Jose M., 2022. "Assembly flowshop scheduling problem: Speed-up procedure and computational evaluation," European Journal of Operational Research, Elsevier, vol. 299(3), pages 869-882.
    8. Mario Levorato & David Sotelo & Rosa Figueiredo & Yuri Frota, 2024. "Efficient solutions to the m-machine robust flow shop under budgeted uncertainty," Annals of Operations Research, Springer, vol. 338(1), pages 765-799, July.
    9. Yunhe Wang & Xiangtao Li & Zhiqiang Ma, 2017. "A Hybrid Local Search Algorithm for the Sequence Dependent Setup Times Flowshop Scheduling Problem with Makespan Criterion," Sustainability, MDPI, vol. 9(12), pages 1-35, December.
    10. Karimi-Mamaghan, Maryam & Mohammadi, Mehrdad & Meyer, Patrick & Karimi-Mamaghan, Amir Mohammad & Talbi, El-Ghazali, 2022. "Machine learning at the service of meta-heuristics for solving combinatorial optimization problems: A state-of-the-art," European Journal of Operational Research, Elsevier, vol. 296(2), pages 393-422.
    11. Ruiz, Ruben & Stutzle, Thomas, 2008. "An Iterated Greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives," European Journal of Operational Research, Elsevier, vol. 187(3), pages 1143-1159, June.
    12. Ciavotta, Michele & Minella, Gerardo & Ruiz, Rubén, 2013. "Multi-objective sequence dependent setup times permutation flowshop: A new algorithm and a comprehensive study," European Journal of Operational Research, Elsevier, vol. 227(2), pages 301-313.
    13. Benavides, Alexander J. & Vera, Antony, 2022. "The reversibility property in a job-insertion tiebreaker for the permutational flow shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 297(2), pages 407-421.
    14. Da Col, Giacomo & Teppan, Erich C., 2022. "Industrial-size job shop scheduling with constraint programming," Operations Research Perspectives, Elsevier, vol. 9(C).
    15. Pagnozzi, Federico & Stützle, Thomas, 2021. "Automatic design of hybrid stochastic local search algorithms for permutation flowshop problems with additional constraints," Operations Research Perspectives, Elsevier, vol. 8(C).
    16. Rossit, Daniel Alejandro & Tohmé, Fernando & Frutos, Mariano, 2018. "The Non-Permutation Flow-Shop scheduling problem: A literature review," Omega, Elsevier, vol. 77(C), pages 143-153.
    17. Karimi-Mamaghan, Maryam & Mohammadi, Mehrdad & Pasdeloup, Bastien & Meyer, Patrick, 2023. "Learning to select operators in meta-heuristics: An integration of Q-learning into the iterated greedy algorithm for the permutation flowshop scheduling problem," European Journal of Operational Research, Elsevier, vol. 304(3), pages 1296-1330.
    18. Gmys, Jan & Mezmaz, Mohand & Melab, Nouredine & Tuyttens, Daniel, 2020. "A computationally efficient Branch-and-Bound algorithm for the permutation flow-shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 284(3), pages 814-833.
    19. Shahaboddin Shamshirband & Mohammad Shojafar & A. Hosseinabadi & Maryam Kardgar & M. Nasir & Rodina Ahmad, 2015. "OSGA: genetic-based open-shop scheduling with consideration of machine maintenance in small and medium enterprises," Annals of Operations Research, Springer, vol. 229(1), pages 743-758, June.
    20. 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.

    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:eee:matcom:v:234:y:2025:i:c:p:169-193. 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: Catherine Liu (email available below). General contact details of provider: http://www.journals.elsevier.com/mathematics-and-computers-in-simulation/ .

    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.