Multi-level multi-item lot size planning with limited resources and general manufacturing structure. (Mehrstufige Mehrprodukt-Losgrößenplanung bei beschränkten Ressourcen und genereller Erzeugnisstruktur.) (German) Zbl 0776.90016
Summary: A heuristic approach for the dynamic multi-level multi-item lotsizing problem in general product structures with multiple constrained resources and setup times is proposed. With the help of Lagrangean relaxation the capacitated multi-level lotsizing problem is decomposed into several uncapacitated single-item lotsizing problems. From the solutions of these single-item problems lower bounds on the minimal objective value are derived. Upper bounds are generated by means of a heuristic finite scheduling procedure. The quality of the approach is tested with reference to various problem groups of differing sizes.
MSC:
| 90B05 | Inventory, storage, reservoirs |
| 90-08 | Computational methods for problems pertaining to operations research and mathematical programming |
Software:
MlclspReferences:
| [1] | Bahl HC, Ritzman LP, Gupta JND (1987) Determining lot sizes and resource requirements: A review. Oper Res 35:329–345 · doi:10.1287/opre.35.3.329 |
| [2] | Billington PJ (1983) Multi-level lot-sizing with a bottleneck work center. Ph.D. Dissertation. Cornell University, Ithaca, New York |
| [3] | Chen W-H, Thizy J-M (1990) Analysis of relaxations for the multi-item capacitated lot-sizing problem. Ann Oper Res 26:29–72 · Zbl 0709.90030 · doi:10.1007/BF02248584 |
| [4] | Crowder H (1976) Computational improvements for subgradient optimization. Symposia Mathematica 19:357–372 · Zbl 0338.90042 |
| [5] | Diaby M, Bahl HC, Karwan MH, Zionts S (1992) A lagrangean relaxation approach for very-large-scale capacitated lot-sizing. Manag Sci 38:1329–1340 · Zbl 0758.90020 · doi:10.1287/mnsc.38.9.1329 |
| [6] | Dixon PS, Silver EA (1981) A heuristic solution procedure for multi-item, single-level, limited capacity lot-sizing problem. J Oper Manag 2:22–39 · doi:10.1016/0272-6963(81)90033-4 |
| [7] | Federgruen A, Tzur M (1991) A simple forward algorithm to solve general dynamic lot sizing models withn periods inO(n logn) orO(n) time. Manag Sci 37:909–925 · Zbl 0748.90011 · doi:10.1287/mnsc.37.8.909 |
| [8] | Fisher ML (1981) The lagrangian relaxation method for solving integer programming problems. Manag Sci 27:1–18 · Zbl 0466.90054 · doi:10.1287/mnsc.27.1.1 |
| [9] | Fleischmann B (1990) The discrete lot-sizing and scheduling problem. Eur J Oper Res 44:337–348 · Zbl 0689.90043 · doi:10.1016/0377-2217(90)90245-7 |
| [10] | Gupta YP, Keung YK, Gupta MC (1992) Comparative analysis of lot-sizing models for multi-stage systems: A simulation study. Int J Prod Res 30:695–716 · Zbl 0729.90966 |
| [11] | Heinrich CE (1987) Mehrstufige Losgrößenplanung in hierarchisch strukturierten Produktionsplanungssystemen. Springer, Berlin Heidelberg New York |
| [12] | Held M, Wolfe P, Crowder HP (1974) Validation of subgradient optimization. Math Prog 6:62–88 · Zbl 0284.90057 · doi:10.1007/BF01580223 |
| [13] | Lozano S, Larraneta J, Onieva L (1991) Primal-dual approach to the single level capacitated lot-sizing problem. Eur J Oper Res 51:354–366 · Zbl 0743.90042 · doi:10.1016/0377-2217(91)90311-I |
| [14] | Maes J (1987) Capacitated lotsizing techniques in manufacturing resource planning. Ph.D. Dissertation, Katholieke Universiteit Leuven, Fakulteit der Toegepaste Wetenschappen, Leuven |
| [15] | Maes J, Van Wassenhove LN (1986) A simple heuristic for the multi-item single level capacitated lotsizing problem. OR Lett 4:265–273 · Zbl 0596.90029 |
| [16] | Maes J, Van Wassenhove LN (1991) Capacitated dynamic lotsizing heuristics for serial systems. Int J Prod Res 29:1235–1249 · doi:10.1080/00207549108930130 |
| [17] | Maes J, McClain JO, Van Wassenhove LN (1991) Multilevel capacitated lotsizing complexity and LP-based heuristics. Eur J Oper Res 53:131–148 · Zbl 0734.90036 · doi:10.1016/0377-2217(91)90130-N |
| [18] | Nemhauser GL, Wolsey LA (1988) Integer and combinatorial optimization. Wiley, New York · Zbl 0652.90067 |
| [19] | Salomon M (1991) Deterministic lotsizing models for production planning. Springer, Berlin Heidelberg New York · Zbl 0761.90054 |
| [20] | Shapiro JF (1979) A survey of lagrangean techniques for discrete optimization. Ann Discr Math 5:113–138 · Zbl 0411.90054 · doi:10.1016/S0167-5060(08)70346-7 |
| [21] | Tempelmeier H (1992) Material-Logistik. Grundlagen der Bedarfs- und Losgrößenplanung in PPS-Systemen. 2. Aufl. Springer, Berlin Heidelberg New York |
| [22] | Tempelmeier H, Helber S (1993) A heuristic for dynamic multiitem multi-level capacitated lotsizing for general product structures. Eur J Oper Res (forthcoming) · Zbl 0809.90070 |
| [23] | Thizy J-M (1991) Analysis of lagrangian decomposition for the multi-item capacitated lot-sizing problem. INFOR 29:271–283 · Zbl 0778.90008 |
| [24] | Thizy J-M, Van Wassenhove LN (1985) Lagrangean relaxation for multi-item capacitated lot-sizing problem: A heuristic implementation. IIE Trans 17:308–313 · doi:10.1080/07408178508975308 |
| [25] | Trigeiro WW (1987) A dual-cost heuristic for the capacitated lot sizing problem. IIE Trans 19:67–72 · doi:10.1080/07408178708975371 |
| [26] | Trigeiro WW, Thomas LJ, McClain JO (1989) Capacitated lot sizing with setup times. Manag Sci 35:353–366 · doi:10.1287/mnsc.35.3.353 |
| [27] | Wagelmans A, Van Hoesel S, Kolen A (1992) Economic lot sizing: AnO(n logn) algorithm that runs in linear time in the Wagner-Whitin case. Oper Res 40:145–155 · Zbl 0771.90031 · doi:10.1287/opre.40.1.S145 |
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.
