Minimizing Single-Machine Completion Time Variance

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...

Full description

Saved in:
Bibliographic Details
Published in:Management science 1995-09, Vol.41 (9), p.1448-1455
Main Authors: Ventura, Jose A, Weng, Michael X
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
completion time variance
Error rates
Exact sciences and technology
Heuristic
Heuristics
Industrial economics
Integer programming
Job shops
Lagrangian function
Lagrangian relaxation
Lateness
Management science
Operational research and scientific management
Operational research. Management science
Production systems
Scheduling
Scheduling, sequencing
Studies
Time management
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0025-1909
1526-5501
DOI:10.1287/mnsc.41.9.1448