Reentrant open shop scheduling problem with time lags and no-wait constraints

In this work, we consider the two-machine reentrant open shop scheduling problem with no-wait and exact time lags constraints. The objective is to minimize the makespan. We first prove that this problem is NP-hard in the strong sense, then we provide some polynomial sub-problems. To solve the general problem, a heuristic and metaheuristics with hybridizations are proposed with numerical experiments.