Exact makespan minimization of unrelated parallel machines

Abstract

We study methods for the exact solution of the unrelated parallel machine problem with makespan minimization, generally denoted as $R||C_\text{max}$. 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||C_\text{max}$ 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.

Keywords

• unrelated parallel machine problem
• makespan
• variable fixing
• binary knapsack
• Lagrangian relaxation