Vai al contenuto

Formulazioni dei problemi di scheduling

Parte 2 · Formulazioni dei problemi e loro proprietà · Capitolo 14 · Dispensa, volume 2 (PDF) · Slide · Esercizi: Problemi di scheduling

Prerequisiti

Obiettivi

Alla fine di questo capitolo saremo in grado di:

  • scrivere il modello PLI di \(P\|C_{\max}\) e spiegare come la variabile di makespan è collegata ai carichi delle macchine;

  • scrivere i rilassamenti lineari e i loro duali, e dimostrare che il loro valore ottimo è \(\sum_j t_j / m\);

  • dimostrare che il bound LP vale almeno \(1/m\) del valore ottimo, e che il fattore è tight;

  • usare le disuguaglianze valide e i vincoli di rottura delle simmetrie del modello.

14.1 Panoramica della famiglia

  • I modelli PLI dei problemi di scheduling su macchine parallele usano l'insieme \(\mathscr{H}=\{1,2,\ldots,m\}\) delle macchine e una variabile di assegnamento binaria \(x_{jh}\) per ogni lavoro \(j \in \mathscr{J}\) e ogni macchina \(h \in \mathscr{H}\).

  • Una variabile continua \(C_{\max}\) rappresenta il makespan: un vincolo per ogni macchina impone che \(C_{\max}\) sia almeno pari al carico della macchina.

  • La funzione obiettivo minimizza \(C_{\max}\), quindi all'ottimo è uguale al carico massimo.

I modelli di scheduling sono modelli di assegnamento dei lavori alle macchine, come i modelli di packing assegnano gli oggetti ai contenitori; l'obiettivo min-max è linearizzato con la variabile di makespan \(C_{\max}\).

  • La tabella elenca i membri della famiglia, con il nome del loro modello PLI e la sezione che lo scrive.
Problema Modello Variabili Sezione
\(P\|C_{\max}\) \(\mathrm{ILP}_{P\|C_{\max}}\) \(x_{jh}\) binarie e \(C_{\max}\) continua 14.2

  • Panoramica

    Panoramica della famiglia

    Apri

  • 14.2 Un modello PLI per il problema di scheduling su macchine parallele identiche

    Alcune proprietà teoriche importanti

    Apri

Avanti: 14.2 Un modello PLI per il problema di scheduling su macchine parallele identiche

Esercizi su questo capitolo: Problemi di scheduling