Scheduling su macchina singola, Giuseppe Bruno « Ricerca Operativa II « Ingegneria

Argomenti della lezione

Definizioni generali
Metodi di risoluzione
Problemi statici
Problemi dinamici

Definizioni generali

Sulla base delle caratteristiche delle operazioni è possibile distinguere tra:

Problemi a fase unica
Tutte le lavorazioni richiedono una sola operazione e, pertanto, si può parlare indifferentemente di lavorazione o operazione (job o task);

Problemi multifase
Ogni lavorazione che, in questo caso, viene detta job, è composta da più operazioni tra le quali esistono vincoli di precedenza.

Definizioni generali (segue)

Un problema di scheduling su macchina singola è un problema a fase singola caratterizzato dalla presenza di una sola macchina.

I problemi su macchina singola possono essere:

Statici se tutte le operazioni sono disponibili all’istante iniziale
- (r_j=0 ∀ j)
Dinamici se le operazioni sono disponibili in tempi diversi
- ( ∃ j: r_j>0)

Metodi di risoluzione

Come tutti i problemi di ottimizzazione un problema di scheduling può essere risolto con metodi esatti o con metodi euristici in funzione della sua complessità.

Un metodo costruttivo molto utilizzato per risolvere problemi di scheduling è il metodo delle liste di priorità (dispatching rules). Si tratta di un metodo costruttivo che, in fase di inizializzazione, ordina le operazioni sulla base di regole o indici di priorità (dispatching rules), e quindi costruisce la soluzione assegnandole, secondo quest’ordine, alle macchine disponibili.

Le regole di priorità sono statiche se il valore dell’indice non dipende dal tempo di inizio dell’operazione, dinamiche altrimenti.

Per alcuni problemi, scelta opportunamente la regola di priorità, il metodo ottiene la soluzione ottima.

Metodi di risoluzione (segue)

Il metodo delle regole di priorità (dispatching rules)

1. Inizializzazione
Si ordinano le operazioni secondo una regola di priorità (j₁,… j_n) e si costruisce la soluzione parziale S={j₁}.

2. Scelta elemento da aggiungere alla soluzione parziale
All’iterazione k si sceglie l’operazione j_k da aggiungere alla soluzione parziale e la si schedula al più presto in modo da rispettare i vincoli presenti.

3. Criterio di arresto
Se tutte le operazioni sono state schedulate, l’algoritmo si arresta, altrimenti si torna al passo 2.

Metodi di risoluzione (segue)

Regole di priorità statiche più utilizzate

FCFS (First Come First Served)
Tempo di rilascio crescente

WSPT (Weighted Shortest Processing Time)
Rapporto w_j/p_j decrescente ovvero, se w_j=1 ∀j, tempo di processamento crescente

LPT (Longest Processing Time)
Tempo di processamento decrescente

EDD (Earliest Due Date)
Tempo di scadenza crescente

MST (Minimum Slack Time)
Valore della slack sl_j=d_j-r_j-p_j crescente (dinamica)

CR (Critical Ratio) (d_j-r_j)/p_j
Valore del rapporto (d_j-r_j)/p_j crescente (dinamica)

Problemi statici

1 ||C_max 1 || Σw_jC_j 1 ||L_max

Sono problemi di complessità polinomiale per i quali è possibile ottenere la soluzione ottima attraverso l’applicazione di opportune regole di priorità.

1 || C_max
Si può applicare qualsiasi regola

1 || Σw_jC_j
Si deve applicare la regola WSPT (Weighted Shortest Proc. Time)

1 || L_max
Si deve applicare la regola EDD (Earliest Processing Time)

Problemi statici (segue)

Problemi dinamici

1 |r_j|C_max;

1 |r_j| Σw_jC_j;

1 |r_j |L_max

Ad eccezione del problema 1|r_j|C_max che resta polinomiale, gli altri problemi sono di tipo NP-hard.

Il metodo delle liste di priorità può essere esteso anche al caso dinamico. Dopo aver definito la schedulazione di un insieme di operazioni fino all’istante t, si individua l’insieme O_t delle operazioni disponibili, ovvero che presentano r_j ≤ t.

Tra le operazioni O_t si schedula quella che presenta la priorità maggiore secondo la regola utilizzata.

Il procedimento si itera assumendo, come nuovo istante t, il tempo di completamento della nuova operazione schedulata

Problemi dinamici

1. Inizializzazione
Si pone O’=O e t=min _j∈O‘ r_j

2. Aggiunta di un nuovo elemento alla soluzione parziale
Si individuano le operazioni O_t={j∈O‘: r_j≤t}; si individua l’operazione j*∈O_t che presenta il valore di priorità più elevato secondo la regola scelta.
Si pone s_j*=t, C_j*= t+ p_j* e O’=O’-{j*}.

3. Criterio di arresto
Se la soluzione è completa (O’=Ø) l’algoritmo si arresta; altrimenti si pone t= max(C_j*, min _j∈_O’ r_j) e si ritorna al passo 2.

Il valore di t al passo 3 viene aggiornato considerando che in certi istanti può accadere che O_t=Ø perché tutte le operazioni ancora da schedulare presentano r_j≥t; in questo caso, quindi, la schedulazione deve ripartire dal valore di r_j minore.

Problemi dinamici (segue)

La scelta della regola di priorità dipende dall’obiettivo; si possono, pertanto, utilizzare le stesse regole del caso statico.

Le soluzioni prodotte dalla metodologia indicata sono senza ritardo (non delay) dal momento che non è prevista la possibilità che la macchina resti inattiva nel caso sia nelle condizioni di poter effettuare un’operazione.