GARP: A New Genetic Algorithm for the Unrelated Parallel Machine Scheduling Problem with Setup Times

This work addresses the Unrelated Parallel Machine Scheduling Problem where setup times are sequence-dependent and machine-dependent, the UPMSPST. The maximum completion time of the schedule, known as makespan, is considered as the objective to minimize. The UPMSPST is often found in industries and belongs to the NP-hard class. Aiming to its resolution, is proposed an algorithm named GARP. This algorithm is based on Genetic Algorithm (GA) combined with Variable Neighborhood Descent (VND) and Path Relinking (PR). In addition, is used a local search method based on a Mixed-Integer Programming (MIP) model to solve the Asymmetric Traveling Salesman Problem (ATSP). The developed algorithm explores the solution space using multiple insertions and swaps movements. GARP was tested using benchmark instances and the computational results showed that it is able to produce better solutions than the algorithms found in literature, with lower variability and setting new upper bounds for the majority of the test problems.