Deterministic and Random Single Machine Sequencing with Variance Minimization

Vina Vani and M. Raghavachari
Additional contact information
Vina Vani: Gujarat University, Ahmedabad, India
M. Raghavachari: Indian Institute of Management, Ahmedabad, India, and the University of Pennsylvania, Philadelphia, Pennsylvania

Operations Research, 1987, vol. 35, issue 1, 111-120

Abstract: We discuss the problem of scheduling several jobs on a single machine so as to minimize the variance of the jobs' completion times. By exploiting the well-known pooled variance formula, we obtain a general formula for the change in variance due to the interchange of two specified jobs whose positions have not been fixed in the sequence. This result permits us to obtain explicit optimal sequences for problems with 6 or 7 jobs, and to show that Schrage's conjecture on positioning the job with the third largest processing time is true for problems with up to 18 jobs. We then develop a heuristic procedure based on a variance interchange formula and compare it with other known heuristic methods. We also consider a problem never before examined, namely, the case when processing times are not known deterministically but are random variables. We obtain some general results, under certain assumptions on the parameters of the distributions of processing times, and extend to the random situation many results applicable to the deterministic case. Finally, we give some results for the exponential distribution of processing times.

Keywords: 581 machine sequencing; 589 job shop scheduling (search for similar items in EconPapers)
Date: 1987
References: Add references at CitEc
Citations: View citations in EconPapers (21)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.35.1.111 (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:35:y:1987:i:1:p:111-120

Access Statistics for this article

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