Pruning by dominance in best-first search for the job shop Scheduling problem with total flow time
Best-First search is a problem solving paradigm that allows to design exact or admissible algorithms. In this paper, we confront the Job Shop Scheduling problem with total flow time minimization by means of the A (*) algorithm. We devised a heuristic from a problem relaxation that relies on computing Jackson's preemptive schedules. In order to reduce the effective search space, we formalized a method for pruning nodes based on dominance relations and established a rule to apply this method efficiently during the search. By means of experimental study, we show that the proposed method is more efficient than a genetic algorithm in solving instances with 10 jobs and 5 machines and that pruning by dominance allows A (*) to reach optimal schedules, while these instances are not solved by A (*) otherwise. These experiments have also made it clear that the Job Shop Scheduling problem with total flow time minimization is harder to solve than the same problem with makespan minimization.
pruning by dominance job shop scheduling total flow time minimization best first search admissible heuristics