IDEAS home Printed from https://ideas.repec.org/a/eee/jomega/v123y2024ics0305048323001615.html
   My bibliography  Save this article

Historical information based iterated greedy algorithm for distributed flowshop group scheduling problem with sequence-dependent setup times

Author

Listed:
  • He, Xuan
  • Pan, Quan-Ke
  • Gao, Liang
  • Neufeld, Janis S.
  • Gupta, Jatinder N.D.

Abstract

Distributed flowshop group scheduling problem (DFGSP) is commonly seen in modern industry. However, research works on DFGSP with total flow time criterion are rarely reported. The DFGSP consists of three coupled sub-problems, i.e., factory assignment for each group, group sequence in each factory, and job sequence within each group. A historical information-based iterated greedy algorithm (HIG) is proposed for solving the DFGSP with the objective of minimizing total flow time. The HIG integrates an iterated greedy algorithm (IG) with a group-based insertion operator, a job-based insertion operator, a domination criterion-based swap operator, and a historical information-based constructive solution method. The domination criterion is an effective inequality, which can deterministically optimize the objective value of a partial sequence even if the scheduling sequence of subsequent jobs is unknown. In the constructive solution method, a set covering model is designed to capture the effective factory allocation patterns for the groups hidden in the historical solutions to speed up the search for the IG. The comprehensive experiments on 810 test instances demonstrate the effectiveness of HIG.

