Solving the hybrid flow shop scheduling problem with limited human resource constraint

Abstract In this paper, an m-stage hybrid flow shop scheduling problem with limited workforce in charge of performing setup operations is addressed. Indeed, such workforce represents a critical resource since the number of workers assigned to each production stage is lower than the number of machines in the same stage. A novel discrete backtracking search algorithm powered by a tabu search operating through a new encoding structure, denoted as BSATS, is designed for the problem at hand. The proposed metaheuristic has been properly calibrated and then an exhaustive comparison analysis involving several evolutionary algorithms from the relevant literature has been carried out. Additionally, a mixed integer linear programming model has been formalized in order to optimally solve a set of small-sized test cases. The numerical results obtained, together with a consistent convergence analysis, confirm both the effectiveness and the efficiency of the proposed method.