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.
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
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.
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.
Obiettivi di un problema di scheduling
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.
Vincoli di un problema di scheduling
Esempi di vincoli tecnologici
I problemi di scheduling si possono classificare sulla base di
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 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 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 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.
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.
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.
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.
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)
1. Introduzione al corso di Ricerca operativa II
2. Generalità e classificazione dei sistemi di produzione
3. La logistica dei sistemi di produzione
4. Introduzione all'ottimizzazione combinatoria
5. Fondamenti di teoria della complessità computazionale
6. Algoritmi euristici costruttivi e migliorativi
10. Problemi di Localizzazione
12. Introduzione alla gestione delle scorte
13. Modelli stocastici per la gestione delle scorte
14. Modelli discreti per la gestione delle scorte
15. Introduzione allo scheduling
16. Scheduling su macchina singola
17. Problemi di scheduling su macchina singola e su macchine parall...