## Awi Federgruen

*Heuristics for multimachine scheduling problems with earliness and tardiness costs*

Coauthor(s): Gur Mosheiov.

#### Download:

Adobe Acrobat PDF

**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 to 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 *0(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 *0(N*^{-2}) under very general conditions with respect to the function *F.* In addition, we report on a numerical study showign 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.

**Source:** *Management Science*

**Exact Citation:**

Federgruen, Awi, and Gur Mosheiov. "Heuristics for multimachine scheduling problems with earliness and tardiness costs." *Management Science* 42, no. 11 (November 1996): 1544-1555.

**Volume:** 42

**Number:** 11

**Pages:** 1544-1555

**Date:**
11
1996