A dual algorithm for the economic lot-sizing problem. (English) Zbl 0738.90022
Summary: A linear description for the economic lot-sizing problem consisting of exponentially many linear inequalities was given by I. Barany, T. Van Roy and L. A. Wolsey [Math. Program. Study 22, 32-43 (1984; Zbl 0551.90068)]. Using this formulation we present a dual algorithm for the economic lot-sizing problem, which is of the same complexity as the Wagner and Whitin dynamic programming algorithm. Besides its use in sensitivity analysis the dual algorithm also provides an alternative proof of the fact that the linear description is complete.
MSC:
| 90B05 | Inventory, storage, reservoirs |
| 90C05 | Linear programming |
| 90-08 | Computational methods for problems pertaining to operations research and mathematical programming |
Citations:
Zbl 0551.90068References:
| [1] | Afentakis, P.; Gavish, B.; Karmarkar, U., Computationally efficient optimal solutions to the lot-sizing problem in multistage assembly systems, Management Science, 30, 2, 222-239 (1984) · Zbl 0552.90045 |
| [2] | Afentakis, P.; Gavish, B., Optimal lot-sizing algorithm for complex product structures, Operations Research, 34, 237-249 (1986) · Zbl 0602.90048 |
| [3] | Barany, I.; Van Roy, T. J.; Wolsey, L. A., Uncapacitated lot-sizing: The convex hull of solutions, Mathematical Programming Study, 22, 32-43 (1984) · Zbl 0551.90068 |
| [4] | Crowston, W. B.; Wagner, M. H., Dynamic lot size models for multi-stage assembly systems, Management Science, 20, 1, 14-21 (1973) · Zbl 0304.90039 |
| [5] | Crowston, W. B.; Wagner, M. H.; Williams, J. F., Economic lot size determinazation in multi-stage assembly systems, Management Science, 19, 5, 517-527 (1973) · Zbl 0251.90013 |
| [6] | Erickson, R. E.; Monma, C. L.; Veinott, A. F., Minimum concave cost network flows (1985), Stanford University: Stanford University Stanford, CA |
| [7] | Florian, M.; Klein, M., Deterministics production planning with concave costs and capacity constraints, Management Science, 26, 7, 12-20 (1971) |
| [8] | Florian, M.; Lenstra, J. K.; Rinnoy Kan, A. H.G., Deterministic production planning: Algorithms and complexity, Management Science, 26, 7, 669-679 (1980) · Zbl 0445.90025 |
| [9] | Hoesel, S.van; Wagelmans, A.; Wolsey, L., Economic lot-sizing with start-up costs: The convex hull (1990), Research Report Econometric Institute Erasmus University |
| [10] | Love, S. F., A facilities in series inventory model with nested schedules, Management Science, 18, 5, 327-338 (1972) · Zbl 0237.90015 |
| [11] | Maxwell, W. L.; Muckstadt, J. A., Establishing consistent and realistic reorder intervals in production distribution systems, Operations Research, 33, 6, 1316-1341 (1985) · Zbl 0579.90048 |
| [12] | Pochet, Y., Lot-sizing problems reformulation and cutting plane algorithms, (Ph.D. Louvain-La-Neuve (1987), CORE) |
| [13] | Wagelmans, A.; Hoesel, S.van, Sensitivity analysis for the economic lot-sizing problem (1990), Research Report Econometric Institute Erasmus University |
| [14] | Wagelmans, A.; Hoesel, S.van; Kolen, A., Economic lot-sizing: An \(O(n\) log \(n)\)-algorithm that runs in linear time in the Wagner-Whitin case, (Research Report RM 89037 (1989), Rijksuniversiteit Limburg) · Zbl 0771.90031 |
| [15] | Wagner, H. M.; Whitin, T. M., Dynamic version of the economic lot size model, Management Science, 5, 1, 89-96 (1959) · Zbl 0977.90500 |
| [16] | Wolsey, L. A., Uncapacitated lot-sizing problems with start-up costs, (CORE discussion paper 8801 (1988), Louvain-La-Neuve) · Zbl 0696.90021 |
| [17] | Zangwill, W. I., A deterministic multiproduct, multifacility production and inventory model, Operations Research, 14, 3, 486-508 (1966) · Zbl 0142.17105 |
| [18] | 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, 9, 506-527 (1969) · Zbl 0172.44603 |
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.
