Minimizing single-machine completion time variance

Minimizing single-machine completion time variance

0.00 Avg rating0 Votes
Article ID: iaor19961605
Country: United States
Volume: 41
Issue: 9
Start Page Number: 1448
End Page Number: 1455
Publication Date: Sep 1995
Journal: Management Science
Authors: ,
Keywords: programming: integer, heuristics, programming: quadratic
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 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.

Reviews

Required fields are marked *. Your email address will not be published.