A LAGRANGEAN RELAXATION APPROACH FOR MULTI PRODUCT, MULTI ECHELON SYSTEMS WITH CAPACITATED DYNAMIC LOTSIZING

Year 1995, Volume: 13 , 117 - 133, 31.12.1995

Ş. Armağan Tarım João Paulo De-barros

Abstract

This paper focuses on multi-echelon inventory systems
having an arborescent structure. In the structure each intermediate facility
has exactly one predecessor and possibly several successors. All inventory costs
are assumed linear- with ordering cost that is independent of the order
quantity for each stocking point. The model takes account of dynamic cost
structure and dynamic demand pattern as well as capacity limitations. The paper
exploits a mixed bivalent programming model to determine what inventory levels,
if anv, should be maintained at the various stocking paints in order to
minimise total inventory cost of the entire system. A computationally efficient
Lagrangean relaxation-based procedure is developed to decompose the model into
submodels by each stocking point and product.

Keywords

Inventory, Integer Programming, Modelling, Production

References

• McLaren, B. J. , A Study of Multiple Level •Lot Sizing Techniques for Material Requirements Planning Systems, Unpublished Ph.D. Dissertation, Purdue University, 1976.
• Afentakis, P. , B.Gavish, and U.Karmarkar, 'FComputationaliy Efficient Optimal Solutions to the Lot-Sizing Problem in Multistage Assembly Systems," Management Science, Vol. 30, 1984, pp.222-239,
• Crowston, W.B., and MH. Wagner, "Dynamic Lot Size Models for Multi-Stage Assembly Systems," Management Science, vol. 20, 1973, pp. 14-21.
• Graves, S.C., "Multi-Stage Lot Sizing: An Iterative Procedure," in Schwarz, L-B- (ed.), Multi-Level Productionflnventory Control Systems: Theory and Practice, Studies in the Management Science, Vol. 16, North-Holland: Amsterdam, 1981.
• Tanm, S.A., "A Survey of Multi-Echelon Inventory Models, 't , Hacettepe Üniversitesi, Iktisadi ve Idari Bilimler Fakültesi Dergisi, vol. 11, 1993, pp.115-150.
• Clark, A. J. , and S.Herbert, "Optimal Policies for a MultiEchelon Invent0EY Problem," Management Science, Vol. 6, 1960, pp,475-490.
• Blackburn, J.D., and R.A.Millen, "Improved Heuristic for Multi Stage Requirements Planning Systems," Management Sciencez Vol.28,
• Crowston, W.B., and MH. Wagner, "Dynamic Lot Size Models For Multistage Assembly Systems," Management Science, Vol.20, -1973, pp. 14-21.
• Crowston, w.B., M.H. Wagner, and J.F. "Economic Lot Size Determination in Multi-Stage Assembly Systems, Management Science, Vol. 19, 1973, pp. 517-527.
• Schwarz, L. G. , and L.Schrage, "Optimal and System Myopic Policies for Multi-Echelon Production/lnventory Assembly Systems," Management Science, Vol.2i, 1975.
• Afentakis, P , and B.Gavish, Bill of Material Processor Algorithms -Time and StOrage Complexity Analysis, Working Paper, The Graduate School of Management, University of Rochester, Rochester, New York, 1983.
• Held, M. , and R.M.Karp, "The Traveliing Salesman Problem and Minimum Spanning Trees," Operations Research, Vol. 18, 1970, pp.1138-1162.
• Fisher, M.L., "Optimal Solution of Scheduling Problems Using Lagrange Multipliers: Part l," Operations Research, Vol.21, 1973, pp. 1114-1127.
• Shapiro, J.F., "Generalized Lagrange Multipliers in Integer Programming," Operations Research, Vol. 19, 1971, pp.68-76.
• Fisher, ML. , and J.F-Shapiro, "Constructive Duality in Integer Programming," SIAM Journal of Applied Mathematics, Vol.27, 1974, pp 31-52.
• [Geoffrion, A.M., "Lagrangean Relaxation for Integer Programming," Mathematical Programming Study, V01.2 1974, pp. 82-114.
• Fisher, ML. , "The Lagrangian Relaxation Methods for Solving Integer Programming Problems," Management Science, Vol.27, 1981, pp. 1-18.
• Fisher, M.L., I'An Applications Oriented Guide to Lagrangian Relaxation," Interfaces, Vol. 15, 1985, pp. 10-21.
• [19] Shapiro, J.F., "A Survey of Lagrangean Techniques Discrete Optimization, n Annals of Discrete Mathematics, Vol. 5, 1979, pp. 113-118. Zangwill, W.I., "A Backlogging Model and a Multi-Echelon Model of Dynamic Economic Lot Size Production System -A Network Approach," Management Science, Vol. 15, 1969, pp.506-527.
• Camerini, P.M., L.Fratta, and F.Maffioli, "On Improving Relaxation Methods by Modified Gradient Techniques, " Mathematical Programming Study, Vol. 3, 1975, pp.26-34.
• Held, M, P,W01fe, and H.D.Crowder, "Validation of Subgradient Optimization," Mathematical Programming, Vol. 6, 1974, pp. 62-88b