Job-shop production scheduling with reverse flows

We start by analyzing the complexity and identifying particular cases of the problem. Then, we provide a mathematical model that we use in conjunction with a solver to determine the computational times. These times are often too long because the problem is NP-hard. Thus, in this paper, we present a new heuristic method for solving the NP-hard 3-machine case. We evaluate the performance of this heuristic by computing several lower bounds and conducting tests on a Taillard-based benchmark. These tests give satisfying results and show that the heuristic ensures good performance when the two flows have comparable numbers of jobs. Then, we suggest a hybrid method that consists of a combination between a heuristic and a solver-based procedure to address the m-machine problem.