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 » 16.Scheduling su macchina singola


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
    • (rj=0 ∀ j)
  • Dinamici se le operazioni sono disponibili in tempi diversi
    • ( ∃ j: rj>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à (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 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 wj/pj decrescente ovvero, se wj=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 slj=dj-rj-pj crescente (dinamica)

CR (Critical Ratio) (dj-rj)/pj
Valore del rapporto (dj-rj)/pj crescente (dinamica)

Problemi statici

1 ||Cmax 1 || ΣwjCj 1 ||Lmax

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

1 || Cmax
Si può applicare qualsiasi regola

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

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

Problemi statici (segue)


Problemi statici (segue)


Problemi dinamici

1 |rj|Cmax;

1 |rj| ΣwjCj;

1 |rj |Lmax

Ad eccezione del problema 1|rj|Cmax 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 Ot delle operazioni disponibili, ovvero che presentano rjt.

Tra le operazioni Ot 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 jO‘ rj

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

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

Il valore di t al passo 3 viene aggiornato considerando che in certi istanti può accadere che Ot=Ø perché tutte le operazioni ancora da schedulare presentano rj≥t; in questo caso, quindi, la schedulazione deve ripartire dal valore di rj 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.


Problemi dinamici (segue)


Problemi dinamici (segue)


Problemi dinamici (segue)


Problemi dinamici (segue)


Problemi dinamici (segue)


Problemi dinamici (segue)


  • 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