The application of valid inequalities to the multi-stage lot-sizing problem. (English) Zbl 0830.90033
Summary: A capacitated multi-stage lot-sizing problem for general product structures with setup and lead times is considered. The problem is formulated as a mixed integer linear program and valid inequalities that are high dimension faces of the problem’s convex hull are identified. A fast separation algorithm is developed to iteratively select those inequalities that cut off the solution of the linear programming relaxation. The resulting much improved lower bounds are used in a branch-and-bound algorithm. Computational test results are presented.
Software:
OSLReferences:
| [1] | Bahl, H. C.; Ritzman, L. P.; Gupta, J. N.D., Determining lot-sizes and resource requirements: a review, Ops Res., 35, 237-249 (1987) |
| [2] | Johnson, L. A.; Montgomey, D. C., Operations Research in Production Planning, Scheduling and Inventory Control (1974), Wiley: Wiley New York |
| [3] | Zangwill, W. I., A backlogging model and a multi-echelon model of a dynamic economic lot-size production system—a network approach, Mgmt Sci., 15, 506-527 (1969) · Zbl 0172.44603 |
| [4] | Konno, H., Minimum concave cost production system: a further generalization of multi-echelon model, Math. Prog., 41, 185-193 (1988) · Zbl 0662.90037 |
| [5] | Steinberg, E.; Napier, H. A., Optimal multi-level lot-sizing for requirements planning systems, Mgmt Sci., 26, 1258-1271 (1980) · Zbl 0447.90017 |
| [6] | Afentakis, P.; Gavish, B.; Karmarkar, U., Computationally efficient optimal solutions to the lot-sizing problem in multistage assembly systems, Mgmt Sci., 30, 222-239 (1984) · Zbl 0552.90045 |
| [7] | Afentakis, P.; Gavish, B., Optimal lot-sizing algorithms for complex product structures, Ops Res., 34, 237-249 (1986) · Zbl 0602.90048 |
| [8] | Crowston, W. B.; Wagner, M. H.; Williams, J. F., Economic lot size determination in multi-stage assembly systems, Mgmt Sci., 19, 517-527 (1973) · Zbl 0251.90013 |
| [9] | Crowston, W. B.; Wagner, M. H., Dynamic lot-size models for multi-stage assembly systems, Mgmt Sci., 20, 517-527 (1973) · Zbl 0251.90013 |
| [10] | Schwarz, L. B.; Schrage, L., Optimal and system myopic policies for multi-echelon production/inventory assembly systems, Mgmt Sci., 21, 1285-1294 (1975) · Zbl 0307.90021 |
| [11] | Goyal, S. K.; Gunasekaran, A., Multi-stage production-inventory systems, Eur. J. Opl Res., 46, 1-20 (1990) · Zbl 0702.90035 |
| [12] | Maes, J.; McClain, J. O.; Van Wassenhove, L. N., Multilevel capacitated lotsizing complexicity and LP-based heuristics, Eur. J. Opl Res., 53, 131-148 (1991) · Zbl 0734.90036 |
| [13] | Gomory, R. E., Outline of an algorithm for integer solutions to linear programs, Bull. Am. Math. Soc., 64, 275-278 (1958) · Zbl 0085.35807 |
| [14] | Barany, I.; Van Roy, T. J.; Wolsey, L. A., Strong formulations for multi-item capacitated lot-sizing, Mgmt Sci., 30, 1255-1261 (1984) · Zbl 0601.90037 |
| [15] | Clark, A. R.; Armentano, V. A., Echelon stock formulations for multi-stage lot-sizing with lead times, Int. J. Syst. Sci., 24, 1759-1775 (1993) · Zbl 0785.93010 |
| [16] | Vollman, T. E.; Berry, W. T.; Whybark, D. C., Manufacturing Planning and Control Systems (1988), Dow-Jones: Dow-Jones Irwin, IL |
| [17] | Clark, A. P.; Scarf, H., Optimal policities for a multi-echelon inventory problem, Mgmt Sci., 6, 475-490 (1960) |
| [18] | Clark, A. R.; Armentano, V. A., The application of valid inequalities to the multi-stage lot-sizing problem, (Technical Report #11 (1993), Faculty of Electrical Engineering, Universidade Estadual de Campinas: Faculty of Electrical Engineering, Universidade Estadual de Campinas Brazil) · Zbl 0830.90033 |
| [19] | Nemhauser, G. L.; Wolsey, L. A., Integer and Combinatorial Optimization (1988), Wiley: Wiley New York · Zbl 0469.90052 |
| [20] | Van Roy, T. J.; Wolsey, L. A., Solving mixed integer programming problems using automatic reformulation, Ops Res., 35, 45-57 (1987) · Zbl 0614.90082 |
| [21] | Van Roy, T. J.; Wolsey, L. A., Valid inequalities for mixed 0-1 programs, Discr. Appl. Math., 14, 199-213 (1986) · Zbl 0593.90058 |
| [22] | IBM, Optimization Subroutine Library (OSL) User’s Guide (1991), Release 2 |
| [23] | Freund, J. E.; Walpole, R. E., Mathematical Statistics (1980), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0426.62001 |
| [24] | White, J.; Yeats, A.; Skipworth, G., Tables for Statisticians (1979), Thorns: Thorns Cheltenham |
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.
