Logistica 2

Università degli Studi di Trieste Piazzale Europa 1, 34100 Trieste Facoltà di INGEGNERIA Corso di Laurea in INGEGNERIA INFORMATICA Anno Accademico 2004/2005

Logistica 2

Studente: Giorgio Davanzo [email protected]

Docente: Prof. Pestelli

LOGISTICA II

1 di Giorgio DAVANZO

MRP: MRP: Materials Requirement Planning; si decide la disponibilità dei materiali. Metodologie: si può usare un procedimento EURISTICO (conoscenza esatta della domanda nel breve periodo) o uno ESATTO (conoscenza esatta nel lungo periodo). Metodi Euristici: K costo di riordino, h costo mantenimento al giorno, ri domanda da soddisfare in i • Silver Meal: trova il minimo costo medio per periodo; G(j) = (K+ h r2 + 2 h r3 + ....+ (j-1) h rj )/j si riordina nel periodo j° che è minimo locale, cioè G(j°-1) > G(j°) e G(j°) < G(j°+1) • Least Unit Cost: G(j) = (K+ h r2 + 2 h r3+...+(j-1) h rj )/ (r1 +r2+...+ rj) cerca il minimo per il costo medio per prodotto; si riordina in J° minimo locale. • Part Period Balancing: costi di mantenimento = costi di riordino. G(j) = h r2 + 2 h r3 + ....+ (j-1) h rj si riordina in J° primo minimo locale di |K - G(J)| Metodo Esatto – Wagner Within: si risolve con un grafo. • si crea un nodo per ogni giorno e uno finale detto dummy; all’interno segno la domanda per quel giorno. • si crea un arco per ogni coppia di nodi i,j con j > i • ad ogni arco (i,j) associo il costo che pagherei il giorno i per un lotto che dura fino a j-1 • cerco il percorso minimo Ædijkstra: si parte dall’inizio, e si assegna ad ogni nodo un valore temporaneo dato dal tempo necessario a raggiungerlo secondo l’arco che li unisce, poi si marca il valore minimo come definitivo; ora si parte da quello marcato come minimo e si ripete per ogni nodo a lui connesso, cambiando il valore assegnato se questo è minore del precedente e ricalcolando il minimo tra quelli non già segnati. MRP a capacità finita: se non si ha una capacità produttiva ∞, forse conviene anticipare certi ordini. • Verifica: si può soddisfare la domanda senza ritardo se Domanda Cumulata(T)≤CapacitàCumulata(T) ∀ T. Non basta controllare in T = Tfin , perché potrei non soddisfare alcuni ordini centrali. • Anticipazione: FOR (T:=Tfin ; T>0; T--) {anticipo ordini se serve} Capacità Comuni – metodo esatto: se certi prodotti dipendono dalla stessa squadra di montaggio, conviene aggregare i prodotti e ragionare come minuti-squadra. Devo minimizzare ∀ elemento i suoi costi, cioè trovare min [Σi∈NΣt∈T CostiRiordino(i,t) + CostiMagazzino (i,t)] con N=num. totale elementi e T=durata indafine. CostiRiordino(i,t) = KiYi t cioè ∀i il giorno t pago costi fissi solo se ho acquistato/prodotto almeno un’unita di i CostiMagazzino(i,t) = hi Ii t ∀i il giorno t pago costi di mantenimento proporzionali al numero di pezzi i che ho. Per default, assegno al prodotto finito i = 1. Vincoli: • Prodotto finito: soddisfare la domanda, cioè ∀t R(t) + Ii t = X i t + Ii (t-1) con Xi t # prodotti finiti realizzati in t e Ii (t-1) unità in magazzino • Soddisfare la domanda del prodotto intermedio: questa dipende dalla domanda del prodotto padre; • Rispettare le capacità • Considerare i set-up • Positività ed Interezza delle variabili

