Equivalence of the LP relaxations of two strong formulations for the capacitated lot-sizing problem with setup times

Date

2008-10-01

Author

Denizel, Meltem
ALTEKİN, FATMA TEVHİDE
Süral, Haldun
Stadtler, Hartmut

Metadata

Show full item record

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

Item Usage Stats

41
views

0
downloads

The multi-item Capacitated Lot-Sizing Problem (CLSP) has been widely studied in the literature due to its relevance to practice, such as its application in constructing a master production schedule. The problem becomes more realistic with the incorporation of setup times since they may use up significant amounts of the available resource capacity. In this paper, we present a proof to show the linear equivalence of the Shortest Path (SP) formulation and the Transportation Problem (TP) formulation for CLSP with setup costs and times. Our proof is based on a linear transformation from TP to SP and vice versa. In our proof, we explicitly consider the case when there is no demand for an item in a period, a case that is frequently observed in the real world and in test problems in the literature. The equivalence result in this paper has an impact on the choice of model formulation and the development of solution procedures.

Subject Keywords

Management Science and Operations Research

URI

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

Journal

OR SPECTRUM

DOI

https://doi.org/10.1007/s00291-007-0094-3

Collections

Department of Industrial Engineering, Article

Suggestions

OpenMETU
Core

A Lagrangean relaxation approach for the mixed-model flow line sequencing problem Eliiyi, Deniz Tuersel; Oezlen, Melih (Elsevier BV, 2008-03-01) In this study, a mixed-model flow line sequencing problem is considered. A mixed-model flow line is a special case of production line where products are transported on a conveyor belt, and different models of the same product are intermixed on the same line. We have focused on product-fixed, rate-synchronous lines with variable launching. Our objective function is minimizing makespan. A heuristic algorithm based on Lagrangean relaxation is developed for the problem, and tested in terms of solution quality a...
Mixed integer programming-based solution procedure for single-facility location with maximin of rectilinear distance Nadirler, D.; Karasakal, Esra (Informa UK Limited, 2008-04-01) In this paper, we study the 1-maximin problem with rectilinear distance. We locate a single undesirable facility in a continuous planar region while considering the interaction between the facility and existing demand points. The distance between facility and demand points is measured in the rectilinear metric. The objective is to maximize the distance of the facility from the closest demand point. The 1-maximin problem has been formulated as an MIP model in the literature. We suggest new bounding schemes t...
On the classical Maki-Thompson rumour model in continuous time Belen, Selma; Kropat, Erik; Weber, Gerhard Wilhelm (Springer Science and Business Media LLC, 2011-03-01) In this paper, the Maki-Thompson model is slightly refined in continuous time, and a new general solution is obtained for each dynamics of spreading of a rumour. It is derived an equation for the size of a stochastic rumour process in terms of transitions. We give new lower and upper bounds for the proportion of total ignorants who never learned a rumour and the proportion of total stiflers who either forget the rumour or cease to spread the rumour when the rumour process stops, under general initial condit...
Investigation of process-affected zone in ultrasonic embossing of microchannels on thermoplastic substrates Sucularli, Ferah; Arıkan, Mehmet Ali Sahir; Yıldırım, Ender (Elsevier BV, 2020-02-01) In this paper, the process-affected zone in ultrasonically embossed thermoplastic substrates is investigated both numerically and experimentally. Commercialization of microfluidic devices challenges the need for high-speed manufacturing of plastic chips. Ultrasonic embossing is considered as an alternative method since the cycle time can be as low as a few seconds per chip while keeping the cost relatively low. To examine the ultrasonic embossing process, experiments were carried out to replicate 200 mu m w...
Formulation and solution of an optimal control problem for industrial project control Schmidt, Klaus Verner (Springer Science and Business Media LLC, 2019-09-15) n this paper, we consider the monitoring and control of industrial projects that are performed by executing different activities within a given time duration. Hereby, it is desired to apply project control to each activity in order to avoid unexpected deviations in the project cost, respecting that the amount and cost of project control needs to be limited. We model the general setting of industrial project control as an optimal control problem with the goal of maximizing the cost reduction (savings) when a...

Citation Formats

M. Denizel, F. T. ALTEKİN, H. Süral, and H. Stadtler, “Equivalence of the LP relaxations of two strong formulations for the capacitated lot-sizing problem with setup times,” OR SPECTRUM, pp. 773–785, 2008, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/47352.