Improved dynamic programs for some batching problems involving the maximum lateness criterion. (English) Zbl 0969.90049
Summary: 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 literatare 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(n^2)\) time, where \(n\) is the number of jobs. We present improved implementations of these dynamic programs that are based on monotonicity properties of the objective expressed as a function of the total processing time of the first batch. These properties and the use of efficient data structures enable optimal solutions to be found for each of the four problems in \(O(n\log n)\) time; in two cases, the batching step is actually performed in linear time and the overall complexity is determined by the sorting step.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C39 | Dynamic programming |
| 90C60 | Abstract computational complexity for mathematical programming problems |
References:
| [1] | Aggarwal, A.; Park, J. K., Improved algorithms for economic lot size problems, Oper. Res., 41, 3, 549-571 (1993) · Zbl 0820.90035 |
| [2] | Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., Data Structures and Algorithms (1987), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0307.68053 |
| [3] | Albers, S.; Brucker, P., The complexity of one-machine batching problems, Disc. Appl. Math., 47, 87-107 (1993) · Zbl 0792.90035 |
| [4] | Baker, K. R., Scheduling the production of components at a common facility, IIE Trans., 20, 1, 32-35 (1988) |
| [5] | Brucker, P., Scheduling Algorithms (1995), Springer: Springer Berlin · Zbl 0839.90059 |
| [6] | Brucker, P.; Gladky, A.; Hoogeveen, H.; Kovalyov, M. Y.; Potts, C. N.; Tautenhahn, T.; van de Velde, S., Scheduling a batching machine, J. Schedul., 1, 31-54 (1998) · Zbl 0909.90172 |
| [7] | Coffman, E. G.; Yannakakis, M.; Magazine, M. J.; Santos, C., Batch sizing and job sequencing on a single machine, Ann. Oper. Res., 26, 135-147 (1990) · Zbl 0712.90035 |
| [8] | Federgruen, A.; Tzur, M., A simple forward algorithm to solve general dynamic lot sizing models with \(n\) periods in \(O(n logn)\) or \(O (n)\) time, Manage. Sci., 37, 909-925 (1991) · Zbl 0748.90011 |
| [9] | A.E. Gerodimos, C.A. Glass, C.N. Potts, Scheduling customised jobs on a single machine under item availability, unpublished report, Faculty of Mathematical Studies, University of Southampton, UK (1999); A.E. Gerodimos, C.A. Glass, C.N. Potts, Scheduling customised jobs on a single machine under item availability, unpublished report, Faculty of Mathematical Studies, University of Southampton, UK (1999) |
| [10] | Gerodimos, A. E.; Glass, C. A.; Potts, C. N., Scheduling the production of two-operation jobs on a single machine, Euro. J. Oper. Res., 120, 250-259 (2000) · Zbl 0953.90027 |
| [11] | Kovalyov, M. Y.; Potts, C. N., Scheduling with batching: a review, Euro. J. Oper. Res., 120, 228-249 (2000) · Zbl 0953.90028 |
| [12] | Santos, C. A.; Magazine, M. J., Batching in single operation manufacturing systems, Oper. Res. Lett., 4, 3, 99-103 (1985) · Zbl 0572.90051 |
| [13] | van Hoesel, S.; Wagelmans, A.; Moerman, B., Using geometric techniques to improve dynamic programming algorithms for the economic lot-sizing problem and extensions, Euro. J. Oper. Res., 75, 312-331 (1994) · Zbl 0806.90125 |
| [14] | Wagelmans, A.; van Hoesel, S.; Kolen, A., Economic lot sizing: an \(O(n logn)\) algorithm that runs in linear time in the Wagner-Whitin case, Oper. Res., 40, Supp. 1, 145-156 (1992) · Zbl 0771.90031 |
| [15] | Webster, S.; Baker, K. R., Scheduling groups of jobs on a single machine, Oper. Res., 43, 692-703 (1995) · Zbl 0857.90062 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