CPM e PERT: CPM: Critical Path Method PERT: Project Evaluation and Review Technique Rappresentare un progetto: si usa un grafo • ogni arco è un’attività, sopra vi è indicata la durata • ogni nodo è un evento, dentro vi sono scritti gli estremi temporali in cui deve occorrere l’evento • non ci possono essere oggetti con entrambi i nodi in comune, né parallelismi Æ si inseriscono attività dummy di durata nulla. • Estremo Inferiore: è l’earliest starting time; quello iniziale (sx grafico) = 0, i successivi sono la somma della durata delle attività che portano al nodo partendo dall’inizio progetto; se più rami portano allo stesso nodo, si sceglie il valore maggiore. • Estremo Superiore: è il latest completion time; quello finale (dx grafico) = ES(finale), i precedenti sono la differenza tra l’ultimo e la durata che porterà ad esso (si procede alla rovescia); se più rami portano allo stesso nodo, si sceglie il valore minore.

2 LOGISTICA II • Percorso critico: è quello che unisce i nodi con ES = LC PERT: è un metodo statistico; ad ogni arco sono associate durata media attesa e deviazione della durata, di solito calcolate sulla distribuzione gamma: m = valore + probabile, a = durata minima, b = durata massima • durata media: µ = (a + 4m + b)/6 • deviazione della durata: σ = (b - a)/6

SCHEDULAZIONE: Terminologia: • task: operazione elementare di lavorazione; • job: insieme parzialmente ordinato di task che descrivono una lavorazione complessa; • machina: una risorsa che può eseguire al massimo una attività (task) alla volta; le macchine possono essere messe in serie, parallelo o Bucket Brigade (brigata dei secchi, come i pompieri. Se una macchina è affamata perché un’altra non ha finito, le ruba il lavoro) • starvation: macchina che non ha niente su cui lavorare • scheduling ammissibile: rispetta tutti i vincoli • scheduling ottimo: minimizza un dato criterio • caratteristiche dei task: Release Time [ri] (data di inizio), Due Date [di] (data di consegna violabile ma con penale), Dead Line [Di] (data di consegna non violabile) e Processing Time [Pi] (tempo di esecuzione) • variabile principale: Ci tempo di completamento • preemption: è possibile sospendere un task per farne un altro Dati: • Tardiness Ti = ritardo = (Ci – di)+ è >0 se >0, 0 se ≤ 0; • Earliness Ei = anticipo = (di – Ci)+; • Lateness Li = tempo di ritardo = Ci – di Misure: • Semi Attivo: non è possibile anticipare l’esecuzione di un job senza alterare la sequenza degli stessi • Attivo: non è possibile anticipare l’esecuzione di un job anche alterando la sequenza degli stessi Notazione: Tipo Problema / caratteristiche job o task/ obiettivo tipo problema: caratteristiche job: obiettivo: – 1: singola macchina – P m: macchine parallele (generico) – F n: flow shop di n task su n macchine – J n job shop (ordine diverso per ogni job) su n macchine – O open shop (non vi è ordine nelle operazioni di un job)

– pmtn: è ammessa la preemption – prec: esistono precedenze tra i task dei job o tra i job – ri: i job hanno release time diverso da zero, – Di : i job hanno deadline diversa da infinito, – pi=1: tutti i job hanno tempo di esecuzione 1

– Tmax, : minimizzare tardiness massima –ΣiTi : minimizzare tardiness media –ΣiwiCi: minimizzare tempi di completamento pesati

1/ / Σi Ci : minimizzare il tempo medio di completamento su singola macchina di job con identica release time; si risolve con Shortes Processing Time First, cioè si ordinano i job svolgendo prima i più rapidi 1/ / Σi wiCi : wi sono i pesi – peso > = lavoro + importante. Si usa la Politca di Smith, ordinando in modo crescente il rapporto Pi / wi 1/ / Lmax : minimizzare la lateness massima (e quindi anche della tardiness massima ) su singola macchina di job con identica release time ma due date diverse; si risolve con Earliest Due Date first: si eseguono prima i job con due date più piccola 1/ / ΣiUi : minimizzare il numero di job che sono tardy, si risolve con Algoritmo di Moore: • ordinare i job per EDD (Di) • se un job supera la Dead Line, elimino tra i precedenti il più lungo (potrebbe essere il job stesso) 1/ prec / maxigi(ci) : minimizzare il valore massimo assunto da certe misure gi per job su singola macchina con identica release time ma in presenza di precedenze. 1. dall’insieme J dei job determinare l’insieme V dei job che non precedono altri job non ancora schedulati 2. determinare il job k in V t.c.: gk( τ) = mink∈V gk(τ) con τ = Σi∈ J pi 3. porre J = J \{k} ; se |J| > 0 tornare a 1), altrimenti stop 1/ Di=D /ΣiEi : minimizzare l’earliness media su singola macchina di job con identica release time e identica deadline. Si risolve con Longest Processing Time first, eseguendo prima i job più lunghi

