Tabu search and particle swarm optimization algorithms for two identical parallel machines scheduling problem with a single server

Abstract

This paper proposes two efficient algorithms, which are tabu search and particle swarm optimization, for scheduling two identical parallel machines with a single server. The server has to set up the relevant machine before starting job processing. The objective is to minimize the makespan. This problem is considered unary NP-hard problem. The performance of the two proposed algorithms is evaluated using previously solved instances from the literature. The instances were solved using three different algorithms, which are genetic algorithm (GA), simulated annealing algorithm (SA) and I-L algorithm. We used the results of these three algorithms as a benchmark to compare with the two new introduced algorithms, which are tabu search (TS) and geometric particle swarm optimization (GPSO). The obtained results show that the proposed algorithms have a great performance for large instances. Moreover, the obtained results are very close to a lower bound, and in some instances, an optimal solution is achieved. In addition, TS performs better than SA and GA in term of average makespan for large instances and outperforms all algorithms in term of reaching the lower bound for all instances greater than 200 jobs, while GPSO comes second.

Keywords

• Scheduling
• Identical parallel machines
• Single server
• Tabu search
• PSO