New bounds for move evaluation in the flexible job-shop scheduling problem

Neighborhood-based search algorithms have been shown to be highly competitive in solving scheduling problems. The performance of these algorithms is directly related to how the neighbors of a solution are explored at each iteration. This has motivated researchers to investigate efficient estimations of the objective function that allow choosing from the neighbors of a solution without completely evaluating them. Especially important are those estimation functions that are guaranteed to be lower or upper bounds. Several papers have proposed lower bounds for the flexible job-shop problem, not only for the classical makespan objective function but also for any regular criterion. However, despite their interest, the research on upper bounds has not been extensive and, to the best of our knowledge, there is no proposal in the literature targeting the flexible job-shop scheduling problem. This paper proposes both new lower and upper bounds for any regular criterion after rescheduling any operation in the flexible job-shop scheduling problem. A thorough experimental study shows that our bounds are more accurate than existing ones, and lead to better solutions when embedded into a neighborhood-based search algorithm. Moreover, we show that two previous lower bounds from the literature are not valid in some cases, as they can overestimate the objective function. In addition, we propose an improved algorithm to check the dependencies between operations by including a pruning mechanism in a bidirectional search procedure. Our computational results show that this algorithm can be significantly faster than previous approaches. • Novel move quality bounds are proposed for the flexible job shop scheduling problem. • The proposed lower and upper bounds are valid for any regular criterion. • An improved algorithm checks the existence of a path between two operations. • Extensive computational experiments show the efficiency and accuracy of bounds. • Numerical results also show dominance over lower bounds from the literature.