Vai al contenuto

Problemi di scheduling

Parte 1 · Problemi di ottimizzazione combinatoria · Capitolo 7 · Dispensa, volume 1 (PDF) · Slide · Esercizi: Problemi di scheduling

Prerequisiti

Obiettivi

Al termine di questo capitolo saremo in grado di:

  • classificare un problema di scheduling con la notazione a tre campi ed enunciare il problema \(P\,||\,C_{\max}\);

  • descrivere uno schedule tramite gli insiemi di lavori delle macchine e calcolare carichi e makespan;

  • contare gli assegnamenti e gli schedule distinti di un'istanza;

  • costruire a mano un primo schedule, assegnando ogni lavoro alla macchina meno carica;

  • calcolare un lower bound sul makespan ottimo e usarlo per dimostrare che uno schedule è ottimo.

7.1 Panoramica della famiglia

  • I problemi di scheduling di questo capitolo hanno gli stessi dati: un insieme \(\mathscr{J} = \{1,2,\dots,n\}\) di \(n\) lavori, \(m\) macchine parallele e, per ogni lavoro, un tempo di processamento.

  • Una soluzione assegna ogni lavoro a una macchina: i lavori \(J_h\) della macchina \(h\) sono processati uno dopo l'altro, e la macchina li completa all'istante \(L_h\), il suo carico.

  • L'obiettivo è minimizzare il makespan \(C_{\max} = \max_h L_h\), l'istante di completamento dell'ultimo lavoro.

Un problema di scheduling su macchine parallele ripartisce i lavori fra le macchine in modo che l'ultima macchina finisca il prima possibile. I membri della famiglia differiscono per l'ambiente delle macchine, descritto dalla notazione a tre campi.

  • La tabella elenca i membri della famiglia, con la sezione che definisce ciascuno di essi.
Problema Notazione Macchine Sezione
macchine parallele identiche \(P\,||\,C_{\max}\) ogni lavoro richiede \(t_j\) su ogni macchina 7.2
macchine con velocità diverse \(Q\,||\,C_{\max}\) la macchina \(h\) ha una propria velocità 7.1.1
macchine parallele scorrelate \(R\,||\,C_{\max}\) il lavoro \(j\) richiede \(t_{jh}\) sulla macchina \(h\) 7.1.1

7.1.1 La notazione a tre campi

  • I problemi di scheduling si classificano con la notazione a tre campi \(\alpha\,|\,\beta\,|\,\gamma\) di Graham, Lawler, Lenstra e Rinnooy Kan, dove:

    1. \(\alpha\) descrive l'ambiente delle macchine: \(1\) per una sola macchina, \(P\) per macchine parallele identiche, \(Q\) per macchine parallele con velocità diverse, \(R\) per macchine parallele scorrelate;

    2. \(\beta\) descrive le caratteristiche dei lavori, come le date di rilascio \(r_j\) o i vincoli di precedenza prec; un campo vuoto indica che non ce ne sono;

    3. \(\gamma\) descrive la funzione obiettivo, come il makespan \(C_{\max}\) o la somma dei tempi di completamento \(\sum_j C_j\).

  • In questa notazione, \(P\,||\,C_{\max}\) è il problema di schedulare lavori senza caratteristiche aggiuntive su macchine parallele identiche, minimizzando il makespan.

  • Panoramica

    Panoramica della famiglia · La notazione a tre campi

    Apri

  • 7.2 Scheduling su macchine parallele identiche

    Contare le soluzioni · Un primo schedule a mano · Un lower bound combinatorio · Relazione con il problema del bin packing · Osservazioni

    Apri

Avanti: 7.2 Scheduling su macchine parallele identiche

Esercizi su questo capitolo: Problemi di scheduling

Approfondimento: che cosa fa il corso su questo problema