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.