On Johnson's Two-Machine Flow Shop with Random Processing Times

Peng-Sheng Ku and Shun-Chen Niu
Additional contact information
Peng-Sheng Ku: The University of Texas at Dallas, Richardson, Texas
Shun-Chen Niu: The University of Texas at Dallas, Richardson, Texas

Operations Research, 1986, vol. 34, issue 1, 130-136

Abstract: A set of n jobs is to be processed by two machines in series that are separated by an infinite waiting room; each job requires a (known) fixed amount of processing from each machine. In a classic paper, Johnson gave a simple rule for ordering of the set of jobs to minimize the time until the system becomes empty, i.e., the makespan. This paper studies a stochastic generalization of this problem in which job processing times are independent random variables. Our main result is a sufficient condition on the processing time distributions that implies that the makespan becomes stochastically smaller when two adjacent jobs in a given job sequence are interchanged. We also give an extension of the main result to job shops.

Keywords: 581 scheduling; 583 flow shop and job shop; 585 stochastic processing times (search for similar items in EconPapers)
Date: 1986
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.34.1.130 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:34:y:1986:i:1:p:130-136

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().