Controllo e scheduling delleoperazioni

Paolo DettiDipartimento di Ingegneria dell’Informazione

Università di Siena

PRODOTTOPRODOTTO

PROCESSOPROCESSO

FLUSSO DI PRODUZIONEFLUSSO DI PRODUZIONE

ORGANIZZAZIONEORGANIZZAZIONE

COORDINAMENTOCOORDINAMENTO

PIANIFICAZIONEPIANIFICAZIONE

SCHEDULINGSCHEDULING quandoquando

che cosache cosa chichi

Organizzazione della produzione

comecome

Sono dati:• Un insieme di lavori (job): ognuno costituito da una o più operazioni• Un insieme di risorse (macchine) che devono essere utilizzate per eseguire i lavori

Pianificazione della produzione: schedulazione di dettaglio

Scheduling delle operazioni

Scelta dei tempi di inizio e fine di ogni operazione su ogni macchina

Consideriamo:3 lavori e 3 macchine

(M3,6)(M2,5)(M1,10)J1

(M2,4)(M3,10)(M1,2)J3

-(M1,8)(M2,5)J2

Sequenza delle operazionioperazione=(macchina, tempo)

Job

Scheduling delle operazioni

Diagramma di Gantt

(M3,6)(M2,5)(M1,10)J1

(M2,4)(M3,10)(M1,2)J3

-(M1,8)(M2,5)J2

Sequenza OperazioniJob

21

10

2

5

1

15 20

3

26

1

28

3

3

12 22

M3

M2

M1

Diagramma di Gantt

(M3,6)(M2,5)(M1,10)J1

(M2,4)(M3,10)(M1,2)J3

-(M1,8)(M2,5)J2

Sequenza OperazioniJob

M3

M2

M1 23

2

1

12

2

5

1

17 20

3

21

1

23

3

Classificazione dei problemi di scheduling

Caratterizzazione dei lavori:

• tempo di processamento pj (pkj)

• data di consegna (duedate o deadline) dj

• data di rilascio (release date) rj

• peso del lavoro (priorità) wj

• tempo di set-up tra due lavori sij

Classificazione dei problemi di scheduling

Caratterizzazione delle risorse e dell’ambiente produttivo:

• macchina singola• macchine parallele

� identiche � scorrelate� uniformi

• Flow shop• Job shop

Macchina singola

LAVORI M

Macchine parallele

LAVORI

M1

M2

M3

Macchine in linea (Flow shop)

LAVORI M1 M2 Mm

EsempioM1 M2

IN OUT

EsempioM1 M2

IN OUT

Job shop

LAVORI

M1 M2

M3

Dato il lavoro i con release date e duedate:

• tempo di completamento Ci

• tempo di attraversamento Fi= Ci – ri

• Lateness Li= Ci – di

• Tardiness Ti= max{ 0, Ci – di }• Earliness Ei= max{ 0, di – Ci } • Lavori in ritardo Ui= 1 se Ci > di

Ui= 0 se Ci ≤≤≤≤ di

Misure di prestazione(lavori)

Li < 0 di

Li > 0

Cianticipo ritardo

Ci- di

Li(Ci)

Ritardo del lavoro i : Li = Ci-di

di: tempo di consegna (duedate) per il lavoro i

Lateness(Ritardo)

• somma dei tempi di completamento: ΣΣΣΣiCi

• flow time totale: ΣΣΣΣi Fi

• massima Lateness: Lmax = maxi Li

• massima Tardiness: Tmax = maxi Ti

•Tardiness totale pesata ΣΣΣΣi wi Ti

• makespan Cmax = maxi Ci

• numero di lavori in ritardo ΣΣΣΣi Ui

Misure di prestazione(sistema)

Equivalenza tra misure

Misure di prestazione

( )�����=====

−+=−=n

iii

n

ii

n

ii

n

ii

n

ii drFdCL

11111

Misure di prestazione

{ }{ } { }{ }

{ } { }0,max0,,...,max0,max,...,0,maxmax

0,,...,max

max1

1

1max

LLLLL

TTT

n

n

n

===

==

Una sol. che minimizza Lmax minimizza anche

Tmax (ma, in generale, non è vero il viceversa):

Scheduling su singola macchina

Descrizione del problemaUn insieme di n operazioni deve essere eseguito su una macchina

DatiI tempi di processamento pi, i=1,…,n, del lavoro i sulla macchina sono noti.

ObiettivoSequenziare le operazioni sulla macchina in modo da minimizzare la somma dei tempi di completamento.

min ΣΣΣΣiCi

Gantt del Sequenziamento

p4 pn

Cn=Σi pi: tempo di completamento totale (makespan)

tempoop1

C1

p1

op2

C2

p2

C3

p3

op4

C4 Cn

