Scheduling per minimizzare i ritardi

Problema della minimizzazione dei ritardi:

• una singola risorsa in grado di elaborare un unico job
• il job richiede $t_j$ unità di tempo e deve essere terminato entro il tempo $d_j$ (scadenza)
• considerazione: se $j$ comincia al tempo $s_j$ allora finisce al tempo $f_j=s_j+t_j$

<aside> 💡 ritardo del job $j$ è definito come $l_j=max\{0,f_j-d_j\}$

</aside>

• input: $n$ job ciascuno dei quali richiede $t_j$ unità di tempo e deve essere terminato entro il tempo $d_j$ (scadenza)
• obiettivo: trovare uno scheduling di tutti i job che minimizzi il ritardo massimo $L=max\space l_j$
• uno scheduling assegna ad ogni job $j$ un tempo di inizio $s_j$

Minimizzare il ritardo

Schema greedy: considera i job in un certo ordine

• shortest processing time first: considera i job in ordine non decrescente dei tempi di elaborazione $t_j$
• earliest deadline first: considera i job in ordine non decrescente dei tempi entro i quali devono essere ultimati $d_j$
• smallest slack: considera i job in ordine non decrescente degli scarti $d_j-t_j$

Algoritmo greedy: earliest deadline first

Inversioni

<aside> 💡 Un’inversione in uno scheduling $S$ è una coppia di job $i$ e $j$ tali che $d_i < d_j$ ma $j$ viene eseguito prima di $i$

</aside>

Ottimalità soluzione greedy

1. la soluzione greedy ha le seguenti proprietà:
   1. nessun idle time: non ci sono momenti in cui la risorsa non è utilizzata
   2. nessuna inversione: se un job $j$ ha scadenza maggiore di quella di un job $i$ allora viene eseguito dopo $i$