Indietro

ⓘ Notazione per i problemi di schedulazione




                                     

ⓘ Notazione per i problemi di schedulazione

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 un 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 del 1979 per identificare le tipologie dei problema di schedulazione. Lo schema di classificazione fa ricorso a tre campi α | β | γ {\displaystyle \alpha |\beta |\gamma } che riflettono nellordine le caratteristiche delle macchine, delle operazioni ed infine specificano il criterio di prestazione funzione obiettivo adottato per valutare la schedula.

Per n lotti assegnati L 1, L 2, …, L n {\displaystyle L_{1},L_{2},\ldots,L_{n}} da lavorare per mezzo di m macchine M 1, M 2, …, m {\displaystyle M_{1},M_{2},\ldots,M_{m}} si adottano le seguenti ipotesi:

  • ogni lotto può essere lavorato da una ed una sola macchina alla volta
  • ogni macchina può lavorare un solo lotto 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.

                                     

1. Ambiente delle macchine

Il primo campo α = α 1 α 2 {\displaystyle \alpha =\alpha _{1}\alpha _{2}} specifica lambiente delle macchine.

Il parametro α 1 2 { ∅, P, Q, R, O, F, J } {\displaystyle \alpha _{1}{\mathcal {2}}\left\{\emptyset,P,Q,R,O,F,J\right\}} caratterizza il tipo di macchina utilizzato:

Il parametro α 2 { ∅, m } {\displaystyle \alpha _{2}{\mathcal {2}}\left\{\emptyset,m\right\}} caratterizza il numero di macchine nel problema:

Si osservi che α 1 = ∅ {\displaystyle \alpha _{1}=\emptyset } se e solo se α 2 = 1 {\displaystyle \alpha _{2}=1}

                                     

2. Caratteristica dei lotti

Il secondo campo β = β 1, β 2, β 3, β 4, β 5, β 6, β 7, β 8 {\displaystyle \beta =\beta _{1},\beta _{2},\beta _{3},\beta _{4},\beta _{5},\beta _{6},\beta _{7},\beta _{8}} descrive un certo numero di caratteristiche dei lotti definiti come nel seguito. Il parametro β 1 2 { ∅, p m t n } {\displaystyle \beta _{1}{\mathcal {2}}\left\{\emptyset,pmtn\right\}} 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.

Il parametro β 2 { ∅, r e s } {\displaystyle \beta _{2}{\mathcal {2}}\left\{\emptyset,res\right\}} indica la presenza di risorse scarse.

Il parametro β 3 2 { ∅, p r e c, u a n, t r e e, c h a i n s } {\displaystyle \beta _{3}{\mathcal {2}}\left\{\emptyset,prec,uan,tree,chains\right\}} indica la presenza di vincoli di precedenza tra i lotti.

Il parametro β 4 2 { ∅, r j } {\displaystyle \beta _{4}{\mathcal {2}}\left\{\emptyset,r_{j}\right\}} 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.

Il parametro β 5 2 { ∅, p i j = p, m i n p ≤ p i j ≤ m a x p } {\displaystyle \beta _{5}{\mathcal {2}}\left\{\emptyset,p_{ij}=p,minp\leq p_{ij}\leq maxp\right\}} descrive il tempo per la lavorazione i-esima sulla macchina j-esima, p i j {\displaystyle p_{ij}}.

Nel caso α 1 2 { P, Q } {\displaystyle \alpha _{1}{\mathcal {2}}\left\{P,Q\right\}} il parametro p i j {\displaystyle p_{ij}} è rimpiazzato dalla notazione p i {\displaystyle p_{i}}

Il parametro β 6 2 { ∅, d ~ } {\displaystyle \beta _{6}{\mathcal {2}}\left\{\emptyset,{\tilde {d}}\right\}} indica la presenza di scadenze temporali.

Nel caso di sistemi job-shop il parametro β 7 2 { ∅, n j ≤ k } {\displaystyle \beta _{7}{\mathcal {2}}\left\{\emptyset,n_{j}\leq k\right\}} indica il numero massimo di lavorazioni che costituiscono un lotto.

Nel caso di sistemi dedicati il parametro β 8 2 { ∅, n o − w a i t } {\displaystyle \beta _{8}{\mathcal {2}}\left\{\emptyset,no-wait\right\}} indica la presenza di spazi di stoccaggio intermedi tra le macchine," buffer”, atti ad ospitare i lotti in attesa dellinizio della lavorazione successiva.