IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v129y2004i1p171-18510.1023-banor.0000030687.72169.c7.html
   My bibliography  Save this article

Scheduling Three-Operation Jobs in a Two-Machine Flow Shop to Minimize Makespan

Author

Listed:
  • Jatinder Gupta
  • Christos Koulamas
  • George Kyparisis
  • Chris Potts
  • Vitaly Strusevich

Abstract

This paper considers a variant of the classical problem of minimizing makespan in a two-machine flow shop. In this variant, each job has three operations, where the first operation must be performed on the first machine, the second operation can be performed on either machine but cannot be preempted, and the third operation must be performed on the second machine. The NP-hard nature of the problem motivates the design and analysis of approximation algorithms. It is shown that a schedule in which the operations are sequenced arbitrarily, but without inserted machine idle time, has a worst-case performance ratio of 2. Also, an algorithm that constructs four schedules and selects the best is shown to have a worst-case performance ratio of 3/2. A polynomial time approximation scheme (PTAS) is also presented. Copyright Kluwer Academic Publishers 2004

Suggested Citation

  • Jatinder Gupta & Christos Koulamas & George Kyparisis & Chris Potts & Vitaly Strusevich, 2004. "Scheduling Three-Operation Jobs in a Two-Machine Flow Shop to Minimize Makespan," Annals of Operations Research, Springer, vol. 129(1), pages 171-185, July.
    • Handle: RePEc:spr:annopr:v:129:y:2004:i:1:p:171-185:10.1023/b:anor.0000030687.72169.c7
    DOI: 10.1023/B:ANOR.0000030687.72169.c7
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1023/B:ANOR.0000030687.72169.c7
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1023/B:ANOR.0000030687.72169.c7?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.

    Citations

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


    Cited by:

    1. 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.
    2. Lin-Hui Sun & Kai Cui & Ju-Hong Chen & Jun Wang & Xian-Chen He, 2013. "Some results of the worst-case analysis for flow shop scheduling with a learning effect," Annals of Operations Research, Springer, vol. 211(1), pages 481-490, December.
    3. Bertrand M. T. Lin & F. J. Hwang & Jatinder N. D. Gupta, 2017. "Two-machine flowshop scheduling with three-operation jobs subject to a fixed job sequence," Journal of Scheduling, Springer, vol. 20(3), pages 293-302, June.
    4. Gultekin, Hakan, 2012. "Scheduling in flowshops with flexible operations: Throughput optimization and benefits of flexibility," International Journal of Production Economics, Elsevier, vol. 140(2), pages 900-911.
    5. Matthias Bultmann & Sigrid Knust & Stefan Waldherr, 2018. "Flow shop scheduling with flexible processing times," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 40(3), pages 809-829, July.
    6. S. Knust & N. V. Shakhlevich & S. Waldherr & C. Weiß, 2019. "Shop scheduling problems with pliable jobs," Journal of Scheduling, Springer, vol. 22(6), pages 635-661, December.

    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:spr:annopr:v:129:y:2004:i:1:p:171-185:10.1023/b:anor.0000030687.72169.c7. 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.

    We have no bibliographic references for this item. You can help adding them by using 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.