Counting Longest Paths to Guide Neighborhood Search for Large-Scale Job Shop Scheduling

This paper proposes a non-uniform neighborhood relation which has been developed to solve job shop scheduling by simulated annealing-based algorithms. To represent the job shop scheduling problem we employ the model of disjunctive graphs. The generation probability of a neighbor depends on the number of longest paths in the underlying graph representation and gives a preference to transitions where a decrease of longest paths is most likely. The choice of the generation probability has been confirmed by our computational experiments. For optimal and near optimal solutions we observed a small number of longest paths, e.g., our best solutions for problem instances with a maximum number of about 50 longest paths had only between one and five longest paths. Using this neighborhood relation combined with a specifically designed cooling schedule, we could improve five upper bounds of the large unsolved 20×20 and 50×10 benchmark problems YN1, YN4, SWV12, SWV13, and SWV15. The maximum improvement shortens the gap between the lower and the previous upper bound by about 57%. Approximations within 1% and 5% of the upper bounds on YN1-YN4, SWV11-SWV13, and SWV15 were achieved in a relatively short run-time.