Minimizing Single-Machine Completion Time Variance

Jose A. Ventura and Michael X. Weng
Additional contact information
Jose A. Ventura: Department of Industrial and Manufacturing Engineering, 207 Hammond Building, The Pennsylvania State University, University Park, Pennsylvania 16802
Michael X. Weng: Department of Industrial and Management Systems Engineering, 4202 East Fowler Avenue, University of South Florida, Tampa, Florida 33620

Management Science, 1995, vol. 41, issue 9, 1448-1455

Abstract: In this article the problem of minimizing the completion time variance in n-job, single-machine scheduling is considered. The release times for all jobs are assumed to be zero. A new quadratic integer programming formulation is introduced. A Lagrangian relaxation (LR) procedure is developed to find a lower bound (LB) to the optimal objective value. When the number of jobs is between 100 and 500, our computational study shows that the lower bounds obtained by the LR procedure are very close to the best known objective values. A new heuristic algorithm is also described. The first phase of the heuristic algorithm is a construction procedure whose purpose is to identify a good initial sequence. The second phase is an improvement procedure based on pairwise interchanges. The new heuristic algorithm provides improved solutions compared to the best known heuristic.

Keywords: scheduling; completion time variance; integer programming; Lagrangian relaxation (search for similar items in EconPapers)
Date: 1995
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.41.9.1448 (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:ormnsc:v:41:y:1995:i:9:p:1448-1455

Access Statistics for this article

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