Analysis of bounds for a capacitated single-item lot-sizing problem. (English) Zbl 1159.90368
Summary: Lot-sizing problems are cornerstone optimization problems for production planning with time varying demand. We analyze the quality of bounds, both lower and upper, provided by a range of fast algorithms. Special attention is given to LP-based rounding algorithms.
References:
| [1] | Wagner, H.; Whitin, T., A dynamic version of the economic lot-size model, Management Science, 5, 89-96 (1958) · Zbl 0977.90500 |
| [2] | Florian, M.; Klein, M., Deterministic production planning with concave costs and capacity constraints, Management Science, 18, 12-20 (1971) · Zbl 0273.90023 |
| [3] | Chen, H.-D.; Lee, C.-Y., A new dynamic programming algorithm for the single item capacitated dynamic lot-size model, Journal of Global Optimization, 4, 285-300 (1994) · Zbl 0812.90037 |
| [4] | Leung, J.; Magnanti, T.; Vachani, R., Facets and algorithms for capacitated lot-sizing, Mathematical Programming, 45, 331-359 (1989) · Zbl 0681.90060 |
| [5] | Pochet, Y., Valid inequalities and separation for capacitated economic lot-sizing, Operations Research Letters, 7, 109-115 (1988) · Zbl 0653.90051 |
| [6] | Pochet, Y.; Wolsey, L., Polyhedra for lot-sizing with Wagner-Whitin costs, Mathematical Programming, 67, 297-323 (1994) · Zbl 0822.90049 |
| [7] | Miller A. Polyhedral approaches to capacitated lot-sizing problems. Ph.D. thesis, Georgia Institute of Technology, 1999.; Miller A. Polyhedral approaches to capacitated lot-sizing problems. Ph.D. thesis, Georgia Institute of Technology, 1999. |
| [8] | Van Hoesel, C.; Wagelmans, A., Fully polynomial approximation schemes for single-item capacitated economic lot-sizing problems, Mathematics of Operations Research, 26, 339-357 (2001) · Zbl 1082.90532 |
| [9] | Bitran, G.; Yanasse, H., Computational complexity of the capacitated lot-size problem, Management Science, 28, 1174-1186 (1982) · Zbl 0502.90046 |
| [10] | Vazirani, V., Approximation algorithms (2001), Springer: Springer New York · Zbl 1138.90417 |
| [11] | Bar-Noy, A.; Guha, S.; Naor, J.; Schieber, B., Approximating the throughput of multiple machines in real-time scheduling, SIAM Journal on Computing, 31, 331-352 (2001) · Zbl 0994.68073 |
| [12] | Goemans, M. X.; Queyranne, M.; Schulz, A. S.; Skutella, M.; Wang, Y., Single machine scheduling with release dates, SIAM Journal on Discrete Mathematics, 15, 165-192 (2002) · Zbl 1009.90096 |
| [13] | Hall, L. A.; Schulz, A. S.; Shmoys, D. B.; Wein, J., Scheduling to minimize average completion time: off-line and on-line approximation algorithms, Mathematics of Operations Research, 22, 513-544 (1997) · Zbl 0883.90064 |
| [14] | Savelsbergh, M.; Uma, R.; Wein, J., An experimental study of LP-based approximation algorithms for scheduling problems, INFORMS Journal on Computing, 17, 123-136 (2005) · Zbl 1239.90053 |
| [15] | Schulz, A. S.; Skutella, M., Scheduling unrelated machines by randomized rounding, SIAM Journal on Discrete Mathematics, 15, 450-469 (2002) · Zbl 1055.90040 |
| [16] | Van Hoesel, C.; Wagelmans, A., An \(O(T^3)\) algorithm for the economic lot-sizing problem with constant capacities, Management Science, 42, 142-150 (1996) · Zbl 0851.90058 |
| [17] | Nemhauser, G.; Wolsey, L., Integer and combinatorial optimization (1988), Wiley: Wiley New York · Zbl 0652.90067 |
| [18] | Hardin JR. Resource-constrained scheduling and production planning: linear programming-based studies. Ph.D. thesis, Georgia Institute of Technology, 2001.; Hardin JR. Resource-constrained scheduling and production planning: linear programming-based studies. Ph.D. thesis, Georgia Institute of Technology, 2001. |
| [19] | Csirik, J.; Frenk, J.; Labbé, M.; Zhang, S., Heuristics for the 0-1 min-knapsack problem, Acta Cybernetica, 10, 15-20 (1991) · Zbl 0741.90048 |
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.
