Heuristics for Multimachine Scheduling Problems with Earliness and Tardiness Costs

A. Federgruen and G. Mosheiov
Additional contact information
A. Federgruen: Graduate School of Business, Columbia University, New York, New York 10027
G. Mosheiov: School of Business Administration and Department of Statistics, Hebrew University, Jerusalem

Management Science, 1996, vol. 42, issue 11, 1544-1555

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

Keywords: multimachine scheduling; earliness and tardiness costs; heuristics; worst case; asymptotic and probabilistic analysis (search for similar items in EconPapers)
Date: 1996
References: Add references at CitEc
Citations: View citations in EconPapers (13)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.42.11.1544 (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:42:y:1996:i:11:p:1544-1555

Access Statistics for this article

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