A parallel machine scheduling problem with two-agent and tool change activities: an efficient hybrid metaheuristic algorithm

Scheduling with multiple agents has been widely studied. However, a little work has been done on multi-agent scheduling with availability constraints. This paper addresses a two-agent parallel machine scheduling problem with tool change activities. The aim is to minimise the total completion time of all jobs while keeping the maximum makespan of agent two's jobs below a fixed level. A mathematical model is presented to solve the problem optimally in small-sized instances. Then, an imperialist competitive algorithm (ICA) is developed to solve large-sized instances of the problem. For further enhancement, the proposed ICA is hybridised with a simple but efficient local search algorithm. A set of experimental instances are carried out to evaluate the algorithm. The proposed algorithm is carefully evaluated for its performance against an available algorithm. The results of computational experiments show the desirable performance of the proposed algorithm.