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

2008-10-01
Denizel, Meltem
ALTEKİN, FATMA TEVHİDE
Süral, Haldun
Stadtler, Hartmut
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.

Suggestions

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...
Rebalancing the assembly lines with total squared workload and total replacement distance objectives
Girit, Utku; Azizoğlu, Meral (Informa UK Limited, 2020-01-01)
Assembly line balancing is an important and well recognised operations research problem. The current line balance may not stay optimal, even feasible, due to the disruptions in one or more workstations. In this study, after the disruption, we aim to rebalance the assembly line by considering the trade-off between workload balancing (fairness measure) and total replacement distance for the tasks assigned to the different workstations (stability measure). We try to generate all non-dominated objective functio...
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.