Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Giuseppe Bruno » 17.Problemi di scheduling su macchina singola e su macchine parallele


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 |sij| Cmax
Sequenziamento di operazioni in presenza di tempi di setup sij

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

Altri problemi su macchina singola (segue)

1 |sij| Cmax

Problema del sequenziamento di operazioni su una macchina

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

  • pj il tempo di esecuzione dell’operazione j;
  • sij 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 Cmax

(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 |sij| Cmax
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)


Altri problemi su macchina singola (segue)


Altri problemi su macchina singola (segue)


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:

  • pj il tempo di esecuzione dell’operazione j
  • dj 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;
  • Jk soluzione provvisoriamente individuata fino alla iterazione k;
  • Jk insieme delle operazioni che, fino all’iterazione k, si è già stabilito che saranno schedulate in ritardo;
  • Jk=J-Jk-Jk 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 Jk.

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 Jk, 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, Jo=Ø, Jo=Ø, Jo=J e t=0.

2. Analisi di un nuovo elemento
Si individua l’operazione j* di Jk con il minimo tempo di scadenza (regola EDD) e la si inserisce in Jk+1=Jk∪{j*}.
Se Cj*=t+pj*>dj*, si individua j**∈jk+1 con tempo di processamento massimo che viene schedulata definitivamente in ritardo.
Quindi si pone Jk+1= Jk+1-{j**} e J’k+1=J’k∪{j**};
J”k+1=Jk-{j*}, t=Σj∈Jkpj, k=k+1.

3. Criterio di arresto
Se Jk=Ø l’algoritmo si arresta; si schedulano le operazioni di Jk secondo l’ordine individuato e le operazioni di Jk 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à (j1,… jn) e si costruisce la soluzione parziale S={j1}.

2. Scelta elemento da aggiungere alla soluzione parziale
All’iterazione k si sceglie l’operazione jk, 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||Cmax Pm|| ΣwjCj Pm||Lmax

Pm||Cmax

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

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

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

Problemi su macchine parallele (segue)


Problemi su macchine parallele (segue)

Pm|preemptive|Cmax

Problema polinomiale.
Rappresenta un rilassamento del problema P||Cmax 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||Cmax
In pratica la soluzione ottima è pari a (Σpj/m) quando è possibile ottenere il bilanciamento perfetto, mentre è pari a (max pj) quando è presente un’operazione con tempo di processamento maggiore di (Σpj/m).


  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion