A Matheuristic to the Unrelated Parallel Machine Scheduling Problem

This paper presents a Fix-and-Optimize approach for the Unrelated Parallel Machine Scheduling Problem (UPMSP). In short, the UPMSP consists of assigning jobs to unrelated parallel machines where different processing times incur for the same job in different machines. Additionally, a setup time is considered between the execution of jobs in the same machine. Fix-and-Optimize is a matheuristic that iteratively selects a subset of variables to be fixed to their current values so that the remaining variables will compose a sub-problem to be optimized by an integer programming solver. In the proposed approach, each sub-problem consists of a subset of jobs that are assigned to a subset of machines in the incumbent solution. In the conducted experiments on benchmark instances, the proposed Fix-and-Optimize algorithm achieved remarkable results. It outperformed two state-of-the-art exact approaches to the UPMSP and achieved competitive results when compared to the literature’s best performing heuristic method for this problem.