IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v49y2001i2p293-304.html

The Asymptotic Optimality of the SPT Rule for the Flow Shop Mean Completion Time Problem

Author

Listed:
  • Philip Kaminsky

    (Industrial Engineering and Operations Research, University of California, Berkeley, California 94720)

  • David Simchi-Levi

    (Massachusetts Institute of Technology, Cambridge, Massachusetts 02139-4307)

Abstract

In the flow shop mean completion time problem, a set of jobs has to be processed on m -machines. Every machine has to process each one of the jobs, and every job has the same routing through the machines. The objective is to determine a sequence of the jobs on the machines so as to minimize the sum of the completion times of all jobs on the final machine. In this paper, we prove the asymptotic optimality of the Shortest Processing Time algorithm for any continuous, independent, and identically distributed job processing times.

Suggested Citation

  • Philip Kaminsky & David Simchi-Levi, 2001. "The Asymptotic Optimality of the SPT Rule for the Flow Shop Mean Completion Time Problem," Operations Research, INFORMS, vol. 49(2), pages 293-304, April.
    • Handle: RePEc:inm:oropre:v:49:y:2001:i:2:p:293-304
    DOI: 10.1287/opre.49.2.293.13536
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.49.2.293.13536
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.49.2.293.13536?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
    ---><---

    References listed on IDEAS

    as
    1. 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.
    2. Richard Loulou, 1984. "Tight Bounds and Probabilistic Analysis of Two Heuristics for Parallel Processor Scheduling," Mathematics of Operations Research, INFORMS, vol. 9(1), pages 142-150, February.
    3. Martin J. Krone & Kenneth Steiglitz, 1974. "Heuristic-Programming Solution of a Flowshop-Scheduling Problem," Operations Research, INFORMS, vol. 22(3), pages 629-638, June.
    4. Philip Kaminsky & David Simchi-Levi, 1998. "Probabilistic Analysis and Practical Algorithms for the Flow Shop Weighted Completion Time Problem," Operations Research, INFORMS, vol. 46(6), pages 872-882, December.
    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. Hui Liu & Maurice Queyranne & David Simchi‐Levi, 2005. "On the asymptotic optimality of algorithms for the flow shop problem with release dates," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(3), pages 232-242, April.
    2. Philip Kaminsky, 2003. "The effectiveness of the longest delivery time rule for the flow shop delivery time problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 50(3), pages 257-272, April.

    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. Philip Kaminsky & Onur Kaya, 2008. "Scheduling and due‐date quotation in a make‐to‐order supply chain," Naval Research Logistics (NRL), John Wiley & Sons, vol. 55(5), pages 444-458, August.
    2. Cathy H. Xia & George J. Shanthikumar & Peter W. Glynn, 2000. "On the Asymptotic Optimality of the SPT Rule for the Flow Shop Average Completion Time Problem," Operations Research, INFORMS, vol. 48(4), pages 615-622, August.
    3. Hui Liu & Maurice Queyranne & David Simchi‐Levi, 2005. "On the asymptotic optimality of algorithms for the flow shop problem with release dates," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(3), pages 232-242, April.
    4. De Giovanni, L. & Pezzella, F., 2010. "An Improved Genetic Algorithm for the Distributed and Flexible Job-shop Scheduling problem," European Journal of Operational Research, Elsevier, vol. 200(2), pages 395-408, January.
    5. 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.
    6. 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.
    7. Mehravaran, Yasaman & Logendran, Rasaratnam, 2012. "Non-permutation flowshop scheduling in a supply chain with sequence-dependent setup times," International Journal of Production Economics, Elsevier, vol. 135(2), pages 953-963.
    8. Kis, Tamas & Pesch, Erwin, 2005. "A review of exact solution methods for the non-preemptive multiprocessor flowshop problem," European Journal of Operational Research, Elsevier, vol. 164(3), pages 592-608, August.
    9. Lunardi, Willian T. & Birgin, Ernesto G. & Ronconi, Débora P. & Voos, Holger, 2021. "Metaheuristics for the online printing shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 293(2), pages 419-441.
    10. Nazim Sami & Karim Amrouche & Mourad Boudhar, 2024. "New efficient algorithms for the two-machine no-wait chain-reentrant shop problem," Journal of Combinatorial Optimization, Springer, vol. 47(5), pages 1-29, July.
    11. Zhengcai Cao & Lijie Zhou & Biao Hu & Chengran Lin, 2019. "An Adaptive Scheduling Algorithm for Dynamic Jobs for Dealing with the Flexible Job Shop Scheduling Problem," Business & Information Systems Engineering: The International Journal of WIRTSCHAFTSINFORMATIK, Springer;Gesellschaft für Informatik e.V. (GI), vol. 61(3), pages 299-309, June.
    12. Detienne, Boris & Sadykov, Ruslan & Tanaka, Shunji, 2016. "The two-machine flowshop total completion time problem: Branch-and-bound algorithms based on network-flow formulation," European Journal of Operational Research, Elsevier, vol. 252(3), pages 750-760.
    13. Quadt, Daniel & Kuhn, Heinrich, 2007. "A taxonomy of flexible flow line scheduling procedures," European Journal of Operational Research, Elsevier, vol. 178(3), pages 686-698, May.
    14. Peter Francis & Karen Smilowitz & Michal Tzur, 2006. "The Period Vehicle Routing Problem with Service Choice," Transportation Science, INFORMS, vol. 40(4), pages 439-454, November.
    15. 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.
    16. Rossi, Andrea, 2014. "Flexible job shop scheduling with sequence-dependent setup and transportation times by ant colony with reinforced pheromone relationships," International Journal of Production Economics, Elsevier, vol. 153(C), pages 253-267.
    17. Federico Della Croce & Andrea Grosso & Fabio Salassa, 2014. "A matheuristic approach for the two-machine total completion time flow shop problem," Annals of Operations Research, Springer, vol. 213(1), pages 67-78, February.
    18. Igor Averbakh & Oded Berman, 1999. "A Simple Heuristic for m-Machine Flow-Shop and its Applications in Routing-Scheduling Problems," Operations Research, INFORMS, vol. 47(1), pages 165-170, February.
    19. Goncharov, Yaroslav & Sevastyanov, Sergey, 2009. "The flow shop problem with no-idle constraints: A review and approximation," European Journal of Operational Research, Elsevier, vol. 196(2), pages 450-456, July.
    20. K. Z. Gao & P. N. Suganthan & Q. K. Pan & T. J. Chua & T. X. Cai & C. S. Chong, 2016. "Discrete harmony search algorithm for flexible job shop scheduling problem with multiple objectives," Journal of Intelligent Manufacturing, Springer, vol. 27(2), pages 363-374, April.

    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:inm:oropre:v:49:y:2001:i:2:p:293-304. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.