Changeover formulations for discrete-time mixed-integer programming scheduling models

Sara Velez, Yachao Dong, Christos T. Maravelias

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

Abstract

Changeover times can have a significant impact on the scheduling of manufacturing operations. Unfortunately, accounting for changeovers in mixed-integer programming (MIP) scheduling formulations makes the resulting models computationally more expensive. We propose five new formulations for sequence-dependent changeovers, applicable to a wide range of scheduling problems. We generate constraints for different sets of time points and sets of tasks. We also propose valid inequalities for makespan minimization. Furthermore, we prove results regarding the relative tightness of each formulation. Finally, we perform a computational study. Interestingly, we find that tighter formulations do not always lead to faster solution times, and we show that some of the new formulations perform better than the previously proposed ones.

Original languageEnglish (US)
Pages (from-to)949-963
Number of pages15
JournalEuropean Journal of Operational Research
Volume260
Issue number3
DOIs
StatePublished - Aug 1 2017
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Keywords

  • Formulation tightness
  • Integer programming
  • Manufacturing scheduling
  • Scheduling

Fingerprint Dive into the research topics of 'Changeover formulations for discrete-time mixed-integer programming scheduling models'. Together they form a unique fingerprint.

Cite this