Single machine multi-product capacitated lot sizing with sequence-dependent setups

Bernardo Almada-Lobo*, Diego Klabjan, Maria Antónia Carravilla, José F. Oliveira

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

87 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)4873-4894
Number of pages22
JournalInternational Journal of Production Research
Issue number20
StatePublished - Oct 2007


  • Capacitated lot sizing and scheduling
  • Heuristics
  • Integer programming
  • Sequence-dependent setup

ASJC Scopus subject areas

  • Strategy and Management
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering


Dive into the research topics of 'Single machine multi-product capacitated lot sizing with sequence-dependent setups'. Together they form a unique fingerprint.

Cite this