IDEAS home Printed from https://ideas.repec.org/a/eee/oprepe/v6y2019ics2214716018300526.html

Multi-Stage assembly flow shop with setup time and release time

Author

Listed:
  • Sheikh, Shaya
  • Komaki, G.M.
  • Kayvanfar, Vahid
  • Teymourian, Ehsan

Abstract

This article addresses multi-stage assembly flow shop for the first time. We propose several industrial applications of this system in which the opening stage has m parallel machines and the following stages (e.g. assembly, transportation, painting, packaging, etc.) complete and prepare products for delivery. We develop a mixed binary linear optimization model and a constraint-free mathematical presentation for this problem. We explore performance measures of makespan and total completion time and derive polynomial optimal solutions for special cases that are likely to occur in industry. We also propose lower bounds as well as nine efficient heuristics for solving the problem with the objective of minimizing makespan. The results reveal that the proposed lower bounds is tight enough. Moreover, the optimization models and derived polynomial algorithms can be applied to assembly flow shops without setup or release time. Finally, we implement General Variable Neighborhood Search (GVNS) and Grey Wolf Optimizer to improve the heuristic solutions. Comparison of employed algorithms on randomly generated instances indicates that GVNS outperforms other heuristics. The performance of proposed heuristics and meta-heuristics are confirmed with detailed statistical analysis.

Suggested Citation

  • 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).
    • Handle: RePEc:eee:oprepe:v:6:y:2019:i:c:s2214716018300526
    DOI: 10.1016/j.orp.2019.100111
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S2214716018300526
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.orp.2019.100111?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. Jin Deng & Ling Wang & Sheng-yao Wang & Xiao-long Zheng, 2016. "A competitive memetic algorithm for the distributed two-stage assembly flow-shop scheduling problem," International Journal of Production Research, Taylor & Francis Journals, vol. 54(12), pages 3561-3577, June.
    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. 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.
    4. C. N. Potts & S. V. Sevast'janov & V. A. Strusevich & L. N. Van Wassenhove & C. M. Zwaneveld, 1995. "The Two-Stage Assembly Scheduling Problem: Complexity and Approximation," Operations Research, INFORMS, vol. 43(2), pages 346-355, April.
    5. Yokoyama, Masao & Santos, Daryl L., 2005. "Three-stage flow-shop scheduling with assembly operations to minimize the weighted sum of product completion times," European Journal of Operational Research, Elsevier, vol. 161(3), pages 754-770, March.
    6. Allahverdi, Ali & Soroush, H.M., 2008. "The significance of reducing setup times/setup costs," European Journal of Operational Research, Elsevier, vol. 187(3), pages 978-984, June.
    7. 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.
    8. Niloofar Shoaardebili & Parviz Fattahi, 2015. "Multi-objective meta-heuristics to solve three-stage assembly flow shop scheduling problem with machine availability constraints," International Journal of Production Research, Taylor & Francis Journals, vol. 53(3), pages 944-968, February.
    9. 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.
    10. 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.
    11. Zahra Tajbakhsh & Parviz Fattahi & Javad Behnamian, 2014. "Multi-objective assembly permutation flow shop scheduling problem: a mathematical model and a meta-heuristic algorithm," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 65(10), pages 1580-1592, October.
    12. Chung-Yee Lee & T. C. E. Cheng & B. M. T. Lin, 1993. "Minimizing the Makespan in the 3-Machine Assembly-Type Flowshop Scheduling Problem," Management Science, INFORMS, vol. 39(5), pages 616-625, May.
    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. Huang, Xue & He, Hongyu & Bei, Hong-Bin & Zhao, Yanzhi & Wang, Ning & Chang, Yu, 2025. "Group-scheduling with simultaneous learning effects and convex resource allocations," Operations Research Perspectives, Elsevier, vol. 15(C).

    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. Framinan, Jose M. & Perez-Gonzalez, Paz & Fernandez-Viagas, Victor, 2019. "Deterministic assembly scheduling problems: A review and classification of concurrent-type scheduling models and solution procedures," European Journal of Operational Research, Elsevier, vol. 273(2), pages 401-417.
    2. Pourya Pourhejazy & Chen-Yang Cheng & Kuo-Ching Ying & Nguyen Hoai Nam, 2023. "Meta-Lamarckian-based iterated greedy for optimizing distributed two-stage assembly flowshops with mixed setups," Annals of Operations Research, Springer, vol. 322(1), pages 125-146, March.
    3. 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.
    4. 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.
    5. Allahverdi, Ali, 2016. "A survey of scheduling problems with no-wait in process," European Journal of Operational Research, Elsevier, vol. 255(3), pages 665-686.
    6. 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.
    7. Dominik Kress & David Müller & Jenny Nossack, 2019. "A worker constrained flexible job shop scheduling problem with sequence-dependent setup times," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 41(1), pages 179-217, March.
    8. 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.
    9. Chin-Chia Wu & Xingong Zhang & Danyu Bai & Ameni Azzouz & Wen-Hsiang Wu & Xin-Rong Chen & Win-Chin Lin, 2024. "Sequencing a tri-criteria multiple job classes and customer orders problem on a single machine by using heuristics and simulated annealing method," Operational Research, Springer, vol. 24(1), pages 1-22, March.
    10. Zhang, Zhe & Song, Xiaoling & Huang, Huijung & Zhou, Xiaoyang & Yin, Yong, 2022. "Logic-based Benders decomposition method for the seru scheduling problem with sequence-dependent setup time and DeJong’s learning effect," European Journal of Operational Research, Elsevier, vol. 297(3), pages 866-877.
    11. Elisama Araújo Silva Oliveira & Elizabeth Wanner & Elisangela Martins Sá & Sérgio Ricardo Souza, 2025. "A local branching-based solution for the multi-period cutting stock problem with tardiness, earliness, and setup costs," Journal of Heuristics, Springer, vol. 31(1), pages 1-57, March.
    12. 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.
    13. Hinder, Oliver & Mason, Andrew J., 2017. "A novel integer programing formulation for scheduling with family setup times on a single machine to minimize maximum lateness," European Journal of Operational Research, Elsevier, vol. 262(2), pages 411-423.
    14. Shen, Liji & Dauzère-Pérès, Stéphane & Neufeld, Janis S., 2018. "Solving the flexible job shop scheduling problem with sequence-dependent setup times," European Journal of Operational Research, Elsevier, vol. 265(2), pages 503-516.
    15. Ying, Kuo-Ching & Pourhejazy, Pourya & Lin, Zhi-Rong, 2025. "Scheduling with sequence-dependent setup times in short-term production planning: A main path analysis-based review," Operations Research Perspectives, Elsevier, vol. 14(C).
    16. Dirk Briskorn & Konrad Stephan & Nils Boysen, 2022. "Minimizing the makespan on a single machine subject to modular setups," Journal of Scheduling, Springer, vol. 25(1), pages 125-137, February.
    17. Jin Xu & Natarajan Gautam, 2020. "On competitive analysis for polling systems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 67(6), pages 404-419, September.
    18. 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.
    19. Rauchecker, Gerhard & Schryen, Guido, 2019. "An exact branch-and-price algorithm for scheduling rescue units during disaster response," European Journal of Operational Research, Elsevier, vol. 272(1), pages 352-363.
    20. Felix Winter & Nysret Musliu, 2022. "A large neighborhood search approach for the paint shop scheduling problem," Journal of Scheduling, Springer, vol. 25(4), pages 453-475, August.

    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:oprepe:v:6:y:2019:i:c:s2214716018300526. 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/operations-research-perspectives .

    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.