Parallel variable neighborhood search algorithm to minimize the makespan on hybrid flow shop problems

Abstract

Flow-shop scheduling problems represents a class of scheduling problems with a focus on processing a given set of jobs, where all jobs have to be processed in an identical order on a given number of machines. Hybrid flow-shop (HFS) problems overcome one of the limitations of the classical flow-shop model by allowing parallel processors at each stage of task processing. HFS problems are common manufacturing environments in many industries, such as the glass, building materials, steel, paper and textile industries. In this paper, we propose parallel variable neighborhood search algorithm (PVNS) for solving the HFS scheduling problem with minimum makespan objective. Initial solution is obtained by reduced version of the variable neighborhood search, called reduced variable neighborhood search algorithm (RVNS). Analysis of the most CPU consuming computational parts of the algorithm are done and obtained parts are parallelized. The proposed algorithm is tested on the well-known benchmark problems for HFS problem. Experimental results show that the proposed algorithm is a viable and effective approach for the hybrid flow shop scheduling problem.