IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v216y2012i3p544-552.html
   My bibliography  Save this article

Approximation algorithms for the parallel flow shop problem

Author

Listed:
  • Zhang, Xiandong
  • van de Velde, Steef

Abstract

We consider the NP-hard problem of scheduling n jobs in m two-stage parallel flow shops so as to minimize the makespan. This problem decomposes into two subproblems: assigning the jobs to parallel flow shops; and scheduling the jobs assigned to the same flow shop by use of Johnson’s rule. For m=2, we present a 32-approximation algorithm, and for m=3, we present a 127-approximation algorithm. Both these algorithms run in O(nlogn) time. These are the first approximation algorithms with fixed worst-case performance guarantees for the parallel flow shop problem.

Suggested Citation

  • Zhang, Xiandong & van de Velde, Steef, 2012. "Approximation algorithms for the parallel flow shop problem," European Journal of Operational Research, Elsevier, vol. 216(3), pages 544-552.
    • Handle: RePEc:eee:ejores:v:216:y:2012:i:3:p:544-552
    DOI: 10.1016/j.ejor.2011.08.007
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221711007193
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2011.08.007?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. Hoogeveen, J. A. & Lenstra, J. K. & Veltman, B., 1996. "Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard," European Journal of Operational Research, Elsevier, vol. 89(1), pages 172-175, February.
    2. Ruiz, Rubén & Vázquez-Rodríguez, José Antonio, 2010. "The hybrid flow shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 205(1), pages 1-18, August.
    3. J.N.D. Gupta & A.M.A. Hariri & C.N. Potts, 1997. "Scheduling a two-stage hybrid flow shop with parallel machines at the first stage," Annals of Operations Research, Springer, vol. 69(0), pages 171-191, January.
    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. Jianming Dong & Joshua Chang & Bing Su & Jueliang Hu & Guohui Lin, 2020. "Two-stage open-shop scheduling with a two-machine flow shop as a stage: approximation algorithms and empirical experiments," Journal of Scheduling, Springer, vol. 23(5), pages 595-608, October.
    2. Jianming Dong & Ruyan Jin & Jueliang Hu & Guohui Lin, 2019. "A fully polynomial time approximation scheme for scheduling on parallel identical two-stage openshops," Journal of Combinatorial Optimization, Springer, vol. 37(2), pages 668-684, February.
    3. Mao, Kun & Pan, Quan-ke & Pang, Xinfu & Chai, Tianyou, 2014. "A novel Lagrangian relaxation approach for a hybrid flowshop scheduling problem in the steelmaking-continuous casting process," European Journal of Operational Research, Elsevier, vol. 236(1), pages 51-60.
    4. 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.

    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. A. G. Leeftink & R. J. Boucherie & E. W. Hans & M. A. M. Verdaasdonk & I. M. H. Vliegen & P. J. Diest, 2018. "Batch scheduling in the histopathology laboratory," Flexible Services and Manufacturing Journal, Springer, vol. 30(1), pages 171-197, June.
    2. Luo, Hao & Du, Bing & Huang, George Q. & Chen, Huaping & Li, Xiaolin, 2013. "Hybrid flow shop scheduling considering machine electricity consumption cost," International Journal of Production Economics, Elsevier, vol. 146(2), pages 423-439.
    3. Figielska, Ewa, 2014. "A heuristic for scheduling in a two-stage hybrid flowshop with renewable resources shared among the stages," European Journal of Operational Research, Elsevier, vol. 236(2), pages 433-444.
    4. Jianming Dong & Ruyan Jin & Jueliang Hu & Guohui Lin, 2019. "A fully polynomial time approximation scheme for scheduling on parallel identical two-stage openshops," Journal of Combinatorial Optimization, Springer, vol. 37(2), pages 668-684, February.
    5. Ruiz, Rubén & Vázquez-Rodríguez, José Antonio, 2010. "The hybrid flow shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 205(1), pages 1-18, August.
    6. Byung-Cheon Choi & Kangbok Lee, 2013. "Two-stage proportionate flexible flow shop to minimize the makespan," Journal of Combinatorial Optimization, Springer, vol. 25(1), pages 123-134, January.
    7. Jianming Dong & Joshua Chang & Bing Su & Jueliang Hu & Guohui Lin, 2020. "Two-stage open-shop scheduling with a two-machine flow shop as a stage: approximation algorithms and empirical experiments," Journal of Scheduling, Springer, vol. 23(5), pages 595-608, October.
    8. 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.
    9. Weiya Zhong & Yun Shi, 2018. "Two-stage no-wait hybrid flowshop scheduling with inter-stage flexibility," Journal of Combinatorial Optimization, Springer, vol. 35(1), pages 108-125, January.
    10. Pan, Quan-Ke & Gao, Liang & Li, Xin-Yu & Gao, Kai-Zhou, 2017. "Effective metaheuristics for scheduling a hybrid flowshop with sequence-dependent setup times," Applied Mathematics and Computation, Elsevier, vol. 303(C), pages 89-112.
    11. 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.
    12. Alexis Robbes & Yannick Kergosien & Virginie André & Jean-Charles Billaut, 2022. "Efficient heuristics to minimize the total tardiness of chemotherapy drug production and delivery," Flexible Services and Manufacturing Journal, Springer, vol. 34(3), pages 785-820, September.
    13. 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.
    14. 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.
    15. Nicolás Álvarez-Gil & Rafael Rosillo & David de la Fuente & Raúl Pino, 2021. "A discrete firefly algorithm for solving the flexible job-shop scheduling problem in a make-to-order manufacturing system," 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. 29(4), pages 1353-1374, December.
    16. Billaut, Jean-Charles & Della Croce, Federico & Grosso, Andrea, 2015. "A single machine scheduling problem with two-dimensional vector packing constraints," European Journal of Operational Research, Elsevier, vol. 243(1), pages 75-81.
    17. Weiwei Wang & Biao Zhang & Baoxian Jia, 2023. "A Multiobjective Optimization Approach for Multiobjective Hybrid Flowshop Green Scheduling with Consistent Sublots," Sustainability, MDPI, vol. 15(3), pages 1-29, February.
    18. Alfaro-Fernández, Pedro & Ruiz, Rubén & Pagnozzi, Federico & Stützle, Thomas, 2020. "Automatic Algorithm Design for Hybrid Flowshop Scheduling Problems," European Journal of Operational Research, Elsevier, vol. 282(3), pages 835-845.
    19. S. M. Mousavi & I. Mahdavi & J. Rezaeian & M. Zandieh, 2018. "An efficient bi-objective algorithm to solve re-entrant hybrid flow shop scheduling with learning effect and setup times," Operational Research, Springer, vol. 18(1), pages 123-158, April.
    20. An, Xiangxin & Si, Guojin & Xia, Tangbin & Wang, Dong & Pan, Ershun & Xi, Lifeng, 2023. "An energy-efficient collaborative strategy of maintenance planning and production scheduling for serial-parallel systems under time-of-use tariffs," Applied Energy, Elsevier, vol. 336(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:ejores:v:216:y:2012:i:3:p:544-552. 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/eor .

    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.