Solving job shop scheduling with setup times through constraint-based iterative sampling: an experimental analysis (Q421447)

A core constraint-based search procedure embedded within a larger iterative-sampling search framework is proposed for solving a job-shop scheduling problem with sequence dependent setup times and min/max separation constraints among the activities (SDST-JSSP/max). The core constraint-based search procedure generates a consistent ordering of activities that require the same resource by incrementally adding precedence constraints between activity pairs belonging to a temporally feasible solution. The search procedure is a conflict sampling method biased toward selection of the most critical conflicts coupled with a non-deterministic choice heuristic to guide the base conflict resolution process. The iterative sampling procedure is not tailored to the job-shop problem in any way and it aims at broadening the search space coverage and promoting solution optimization. The effectiveness of the overall heuristic algorithm is demonstrated by performing a set of experiments on a set of previously studied job-shop scheduling benchmark problems with sequence dependent setup times and by introducing a new benchmark with setups and generalized precedence constraints.