IDEAS home Printed from https://ideas.repec.org/a/eee/proeco/v170y2015ipap258-267.html
   My bibliography  Save this article

A hybrid algorithm for the multi-stage flow shop group scheduling with sequence-dependent setup and transportation times

Author

Listed:
  • Liou, Cheng-Dar
  • Hsieh, Yi-Chih

Abstract

This study investigates the multi-stage flow shop group scheduling problem with job transportation times between machines and sequence-dependent setup times between groups. The objective is to minimize the makespan (Fm|fmls, Splk, tijk, prmu|Cmax). It is known that this problem is NP-hard and generalizes the typical multi-stage group scheduling problems. In this paper, a coding scheme is proposed to simultaneously determine both the sequence of jobs in each group and the sequence of groups. By reasonably combining particle swarm optimization (PSO) and genetic algorithms (GA), a fast and easily implemented hybrid algorithm (HA) is developed for solving the considered problem. The effectiveness and efficiency of the proposed HA are demonstrated and compared with those of standard PSO and GA by numerical results of various test instances with group numbers up to 20. In addition, three different lower bounds are developed to evaluate the solution quality of HA. Numerical results indicate that the proposed HA is a viable and effective approach for the studied multi-stage flow shop group scheduling problem.

Suggested Citation

  • Liou, Cheng-Dar & Hsieh, Yi-Chih, 2015. "A hybrid algorithm for the multi-stage flow shop group scheduling with sequence-dependent setup and transportation times," International Journal of Production Economics, Elsevier, vol. 170(PA), pages 258-267.
    • Handle: RePEc:eee:proeco:v:170:y:2015:i:pa:p:258-267
    DOI: 10.1016/j.ijpe.2015.10.002
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0925527315003825
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ijpe.2015.10.002?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. Logendran, Rasaratnam & Carson, Sara & Hanson, Erik, 2005. "Group scheduling in flexible flow shops," International Journal of Production Economics, Elsevier, vol. 96(2), pages 143-155, May.
    2. Fan, Shu-Kai S. & Zahara, Erwie, 2007. "A hybrid simplex search and particle swarm optimization for unconstrained optimization," European Journal of Operational Research, Elsevier, vol. 181(2), pages 527-548, September.
    3. Hamed Hendizadeh, S. & Faramarzi, Hamidreza & Mansouri, S.Afshin & Gupta, Jatinder N.D. & Y ElMekkawy, Tarek, 2008. "Meta-heuristics for scheduling a flowline manufacturing cell with sequence dependent family setup times," International Journal of Production Economics, Elsevier, vol. 111(2), pages 593-605, February.
    4. 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.
    5. Das, Sidhartha R. & Canel, Cem, 2005. "An algorithm for scheduling batches of parts in a multi-cell flexible manufacturing system," International Journal of Production Economics, Elsevier, vol. 97(3), pages 247-262, September.
    6. Allahverdi, Ali & Gupta, Jatinder N. D. & Aldowaisan, Tariq, 1999. "A review of scheduling research involving setup considerations," Omega, Elsevier, vol. 27(2), pages 219-239, April.
    7. M. R. Garey & D. S. Johnson & Ravi Sethi, 1976. "The Complexity of Flowshop and Jobshop Scheduling," Mathematics of Operations Research, INFORMS, vol. 1(2), pages 117-129, May.
    8. Schaller, Jeffrey, 2007. "Scheduling on a single machine with family setups to minimize total tardiness," International Journal of Production Economics, Elsevier, vol. 105(2), pages 329-344, February.
    9. Hatami, Sara & Ruiz, Rubén & Andrés-Romano, Carlos, 2015. "Heuristics and metaheuristics for the distributed assembly permutation flowshop scheduling problem with sequence dependent setup times," International Journal of Production Economics, Elsevier, vol. 169(C), pages 76-88.
    10. Chelouah, Rachid & Siarry, Patrick, 2003. "Genetic and Nelder-Mead algorithms hybridized for a more accurate global optimization of continuous multiminima functions," European Journal of Operational Research, Elsevier, vol. 148(2), pages 335-348, July.
    11. Wang, Xiuli & Cheng, T.C.E., 2009. "Heuristics for parallel-machine scheduling with job class setups and delivery to multiple customers," International Journal of Production Economics, Elsevier, vol. 119(1), pages 199-206, May.
    12. Cheng-Dar Liou & Yi-Chih Hsieh & Yin-Yann Chen, 2013. "A new encoding scheme-based hybrid algorithm for minimising two-machine flow-shop group scheduling problem," International Journal of Systems Science, Taylor & Francis Journals, vol. 44(1), pages 77-93.
    13. Logendran, Rasaratnam & deSzoeke, Paula & Barnard, Faith, 2006. "Sequence-dependent group scheduling problems in flexible flow shops," International Journal of Production Economics, Elsevier, vol. 102(1), pages 66-86, July.
    14. Allahverdi, Ali & Ng, C.T. & Cheng, T.C.E. & Kovalyov, Mikhail Y., 2008. "A survey of scheduling problems with setup times or costs," European Journal of Operational Research, Elsevier, vol. 187(3), pages 985-1032, June.
    15. Löhndorf, Nils & Riel, Manuel & Minner, Stefan, 2014. "Simulation optimization for the stochastic economic lot scheduling problem with sequence-dependent setup times," International Journal of Production Economics, Elsevier, vol. 157(C), pages 170-176.
    16. Solimanpur, M. & Vrat, Prem & Shankar, Ravi, 2004. "A heuristic to minimize makespan of cell scheduling problem," International Journal of Production Economics, Elsevier, vol. 88(3), pages 231-241, April.
    17. Schaller, Jeffrey E. & Gupta, Jatinder N. D. & Vakharia, Asoo J., 2000. "Scheduling a flowline manufacturing cell with sequence dependent family setup times," European Journal of Operational Research, Elsevier, vol. 125(2), pages 324-339, September.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Shuaipeng Yuan & Tieke Li & Bailin Wang, 2021. "A discrete differential evolution algorithm for flow shop group scheduling problem with sequence-dependent setup and transportation times," Journal of Intelligent Manufacturing, Springer, vol. 32(2), pages 427-439, February.
    2. Wang, Kai & Qin, Hu & Huang, Yun & Luo, Mengwen & Zhou, Lei, 2021. "Surgery scheduling in outpatient procedure centre with re-entrant patient flow and fuzzy service times," Omega, Elsevier, vol. 102(C).
    3. Li, Xinyu & Gao, Liang, 2016. "An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem," International Journal of Production Economics, Elsevier, vol. 174(C), pages 93-110.
    4. Hosseini, Amir & Otto, Alena & Pesch, Erwin, 2024. "Scheduling in manufacturing with transportation: Classification and solution techniques," European Journal of Operational Research, Elsevier, vol. 315(3), pages 821-843.

    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. Hamed Hendizadeh, S. & Faramarzi, Hamidreza & Mansouri, S.Afshin & Gupta, Jatinder N.D. & Y ElMekkawy, Tarek, 2008. "Meta-heuristics for scheduling a flowline manufacturing cell with sequence dependent family setup times," International Journal of Production Economics, Elsevier, vol. 111(2), pages 593-605, February.
    2. 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.
    3. Sheikh, Shaya & Komaki, G.M. & Kayvanfar, Vahid & Teymourian, Ehsan, 2019. "Multi-Stage assembly flow shop with setup time and release time," Operations Research Perspectives, Elsevier, vol. 6(C).
    4. Lin, Shih-Wei & Ying, Kuo-Ching & Lu, Chung-Cheng & Gupta, Jatinder N.D., 2011. "Applying multi-start simulated annealing to schedule a flowline manufacturing cell with sequence dependent family setup times," International Journal of Production Economics, Elsevier, vol. 130(2), pages 246-254, April.
    5. Allahverdi, Ali & Ng, C.T. & Cheng, T.C.E. & Kovalyov, Mikhail Y., 2008. "A survey of scheduling problems with setup times or costs," European Journal of Operational Research, Elsevier, vol. 187(3), pages 985-1032, June.
    6. Bozorgirad, Mir Abbas & Logendran, Rasaratnam, 2013. "Bi-criteria group scheduling in hybrid flowshops," International Journal of Production Economics, Elsevier, vol. 145(2), pages 599-612.
    7. Shen, Liji & Buscher, Udo, 2012. "Solving the serial batching problem in job shop manufacturing systems," European Journal of Operational Research, Elsevier, vol. 221(1), pages 14-26.
    8. Og[breve]uz, Ceyda & Sibel Salman, F. & Bilgintürk YalçIn, Zehra, 2010. "Order acceptance and scheduling decisions in make-to-order systems," International Journal of Production Economics, Elsevier, vol. 125(1), pages 200-211, May.
    9. 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.
    10. Fátima Pilar & Eliana Costa e Silva & Ana Borges, 2023. "Optimizing Vehicle Repairs Scheduling Using Mixed Integer Linear Programming: A Case Study in the Portuguese Automobile Sector," Mathematics, MDPI, vol. 11(11), pages 1-23, June.
    11. Nekoiemehr, Nooshin & Selvarajah, Esaignani & Zhang, Guoqing, 2015. "Scheduling of jobs with cross families in two stage manufacturing systems," International Journal of Production Economics, Elsevier, vol. 167(C), pages 88-96.
    12. Zhuang Huang & Jianjun Yang, 2020. "Scheduling Optimization in Flowline Manufacturing Cell Considering Intercell Movement with Harmony Search Approach," Mathematics, MDPI, vol. 8(12), pages 1-21, December.
    13. Solimanpur, Maghsud & Elmi, Atabak, 2013. "A tabu search approach for cell scheduling problem with makespan criterion," International Journal of Production Economics, Elsevier, vol. 141(2), pages 639-645.
    14. Dolgui, Alexandre & Kovalev, Sergey & Kovalyov, Mikhail Y. & Nossack, Jenny & Pesch, Erwin, 2014. "Minimizing setup costs in a transfer line design problem with sequential operation processing," International Journal of Production Economics, Elsevier, vol. 151(C), pages 186-194.
    15. 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.
    16. Bagchi, Tapan P. & Gupta, Jatinder N.D. & Sriskandarajah, Chelliah, 2006. "A review of TSP based approaches for flowshop scheduling," European Journal of Operational Research, Elsevier, vol. 169(3), pages 816-854, March.
    17. Pan, Quan-Ke & Ruiz, Rubén, 2012. "An estimation of distribution algorithm for lot-streaming flow shop problems with setup times," Omega, Elsevier, vol. 40(2), pages 166-180, April.
    18. Antonio Costa & Fulvio Antonio Cappadonna & Sergio Fichera, 2017. "A hybrid genetic algorithm for minimizing makespan in a flow-shop sequence-dependent group scheduling problem," Journal of Intelligent Manufacturing, Springer, vol. 28(6), pages 1269-1283, August.
    19. Feng, Hanxin & Xi, Lifeng & Xiao, Lei & Xia, Tangbin & Pan, Ershun, 2018. "Imperfect preventive maintenance optimization for flexible flowshop manufacturing cells considering sequence-dependent group scheduling," Reliability Engineering and System Safety, Elsevier, vol. 176(C), pages 218-229.
    20. Maryam Mousavi & Hwa Jen Yap & Siti Nurmaya Musa & Farzad Tahriri & Siti Zawiah Md Dawal, 2017. "Multi-objective AGV scheduling in an FMS using a hybrid of genetic algorithm and particle swarm optimization," PLOS ONE, Public Library of Science, vol. 12(3), pages 1-24, March.

    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:proeco:v:170:y:2015:i:pa:p:258-267. 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/locate/ijpe .

    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.