A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times

Abstract

In this work a genetic algorithm is presented for the unrelated parallel machine scheduling problem in which machine and job sequence dependent setup times are considered. The proposed genetic algorithm includes a fast local search and a local search enhanced crossover operator. Two versions of the algorithm are obtained after extensive calibrations using the Design of Experiments (DOE) approach. We review, evaluate and compare the proposed algorithm against the best methods known from the literature. We also develop a benchmark of small and large instances to carry out the computational experiments. After an exhaustive computational and statistical analysis we can conclude that the proposed method shows an excellent performance overcoming the rest of the evaluated methods in a comprehensive benchmark set of instances.

Introduction

In the unrelated parallel machine scheduling problem, there is a set N = {1, … , n} of n jobs that have to be processed on exactly one machine out of a set M = {1, … , m} of m parallel machines. Therefore, each job is made up of one single task that requires a given processing time. Machines are considered unrelated when the processing times of the jobs depend on the machine to which they are assigned to. This is the most realistic case which is also a generalisation of the uniform and identical machines cases. Moreover, the consideration of setup times between jobs is very common in the industry. The setup times considered in this paper are both sequence and machine dependent, that is, setup time on machine i between jobs j and k is different than setup time on the same machine between jobs k and j. In addition, setup time between jobs j and k on machine i is different than setup time between jobs j and k on machine i′.

The most studied optimisation criterion is the minimisation of the maximum completion time of the schedule, a criteria that is known as makespan or C_max. Summing up, in this paper we deal with the unrelated parallel machine scheduling problem with sequence dependent setup times denoted as R/S_ijk/C_max (Pinedo, 2008). We propose and evaluate a genetic algorithm that includes a fast local search and a local search enhanced crossover operator among other innovative features that, as we will see, result in a state-of-the-art performance for this problem.

The remainder of this paper is organised as follows: in Section 2 we review the literature on this problem. In Section 3 a Mixed Integer Programing (MIP) model formulation is presented. In Section 4 we describe in detail the proposed genetic algorithm and preliminary computational results. In Section 5, a Design of Experiments approach is applied in order to calibrate the genetic algorithm. Results of a comprehensive computational and statistical evaluation are reported in Section 6. Finally, conclusions are given in Section 7.