The capacitated lot-sizing and scheduling problem with sequence-dependent setup costs and setup times

Diwakar Gupta, Thorkell Magnusson

Research output: Contribution to journalArticlepeer-review

91 Scopus citations

Abstract

We consider the single machine capacitated lot-sizing and scheduling problem (CLSP) with sequence-dependent setup costs and non-zero setup times, with the additional feature that setups may be carried over from one period to the next, and that setups are preserved over idle periods. We provide an exact formulation of this problem as a mixed-integer program. It is well known that the CLSP is NP-hard. Therefore, we have also developed a heuristic for solving large problem instances. This is coupled with a procedure for obtaining a lower bound on the optimal solution. We carry out a computational study to test the accuracy of several different lower bounding linear relaxations and the approximate solution obtained by the heuristic. In our study, the average deviation of the heuristic solution from the corresponding exact solution depends on the size of the problem and ranges from 10 to 16%. The heuristic is more effective when there are many more products than there are planning periods. This is a desirable property from a practical viewpoint since most firms are likely to implement such a procedure on a rolling horizon basis, solving the problem repeatedly for a few periods at a time.

Original languageEnglish (US)
Pages (from-to)727-747
Number of pages21
JournalComputers and Operations Research
Volume32
Issue number4
DOIs
StatePublished - Apr 1 2005

Keywords

  • Heuristic
  • Lot-sizing
  • Relaxation
  • Scheduling
  • Sequence-dependent
  • Sequencing

Fingerprint Dive into the research topics of 'The capacitated lot-sizing and scheduling problem with sequence-dependent setup costs and setup times'. Together they form a unique fingerprint.

Cite this