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

¹ TBS Business School, 20 BD Lascrosses BP 7010, 31068 Toulouse Cedex 7, France
² Department of Mathematics and Computer Science, TU Eindhoven, 5600 MB Eindhoven, The Netherlands
³ Université de Tours, Laboratoire d’Informatique Fondamentale et Appliquée (EA 6300), ERL CNRS 7002 ROOT, 64 Avenue Jean Portalis, 37200 Tours, France

^* Corresponding author: l.berghman@tbs-education.fr

Received: 14 June 2019
Accepted: 18 March 2020

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.