Mixed integer programming formulations for single machine scheduling problems

Ahmet B. Keha, Ketan Khowala, John Fowler

Research output: Contribution to journalArticlepeer-review

106 Scopus citations


In this paper, the computational performance of four different mixed integer programming (MIP) formulations for various single machine scheduling problems is studied. Based on the computational results, we discuss which MIP formulation might work best for these problems. The results also reveal that for certain problems a less frequently used MIP formulation is computationally more efficient in practice than commonly used MIP formulations. We further present two sets of inequalities that can be used to improve the formulation with assignment and positional date variables.

Original languageEnglish (US)
Pages (from-to)357-367
Number of pages11
JournalComputers and Industrial Engineering
Issue number1
StatePublished - Feb 2009


  • Mixed integer programming
  • Single machine scheduling
  • Valid inequalities

ASJC Scopus subject areas

  • Computer Science(all)
  • Engineering(all)


Dive into the research topics of 'Mixed integer programming formulations for single machine scheduling problems'. Together they form a unique fingerprint.

Cite this