Heuristics for the two-machine scheduling problem with a single server

In this paper, the NP‐hard two‐machine scheduling problem with a single server is addressed. The problem consists of a given set of jobs to be scheduled on two identical parallel machines, where each job must be processed on one of the machines, and prior to processing, the job is set up on its machine using one server; the latter is shared between the two machines. An ant colony optimization (ACO) algorithm is introduced for the problem and its performance was assessed by comparing with an exact solution (branch and bound [B&B]), a genetic algorithm (GA), and simulated annealing (SA). The computational results reflected the superiority of ‘ACO’ in large problems, with a performance similar to SA and GA in smaller problems, while solving the tested problems within a reasonable computational time.