Vai al contenuto

Problemi di scheduling

Catalogo dei problemi di ottimizzazione combinatoria · Catalogo (PDF)

  • Dati \(n\) lavori con i loro tempi di processamento e \(m\) macchine parallele, una soluzione assegna ogni lavoro a una macchina, che lo esegue senza interruzioni.

  • L'obiettivo è minimizzare il makespan \(C_{\max}\), l'istante di completamento dell'ultimo lavoro; nella notazione a tre campi \(\alpha\|C_{\max}\) il campo \(\alpha\) descrive le macchine: identiche (\(P\)), un numero fissato di macchine identiche (\(Pm\)), con velocità diverse (\(Q\)) o scorrelate (\(R\)).

Problema Sigla Differenza
Scheduling su macchine parallele identiche \(P\|C_{\max}\) Il problema centrale della famiglia.
Scheduling su un numero fissato di macchine identiche \(Pm\|C_{\max}\) Caso particolare di \(P\,||\,C_{\max}\) con \(m\) fissato; con \(m=2\) chiede di dividere i lavori in due insiemi con carichi il più possibile uguali.
Scheduling su macchine parallele con velocità diverse \(Q\|C_{\max}\) Generalizza \(P\,||\,C_{\max}\), che è il caso di macchine con la stessa velocità.
Scheduling su macchine parallele scorrelate \(R\|C_{\max}\) Generalizza \(Q\,||\,C_{\max}\) e \(P\,||\,C_{\max}\).