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

Sara Velez, Yachao Dong and Christos T. Maravelias

European Journal of Operational Research, 2017, vol. 260, issue 3, 949-963

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.

Keywords: Scheduling; Integer programming; Formulation tightness; Manufacturing scheduling (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221717300097
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:260:y:2017:i:3:p:949-963

DOI: 10.1016/j.ejor.2017.01.004

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().