Simulated annealing and genetic algorithms for the two-machine scheduling problem with a single server

Abstract

This paper considers the problem of scheduling a set of jobs on two parallel machines to minimise the makespan. Each job requires a set-up which must be done by a single server. The objective is to minimise the makespan. For this strongly NP-hard problem, a simulated annealing and a genetic algorithm are presented. The performance of these algorithms is evaluated for instances with up to 1000 jobs. The results are compared with existing algorithms from the literature. It is observed that the algorithms presented in this paper both show an excellent behaviour and that the objective function values obtained are very close to a lower bound. The superiority over existing algorithms is obtained by using a composite neighbourhood (mutation), generating several neighbours from sub-neighbourhoods with different probabilities and taking the best solution as generated neighbour.

Keywords:

• scheduling
• parallel machines
• single server
• simulated annealing
• genetic algorithm