A new admissible heuristic for the job shop scheduling problem with total flow time

Abstract

In this paper, we face the Job Shop Scheduling problem with total flow time minimization with A∗ Nilsson’s algorithm. We propose a new heuristic based on problem relaxation to One Machine Sequencing problem with tardiness minimization. This heuristic is improved by means of the well-known generalized Emmons’ constraint propagation rules. Additionally, we use a pruning by dominance method to reduce the effective search space. We report results from an experimental study conducted to evaluate the performance of the proposed heuristic and to compare the A* approach with a classic local search procedure. The results show that the proposed heuristic is efficient as A* is able to reach optimal solutions for instances that are not always solved to optimality with the local search procedure; even running for a larger time