In this paper, we conduct a study of the job-shop scheduling problem with reverse flows. This NP-hard problem is characterized by two flows of jobs that cover the same machines in opposite directions. The objective is to minimize the maximal completion time of the jobs (i.e., the makespan). 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. 
Job-shop production scheduling with reverse flows