HEURISTICS FOR MULTIMACHINE SCHEDULING PROBLEMS WITH EARLINESS AND TARDINESS COSTS

We consider multimachine scheduling problems with earliness and tardin ess costs. We first analyze problems in which the cost of a job is giv en by a general nondecreasing, convex function F of the absolute devia tion of its completion time from a (common) unrestrictive due-date, an d 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 low er bound for the minimum cost value and a simple ''Alternating Schedul e'' 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 ca se 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 heur istic (bound) is asymptotically optimal (accurate) and characterize th e convergence rate as O(N-2) under very general conditions with respec t to the function F. In addition, we report on a numerical study showi ng 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 pro portional with N-2, as verified by a regression analysis. Finally, we generalize the heuristic to settings with a possibly restrictive due d ate and general asymmetric, and possibly nonconvex, earliness and tard iness cost functions and demonstrate its excellent performance via a s econd numerical study.