Optimization: Journal of Research in Management

Open Access Open Access  Restricted Access Subscription Access
Open Access Open Access Open Access  Restricted Access Restricted Access Subscription Access

Lagrangian Relaxation for the Capacitated Dynamic Lot Sizing Problem


Affiliations
1 University of Houston-Downtown, College of Business, MMBA, Houston, Texas, United States
2 Department of Industrial and Management Engineering, IIT Kanpur, India
     

   Subscribe/Renew Journal


In this paper, we consider the capacitated dynamic lot-sizing problem and assume that all conditions of Wagner-Whitin (1958) model apply except the capacity restriction. We give three different formulation of the problem. We relax the capacity constraint and initiate the Lagrangian procedure. At each Lagrangian iteration, we solved the uncapacitated lot-sizing problem by the Wagner-Whitin method that runs in O(n2) time. We compare the quality of bounds so obtained. In particular, we find that the Lagrangian procedure that modified the setup cost turned out to be inferior to the Lagrangian procedure that modified only the holding cost.
User
Subscription Login to verify subscription
Notifications
Font Size

  • • Aggarwal, A. & Park, J.K. (1993). Improved algorithms for economic lot-size problem. Operations Research, 41(3), 549-571.

  • • Bitran, G.R. & Yanasse, H.H. (1982). Computational complexity of the capacitated lot size problem. Management Science, 28(10), 1174-86.

  • • Chen, W.H. & Thizy, J.M. (1990). Analysis of relaxations for the Multi-item Capacitated Lot-Sizing Problem. Annals of Operations Research, 26, 29-72.

  • • Diaby, M., Bahl, H.C., Karwan, M.H. & Zionts, S. (1992). A Lagrangian relaxation approach for very large scale capacitated lot-sizing. Management Science, 38(9), 1329-40.

  • • Diaby, M., Bahl, H.C., Karwan, M.H. & Zionts, S. (1992). Capacitated lot-sizing and scheduling by Lagrangian relaxation. European Journal of Operational Research, 59(3), 444-58.

  • • Federgruen, A. & Tzur, M.A. (1991). A simple forward algorithm to solve general dynamic lot sizing models with n periods in O(n log n) or O(n) time. Management Science, 37(8), 909-25.

  • • Fisher, Marshall L. (1985). An applications oriented guide to Lagrangian relaxation. Interfaces,15 (2), 10-21.

  • • Fisher, Marshall L. (2004). The Lagrangian Relaxation Method for Solving Integer Programming Problems. Management Science, 50(12), 1861-1871.

  • • Florian, M., Lenstra, J.K. & Rinnooy Kan, A.H.G. (1980). Deterministic production planning algorithms and complexity. Management Science, 26(7), 669-79.

  • • Held, M., Wolfe, P., & Crowder, H.P. (1974). Validation of subgradient optimization. Mathematical Programming, 6(1), 62-88.

  • • Hindi, K.S. (1995). Computationally efficient solution of multi-item capacitated lot sizing problems. Computers and Industrial Engineering, 28(4), 709-19.

  • • Karmarkar, U.S., Kekre, S. & Kekre, S. (1987). The dynamic lot-sizing problem with startup and reservation costs. Operations Research, 35(3), 389-398.

  • • Lozano, S., Larraneta, J., & Onieva, L. (1991). Primal-dual approach to the single level capacitated lot-sizing problem. European Journal of Operational Research, 51(3), 354-66.

  • • Silver, E.A. & Meal, H.C. (1973). A heuristic for selecting Lot Size requirements for the case of deterministic time-varying demand rate and discrete opportunities for replenishment. Production and Inventory Management, 14(2).

  • • Salomon, M., Kroon, L.G., Kuik, R. & Van Wassenhove, L.N. (1991). Some extensions of the discrete lot-sizing and scheduling problem. Management Science, 37(7), 801-812.

  • • Thizy, J.M. & Van Wassenhove, L.N. (1985). Lagrangian relaxation for the multi-item capacitated lot-sizing problem: a heuristic implementation. IIE Transactions, 17(4), 308-13.

  • • Vanderbeck, F. (1998). Lot-sizing with start-up times. Management Science, 44(10), 1409-1425.

  • • Wagelmans, A. P. M., Van Hoesel, C. P. M. and Kolen, A.(1992). Economic lot sizing: An O(n log n) algorithm that runs in linear time in the Wagner-Whitin case. Operations Research, 40, S145-S156.

  • • Wagner, H.M. & Whitin, T.M. (1958). Dynamic Version of Economic Lot Size Model. Management Science, 5, 89-96.

  • • Wagner, H.M. & Whitin, T.M. (2004). Dynamic Version of the Economic Lot Size Model. Management Science, 50(12), 1770-1774.

  • • Webster, S., 1999. Remarks on: Some extensions of the discrete lot-sizing and scheduling problem. Management Science, 45(5), 768-769.

  • • Wolsey, L.A. (1989). Uncapacitated lot-sizing problems with start-up costs. Operations Research, 37(5), 741-747.

  • • Zoller, K and Robrade, A. (1988). Dynamic Lot-sizing techniques; survey and comparison. Journal of Operations Management, 7(4).


Abstract Views: 303

PDF Views: 0




  • Lagrangian Relaxation for the Capacitated Dynamic Lot Sizing Problem

Abstract Views: 303  |  PDF Views: 0

Authors

Omprakash K. Gupta
University of Houston-Downtown, College of Business, MMBA, Houston, Texas, United States
Syed Ali
Department of Industrial and Management Engineering, IIT Kanpur, India
R. R. K. Sharma
Department of Industrial and Management Engineering, IIT Kanpur, India

Abstract


In this paper, we consider the capacitated dynamic lot-sizing problem and assume that all conditions of Wagner-Whitin (1958) model apply except the capacity restriction. We give three different formulation of the problem. We relax the capacity constraint and initiate the Lagrangian procedure. At each Lagrangian iteration, we solved the uncapacitated lot-sizing problem by the Wagner-Whitin method that runs in O(n2) time. We compare the quality of bounds so obtained. In particular, we find that the Lagrangian procedure that modified the setup cost turned out to be inferior to the Lagrangian procedure that modified only the holding cost.

References