Article ID: | iaor200698 |
Country: | Netherlands |
Volume: | 27 |
Issue: | 3 |
Start Page Number: | 109 |
End Page Number: | 118 |
Publication Date: | Oct 2000 |
Journal: | Operations Research Letters |
Authors: | Wagelmans Albert P.M., Gerodimos A.E. |
Keywords: | combinatorial analysis, programming: dynamic |
We study four scheduling problems involving the maximum lateness criterion and an element of batching. For all the problems that we examine, algorithms appear in the literature that consist of a sorting step to determine an optimal job sequence, followed by a dynamic programming step that determines the optimal batches. In each case, the dynamic program is based on a backward recursion of which a straightforward implementation requires O(