opn

Sequenza S

op3

Obiettivo: min ΣΣΣΣiCi

pn

p4 pn

tempo

op1

C1

p1

op2

C2

p2

C3

p3

op4

C4 Cn

opnop3

op1tempoC3

op3

p3

op4

C4

p4

Cn

opn

C2

p1

C1

op2

p2

op1

se p2 < p1 allora scambiando le op. 1 e 2 si haC2< C1 e C1= C2

C2 + C1 < C2 + C1

S

S’

Regola SPT (shortest processing time first)

SPT: sequenzia prima le operazioni che hanno tempo di esecuzione più piccolo

Consente di minimizzare la somma dei tempi di completamento ΣΣΣΣiCi di n operazioni (lavori) su una macchina

Esempio

2710168pi

54321Lavori

Sequenza ottima (5, 4, 1, 3, 2)

Scheduling su singola macchinaDescrizione del problemaUn insieme di n operazioni devono essere eseguiti su una macchina

DatiI tempi di processamento pi, i=1,…,n, del lavoro i sulla macchina sono noti.Peso wi, i=1,…,n, associato ad ogni lavoro.

ObiettivoSequenziare le operazioni sulla macchina in modo da minimizzare:

min ΣΣΣΣiwiCi

Regola WSPT (weighted shortest processing time)

WSPT: sequenzia prima i lavori che hanno il più piccolo rapporto:

Consente di minimizzare la somma pesata dei tempi di completamento ΣΣΣΣwiCi

i

iwp

Sia pi/ wi > pk/ wk consideriamo i due casi:1. Il lavoro k è sequenziato subito dopo i

2. Il lavoro i è sequenziato subito dopo k

Regola WSPT

DpwpwpwAwwBppAwpAwBobf

ppACpAC

iikikkki

ikikk

ikikk

++++++=+++++=

++=+=

)()()(..

' e '

DpwpwpwAwwBDppAwpAwBobf

ppACpAC

kkikiiki

kikii

kikii

++++++=++++++=

++=+=

)()()(..

e

Se pi/ wi > pk/ wk allora wkpi > wi pk

Regola WSPT

)2.(.)1.(.

0)2.(.)1.(.

obfobf

pwpwobfobf kiik

>�

>−=−

Macchine parallele

LAVORI

M1

M2

M3

J1 J2

J3 J4

Descrizione del probleman lavori devono essere processati da m macchine diverse (unrelated) disposte parallelo.Le macchine possono eseguire un solo lavoro alla volta. Ogni lavoro deve essere eseguito su una ed una sola macchina senza interruzione.

DatiI tempi di processamento pij, i=1,…, m, del lavoro j sulla macchina i sono noti.

ObiettivoAssegnare i lavori alle macchine in modo tale da minimizzare il tempo totale di completamento della macchina più carica (equivalente a minimizzare il makespan).

Scheduling su macchine parallele scorrelate

Esempio

1 2 3 4 51 12 17 19 15 142 30 17 16 31 173 28 27 28 23 27

Lavori

Macchine

M3

M2

M1 J1 J4

J3

t

J5

34

J2

Una soluzione ammissibile

Esempio

1 2 3 4 51 12 17 19 15 142 30 17 16 31 173 28 27 28 23 27

Lavori

Macchine

M3

M2

M1 J1 J4

J2

t

J5

33

J3

Una soluzione ottima

Il problema è NP-completo anche con due macchine identiche

• m=2

•

Complessità

mipp jij ,...,1 ==

Definizione delle variabili

Ci , i=1,…, m, tempo di completamento della macchina i

Una formulazione di PLI

���

=altrimenti 0

macchina alla assegnato è lavoro il se 1 ij xij

{ } sistema il tutto di ntocompletame di tempo max ,...,1max imi CC ==

Nota: il tempo di completamento della macchina più carica corrisponde al tempo di completamento del lavoro che finisce per ultimo

Definizione delle variabili

Il tempo di completamento Ci della generica macchina i è pari a:

Formulazione del Problema

�=

=n

jijiji xpC

1

{ }���

���

== �=

==

n

jijijmiimi xpCC

1,...,1,...,1max maxmax

Una formulazione del Problema

{ }

{ }1,0

1 1

che tale

maxminmin

1

1,...,1max

∈

==

�

��

�

��

���

���

=

�

�

=

==

ij

m

iij

n

jijijmi

x

,...,njx

xpC

Una formulazione di PLI

{ }1,0

1 1

1

che tale min

1

1

∈

==

=≤=

�

�

=

=

ij

m

iij

n

jijiji

x

,...,njx

,...,miWxpC

W

ASSEGNAMENTO DELLE OPERAZIONI DI TAGLIO NELLA PRODUZIONE DI

CAPI DI ABBIGLIAMENTO

Lo scenario produttivo

• La PAL ZILERI produce capi diabbigliamento per l’alta moda

• Ogni capo è costituito da vari pezzidi tessuto (figure)

• Le figure vanno tagliate da un nastroche scorre a velocità costante v0

Lo scenario produttivo

• La disposizione delle figure sulnastro è nota a priori (cutting stockrisolto a monte)

• Il taglio delle figure è effettuato da un insieme di macchine identichedisposte in linea

• Ciascuna macchina ha un’area dilavoro di lunghezza Ws

Piazzamento

Lo scenario produttivo

Ws

figure

Stazioni di lavoro

1

Area di lavoro

•V0 = 12.5 cm/sec• Ws = 2.5 m

2 m

Il problema decisionale

• Il problema è quello di assegnare le figure alle macchine, e di sequenziare i tagli suciascuna macchina

• Ciascun taglio deve avvenire entro unadeterminata finestra temporale (diversa a seconda della macchina cui è assegnatala figura) di ampiezza Ws/v0

Il problema decisionale

• Tra il taglio di una figura e la successiva intercorre un tempo diswitch dipendente dalla sequenza

• Gli obiettivi:– minimizzare il numero di macchine– bilanciare i carichi di lavoro

Il problema decisionale

• L’insieme delle figure relative a unostesso capo e la loro disposizione sultessuto (piazzamento) giungono in tempo reale

• L’assegnamento va deciso in pocotempo (30 sec.)

• Problema decisionale on line

Modello combinatorio

1

11

2

2

23

3

3

4

4

455

66

6

6

Modello combinatorio

Modello combinatorio

Metodologie di soluzione

• Due approcci risolutivi• Approccio esatto, basato su metodi

di programmazione a numeri interi• Approccio euristico, basato su

algoritmi di instradamento push epull

Approccio esatto

• Il problema è simile a un problema divehicle routing con time windows

• Generalizzazione del problema del commesso viaggiatore

• Problema difficile

Approccio esatto

• Sia m l’insieme di tutti i sottoinsiemi di figure che possono essere tagliati da una solamacchina entro la propria finestra temporale(itinerari)

• Ad ogni itinerario è associato un dato insiemedi figure da tagliare

• xk è una variabile di decisione che è pari a 1 se l’itinerario k è assegnato ad una macchina

• La somma Σk xk esprime il numero di itinerari, ossia il numero di macchine

Sia {1,…, n} l’insieme di figure di un piazzamento.

Sia A = {A1,…,Am} una matrice n × m, in cui la generica colonna Ak descrive un itinerario possibile per una macchina. A ha componenti:

Una formulazione di set covering

1 se la figura j è assegnata all’itinerario kajk=

0 altrimenti

{ } ,..., mkx

,..., njxa

x

k

m

kkjk

m

kk

1 1,0

1 1

min

1

1

=∈

=≥�

�

=

=

Sia xk pari a 1 se la colonna Ak è selezionata e 0 altrimenti. Una formulazione del problema è:

(Barnhart C. et al., 1994; Chen, Z.L. and Powell,W.B., 1999; Van den AkkerJ.M. et al., 1999)

Una formulazione di set covering

Approccio esatto

• m è il numero (elevatissimo) dipossibili itinerari

• Anche enumerandoli tutti, occorrerisolvere un problema intero dielevatissime dimensioni>>> generazione di colonne

,...,mkx,...,mkx

,...,njxa

x

k

k

m

kkjk

m

kk

1 0 1 1

1 1

min

1

1

=≥=≤

=≥�

�

=

=

Primale Duale

Generazione di Colonne

1 0

1 1

max

1

1

,...,nju

,...,mkua

u

j

n

jjjk

n

jj

=≥

=≤�

�

=

=

Sia u* la soluzione del problema duale (ristretto).

Un vincolo duale è violato dalla corrente soluzione duale se:

11

* >�=

n

jjk j

ua

Problema di separazione per generare un vincolo duale violatodalla corrente soluzione duale

Un metodo di generazione di colonne

{ }

macchina una su tutte eseguite essere

possono 1)( scelte figure le

1,0

max1

*

=

∈

�=

j

j

n

jj

a

achetale

uaj

Il problema di separazione per generare un vincoloduale violato e quindi una nuova colonna del primaleè:

Un metodo di generazione di colonne

||1*jj

jjijj

uw

Uwsr

=�

Nota che rj e dj sono agreeable (le finestre temporali diogni figura sono tutte lunghe Ws/σ), cioè:

ijij ddrr ≤⇔≤

Problema di separazione senza tempi di set-up (1|rj|ΣwjUj )

Esiste un algoritmo di programmzione dinamica(Lawler and Moore, 1969) per il risolvere il problema1||ΣwjUj

Tale algoritmo può essere esteso al problema1|rj|ΣwjUj se release date e duedate dei lavori sonoagreeable

Un algoritmo di programmazione dinamica

Supponiamo di ordinare i job in modo che d1 ≤≤≤≤ d2 ≤≤≤≤ … ≤≤≤≤ dn (r1 ≤≤≤≤r2 ≤≤≤≤ … ≤≤≤≤ rn)

Sia P(j, t) la soluzione ottima del problema 1|rj|ΣwjUj in cui sonoconsiderati solo i primi j job, ed in cui il tempo totale dicompletamento dei job in tempo è al più t

( )( )

( ) ( ){ }( )

t ,

,1; ,1max

,1

, *

�

�

�

>≤≤+−+−−

+<−=

jj

jjjjj

jj

ddjPdtprtjPuptjP

prttjP

tjP

Metodologie di soluzione

Approccio euristico basato sualgoritmi di instradamento push epull

Applicazione euristica push

1. Si individua la prossima figura daassegnare

2. La figura seleziona una macchina3. La macchina inserisce la figura nel

proprio schedule

push: ordinamento delle figure

• LPT in ordine decrescente di tempo di taglio

• EDD in ordine di uscita dal sistema• ERD in ordine di entrata nel sistema

• ti istante in cui Mi diviene disponibile• Sij = max{rij, ti + cij}

primo istante in cui può iniziare la figura j se assegnata a Mi

• Qij = Sij - ti (idle)

tti

Set-up

Idle: Qij = Sij - ti

Ultima figura tagliata

Sij

Earliest start time per la figura j

ti+cij

push: selezione della macchina

La figura j corrente sceglie la macchina:

• min Ci che si libera prima• min Wi con il minimo carico di lavoro• min Qij che è in grado di tagliare la figura

j col minimo idle

Applicazione euristica pull

1. Si individua la prossima macchina a cui allocare un lavoro

2. La macchina seleziona una figura3. La macchina inserisce la figura nel

proprio schedule

pull: ordinamento delle macchine

La macchina che opera la scelta è quella:

• min Ci che si libera prima

pull: selezione della figura

La macchina Mi corrente sceglie la figura, tra quelle non allocate:

• EDD che uscirà prima dal sistema• ERD che entrerà prima nel sistema• min Qij la figura j che è in grado di tagliare col minimo idle

Inserimento della figura

• In ambedue gli approcci, quando sidetermina un accoppiamentofigura/macchina, la figura deveessere inserita nello schedule corrente della macchina

Inserimento della figura

• INS1 (EDD) le figure sono tagliate in ordine di entrata nel sistema

• INS2 (FIFO) le figure sono tagliate nell’ordine in cui sono state allocate

Ordinamentodelle figure

Selezione macchina Inserim.

Push1 LPT min WiEDD

Push2 EDD min Qij FIFO

Push3 EDD min CiFIFO

Push4 EDD min WiFIFO

Push5 ERD min WiEDD

Euristiche push

Euristiche pull

Ordinamento dellemacchine

Selezione figure Inserim.

Pull 1 min Ci EDD FIFO

Pull 2 min Ci min Qij FIFO

Pull 3 min Ci ERD FIFO

)( jkjjj ptDE +−=

Indici di performance

earliness della figura fjprocessata sulla macchina Mk

jBf EEj ∈

= minmin

n

E

E Bfj

j

�∈=

tempo di completamento del piazzamento

( )imi CC ,..,1maxmax ==

minima earliness del piazzamento

earliness media del piazzamento

m numero di macchine

Istanze reali

• Istanza R1: 624 figure raggruppate in 12 piazzamenti

• Istanza R2: 896 figure raggruppate in 16 piazzamenti

7

Push1 Push2 Push3 Push4 Push5

Emin 1.7 5.9 6.2 1.4

E 10.1 11.7 13.5 11.4 9.8

Cmax 31.5 28.2 28.4 29.2 30.8

m 6 6 6 6 6

Algoritmi push per l’istanza R1

7.4

Pull1 Pull2 Pull3

Emin 6.9 5.9

E 11.2 15 13.5

Cmax 28.5 29.1 28.3

m 6 7 6

Algoritmi pull per l’istanza R1

6.5

Push1 Push2 Push3 Push4 Push5

Emin 1.3 6.2 5.3 0.9

E 10.7 12.4 14.2 12.1 10.4

Cmax 35 29.2 29.3 32.3 34.7

m 7 7 7 7 7

Algoritmi push per l’istanza R2

6.1

Pull1 Pull2 Pull3

Emin 6.3 6.2

E 11.4 14.3 14.1

Cmax 29 30.1 29.5

m 7 7 7

Algoritmi pull per l’istanza R2