TY - JOUR
T1 - Single machine multi-product capacitated lot sizing with sequence-dependent setups
AU - Almada-Lobo, Bernardo
AU - Klabjan, Diego
AU - Carravilla, Maria Antónia
AU - Oliveira, José F.
N1 - Funding Information:
The authors are grateful to Professor Stephen C. Graves from the Sloan School of Management for his helpful comments. The first author is also grateful to the Portuguese Foundation for Science and Technology for awarding him a PhD grant (SFRH/BD/23987/2005).
PY - 2007/10
Y1 - 2007/10
N2 - In production planning in the glass container industry, machine-dependent setup times and costs are incurred for switch overs from one product to another. The resulting multi-item capacitated lot-sizing problem has sequence-dependent setup times and costs. We present two novel linear mixed-integer programming formulations for this problem, incorporating all the necessary features of setup carryovers. The compact formulation has polynomially many constraints, whereas the stronger formulation uses an exponential number of constraints that can be separated in polynomial time. We also present a five-step heuristic that is effective both in finding a feasible solution (even for tightly capacitated instances) and in producing good solutions to these problems. We report computational experiments.
AB - In production planning in the glass container industry, machine-dependent setup times and costs are incurred for switch overs from one product to another. The resulting multi-item capacitated lot-sizing problem has sequence-dependent setup times and costs. We present two novel linear mixed-integer programming formulations for this problem, incorporating all the necessary features of setup carryovers. The compact formulation has polynomially many constraints, whereas the stronger formulation uses an exponential number of constraints that can be separated in polynomial time. We also present a five-step heuristic that is effective both in finding a feasible solution (even for tightly capacitated instances) and in producing good solutions to these problems. We report computational experiments.
KW - Capacitated lot sizing and scheduling
KW - Heuristics
KW - Integer programming
KW - Sequence-dependent setup
UR - http://www.scopus.com/inward/record.url?scp=34548460398&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=34548460398&partnerID=8YFLogxK
U2 - 10.1080/00207540601094465
DO - 10.1080/00207540601094465
M3 - Article
AN - SCOPUS:34548460398
SN - 0020-7543
VL - 45
SP - 4873
EP - 4894
JO - International Journal of Production Research
JF - International Journal of Production Research
IS - 20
ER -