Exact makespan minimization of unrelated parallel machines

E. Åblad, A-B. Strömberg, D. Spensieri. Open Journal of Mathematical Optimization, Vol. 2 (2021), article no. 2, 15 p. Online 11 May 2021.


We study methods for the exact solution of the unrelated parallel machine problem with makespan minimization, generally denoted as R||Cmax. Our original application arises from the automotive assembly process where tasks needs to be distributed among several robots. This involves the solutions of several R||Cmax instances, which proved hard for a MILP solver since the makespan objective induces weak LP relaxation bounds. To improve these bounds and to enable the solution of larger instances, we propose a branch–and–bound method based on a Lagrangian relaxation of the assignment constraints. For this relaxation we derive a criterion for variable fixing and prove the zero duality gap property for the case of two parallel machines. Our computational studies indicate that the proposed algorithm is competitive with state-of-the-art methods on different types of instances. Moreover, the impact of each proposed feature is analysed.

Photo credits: Nic McPhee