AN ANALYSIS OF THE TWO-MACHINE STATIC, STOCHASTIC FLOWSHOP WITH LINEAR COMPLETION TIME COSTS

This study investigated the n-job, two-machine, static flowshop with independent, exponential job processing times and linear completion time or penalty costs. The objective was to find a job sequence which minimizes the expected total penalty cost for all the jobs. This performance measure is more complicated and more complete than that used in all the previous analytical, stochastic, multi-machine, flowshop studies; namely, the expected schedule length. The expected total penalty cost for all the jobs is a function of both the penalty cost associated with each job and the expected job completion time.;The common assumptions made in most of the static, stochastic, multi-machine, flowshop literature were also made in this research. The general approach utilized in this analysis was a comparison of two job sequences in which the first job sequence is the same as the second except that exactly two adjacent jobs i and j have been interchanged. The job sequence with the lower expected total penalty cost for all the jobs is the preferred job sequence.;We developed in this study seven major results (seven theorems). First, it was shown that the job sequence which minimizes the expected total penalty cost for all the jobs is a permutation schedule. Second, for the two-job case, a necessary and sufficient condition was derived for determining the optimal job sequence. Third, for the n-job case, three sufficient conditions were deduced for job i to precede job j. The first condition turned out to be Rothkopf's Rule (1966), while the third condition is the rule developed by Cunningham and Dutta (1973) for minimizing the expected schedule length.;To specify a complete and optimal job sequence for the n-job case, it was necessary to establish that the three sufficient conditions are transitive. Establishing transitivity was the fourth major result of this study.;On the other hand, the expected schedule length depends only on the expected job completion times. This may be a significant shortcoming, since in many flowshops penalty or holding costs may be considered important.;Fifth, three special cases of the general n-job problem were analyzed. In the first special case studied, we assumed some of the jobs have the same expected processing time on each machine. Both a necessary and sufficient, as well as transitive, condition was derived for job i to precede job j. We assumed in the second special case examined that some jobs have the same expected processing time on the first machine. Two sufficient and transitive conditions were deduced for job i and precede job j. In the third special case investigated, we assumed that k(,il) (GREATERTHEQ) k(,jl) + k(,i2) for jobs i and j, where k(,il), k(,jl), and k(,i2) are the parameters of the exponential processing time distributions for job i on machine one, job j on machine one, and job i on machine two, respectively. One sufficient and transitive condition was derived for job i to precede job j. In each of these special cases, the first condition developed for job i to precede job j is Rothkopf's Rule (1966).;The results imply that jobs with relatively high penalty cost and relatively long expected processing times will tend to be sequenced before jobs with relatively low penalty cost and relatively long expected processing times.