Solving a time-indexed formulation for an unrelated parallel machine scheduling problem by preprocessing and cutting planes

Lotte Berghman (Corresponding author), Frits C.R. Spieksma, Vincent T'kindt

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

We consider a time-indexed formulation for the unrelated parallel machine scheduling problem. We show that all polyhedral knowledge known from the single machine problem (in particular, valid inequalities) is applicable to this formulation. We present new facet-inducing valid inequalities and a preprocessing technique involving fixing variables based on reduced costs. We combine both techniques in a basic cutting-plane algorithm and test the performance of the resulting algorithm by running it on randomly generated instances.

Original languageEnglish
Pages (from-to)S1747-S1765
JournalRAIRO - Operations Research
Volume55
DOIs
Publication statusPublished - 2021

Keywords

  • Cutting plane algorithm
  • Time-indexed formulation
  • Unrelated machine scheduling
  • Valid inequalities
  • Variable fixing

Fingerprint Dive into the research topics of 'Solving a time-indexed formulation for an unrelated parallel machine scheduling problem by preprocessing and cutting planes'. Together they form a unique fingerprint.

Cite this