An effective hybrid meta-heuristic for a heterogeneous flow shop scheduling problem

In this paper, we study an extension of the non-permutation flow shop scheduling problem, where n jobs have to be scheduled on m machines, and m workers have to be assigned to operate the m machines. The workers are heterogeneous, that is, the processing time of a job processed on a machine depends on the assigned worker. The objective of the problem is to obtain the best worker allocation and the corresponding job schedule in order to minimize the maximum completion time (makespan). Motivated by the computational complexity of the problem, we propose a Variable Neighborhood Search (VNS) heuristic coupled with Iterated Greedy (IG) algorithm to obtain near optimal solutions. The VNS heuristic is responsible for defining the allocation of workers to machines and IG is responsible for obtaining a schedule of jobs on machines. The performance of our meta-heuristic, named VNS-IG, is compared with the state-of-the-art meta-heuristic proposed in the literature for the problem under study. The results show that our heuristic outperforms the existing algorithm by a significant margin.