Loading...
Please wait, while we are loading the content...
Similar Documents
Heuristics for Multimachine Scheduling Problems with Earliness and Tardiness Costs
| Content Provider | Semantic Scholar |
|---|---|
| Author | Federgruen, Awi Mosheiov, Gur |
| Copyright Year | 1996 |
| 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 ON 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 ON-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. |
| Starting Page | 1544 |
| Ending Page | 1555 |
| Page Count | 12 |
| File Format | PDF HTM / HTML |
| DOI | 10.1287/mnsc.42.11.1544 |
| Volume Number | 42 |
| Alternate Webpage(s) | https://www0.gsb.columbia.edu/mygsb/faculty/research/pubfiles/4088/federgruen_multimachine_scheduling_problems.pdf |
| Alternate Webpage(s) | https://doi.org/10.1287/mnsc.42.11.1544 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
