Generating Robust Partial Order Schedules (Articolo in rivista)

Type
Label
  • Generating Robust Partial Order Schedules (Articolo in rivista) (literal)
Anno
  • 2004-01-01T00:00:00+01:00 (literal)
Alternative label
  • Policella, N., Oddi, A., Smith, S.F. and Cesta, A. (2004)
    Generating Robust Partial Order Schedules
    in Lecture notes in computer science
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • Policella, N., Oddi, A., Smith, S.F. and Cesta, A. (literal)
Pagina inizio
  • 496 (literal)
Pagina fine
  • 511 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
  • 3258 (literal)
Rivista
Note
  • ISI Web of Science (WOS) (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni
  • Policella, N., Oddi, A., and Cesta, A., ISTC-CNR. Smith, S.F., CMU, USA (literal)
Titolo
  • Generating Robust Partial Order Schedules (literal)
Abstract
  • This paper considers the problem of transforming a resource feasible, fixed-times schedule into a partial order schedule (POS) to enhance its robustness and stability properties. Whereas a fixed-times schedule is brittle in the face of unpredictable execution dynamics and can quickly become invalidated, a POS retains temporal flexibility whenever problem constraints allow it and can often absorb unexpected deviation from predictive assumptions. We focus specifically on procedures for generating Chaining Form POSs, wherein activities competing for the same resources are linked into precedence chains. One interesting property of a Chaining Form POS is that it is “makespan preserving” with respect to its originating fixed-times schedule. Thus, issues of maximizing schedule quality and maximizing schedule robustness can be addressed sequentially in a two-step scheduling procedure. Using this approach, a simple chaining algorithm was recently shown to provide an effective basis for transforming good quality solutions into POSs with good robustness properties. Here, we investigate the possibility of producing POSs with better robustness and stability properties through more extended search in the space of Chaining Form POSs. We define two heuristics which make use of a structural property of chaining form POSs to bias chaining decisions. Experimental results on a resource-constrained project scheduling benchmark confirm the effectiveness of our approach. (literal)
Prodotto di
Autore CNR
Insieme di parole chiave

Incoming links:


Autore CNR di
Prodotto
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi
Insieme di parole chiave di
data.CNR.it