A New Heuristic Method for Job-Shop Scheduling Problem

We describe a heuristic method for solving the minimum makespan problem of job shop scheduling. It makes use of the disjunctive graph, and set the direction of the disjunctive arcs as decision variables. The decision variables, as micro bottlenecks, are cleared one by one, following the critical path algorithm. Once a new disjunctive arc is adopted all the implicit disjunctive arcs will be decided. The time complexity is O (n²). Computational testing is performed to solve the notorious ten machines /ten jobs problem in running time of 8.272 CPU seconds on a P-II 450 MHz PC, however, without finding an optimal solution. Finally, we verified the algorithm by testing a 100x30 (100 jobs/30 machines) problem, which may contribute to be one of the new benchmark problems.