Notazione per i problemi di schedulazione
![Voce da controllare](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Emblem-important.svg/40px-Emblem-important.svg.png)
Problemi di schedulazione nel processo produttivo, ciclo di ottimizzazione della fabbrica.
I problemi di schedulazione nella loro forma più semplice consistono in un certo numero di lotti da realizzarsi per mezzo di un dato numero di macchine, ogni lotto presenta una serie di operazioni che devono essere svolte dalle varie macchine in una specifica sequenza: il problema è determinare una schedulazione ammissibile che impieghi il minimo tempo totale.
Nel seguito si descrive lo schema di classificazione introdotto nella pubblicazione di Graham, Lawler, Lenstra, e Rinnooy Kan Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey[1] del 1979 per identificare le tipologie dei problema di schedulazione. Lo schema di classificazione fa ricorso a tre campi che riflettono nell'ordine le caratteristiche delle macchine, delle operazioni ed infine specificano il criterio di prestazione (funzione obiettivo) adottato per valutare la schedula.
Per n lotti assegnati da lavorare per mezzo di m macchine si adottano le seguenti ipotesi:
- ogni macchina può lavorare un solo lotto alla volta
- ogni lotto può essere lavorato da una ed una sola macchina alla volta
Inoltre si ritiene che i tempi delle lavorazioni e tutti gli altri parametri siano noti e fissati: pertanto i problemi di schedulazione esaminati saranno implicitamente di tipo deterministico a differenza dei problemi stocastici in cui i tempi delle lavorazioni e gli altri parametri sono incerti ed aleatori.
Ambiente delle macchine
Il primo campo specifica l'ambiente delle macchine.
Il parametro caratterizza il tipo di macchina utilizzato:
= | macchina singola | |
=P | macchine identiche | |
=Q | macchine uniformi | |
=R | macchine incorrelate | |
=O | macchine dedicate-sistema open shop | |
=F | macchine dedicate-sistema flow shop | |
=J | macchine dedicate-sistema job shop |
Il parametro caratterizza il numero di macchine nel problema:
= | il numero delle macchine è variabile e fa parte degli input del problema | |
=m | il numero delle macchine è costante ed uguale ad un numero intero positivo m |
Si osservi che se e solo se
Caratteristica dei lotti
Il secondo campo descrive un certo numero di caratteristiche dei lotti definiti come nel seguito. Il parametro indica la possibilità di preemption ossia di interrompere arbitrariamente la lavorazione di qualsiasi lotto e di riprenderla più tardi anche su una macchina diversa (job splitting).
= | la preemption non è ammessa | |
=pmtn | le preemptions sono ammesse |
Il parametro indica la presenza di risorse scarse.
= | non è specificato alcun vincolo sulle risorse | |
=res | sono specificati vincoli sulle risorse |
Il parametro indica la presenza di vincoli di precedenza tra i lotti.
Il parametro indica il tempo al pronto, in gergo ready time, ossia indica il tempo in cui un lotto è disponibile per essere lavorato da una qualche macchina.
= | si ipotizza che tutti i ready time sono nulli ovvero tutti i lotti sono disponibili alla lavorazione nello stesso istante | |
= | vengono specificati i tempi al pronto, tempi che possono differire da lotto a lotto j=1,...,n |
Il parametro descrive il tempo per la lavorazione i-esima sulla macchina j-esima, .
= | i lotti presentano tempi di lavorazione arbitrari | |
= | tutti i lotti presentano lo stesso tempo di lavorazione pari a p | |
= | nessun tempo di lavorazione è inferiore a min p o superiore a max p |
Nel caso il parametro è rimpiazzato dalla notazione
Il parametro indica la presenza di scadenze temporali.
= | non esistono scadenze temporali nel sistema | |
= | scadenze temporali sono imposte all'ultimazione delle operazioni |
Nel caso di sistemi job-shop il parametro indica il numero massimo di lavorazioni che costituiscono un lotto.
= | il numero di lavorazioni per ogni lotto è arbitrario oppure il sistema non è di tipo job-shop | |
= | il numero di lavorazioni per ogni lotto non è superiore a k |
Nel caso di sistemi dedicati il parametro indica la presenza di spazi di stoccaggio intermedi tra le macchine, “buffer”, atti ad ospitare i lotti in attesa dell'inizio della lavorazione successiva.
= | si è in presenza di buffer dalla capacità illimitata | |
=no-wait | non esistono buffer tra le macchine e un lotto che ha terminato una lavorazione deve necessariamente incominciare subito la lavorazione sulla macchina successiva |
Criterio di prestazione
Il terzo campo denota il criterio di prestazione adottato.
Note
- ^ R. L. Graham, E. L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey: Ann. Discrete Math. 5, 1979, p.287-326
Bibliografia
- Blazewicz, J.K. Lenstra, A.H.G. Rinnooy Kan, Scheduling subject to resource constraints: classification and complexity: Ann. Discrete Math. 5, 1983, p. 11-24
- Blazewicz, K. Ecker, E. Pesch, G. Schmidt, J. Weglarz, Handbook on Scheduling - From Theory to Applications (International Handbooks on Information Systems): Springer-Verlag Berlin Heidelberg, 2007