3 1/ di=d / Σi(Ei+Ti) : minimizzazare l’earliness e tardiness media su singola macchina di job con identica release time e identica due date. Si risolve con l’algoritmo di V-shaped 1. ordinare i job per LPT 2. porre i job in posizione dispari, ordinati per LPT, prima della due date in modo che il completion time dell’ultimo tra questi job coincida con la due date stessa; 3. porre i job in posizione pari, ordinati per SPT, dopo la due date in modo che lo starting time del primo tra questi job coincida con la due date stessa. SetUp Time – Critical Ratio: minimizza i costi di set-up su singola macchina di job con identica release time; ad ogni istante schedula in base all’urgenza dei task, dove per urgenza si intende il rapporto: tempo esecuzione /(due date - tempo corrente) = pi / (di - t); se vi sono rapporti negativi e positivi, si preferiscono i negativi e si schedulano i job associati a tali valori secondo SPT.

LOGISTICA II

SCHEDULAZIONE – PIU’ MACCHINE: P/ / Σi Ci : si usa sempre SPT, eseguendo per primi i task con tempo di esecuzione minore assegnandoli alla prima macchina disponibile. P/ / Cmax : è difficile, alg. euristico LPT P/ pmtn / Cmax : è risolto dall’algoritmo wrap-around di McNaughton (estendibile opportunamente al caso di macchine uniformi) riempiendo quindi le macchine successivamente fino a soddisfare Cmax* = (Σi pi)/num macchine , spezzando tra una macchina e la successiva i job che eventualmente violano tale valore (ovviamente si esegue prima il pezzo creato sulla macchina successiva). Se ∃pi > Cmax* non posso spezzare il job (non posso fare contemporaneamente parti dello stesso job) Æ occuperò un Cmax > Cmax*. In questo caso vi sono al massimo ( m-1) preemption. È NP-hard determinare uno scheduling ottimo che minimizzi il numero di preemption. P/ prec / Cmax : si disegna un grafo che ha un nodo per ogni job e al suo interno la pi, gli archi indicano le precedenze; si crea un ordine qualunque e si cerca di migliorarlo :-P

ROUTING: Euristiche: Le euristiche usate sono costruttive se creano il circuito hamiltoniano, di miglioramento se migliorano uno esistente; con distanze euclidee, un circuito ottimo non contiene incroci. Nearest Neighbor: si parte da un nodo e si passa al più vicino ad esso. Nearest Neighbor a doppia crescita: una volta creato il primo arco, si procede facendo crescere contemporaneamente entrambi gli estremi. Nodo più lontano: è un algoritmo di inserimento. 1. Si uniscono in un circuito di A/R i due nodi a distanza massima 2. ∀ nodo libero si elencano tutte le distanze dai due nodi, e si sceglie di inserire quello che ha distanza > 3. ora si tratta di decidere dove inserirlo, cioè che arco connettere; lo si inserisce dove la variazione di percorso causa la minor variazione (quando ho solo due nodi, è indifferente come lo metto!) Doppio albero ricoprente: 1. si crea un albero ricoprente minimo 2. si raddoppiano gli archi in modo da avere percorsi di A/R per ogni unione di nodi 3. si descrive il percorso così formato e si eliminano le ripetizioni dei nodi già visitati Christofides: 1. si crea un albero ricoprente minimo 2. si evidenziano i nodi che hanno un numero dispari di archi 3. si connettono i nodi tra loro finché non si hanno solo nodi pari 4. si scrive il percorso così tracciato e si eliminano le ripetizioni 2 – OPT: è un metodo euristico 1. si crea un circuito hamiltoniano 2. si eliminano due rami e si ricongiungono i due semicircuiti; se così facendo miglioro salvo la modifica