On alternative mixed integer programming formulations and LP-based heuristics for lot-sizing with setup times

Date

2006-04-01

Author

Denizel, M
Süral, Haldun

Metadata

Show full item record

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

Item Usage Stats

134
views

0
downloads

We address the multi-item, capacitated lot-sizing problem (CLSP) encountered in environments where demand is dynamic and to be met on time. Items compete for a limited capacity resource, which requires a setup for each lot of items to be produced causing unproductive time but no direct costs. The problem belongs to a class of problems that are difficult to solve. Even the feasibility problem becomes combinatorial when setup times are considered. This difficulty in reaching optimality and the practical relevance of CLSP make it important to design and analyse heuristics to find good solutions that can be implemented in practice. We consider certain mixed integer programming formulations of the problem and develop heuristics including a curtailed branch and bound, for rounding the setup variables in the LP solution of the tighter formulations. We report our computational results for a class of instances taken from literature.

Subject Keywords

Marketing, Management Science and Operations Research, Strategy and Management, Management Information Systems

URI

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

Journal

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY

DOI

https://doi.org/10.1057/palgrave.jors.2601996

Collections

Department of Industrial Engineering, Article

Suggestions

OpenMETU
Core

An interactive approach for multiobjective decision making Koksalan, M; Karasakal, Esra (Informa UK Limited, 2006-05-01) We develop an interactive approach for multiobjective decision-making problems, where the solution space is defined by a set of constraints. We first reduce the solution space by eliminating some undesirable regions. We generate solutions (partition ideals) that dominate portions of the efficient frontier and the decision maker (DM) compares these with feasible solutions. Whenever the decision maker prefers a feasible solution, we eliminate the region dominated by the partition ideal. We then employ an inte...
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...
Scheduling to minimize maximum earliness and number of tardy jobs where machine idle time is allowed Azizoğlu, Meral; Koksalan, SK (Informa UK Limited, 2003-06-01) We address the bicriteria problem of minimizing the number of tardy jobs and maximum earliness on a single machine where machine idle time is allowed. We show that the problem of minimizing the number of tardy jobs while maximum earliness is kept at its minimum value of zero is polynomially solvable. We present polynomial time algorithms for the maximum earliness problem subject to no tardy jobs and the maximum earliness problem for a given set of tardy jobs. Finally, we discuss the use of the latter algori...
Enhanced adjacent extreme-point search and tabu search for the minimum concave-cost uncapacitated transshipment problem Bazlamaçcı, Cüneyt Fehmi (Informa UK Limited, 1996-09-01) Practicable methods for optimising concave-cast, uncapacitated transshipment networks are non exact. In this paper, one such effective method, that of adjacent extreme point search, is further developed to enhance its overall computational efficiency. The enhanced search algorithm is then imbedded in a tabu search scheme which proved capable of finding better solutions, by a wide margin in some instances. Another tabu search scheme, somewhat inferior in terms of solution quality but computationally more eff...
Rescheduling unrelated parallel machines with total flow time and total disruption cost criteria Ozlen, M.; Azizoğlu, Meral (Informa UK Limited, 2011-01-01) In this paper, we consider a rescheduling problem where a set of jobs has already been assigned to unrelated parallel machines. When a disruption occurs on one of the machines, the affected jobs are rescheduled, considering the efficiency and the schedule deviation measures. The efficiency measure is the total flow time, and the schedule deviation measure is the total disruption cost caused by the differences between the initial and current schedules. We provide polynomial-time solution methods to the follo...

Citation Formats

M. Denizel and H. Süral, “On alternative mixed integer programming formulations and LP-based heuristics for lot-sizing with setup times,” JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, pp. 389–399, 2006, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/38587.