Problemi di scheduling su macchina singola e su macchine parallele, Giuseppe Bruno « Ricerca Operativa II « Ingegneria

Argomenti della lezione

Altri problemi su macchina singola
Problemi su macchine parallele

Altri problemi su macchina singola

Oltre ai problemi già trattati nella lezione precedente, tra i problemi a macchina singola ci sono altri problemi di particolare interesse. Tra questi i problemi

1 |s_ij| C_max
Sequenziamento di operazioni in presenza di tempi di setup s_ij

1 || Σδ_j
Minimizzazione del numero di operazioni in ritardo

Altri problemi su macchina singola (segue)

1 |s_ij| C_max

Problema del sequenziamento di operazioni su una macchina

Siano date n operazioni da assegnare ad una macchina. Siano:

p_j il tempo di esecuzione dell’operazione j;
s_ij il tempo che bisogna attendere per iniziare l’operazione j dopo il completamento dell’operazione i (tempo di setup).

Si individui il sequenziamento delle operazioni che minimizzi il C_max

(vedi figura)

Poiché i tempi di processamento sono fissati minimizzare il Cmax equivale a minimizzare la somma dei tempi di setup.

Altri problemi su macchina singola (segue)

1 |s_ij| C_max
Problema del sequenziamento di operazioni su una macchina

Il problema può essere ridotto ad un problema di TSP con n+1 nodi.

Appartiene alla clesse dei problemi NP-hard.

Per la sua risoluzione si possono adottare le tecniche euristiche utilizzabili per la risoluzione del TSP.

Altri problemi su macchina singola (segue)

1 || Σδ_j

Minimizzazione del numero di operazioni in ritardo

Siano date n operazioni da assegnare ad una macchina. Siano:

p_j il tempo di esecuzione dell’operazione j
d_j due date dell’operazione j

Si individui il sequenziamento delle operazioni che minimizzi il numero di operazioni in ritardo Σδ_j.
Il problema è di tipo polinomiale e pertanto si può individuare la soluzione ottima attraverso l’algoritmo che viene descritto.

Altri problemi su macchina singola (segue)

1 || Σδ_j

Si punta ad una soluzione che prevede prima l’esecuzione delle operazioni che si completano in anticipo rispetto alla scadenza e poi delle operazioni in ritardo (l’ordine secondo il quale le operazioni in ritardo vengono effettuate è del tutto irrilevante)

Per descrivere l’algoritmo in grado di individuare la soluzione ottima, considerando l’iterazione generica k, si indichi con

J insieme di tutte le operazioni;
J_k soluzione provvisoriamente individuata fino alla iterazione k;
J‘_k insieme delle operazioni che, fino all’iterazione k, si è già stabilito che saranno schedulate in ritardo;
J“_k=J-J_k-J‘_k insieme restanti operazioni non ancora esaminate.

Altri problemi su macchina singola (segue)

1 || Σδ_j

Alla iterazione k, si considera l’operazione j* di J”_k che presenta il tempo di scadenza minore (regola EDD) e si ipotizza di schedularla a partire dal tempo di completamento dell’ultima operazione di J_k.

Se j* viene completata prima della propria scadenza, viene eseguita.

Se il suo tempo di completamento supera la scadenza, si individua l’operazione j** di J_k, provvisoriamente inserita nella sequenza, che presenta il tempo di processamento maggiore e si stabilisce definitivamente di schedularla in ritardo L’operazione j** viene così inserita nell’insieme J’_k+1.

La procedura si arresta quando sono state analizzate tutte le operazioni.

Altri problemi su macchina singola (segue)

1 || Σδ_j

1. Inizializzazione
Si pone k=0, J_o=Ø, J‘_o=Ø, J“_o=J e t=0.

2. Analisi di un nuovo elemento
Si individua l’operazione j* di J“_k con il minimo tempo di scadenza (regola EDD) e la si inserisce in J_k+1=J_k∪{j*}.
Se C_j*=t+p_j*>d_j*, si individua j**∈j‘_k+1 con tempo di processamento massimo che viene schedulata definitivamente in ritardo.
Quindi si pone J_k+1= J_k+1-{j**} e J’_k+1=J’k∪{j**};
J”_k+1=J“_k-{j*}, t=Σ_j∈Jkp_j, k=k+1.

3. Criterio di arresto
Se J“_k=Ø l’algoritmo si arresta; si schedulano le operazioni di J_k secondo l’ordine individuato e le operazioni di J‘_k secondo un ordine qualsiasi. In caso contrario si ritorna al passo 2.

Problemi su macchine parallele

I problemi su macchine parallele sono, in generale, più complessi dei rispettivi problemi su macchina singola.

Anche per questi problemi si applica il metodo delle liste di priorità (dispatching rules) a condizione di assegnare l’operazione alla macchina con più scarica, ovvero con il tempo di completamento minore.

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

Problemi su macchine parallele (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, si assegna alla macchina più scarica 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.

Problemi su macchine parallele (segue)

Pm||C_max Pm|| Σw_jC_j Pm||L_max

Pm||C_max

Problema NP-hard. Per una buona soluzione si può applicare la regola LPT.

Pm|| Σw_jC_j
Problema polinomiale. La regola WSPT individua la soluzione ottima.

Pm||L_max
Problema NP-hard. Per una buona soluzione si può applicare la regola EDD.

Problemi su macchine parallele (segue)

Pm|preemptive|C_max

Problema polinomiale.
Rappresenta un rilassamento del problema P||C_max dal momento che è possibile frazionare l’esecuzione di un’operazione. Di conseguenza la sua soluzione ottima C*_max rappresenta un limite inferiore per il problema P||C_max
In pratica la soluzione ottima è pari a (Σp_j/m) quando è possibile ottenere il bilanciamento perfetto, mentre è pari a (max p_j) quando è presente un’operazione con tempo di processamento maggiore di (Σp_j/m).