Notazione per i problemi di schedulazione

Template:C 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 del 1979 per identificare le tipologie dei problema di schedulazione. Lo schema di classificazione fa ricorso a tre campi $\alpha |\beta |\gamma$ 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 $L_1,L_2,\dots ,L_n$ da lavorare per mezzo di m macchine $M_1,M_2,\dots ,M_m$ 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 $\alpha ={\alpha }_1{\alpha }_2$ specifica l'ambiente delle macchine.

Il parametro ${\alpha }_{1}2\{\mathrm{\varnothing },P,Q,R,O,F,J\}$ caratterizza il tipo di macchina utilizzato:

${\alpha }_1$	=$\mathrm{\varnothing }$	macchina singola
${\alpha }_1$	=P	macchine identiche
${\alpha }_1$	=Q	macchine uniformi
${\alpha }_1$	=R	macchine incorrelate
${\alpha }_1$	=O	macchine dedicate-sistema open shop
${\alpha }_1$	=F	macchine dedicate-sistema flow shop
${\alpha }_1$	=J	macchine dedicate-sistema job shop

Il parametro ${\alpha }_{2}2\{\mathrm{\varnothing },m\}$ caratterizza il numero di macchine nel problema:

${\alpha }_2$	=$\mathrm{\varnothing }$	il numero delle macchine è variabile e fa parte degli input del problema
${\alpha }_2$	=m	il numero delle macchine è costante ed uguale ad un numero intero positivo m

Si osservi che ${\alpha }_1=\mathrm{\varnothing }$ se e solo se ${\alpha }_2=1$

Caratteristica dei lotti

Il secondo campo $\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 ${\beta }_{1}2\{\mathrm{\varnothing },pmtn\}$ 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).

${\beta }_1$	=$\mathrm{\varnothing }$	la preemption non è ammessa
${\beta }_1$	=pmtn	le preemptions sono ammesse

Il parametro ${\beta }_{2}2\{\mathrm{\varnothing },res\}$ indica la presenza di risorse scarse.

${\beta }_2$	=$\mathrm{\varnothing }$	non è specificato alcun vincolo sulle risorse
${\beta }_2$	=res	sono specificati vincoli sulle risorse

Il parametro ${\beta }_{3}2\{\mathrm{\varnothing },prec,uan,tree,chains\}$ indica la presenza di vincoli di precedenza tra i lotti.

Il parametro ${\beta }_{4}2\{\mathrm{\varnothing },r_j\}$ 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.

${\beta }_4$	=$\mathrm{\varnothing }$	si ipotizza che tutti i ready time sono nulli ovvero tutti i lotti sono disponibili alla lavorazione nello stesso istante
${\beta }_4$	=$r_j$	vengono specificati i tempi al pronto, tempi che possono differire da lotto a lotto j=1,...,n

Il parametro ${\beta }_{5}2\{\mathrm{\varnothing },p_{ij}=p,minp\le p_{ij}\le maxp\}$ descrive il tempo per la lavorazione i-esima sulla macchina j-esima, $p_{ij}$.

${\beta }_5$	=$\mathrm{\varnothing }$	i lotti presentano tempi di lavorazione arbitrari
${\beta }_5$	=$p_{ij}=p$	tutti i lotti presentano lo stesso tempo di lavorazione pari a p
${\beta }_5$	=$minp\le p_{ij}\le maxp$	nessun tempo di lavorazione $p_{ij}$ è inferiore a min p o superiore a max p

Nel caso ${\alpha }_{1}2\{P,Q\}$ il parametro $p_{ij}$ è rimpiazzato dalla notazione $p_i$

Il parametro ${\beta }_{6}2\{\mathrm{\varnothing },\tilde{d}\}$ indica la presenza di scadenze temporali.

${\beta }_6$	=$\mathrm{\varnothing }$	non esistono scadenze temporali nel sistema
${\beta }_6$	=$\tilde{d}$	scadenze temporali sono imposte all'ultimazione delle operazioni

Nel caso di sistemi job-shop il parametro ${\beta }_{7}2\{\mathrm{\varnothing },n_j\le k\}$ indica il numero massimo di lavorazioni che costituiscono un lotto.

${\beta }_7$	=$\mathrm{\varnothing }$	il numero di lavorazioni per ogni lotto è arbitrario oppure il sistema non è di tipo job-shop
${\beta }_7$	=$n_j\le k$	il numero di lavorazioni per ogni lotto non è superiore a k

Nel caso di sistemi dedicati il parametro ${\beta }_{8}2\{\mathrm{\varnothing },no-wait\}$ indica la presenza di spazi di stoccaggio intermedi tra le macchine, “buffer”, atti ad ospitare i lotti in attesa dell'inizio della lavorazione successiva.

${\beta }_8$	=$\mathrm{\varnothing }$	si è in presenza di buffer dalla capacità illimitata
${\beta }_8$	=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 $\gamma$ denota il criterio di prestazione adottato.

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