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
 
I corsi di Ingegneria
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Giuseppe Bruno » 15.Introduzione allo scheduling


Argomenti della lezione

  • Introduzione
  • Definizioni generali
  • Caratteristiche dei problemi di scheduling
  • Classificazione dei problemi
  • Metodi di risoluzione

Introduzione


Introduzione (segue)

Lo scheduling delle attività di produzione

Un processo di produzione si compone di operazioni che richiedono l’impiego di risorse (manodopera, macchinari).

Si pone il problema di allocare le operazioni alle risorse disponibili (loading), di determinare la sequenza secondo la quale le operazioni vanno eseguite (sequencing) ed di definire, per ciascuna operazione, una schedulazione ossia l’individuazione degli istanti di inizio e di completamento di ciascuna operazione (scheduling).

I termini scheduling o schedulazione possono essere utilizzati per indicare la tempificazione secondo la quale le operazioni devono essere realizzate e il processo che conduce alla individuazione di tale tempificazione.

Definizioni generali

Una operazione è l’attività elementare per la cui realizzazione è necessaria una macchina.

Una macchina è uno strumento in grado di svolgere operazioni.

Una macchina può essere;
dedicata se può svolgere solo determinate operazioni;
parallela se può svolgere indifferentemente tutte le operazioni.

Nel caso di macchine parallele si parla di macchine

  • identiche se processano le operazioni con la stessa velocità;
  • uniformi se la velocità delle macchine è differente ma costante ed indipendente dalle operazioni;
  • incorrelate se la velocità dipende dalle operazioni da realizzare.

Definizioni generali (segue)

Tempo di processamento (processing time) pkj

Tempo che occorre alla macchina k per eseguire l’operazione j.

Peso o priorità (weight) wj

Rappresenta un indice di priorità dell’operazione j rispetto a u.

Tempo di rilascio (release time) rj

Istante a partire dal quale l’operazione j può essere processata.

Tempo di inizio (start time) sj

Istante in cui viene iniziata l’operazione j (sj≥ rj).

Tempo di completamento (completion time) Cj

Istante in cui termina l’esecuzione dell’operazione j.

Tempo di scadenza (due date) dj

Istante entro cui l’operazione j dovrebbe essere completata.

Termine massimo (deadline) dj

Termine perentorio entro cui bisogna completare l’operazione j.

 

Definizioni generali (segue)

Tempo di flusso (Flow time) Fj=Cj-rj
Differenza tra il tempo di completamento e il tempo di rilascio; è dato dalla somma del tempo di processamento e del ndica il tempo di complessivo attraversamento.

Ritardo (lateness) Lj=Cj-dj
Differenza tra il tempo di completamento e il tempo di scadenza; se Lj>0 l’operazione é stata completata in ritardo; se Lj<0, invece, essa é stata completata in anticipo.

Tardiness Tj= max{Lj, 0}
Tiene conto solo dei ritardi rispetto ai tempi di completamento.

Scorrimento (slack) slj=dj-rj-pj
Scorrimento possibile per l’esecuzione dell’operazione.

Definizioni generali (segue)


Definizioni generali (segue)


Caratteristiche dei problemi di scheduling


Caratteristiche dei problemi di scheduling (segue)

Obiettivi di un problema di scheduling

  • L’obiettivo (1) è orientato alla efficienza dell’utilizzazione delle macchine;
  • Gli obiettivi (2-3-4) sono orientati all’utenza;
  • Gli obiettivi (5-6-7-8-9) sono orientati alle scadenze.

Gli obiettivi più importanti sono il makespan (Cmax), la somma dei tempi di completamento (ΣCj) e il ritardo massimo (Lmax).

Un obiettivo è regolare se il suo valore non può decrescere con l’aumento del tempo di processamento di una qualsiasi operazione.

Caratteristiche dei problemi di scheduling (segue)

Vincoli di un problema di scheduling

  • ogni macchina non può processare più di una operazione contemporaneamente;
  • ogni operazione deve essere processata al massimo da una macchina alla volta;
  • una operazione può essere eseguita nell’intervallo di tempo [rj, dj);
  • devono essere soddisfatti eventuali vincoli tecnologici.

Caratteristiche dei problemi di scheduling (segue)

Esempi di vincoli tecnologici

  • possibilità di interrompere l’esecuzione di un’operazione e di riprenderla successivamente (scheduling preemptive);
  • vincoli di precedenza tra operazioni;
  • esigenza di attendere dei tempi di setup tra il completamento di un’operazione e l’inizio di un’altra sulla stessa macchina;
  • possibilità di eseguire gruppi di operazioni contestualmente (batching scheduling).

Classificazione dei problemi

I problemi di scheduling si possono classificare sulla base di

  • Caratteristiche delle operazioni;
  • Vincoli temporali;
  • Tipologia delle informazioni a disposizione.

Classificazione dei problemi (segue)

Classificazione in base alle caratteristiche delle operazioni

I problemi a fase unica possono distinguersi, in funzione del numero di macchine, in:

Problemi a macchina singola
In presenza di una sola macchina;

Problemi a macchina parallele
In presenza di una più macchine.


Classificazione dei problemi (segue)

Classificazione in base alle 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.

Classificazione dei problemi (segue)

Classificazione in base ai vincoli temporali

Problemi statici
Se le operazioni sono tutte disponibili all’istante di inizio della schedulazioni (rj=0 per ogni operazione).

Problemi dinamici
Se le operazioni si rendono disponibili nel tempo in modo noto apriori (rj>0 noti apriori).

Problemi on-line
Se le operazioni si rendono disponibili nel tempo in modo non noto apriori (rj>0 non noti apriori).

Classificazione dei problemi (segue)

Classificazione in base alla tipologia di informazioni disponibili

Problemi deterministici
Se i parametri associati alle operazioni (tempi di processamento, tempi di rilascio, scadenze) sono tutti deterministici.

Problemi stocastici
Se qualcuno dei parametri associati alle operazioni (tempi di processamento, tempi di rilascio, scadenze) è definito in termini aleatori.

Classificazione dei problemi (segue)

Metodo per la classificazione di un problema

Un metodo standard per la classificazione di un problema di scheduling è quello della notazione di Graham in base alla quale un problema viene indicato specificando tre tipologie di informazioni

α | β | γ

Essendo
α: informazioni relative alle macchine ed alle fasi;
β: informazioni relative alla presenza di vincoli;
γ: criterio di ottimizzazione.

Esempio:
Pm|preemptive|Cmax
problema su macchine parallele con possibilità di interruzione orientato alla minimizzazione del makespan.

Classificazione dei problemi (segue)

Una soluzione di un problema di scheduling può essere:

Senza ritardo
Se non si verifica mai che una macchina, pur potendo effettuare un’operazione, resti inattiva.

Attiva
Se, per anticipare il completamento di una qualsiasi operazione, si provoca un ritardo nel completamento di altre operazioni.

Non attiva
Se non è attiva.

Una soluzione senza ritardo è anche attiva. Una soluzione attiva può essere con ritardo.

La soluzione ottima di un problema di scheduling è una soluzione attiva ma non necessariamente senza ritardo.

Classificazione dei problemi


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

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)

  • 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