A heuristic method for lot-sizing in multi-stage systems. (English) Zbl 0891.90056
Summary: This article considers the lot-sizing problem in multi-stage production settings with capacity-constrained resources. This problem deals with the determination of a production plan for the end item and its components in order to meet the forecast demand in each period of a planning horizon. The production plan should minimize the sum of production, setup and inventory costs. A heuristic method build upon a formulation of the problem in terms of echelon stock is developed. Computational results are reported and the solutions’ quality is evaluated through Lagrangean lower bounds.
Keywords:
lot-sizing; multi-stage production; capacity-constrained resources; heuristic; Lagrangean lower boundsReferences:
| [1] | Wollman, T. E.; Berry, W. T.; Whybark, D. C., Manufacturing Planning and Control Systems (1988), Dow Jones, Richard D. Irwin: Dow Jones, Richard D. Irwin Illinois |
| [2] | Bahl, H. C.; Ritzman, L. P.; Gupta, J. N.D., Determining lot sizes and resources requirements: a review, Management Science, 35, 329-345 (1987) |
| [3] | Goyal, S. K.; Gunasekaran, A., Multi-stage production-inventory systems, European Journal of Operational Research, 46, 1-20 (1990) · Zbl 0702.90035 |
| [4] | Florian, M.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Deterministic production planning and complexity, Management Science, 26, 669-679 (1980) · Zbl 0445.90025 |
| [5] | Maes, J.; McClain, J. O.; Van Wassenhove, L. N., Multilevel capacitated lotsizing complexity and LP-based heuristics, European Journal of Operational Research, 53, 131-148 (1991) · Zbl 0734.90036 |
| [6] | Zangwill, W. I., A backlogging model and a multi-echelon model of a dynamic economic lot-size production system-a network approach, Management Science, 15, 506-527 (1969) · Zbl 0172.44603 |
| [7] | Crowston, W. B.; Wagner, M. H.; Williams, J. F., Economic lot size determination in multi-stage assembly systems, Management Science, 19, 517-527 (1973) · Zbl 0251.90013 |
| [8] | Crowston, W. B.; Wagner, M. H.; Williams, J. F., Dynamic lot-size models for multi-stage assembly systems, Management Science, 20, 14-21 (1973) · Zbl 0304.90039 |
| [9] | Love, S. F., A facilities in series inventory model with nested schedules, Management Science, 18, 327-338 (1972) · Zbl 0237.90015 |
| [10] | Schwarz, L. B.; Schrage, L., Optimal and system myopic policies for multi-echelon production/inventory assembly systems, Management Science, 21, 1285-1294 (1975) · Zbl 0307.90021 |
| [11] | Afentakis, P.; Gavish, B.; Karmakar, U., Computationally efficient optimal solutions to the lot-sizing problem in multi-stage assembly systems, Management Science, 30, 222-239 (1984) · Zbl 0552.90045 |
| [12] | Afentakis, P.; Gavish, B., Optimal lot-sizing algorithms for complex product structures, Operations Research, 34, 237-249 (1986) · Zbl 0602.90048 |
| [13] | Konno, H., Minimum concave production system: a further generalization of multi-echelon model, Mathematical Programming, 41, 185-193 (1988) · Zbl 0662.90037 |
| [14] | Williams, J. F., Heuristic techniques for simultaneous scheduling, Management Science, 27, 336-352 (1981) · Zbl 0453.90044 |
| [15] | Graves, S. C., Multi-stage lot-sizing: an iterative procedure, (Schwarz, L. B., Multi-Stage Production/Inventory Control Systems: Theory and Practice, TIMS Studies in the Management Science, Vol. 16 (1981), North-Holland: North-Holland Amsterdam), 95-109 · Zbl 0469.90022 |
| [16] | Blackburn, J. D.; Millen, R. A., Improved heuristics for multistage requirements planning systems, Management Science, 28, 44-56 (1982) · Zbl 0486.90035 |
| [17] | Afentakis, P., A parallel heuristic algorithm for lot-sizing in multi-stage production systems, IIE Transportation, 19, 34-42 (1987) |
| [18] | Kuik, R.; Salomon, R., Multi-level lot sizing problem: evaluation of a simulated annealing heuristic, European Journal of Operational Research, 45, 25-37 (1990) · Zbl 0685.90052 |
| [19] | Gupta, Y. P.; Keung, Y. K.; Gupta, M. C., Comparative analysis of lot-sizing models for multi-stage systems: a simulation study, International Journal of Product Research, 30, 695-716 (1992) · Zbl 0729.90966 |
| [20] | Billington, P. J.; McClain, J. O.; Thomas, L. J., Mathematical programming approaches to capacity mrp systems: review formulation and problem reduction, Management Science, 19, 1126-1141 (1983) · Zbl 0519.90039 |
| [21] | Lambrecht, M.; VanderEecken, J., A facilities in series capacity constrained dynamic lot-size model, European Journal Operational Research, 2, 42-49 (1978) · Zbl 0371.90055 |
| [22] | Gabbay, H., Multi-stage production planning, Management Science, 25, 1138-1148 (1979) · Zbl 0466.90035 |
| [23] | Steinberg, E.; Napier, H. A., Optimal multi-level lot-sizing for requirements planning systems, Management Science, 26, 1258-1271 (1980) · Zbl 0447.90017 |
| [24] | Zahorik, A.; Thomas, L. J.; Trigueiro, W. W., Network programming models for production scheduling in multi-stage multi-item capacitated systems, Management Science, 30, 308-325 (1984) · Zbl 0588.90035 |
| [25] | Clark, A. R.; Armentano, V. A., The application of valid inequalities to the multi-stage lot-sizing problem, Computers & Operations Research, 22, 669-680 (1995) · Zbl 0830.90033 |
| [26] | Billington, P. J.; McClain, J. O.; Thomas, L. J., Heuristics for multilevel lot-sizing with a bottleneck, Management Science, 32, 989-1006 (1986) · Zbl 0596.90038 |
| [27] | Roll, Y.; Karni, R., Multi-item, multi-level lot sizing with a aggregate capacity constraint, European Journal of Operational Research, 51, 73-87 (1991) |
| [28] | Wagner, H. M.; Whitin, T. M., Dynamic version of the economic lot size model, Management Science, 5, 89-96 (1958) · Zbl 0977.90500 |
| [29] | Kuik, R.; Salomon, M.; Van Wasenhove, L. N.; Maes, J., Linear programming, simulated annealing and tabu search heuristics for lot sizing in bottleneck assembly systems, IIE Transportation, 25, 62-72 (1993) |
| [30] | Billington, P. J.; Blackburn, J.; Maes, J.; Millen, R.; Van Wassenhove, L. N., Multi-item lot-sizing in capacitated multi-stage serial systems, IIE Transportation, 26, 12-18 (1994) |
| [31] | Clark, A. R.; Armentano, V. A., A heuristic for a resource-capacited multi-stage lot-sizing problem with lead times, Journal of Operational Research Society, 44, 1208-1222 (1995) · Zbl 0845.90038 |
| [32] | Clark, A.; Scarf, H., Optimal policies for multi-echelon inventory problems, Management Science, 6, 475-490 (1960) |
| [33] | Clark, A. R.; Armentano, V. A., Echelon stock formulation for multi-stage lot-sizing with component lead times, International Journal of Systems Science, 24, 1759-1775 (1993) · Zbl 0785.93010 |
| [34] | Geoffrion, A. M., Lagrangean relaxation for integer programming, Mathematics Programming, 2, 82-114 (1974) · Zbl 0395.90056 |
| [35] | Fisher, M. L., The Lagrangean relaxation method for solving integer programming problems, Management Science, 22, 1-18 (1981) · Zbl 0466.90054 |
| [36] | Camerini, P. M.; Frata, L.; Maffioli, F., On improving relaxation methods by modified techniques, Mathematics Programming, 3, 26-34 (1975) · Zbl 0357.90031 |
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.
