IDEAS home Printed from https://ideas.repec.org/a/pal/jorsoc/v55y2004i12d10.1057_palgrave.jors.2601802.html
   My bibliography  Save this article

Generalization of Johnson's and Talwar's scheduling rules in two-machine stochastic flow shops

Author

Listed:
  • P J Kalczynski

    (The University of Toledo)

  • J Kamburowski

    (The University of Toledo)

Abstract

The paper deals with the classical problem of minimizing the makespan in a two-machine flow shop. When the job processing times are deterministic, the optimal job sequence can be determined by applying Johnson's rule. When they are independent and exponential random variables, Talwar's rule yields a job sequence that minimizes the makespan stochastically. Assuming that the random job processing times are independent and Gompertz distributed, we propose a new scheduling rule that is a generalization of both Johnson's and Talwar's rules. We prove that our rule yields a job sequence that minimizes the makespan stochastically. Extensions to m-machine proportionate stochastic flow shops, two-machine stochastic job shops, and stochastic assembly systems are indicated.

Suggested Citation

  • P J Kalczynski & J Kamburowski, 2004. "Generalization of Johnson's and Talwar's scheduling rules in two-machine stochastic flow shops," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(12), pages 1358-1362, December.
    • Handle: RePEc:pal:jorsoc:v:55:y:2004:i:12:d:10.1057_palgrave.jors.2601802
    DOI: 10.1057/palgrave.jors.2601802
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1057/palgrave.jors.2601802
    File Function: Abstract
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1057/palgrave.jors.2601802?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. Kamburowski, Jerzy, 1999. "Stochastically minimizing the makespan in two-machine flow shops without blocking," European Journal of Operational Research, Elsevier, vol. 112(2), pages 304-309, January.
    2. Kenneth N. McKay & Frank R. Safayeni & John A. Buzacott, 1988. "Job-Shop Scheduling Theory: What Is Relevant?," Interfaces, INFORMS, vol. 18(4), pages 84-90, August.
    3. Peng-Sheng Ku & Shun-Chen Niu, 1986. "On Johnson's Two-Machine Flow Shop with Random Processing Times," Operations Research, INFORMS, vol. 34(1), pages 130-136, February.
    4. 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.
    5. R. A. Dudek & S. S. Panwalkar & M. L. Smith, 1992. "The Lessons of Flowshop Scheduling Research," Operations Research, INFORMS, vol. 40(1), pages 7-13, February.
    6. Kamburowski, Jerzy, 2000. "On three-machine flow shops with random job processing times," European Journal of Operational Research, Elsevier, vol. 125(2), pages 440-448, September.
    7. Michael Pinedo, 1982. "Minimizing the Expected Makespan in Stochastic Flow Shops," Operations Research, INFORMS, vol. 30(1), pages 148-162, February.
    Full references (including those not matched with items on IDEAS)

    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. J Jackman & Z Guerra de Castillo & S Olafsson, 2011. "Stochastic flow shop scheduling model for the Panama Canal," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(1), pages 69-80, January.
    2. Gourgand, Michel & Grangeon, Nathalie & Norre, Sylvie, 2003. "A contribution to the stochastic flow shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 151(2), pages 415-433, December.
    3. Gourgand, Michel & Grangeon, Nathalie & Norre, Sylvie, 2005. "Markovian analysis for performance evaluation and scheduling in m machine stochastic flow-shop with buffers of any capacity," European Journal of Operational Research, Elsevier, vol. 161(1), pages 126-147, February.
    4. Ilkyeong Moon & Sanghyup Lee & Moonsoo Shin & Kwangyeol Ryu, 2016. "Evolutionary resource assignment for workload-based production scheduling," Journal of Intelligent Manufacturing, Springer, vol. 27(2), pages 375-388, April.
    5. Ramalhinho Lourenco, Helena, 1996. "Sevast'yanov's algorithm for the flow-shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 91(1), pages 176-189, May.
    6. Jean-Paul Watson & Laura Barbulescu & L. Darrell Whitley & Adele E. Howe, 2002. "Contrasting Structured and Random Permutation Flow-Shop Scheduling Problems: Search-Space Topology and Algorithm Performance," INFORMS Journal on Computing, INFORMS, vol. 14(2), pages 98-123, May.
    7. Framinan, Jose M. & Ruiz, Rubén, 2010. "Architecture of manufacturing scheduling systems: Literature review and an integrated proposal," European Journal of Operational Research, Elsevier, vol. 205(2), pages 237-246, September.
    8. Victor Portougal & David J. Robb, 2000. "Production Scheduling Theory: Just Where Is It Applicable?," Interfaces, INFORMS, vol. 30(6), pages 64-76, December.
    9. Yu, Tae-Sun & Pinedo, Michael, 2020. "Flow shops with reentry: Reversibility properties and makespan optimal schedules," European Journal of Operational Research, Elsevier, vol. 282(2), pages 478-490.
    10. Y N Sotskov & A Allahverdi & T-C Lai, 2004. "Flowshop scheduling problem to minimize total completion time with random and bounded processing times," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(3), pages 277-286, March.
    11. Rubén Ruiz & Ali Allahverdi, 2007. "Some effective heuristics for no-wait flowshops with setup times to minimize total completion time," Annals of Operations Research, Springer, vol. 156(1), pages 143-171, December.
    12. Ruiz, Ruben & Maroto, Concepcion, 2005. "A comprehensive review and evaluation of permutation flowshop heuristics," European Journal of Operational Research, Elsevier, vol. 165(2), pages 479-494, September.
    13. 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.
    14. Portougal, Victor & Trietsch, Dan, 2006. "Johnson's problem with stochastic processing times and optimal service level," European Journal of Operational Research, Elsevier, vol. 169(3), pages 751-760, March.
    15. S. S. Panwalkar & Christos Koulamas, 2019. "The evolution of schematic representations of flow shop scheduling problems," Journal of Scheduling, Springer, vol. 22(4), pages 379-391, August.
    16. Yuri N. Sotskov & Natalja M. Matsveichuk & Vadzim D. Hatsura, 2020. "Schedule Execution for Two-Machine Job-Shop to Minimize Makespan with Uncertain Processing Times," Mathematics, MDPI, vol. 8(8), pages 1-51, August.
    17. Vallada, Eva & Ruiz, Rubén & Framinan, Jose M., 2015. "New hard benchmark for flowshop scheduling problems minimising makespan," European Journal of Operational Research, Elsevier, vol. 240(3), pages 666-677.
    18. Kim, Yeong-Dae, 1995. "Minimizing total tardiness in permutation flowshops," European Journal of Operational Research, Elsevier, vol. 85(3), pages 541-555, September.
    19. Blazewicz, Jacek & Domschke, Wolfgang & Pesch, Erwin, 1996. "The job shop scheduling problem: Conventional and new solution techniques," European Journal of Operational Research, Elsevier, vol. 93(1), pages 1-33, August.
    20. Kamburowski, Jerzy, 1999. "Stochastically minimizing the makespan in two-machine flow shops without blocking," European Journal of Operational Research, Elsevier, vol. 112(2), pages 304-309, January.

    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:pal:jorsoc:v:55:y:2004:i:12:d:10.1057_palgrave.jors.2601802. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.palgrave-journals.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.