id: 06038197
dt: j
an: 06038197
au: Oddi, Angelo; Rasconi, Riccardo; Cesta, Amedeo; Smith, Stephen F.
ti: Solving job shop scheduling with setup times through constraint-based
    iterative sampling: an experimental analysis.
so: Ann. Math. Artif. Intell. 62, No. 3-4, 371-402 (2011).
py: 2011
pu: Springer, Dordrecht
la: EN
cc: 
ut: random-restart; constraint-based reasoning; job-shop scheduling; setup
    times; generalized precedence constraints
ci: 
li: doi:10.1007/s10472-011-9264-8
ab: Summary: This paper presents a heuristic algorithm for solving a job-shop
    scheduling problem with sequence dependent setup times and $min/max$
    separation constraints among the activities (SDST-JSSP/{\sc max}). The
    algorithm relies on a core constraint-based search procedure, which
    generates consistent orderings of activities that require the same
    resource by incrementally imposing precedence constraints on a
    temporally feasible solution. Key to the effectiveness of the search
    procedure is a conflict sampling method biased toward selection of most
    critical conflicts and coupled with a non-deterministic choice
    heuristic to guide the base conflict resolution process. This
    constraint-based search is then embedded within a larger
    iterative-sampling search framework to broaden search space coverage
    and promote solution optimization. The efficacy of the overall
    heuristic algorithm is demonstrated empirically both 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.
rv: