Home |  English version |  Mappa |  Commenti |  Sondaggio |  Staff |  Contattaci Cerca nel sito  
Istituto di scienze e tecnologie della cognizione

Torna all'elenco Contributi in rivista anno 2011

Contributo in rivista

Tipo: Articolo in rivista

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

Anno di pubblicazione: 2011

Autori: Oddi, Angelo ; Rasconi, Riccardo ; Cesta, Amedeo ; Smith, Stephen F.

Affiliazioni autori: CNR-ISTC, Roma1-SanMartino ; CMU - Carnegie Mellon University, Robotics Institute

Autori CNR:


Lingua: inglese

Abstract: 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.

Lingua abstract: inglese

Pagine da: 371

Pagine a: 402


Annals of mathematics and artificial intelligence J.C. Baltzer AG.
Paese di pubblicazione: Svizzera
Lingua: inglese
ISSN: 1012-2443

Numero volume: 62

Numero fascicolo: 3-4

DOI: 10.1007/s10472-011-9264-8

Parole chiave:

  • Constraint-Based Scheduling
  • Job-shop scheduling
  • Setup times
  • Precedence Constraint Posting
  • Random Restart

URL: http://link.springer.com/article/10.1007%2Fs10472-011-9264-8

Altre informazioni: ID_PUMA: /cnr.istc/2011-A0-062. - Rivista pubblicata anche online (ISSN 1573-7470). - Area di valutazione 09 - Ingegneria industriale e informatica

Strutture CNR:


Torna indietro Richiedi modifiche Invia per email Stampa
Home Il CNR  |  I servizi News |   Eventi | Istituti |  Focus