A Lagrangian-based heuristic for the capacitated lot-sizing problem in parallel machines. (English) Zbl 1142.90511
Summary: This paper addresses the capacitated lot-sizing problem involving the production of multiple items on unrelated parallel machines. A production plan should be determined in order to meet the forecast demand for the items, without exceeding the capacity of the machines and minimize the sum of production, setup and inventory costs. A heuristic based on the Lagrangian relaxation of the capacity constraints and subgradient optimization is proposed. Initially, the heuristic is tested on instances of the single machine problem and results are compared with heuristics from the literature. For parallel machines and small problems the heuristic performance is tested against optimal solutions, and for larger problems it is compared with the lower bound provided by the Lagrangian relaxation.
MSC:
| 90C59 | Approximation methods and heuristics in mathematical programming |
| 90C27 | Combinatorial optimization |
Software:
bc-prodReferences:
| [1] | Armentano, V. A.; França, P. M.; Toledo, F. M.B., A network flow model for the capacitated lot-sizing problem, OMEGA, 27, 275-284 (1999) |
| [2] | Bahl, H. C.; Ritzman, L. P.; Gupta, J. N.D., Determining lot sizes and resources requirements: A review, Operations Research, 35, 329-345 (1987) |
| [3] | Belvaux, G.; Wolsey, L. A., BC-PROD: A specialized branch-and-cut system for lot-sizing problems, Management Science, 46, 724-738 (2000) · Zbl 1231.90384 |
| [4] | Belvaux, G.; Wolsey, L. A., Modelling Practical Lot-Sizing Problems as Mixed-Integer Programs, Management Science, 47, 993-1007 (2001) · Zbl 1232.90169 |
| [5] | Camerini, P. M.; Frata, L.; Maffioli, F., On improving relaxation methods by modified gradient techniques, Mathematical Programming Study, 3, 26-34 (1975) · Zbl 0357.90031 |
| [6] | Carreno, J. J., Economic lot scheduling for multiple products on parallel identical processors, Management Science, 36, 348-358 (1990) · Zbl 0699.90050 |
| [7] | Crowder, P., Computational improvements for subgradient optimization, Symposia Matematica, 19, 357-372 (1976) · Zbl 0338.90042 |
| [8] | Diaby, M.; Bahl, H. C.; Karwan, M. H.; Zionts, S., Capacitated lot-sizing and scheduling by Lagrangian relaxation, European Journal of Operational Research, 59, 444-458 (1992) · Zbl 0761.90060 |
| [9] | Diaby, M.; Bahl, H. C.; Karwan, M. H.; Zionts, S., A Lagrangian relaxation approach for very-large-scale capacitated lot sizing, Management Science, 38, 1329-1340 (1992) · Zbl 0758.90020 |
| [10] | Drexl, A.; Kimms, A., Lot sizing and scheduling—survey and extensions, European Journal of Operational Research, 99, 221-235 (1997) · Zbl 0923.90067 |
| [11] | Evans, J. R., An efficient implementation of the Wagner-Whitin algorithm for dynamic lot-sizing problem, Journal of Operations Management, 5, 229-235 (1985) |
| [12] | Gopalakrishnan, M.; Ding, K.; Bourjolly, J. M.; Mohan, S., A tabu-search heuristic for the capacitated lot-sizing problem with set-up carryover, Management Science, 47, 851-863 (2001) · Zbl 1232.90181 |
| [13] | Held, M.; Wolfe, P.; Crowder, P., Validation of subgradient optimization, Mathematical Programming, 6, 62-88 (1974) · Zbl 0284.90057 |
| [14] | Hindi, K. S.; Fleszar, K.; Charalambous, C., An effective heuristic for the CLSP with set-up times, Journal of the Operational Research Society, 54, 490-498 (2003) · Zbl 1070.90036 |
| [15] | Hung, Y. F.; Hu, Y. C., Solving mixed integer programming production planning problems with setups by shadow price information, Computers and Operations Research, 25, 1027-1042 (1998) · Zbl 1042.90594 |
| [16] | Hung, Y. F.; Hu, Y. C., Using tabu search with ranking candidate list to solve production planning problems with setups, Computers and Industrial Engineering, 42, 615-634 (2003) |
| [17] | Jans, R.; Degraeve, Z., Improved lower bounds for the capacitated lot-sizing problem with setup times, Operations Research Letters, 32, 185-195 (2004) · Zbl 1137.90584 |
| [18] | Johnson, L. A.; Montegomery, D. C., Operations Research in Production Planning, Scheduling and Inventory Control (1974), John Wiley & Sons: John Wiley & Sons New York |
| [19] | Karimi, B.; Fatemi Ghomi, S. M.T.; Wilson, J. M., The capacitated lot-sizing problem: A review of models and algorithms, OMEGA, 31, 365-378 (2003) |
| [20] | Kuik, R.; Salomon, M.; Wassenhove, Batching decisions: Structure and models, European Journal of Operational Research, 75, 243-263 (1994) |
| [21] | Lasdon, L. S.; Terjung, R. C., An efficient algorithm for multi-item scheduling, Operations Research, 19, 946-969 (1971) · Zbl 0224.90039 |
| [22] | Lozano, S.; Larraneta, J.; Onieva, L., Primal-dual approach to the single level capacitated lot-sizing problem, European Journal of Operational Research, 51, 354-366 (1991) · Zbl 0743.90042 |
| [23] | Maes, J.; McClain, J. O.; Van Wassenhove, L. N., Multilevel capacitated lotsizing and complexity, European Journal of Operational Research, 53, 131-148 (1991) · Zbl 0734.90036 |
| [24] | Özdamar, L.; Birbil, S. I.; Portmann, M. C., Technical note: New results for the capacitated lot-sizing problem with overtime decisions and setup time, Production Planning and Control, 13, 2-10 (2002) |
| [25] | Sung, C. S., A single-product parallel-facilities production-planning model, International Journal of Systems Science, 17, 983-989 (1986) · Zbl 0595.90040 |
| [26] | Souza, K. X.S.; Armentano, V. A., Multi-item lot-sizing by a cross decomposition based algorithm, Annals of Operations Research, 50, 557-574 (1994) · Zbl 0812.90041 |
| [27] | Trigeiro, W. W., The effect of setup time on production lot sizes, Production and Inventory Management, 28, 50-52 (1987) |
| [28] | Trigeiro, W. W.; Thomas, L. J.; McClain, J. O., Capacitated lot sizing with setup times, Management Science, 35, 353-366 (1989) |
| [29] | Van Roy, T. J., Cross decomposition for mixed integer programming, Mathematical Programming, 25, 46-63 (1983) · Zbl 0505.90057 |
| [30] | Wagner, H. M.; Whitin, T. M., Dynamic version of the economic lot size model, Management Science, 5, 89-96 (1958) · Zbl 0977.90500 |
| [31] | Wolsey, L. A., Solving Multi-Item Lot-Sizing Problems with an MIP Solver Using Classification and Reformulation, Management Science, 48, 1587-1602 (2002) · Zbl 1232.90104 |
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.
