Heuristics for multimachine scheduling problems with earliness and tardiness costs

Heuristics for multimachine scheduling problems with earliness and tardiness costs

0.00 Avg rating0 Votes
Article ID: iaor1998752
Country: United States
Volume: 42
Issue: 11
Start Page Number: 1544
End Page Number: 1555
Publication Date: Nov 1996
Journal: Management Science
Authors: ,
Keywords: heuristics
Abstract:

We consider multimachine scheduling problems with earliness and tardiness costs. We first analyze problems in which the cost of a job is given by a general nondecreasing, convex function F of the absolute deviation of its completion time from a (common) unrestrictive due-date, and the objective is to minimize the sum of the costs incurred for all N jobs. (A special case to which considerable attention is given is the completion time variance problem.) We derive an easily computable lower bound for the minimum cost value and a simple ‘Alternating Schedule’ heuristic, both of which are computable in O(N log N) time. Under mild technical conditions with respect to F, we show that the worst case optimality (accuracy) gap of the heuristic (lower bound) is bounded by a constant as well as by a simple function of a single measure of the dispersion among the processing times. We also show that the heuristic (bound) is asymptotically optimal (accurate) and characterize the convergence rate as O(N–2) under very general conditions with respect to the function F. In addition, we report on a numerical study showing that the average gap is less than 1% even for problems with 30 jobs, and that falls below 0.1% for problems with 90 or more jobs. This study also establishes that the empirical gap is almost perfectly proportional with N–2, as verified by a regression analysis. Finally, we generalize the heuristic to settings with a possibly restrictive due date and general asymmetric, and possibly nonconvex, earliness and tardiness cost functions and demonstrate its excellent performance via a second numerical study.

Reviews

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