Suggested Citation

  • He, Xuan & Pan, Quan-Ke & Gao, Liang & Neufeld, Janis S. & Gupta, Jatinder N.D., 2024. "Historical information based iterated greedy algorithm for distributed flowshop group scheduling problem with sequence-dependent setup times," Omega, Elsevier, vol. 123(C).
    • Handle: RePEc:eee:jomega:v:123:y:2024:i:c:s0305048323001615
    DOI: 10.1016/j.omega.2023.102997
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0305048323001615
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.omega.2023.102997?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 search for a different version of it.

    References listed on IDEAS

    as
    1. Taha Keshavarz & Nasser Salmasi, 2014. "Efficient upper and lower bounding methods for flowshop sequence-dependent group scheduling problems," European Journal of Industrial Engineering, Inderscience Enterprises Ltd, vol. 8(3), pages 366-387.
    2. Ribas, Imma & Companys, Ramon & Tort-Martorell, Xavier, 2011. "An iterated greedy algorithm for the flowshop scheduling problem with blocking," Omega, Elsevier, vol. 39(3), pages 293-301, June.
    3. Xiaoyun Xiong & Peng Zhou & Yunqiang Yin & T. C. E. Cheng & Dengfeng Li, 2019. "An exact branch‐and‐price algorithm for multitasking scheduling on unrelated parallel machines," Naval Research Logistics (NRL), John Wiley & Sons, vol. 66(6), pages 502-516, September.
    4. Shengluo Yang & Zhigang Xu, 2021. "The distributed assembly permutation flowshop scheduling problem with flexible assembly and batch delivery," International Journal of Production Research, Taylor & Francis Journals, vol. 59(13), pages 4053-4071, July.
    5. He, Xuan & Pan, Quan-Ke & Gao, Liang & Neufeld, Janis S., 2023. "An asymmetric traveling salesman problem based matheuristic algorithm for flowshop group scheduling problem," European Journal of Operational Research, Elsevier, vol. 310(2), pages 597-610.
    6. J.S. Neufeld & J.N.D. Gupta & U. Buscher, 2015. "Minimising makespan in flowshop group scheduling with sequence-dependent family set-up times using inserted idle times," International Journal of Production Research, Taylor & Francis Journals, vol. 53(6), pages 1791-1806, March.
    7. Wang, Yuhang & Han, Yuyan & Wang, Yuting & Tasgetiren, M. Fatih & Li, Junqing & Gao, Kaizhou, 2023. "Intelligent optimization under the makespan constraint: Rapid evaluation mechanisms based on the critical machine for the distributed flowshop group scheduling problem," European Journal of Operational Research, Elsevier, vol. 311(3), pages 816-832.
    8. Muter, İbrahim, 2020. "Exact algorithms to minimize makespan on single and parallel batch processing machines," European Journal of Operational Research, Elsevier, vol. 285(2), pages 470-483.
    9. Saeed Behjat & Nasser Salmasi, 2017. "Total completion time minimisation of no-wait flowshop group scheduling problem with sequence dependent setup times," European Journal of Industrial Engineering, Inderscience Enterprises Ltd, vol. 11(1), pages 22-48.
    10. Jae-Gon Kim & Seokwoo Song & BongJoo Jeong, 2020. "Minimising total tardiness for the identical parallel machine scheduling problem with splitting jobs and sequence-dependent setup times," International Journal of Production Research, Taylor & Francis Journals, vol. 58(6), pages 1628-1643, March.
    11. B. Naderi & Nasser Salmasi, 2012. "Permutation flowshops in group scheduling with sequence-dependent setup times," European Journal of Industrial Engineering, Inderscience Enterprises Ltd, vol. 6(2), pages 177-198.
    12. Lin, Shih-Wei & Ying, Kuo-Ching, 2013. "Minimizing makespan in a blocking flowshop using a revised artificial immune system algorithm," Omega, Elsevier, vol. 41(2), pages 383-389.
    13. Yanıkoğlu, İhsan & Yavuz, Tonguc, 2022. "Branch-and-price approach for robust parallel machine scheduling with sequence-dependent setup times," European Journal of Operational Research, Elsevier, vol. 301(3), pages 875-895.
    14. Chung, Chia-Shin & Flynn, James & Kirca, Omer, 2002. "A branch and bound algorithm to minimize the total flow time for m-machine permutation flowshop problems," International Journal of Production Economics, Elsevier, vol. 79(3), pages 185-196, October.
    15. Naderi, Bahman & Ruiz, Rubén, 2014. "A scatter search algorithm for the distributed permutation flowshop scheduling problem," European Journal of Operational Research, Elsevier, vol. 239(2), pages 323-334.
    16. Fernandez-Viagas, Victor & Molina-Pariente, Jose M. & Framinan, Jose M., 2020. "Generalised accelerations for insertion-based heuristics in permutation flowshop scheduling," European Journal of Operational Research, Elsevier, vol. 282(3), pages 858-872.
    17. 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.
    18. Ozturk, Onur, 2020. "A truncated column generation algorithm for the parallel batch scheduling problem to minimize total flow time," European Journal of Operational Research, Elsevier, vol. 286(2), pages 432-443.
    19. Taha Keshavarz & Nasser Salmasi & Mohsen Varmazyar, 2019. "Flowshop sequence-dependent group scheduling with minimisation of weighted earliness and tardiness," European Journal of Industrial Engineering, Inderscience Enterprises Ltd, vol. 13(1), pages 54-80.
    20. Jacob Lohmer & Rainer Lasch, 2021. "Production planning and scheduling in multi-factory production networks: a systematic literature review," International Journal of Production Research, Taylor & Francis Journals, vol. 59(7), pages 2028-2054, April.
    21. Victor Fernandez-Viagas & Jose M. Framinan, 2015. "A bounded-search iterated greedy algorithm for the distributed permutation flowshop scheduling problem," International Journal of Production Research, Taylor & Francis Journals, vol. 53(4), pages 1111-1123, February.
    22. Ruiz, Rubén & Pan, Quan-Ke & Naderi, Bahman, 2019. "Iterated Greedy methods for the distributed permutation flowshop scheduling problem," Omega, Elsevier, vol. 83(C), pages 213-222.
    23. Missaoui, Ahmed & Ruiz, Rubén, 2022. "A parameter-Less iterated greedy method for the hybrid flowshop scheduling problem with setup times and due date windows," European Journal of Operational Research, Elsevier, vol. 303(1), pages 99-113.
    24. Wang, Haibo & Alidaee, Bahram, 2019. "Effective heuristic for large-scale unrelated parallel machines scheduling problems," Omega, Elsevier, vol. 83(C), pages 261-274.
    25. Wu, Xueqi & Che, Ada, 2019. "A memetic differential evolution algorithm for energy-efficient parallel machine scheduling," Omega, Elsevier, vol. 82(C), pages 155-165.
    26. Ankit Khare & Sunil Agrawal, 2021. "Effective heuristics and metaheuristics to minimise total tardiness for the distributed permutation flowshop scheduling problem," International Journal of Production Research, Taylor & Francis Journals, vol. 59(23), pages 7266-7282, December.
    27. Lin, Shih-Wei & Ying, Kuo-Ching, 2016. "Optimization of makespan for no-wait flowshop scheduling problems using efficient matheuristics," Omega, Elsevier, vol. 64(C), pages 115-125.
    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. He, Xuan & Pan, Quan-Ke & Gao, Liang & Neufeld, Janis S., 2023. "An asymmetric traveling salesman problem based matheuristic algorithm for flowshop group scheduling problem," European Journal of Operational Research, Elsevier, vol. 310(2), pages 597-610.
    2. Perez-Gonzalez, Paz & Framinan, Jose M., 2024. "A review and classification on distributed permutation flowshop scheduling problems," European Journal of Operational Research, Elsevier, vol. 312(1), pages 1-21.
    3. Xiaohui Zhang & Xinhua Liu & Shufeng Tang & Grzegorz Królczyk & Zhixiong Li, 2019. "Solving Scheduling Problem in a Distributed Manufacturing System Using a Discrete Fruit Fly Optimization Algorithm," Energies, MDPI, vol. 12(17), pages 1-24, August.
    4. Chenyao Zhang & Yuyan Han & Yuting Wang & Junqing Li & Kaizhou Gao, 2023. "A Distributed Blocking Flowshop Scheduling with Setup Times Using Multi-Factory Collaboration Iterated Greedy Algorithm," Mathematics, MDPI, vol. 11(3), pages 1-25, January.
    5. Arshad Ali & Yuvraj Gajpal & Tarek Y. Elmekkawy, 2021. "Distributed permutation flowshop scheduling problem with total completion time objective," OPSEARCH, Springer;Operational Research Society of India, vol. 58(2), pages 425-447, June.
    6. Wang, Yuhang & Han, Yuyan & Wang, Yuting & Tasgetiren, M. Fatih & Li, Junqing & Gao, Kaizhou, 2023. "Intelligent optimization under the makespan constraint: Rapid evaluation mechanisms based on the critical machine for the distributed flowshop group scheduling problem," European Journal of Operational Research, Elsevier, vol. 311(3), pages 816-832.
    7. Bai, Danyu & Tang, Mengqian & Zhang, Zhi-Hai & Santibanez-Gonzalez, Ernesto DR, 2018. "Flow shop learning effect scheduling problem with release dates," Omega, Elsevier, vol. 78(C), pages 21-38.
    8. Yong Wang & Yuting Wang & Yuyan Han, 2023. "A Variant Iterated Greedy Algorithm Integrating Multiple Decoding Rules for Hybrid Blocking Flow Shop Scheduling Problem," Mathematics, MDPI, vol. 11(11), pages 1-25, May.
    9. Nouha Nouri & Talel Ladhari, 2018. "Evolutionary multiobjective optimization for the multi-machine flow shop scheduling problem under blocking," Annals of Operations Research, Springer, vol. 267(1), pages 413-430, August.
    10. Xu, Jun & Wang, Jun-Qiang & Liu, Zhixin, 2022. "Parallel batch scheduling: Impact of increasing machine capacity," Omega, Elsevier, vol. 108(C).
    11. Mohammad Reza Hosseinzadeh & Mehdi Heydari & Mohammad Mahdavi Mazdeh, 2022. "Mathematical modeling and two metaheuristic algorithms for integrated process planning and group scheduling with sequence-dependent setup time," Operational Research, Springer, vol. 22(5), pages 5055-5105, November.
    12. Alessandro Druetto & Erica Pastore & Elena Rener, 2023. "Parallel batching with multi-size jobs and incompatible job families," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 31(2), pages 440-458, July.
    13. Joaquín Bautista-Valhondo & Rocío Alfaro-Pozo, 2020. "Mixed integer linear programming models for Flow Shop Scheduling with a demand plan of job types," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 28(1), pages 5-23, March.
    14. Zhang, Zhe & Gong, Xue & Song, Xiaoling & Yin, Yong & Lev, Benjamin & Chen, Jie, 2022. "A column generation-based exact solution method for seru scheduling problems," Omega, Elsevier, vol. 108(C).
    15. Wu, Xueqi & Che, Ada, 2020. "Energy-efficient no-wait permutation flow shop scheduling by adaptive multi-objective variable neighborhood search," Omega, Elsevier, vol. 94(C).
    16. Husseinzadeh Kashan, Ali & Ozturk, Onur, 2022. "Improved MILP formulation equipped with valid inequalities for scheduling a batch processing machine with non-identical job sizes," Omega, Elsevier, vol. 112(C).
    17. Ansis Ozolins, 2019. "Improved bounded dynamic programming algorithm for solving the blocking flow shop problem," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 27(1), pages 15-38, March.
    18. Tian, Zheng & Zheng, Li, 2024. "Single machine parallel-batch scheduling under time-of-use electricity prices: New formulations and optimisation approaches," European Journal of Operational Research, Elsevier, vol. 312(2), pages 512-524.
    19. Hamza Jouhari & Deming Lei & Mohammed A. A. Al-qaness & Mohamed Abd Elaziz & Ahmed A. Ewees & Osama Farouk, 2019. "Sine-Cosine Algorithm to Enhance Simulated Annealing for Unrelated Parallel Machine Scheduling with Setup Times," Mathematics, MDPI, vol. 7(11), pages 1-18, November.
    20. Yin, Yunqiang & Luo, Zunhao & Wang, Dujuan & Cheng, T.C.E., 2023. "Wasserstein distance‐based distributionally robust parallel‐machine scheduling," Omega, Elsevier, vol. 120(C).

    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:jomega:v:123:y:2024:i:c:s0305048323001615. 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.elsevier.com/wps/find/journaldescription.cws_home/375/description#description .

    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.