Exact Approaches to the Problem of Robust Scheduling on Parallel Machines

In the Parallel Machine Scheduling Problem with makespan minimization, there is a set of tasks with processing times and a set of identical parallel machines. Each machine can process a maximum of one task at a time, and preemption is not allowed. The goal is to schedule all tasks while minimizing the maximum completion time. In practical applications, processing times are often uncertain. This paper addresses a robust variant of the problem that considers such uncertainties. We adopt the budget uncertainty set, limiting the number of tasks that can deviate from their nominal processing times on each machine. We propose two exact approaches to solve this Robust Parallel Machine Scheduling Problem: an arc flow formulation and a binary search procedure. To evaluate the performance of the proposed methods, we tested them in literature instances and compared the results with previous studies, highlighting the most effective approaches.