Lagrangean relaxation based heuristics for lot sizing with setup times

Date

2009-04-01

Author

Süral, Haldun
Van Wassenhove, Luk N.

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

110
views

0
downloads

We consider a lot sizing problem with setup times where the objective is to minimize the total inventory carrying cost only. The demand is dynamic over time and there is a single resource of limited capacity. We show that the approaches implemented in the literature for more general versions of the problem do not perform well in this case. We examine the Lagrangean relaxation (LR) of demand constraints in a strong reformulation of the problem. We then design it primal heuristic to generate upper bounds and combine it with the LR problem within a subgradient optimization procedure. We also develop it simple branch and bound heuristic to solve the problem. Computational results oil test problems taken from the literature show that our relaxation procedure produces consistently better solutions than the previously developed heuristics in the literature.

Subject Keywords

Management Science and Operations Research, Modelling and Simulation, Information Systems and Management

URI

https://hdl.handle.net/11511/38679

Journal

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH

DOI

https://doi.org/10.1016/j.ejor.2007.11.052

Collections

Department of Industrial Engineering, Article

Suggestions

OpenMETU
Core

A deterministic inventory/production model with general inventory cost rate function and piecewise linear concave production costs Bayındır, Zeynep Pelin; Frenk, J. B. G. (Elsevier BV, 2007-05-16) We present a thorough analysis of the economic production quantity model with shortages under a general inventory cost rate function and piecewise linear concave production costs. Consequently, an effective solution procedure, particularly useful for an approximation scheme, is proposed. A computational study is appended to illustrate the performance of the proposed solution procedure.
Heuristics for multi-item two-echelon spare parts inventory control subject to aggregate and individual service measures Topan, Engin; Bayındır, Zeynep Pelin; Tan, Tarkan (Elsevier BV, 2017-01-01) We consider a multi-item two-echelon spare parts inventory system in which the central warehouse operates under a (Q, R) policy and local warehouses implement (S-1,S) policy. The objective is to find the policy parameters minimizing expected system-wide inventory holding and fixed ordering subject to aggregate and individual response time constraints. Using an exact evaluation we provide a very efficient and effective heuristic, and also a tight lower bound for real-world, large-scale two-echelon spare part...
An efficient algorithm for the capacitated single item dynamic lot size problem Kırca, Ö. (Elsevier BV, 1990-3) A dynamic programming based algorithm is developed for the single item lot size problem with concave costs and arbitrary capacities. By making use of the extreme point properties of the problem, first the set of all feasible cumulative production levels that may occur in an optimal solution is generated. In the second stage, a dynamic programming procedure is carried out over this set. The worst case computational effort is equal to that of the standard dynamic programming approach but extensive computation...
A NEW HEURISTIC APPROACH FOR THE MULTIITEM DYNAMIC LOT-SIZING PROBLEM KIRCA, O; KOKTEN, M (Elsevier BV, 1994-06-09) In this paper a framework for a new heuristic approach for solving the single level multi-item capacitated dynamic lot sizing problem is presented. The approach uses an iterative item-by-item strategy for generating solutions to the problem. In each iteration a set of items are scheduled over the planning horizon and the procedure terminates when all items are scheduled. An algorithm that implements this approach is developed in which in each iteration a single item is selected and scheduled over the planni...
Multiobjective traveling salesperson problem on Halin graphs Ozpeynirci, Ozgur; Köksalan, Mustafa Murat (Elsevier BV, 2009-07-01) In this paper, we study traveling salesperson (TSP) and bottleneck traveling salesperson (BTSP) problems on special graphs called Halin graphs. Although both problems are NP-Hard on general graphs, they are polynomially solvable on Halin graphs. We address the multiobjective versions of these problems. We show computational complexities of finding a single nondominated point as well as finding all nondominated points for different objective function combinations. We develop algorithms for the polynomially s...

Citation Formats

H. Süral and L. N. Van Wassenhove, “Lagrangean relaxation based heuristics for lot sizing with setup times,” EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, pp. 51–63, 2009, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/38679.