An Application of the Local Branching to the Identical Parallel Machines Scheduling Problem

Abstract

In this paper, we consider the Identical Parallel Machine Scheduling Problem, with sequence-dependent setup time and the aim of minimizing makespan. We present two solution approaches: mathematical formulation of Mixed Integer Linear Programming (MILP) and the exact Local Branching method. The aim of this paper is the application and comparison of performance between the two approaches and the analysis of the convergence of each method. This analysis was based on the variation of setup times (between 10% and 50% of the processing time of the task in a machine, depending on the test performed), number of tasks (20, 30, 40, 50 and 100) and the number of machines available (3 and 5 machines). Both approaches were tested with a computational time of one hour in each test. As a consequence, we compared the optimality GAP for all instances by calculating the Lower Bound of each generated problem. The results obtained for instances with 30 tasks or more indicate that the Local Branching method presented better results when having a more significant number of machines. This gain increases as there is an increase in the number of tasks and machines. For smaller problems and with fewer parallel machines, the MILP approach presents lower GAP values.