Combining global pruning rules with depth-first search for the job shop scheduling problem with operators

Abstract

We propose an enhanced depth- rst heuristic search algorithm to face the job shop scheduling problem with operators. This problem extends the classical job shop scheduling problem by considering a limited number of human operators that assist the processing of the operations. We considered total ow time minimization as objective function which makes the problem harder to solve and more interesting from a practical point of view than minimizing the makespan. The proposed method exploits a schedule generation scheme termed OG&T, two admissible heuristics and some powerful global pruning rules that require recording expanded states. We have conducted an experimental study across several benchmarks to evaluate our algorithm. The results show that the global pruning method is really e ective and that the proposed approach is quite competent for solving this problem