Solving Job Shop Scheduling with Setup Times through Constraint-based Iterative Sampling: an Experimental Analysis

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/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.

Tipo Pubblicazione: 
Articolo
Author or Creator: 
Oddi, Angelo
Rasconi, Riccardo
Cesta, Amedeo
Smith, Stephen F.
Publisher: 
J.C. Baltzer AG., Basel, Svizzera
Source: 
Annals of mathematics and artificial intelligence 62 (2011): 371–402. doi:10.1007/s10472-011-9264-8
info:cnr-pdr/source/autori:Oddi, Angelo ; Rasconi, Riccardo ; Cesta, Amedeo ; Smith, Stephen F./titolo:Solving Job Shop Scheduling with Setup Times through Constraint-based Iterative Sampling: an Experimental Analysis/doi:10.1007/s10472-011-9264-8/rivis
Date: 
2011
Resource Identifier: 
http://www.cnr.it/prodotto/i/201352
https://dx.doi.org/10.1007/s10472-011-9264-8
info:doi:10.1007/s10472-011-9264-8
http://link.springer.com/article/10.1007%2Fs10472-011-9264-8
Language: 
Eng
ISTC Author: 
Ritratto di Angelo Oddi
Real name: 
Ritratto di Riccardo Rasconi
Real name: 
Ritratto di Amedeo Cesta
Real name: