Università degli Studi di Napoli Facoltà di Ingegneria Corso di Laurea in Ingegneria Meccanica - Gestionale Cattedra di GESTIONE DELLA PRODUZIONE INDUSTRIALE LA PROGRAMMAZIONE OPERATIVA APPLICAZIONE DELLE TECNICHE DI SCHEDULING Docente Prof. Ing. Liberatina C. Santillo Consulente industriale Dott. Ing.Ferdinando Palazzo Collaboratori Dott.Ing. Teresa Murino Dott. Ing. Sergio Gallo Anno Accademico 2001/2002 La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Strumenti Bibliografia [1] Brandolese, Gestione della produzione industriale, HOEPLI, Milano, 1991. [2] Levy, MRP II logica e implementazione, Franco Angeli, Milano 1993. [3] Baker, Introduction to sequencing & scheduling, John Wiley & Sons, New York, 1974. [4] Johnson S. M., Optimal two and three stage production schedules with setup times included, Naval Research Logistics Quarterly, vol. 1, 1954. [5] Campbell H.G., Dudek R.A., Smith M.L., A heuristic algorithm for the n job machine sequencing problem, Management Science. [6] Bongaerts L., Valkenaers P., Wyns J.,1995. [7] A. Grando, Produzione e logistica, UTET, Milano, 1996. [8] Masturzi. Organizzazione e gestione della produzione industriale ,vol.III. Liguori editore,1990 Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Strumenti Lettura di approfondimento Scheduling di Michael Pinedo Problem solving [email protected] Tel. 3381884886 Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Introduzione OBIETTIVI • Ridurre il tempo di raccolta dati • Aumentare il tempo e la correttezza delle decisioni • Aumentare gli standard qualitativi dei servizi e/o dei prodotti • Realizzare report efficaci OBIETTIVO DELLA RICERCA INDUSTRIALE Sviluppo ed applicazione di sistemi Software basati su tecnologia WEB e tecniche innovative di scheduling Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Introduzione DECISION SUPPORT SYSTEM Un DSS è un sistema software che richiede una stretta interazione on-line con l’utente per assisterlo in processi decisionali complessi e vincolati senza sostituirsi ad esso L’obiettivo è quello di migliorare l’efficacia della decisione Generalmente include tre sottosistemi : • di gestione dei dati • di gestione dei modelli • di interfaccia utente Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Introduzione RUOLO DELL’ANALISTA E DEL DECISORE Mondo simbolico Analista Analisi Risultati Decision Maker Situazione Decisionale Mondo reale Ing. Ferdinando Palazzo Intuizione Interpretazione Astrazione Modello Decisione La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Introduzione STRUTTURA CONCETTUALE DI UN DSS Domanda (1) (2) (3) Linguaggio Raccolta di informazioni Riconoscimento del problema Formulazione del modello Decisore Informazioni memorizzate circa il dominio del problema Analisi ……… DSS Risultato (1) Linguaggio del sistema (2) Sistema di risoluzione del problema (3) Sistema di conoscenza Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Metodologie e strumenti IL DATAWAREHOUSE E’ un nuovo sistema di supporto decisionale ed in questo si colloca non solo come una novità tecnologica ma anche strategica In che modo? Rivoluzionando l’attività di analisi, permette di navigare attraverso differenti viste di dati elaborate da altrettante diverse modalità di aggregazione Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Metodologie e strumenti L’AMBIENTE INFORMATIVO STRATEGICO ED INTEGRATO Magazzino Marketing Prodotti Data Warehouse Aziendale Finanza Ordini Vendite Contatti Data Marts settoriali Dati esterni e non strutturati Cassa Situazione precedente/ Aree di Business Metadati Tecnici e di Business Ambiente Operativo Ing. Ferdinando Palazzo Ambiente Warehouse Data Marts Personalizzati 4 La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Tecnologia innovativa SCHEMA DEL FLUSSO DI INFORMAZIONE Acquisizione dei dati UI Connessione ed CPU Presentazione del risultato Ing. Ferdinando Palazzo Composizione Stringa di ricerca Formattazione risultato DB ottenimento risultato La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Strumenti DIAGRAMMA DI GANTT La durata delle singole attività è indicata dalla lunghezza delle barre, mentre le relazioni di dipendenza tra due attività sono solitamente rappresentate da frecce, gli eventi significativi del progetto sono evidenziati infine da contrassegni di forma romboidale Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Strumenti DIAGRAMMA WBS Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Strumenti Ing. Ferdinando Palazzo ATTIVITA’ DEL PROGETTO La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Strumenti Ing. Ferdinando Palazzo Schema generico della fase progettuale ed operativa La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Strumenti DIAGRAMMA DI GANTT MACCHINA 1 I J MACCHINA 2 MACCHINA 1 MACCHINA 2 Ing. Ferdinando Palazzo J I J I J I La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Strumenti MACCHINA 1 DIAGRAMMA DI GANTT J I MACCHINA 2 MACCHINA 1 MACCHINA 2 Ing. Ferdinando Palazzo I I J J J I La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Introduzione CARATTERISTICHE DEI PROTOTIPI ATTUALMENTE VENDUTI • VISIBILITA’ • SCALABILITA’ • ADOTTABILITA’ • FLESSIBILITA’ Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Strumenti ESEMPI DI PROTOTIPI TENDENZA INDUSTRIALE ATTUALE : • TECNICA DRAG AND DROP • MONITORAGGIO RISORSE • SPEECH ENGINE Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Definizioni La programmazione operativa Fa riferimento al breve periodo Si articola in tre momenti principali : • loading • sequencing • scheduling Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Definizioni Fase di loading Nella fase di allocazione (loading) delle operazioni sulle singole risorse disponibili, nota l’entità di ciascun ordine e, quindi, il relativo fabbisogno di macchine e di attrezzature, si verifica la possibilità di soddisfare tale fabbisogno con le risorse disponibili ripartendo l’insieme degli ordini tra le singole stazioni di lavoro In sintesi Significa l’assegnare i job ai centri di processamento. Una corretta assegnazione è tale da minimizzare i costi, l’idle time ed i tempi di completamento Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Definizioni Fase di sequencing Nella fase di sequencing si ricerca, per ogni centro di lavoro, la sequenza secondo la quale conviene che vengano eseguiti gli ordini in precedenza attribuiti a tale centro Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Definizioni Fase di scheduling Nella fase di scheduling vero e proprio, a ciascun ordine, oramai assegnato ad uno specifico centro ed al quale compete una specifica posizione nella sequenza produttiva, viene associato un istante di inizio ed uno di fine lavorazione Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Cause ed effetti IN PRATICA… Non sempre è necessario affrontare tutte le fasi sopra riportate. Ad esempio è evidente che se il sistema è costituito da un’unica macchina, la fase 1 non esiste !!! Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Strumenti Ipotesi alla base dei modelli di scheduling • Le risorse da utilizzare sono note e non è possibile decidere a questo livello eventuali aumenti di macchinario o di orario • In genere, la risorsa critica (considerata nel modello) è una sola ed è costituita dalle macchine del sistema • Gli operatori sono considerati sempre disponibili e con perfetta intercambiabilità di mansioni Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Strumenti Ipotesi alla base dei modelli di scheduling • I job sono completamente definiti (routing, entità di lotti, ecc.); non è detto però che i job siano tutti simultaneamente noti e disponibili per la lavorazione, ma possono pervenire in tempi successivi. In ogni caso quando un job è pervenuto al sistema, la sua data di possibile inizio lavorazione e la sua data di consegna sono fissate e note • I tempi di trasporto sono trascurabili • Non si considera la presenza di buffer interoperazionali Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Introduzione Ipotesi alla base dei modelli di scheduling • Una macchina non può lavorare più di un job alla volta • un job non può essere lavorato contemporaneamente su più macchine, non vengono quindi modellati processi di assemblaggio in cui i sottoinsiemi diversi di uno stesso job sono montati contemporaneamente in stazioni diverse • Data la brevità dell’orizzonte temporale considerato, vengono trascurati “i costi di mantenimento a scorta”, cioè non viene associata nessuna penalità all’anticipo di un job purché la sua lavorazione avvenga tra la data di possibile inizio e la data di consegna Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Definizioni Tecniche di scheduling Una differenziazione riguardante le tecniche di scheduling è quella relativa alla differenza esistente fra forward scheduling e backward scheduling. Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Definizioni Forward Scheduling Metodologia di schedulazione secondo la quale lo schedulatore comincia con una prestabilita data di inizio per la prima operazione e procede con le operazioni successive, calcolando i tempi in avanti rispetto alla data da cui si è partiti Vantaggioso quando il consumatore, esterno o interno, chiede il completamento di un particolare ordine entro una determinata data Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Definizioni Backward Scheduling Metodologia di schedulazione secondo la quale lo schedulatore comincia con una data prestabilita della fine dell’ultima operazione e da questa calcola le date delle operazioni precedenti effettuando un calcolo all’indietro fino a giungere alla prima operazione della lista Vantaggio • si può rinviare il più possibile il rilascio di un ordine cominciando la sua lavorazione solo quando un ulteriore rinvio potrebbe compromettere il rispetto della data di consegna dell’ordine stesso • si evita il sovraccarico dell’impianto di produzione evitando di effettuare una lavorazione prima del necessario Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Classificazione Classificazione dei modelli utilizzabili per la programmazione operativa • Classificazione in base al sistema produttivo • Classificazione in base agli obiettivi della programmazione • Classificazione in base al tipo di tecnica utilizzata Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Classificazione A cosa serve la classificazione ? Permette di conoscere: • in quali realtà produttive il modello è utilizzabile • quali parametri di prestazione esso ottimizza • quali sono le sue concrete possibilità di applicazione in relazione ai tempi di ottenimento della soluzione Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Classificazione Simbologia (proposta da Graham e Blazewicz) J|M|P|O • J rappresenta il numero di jobs nel sistema • M è il numero di macchine nel sistema • P è il tipo di processo produttivo (flowshop, jobshop, etc) • O è l’obiettivo che si vuole raggiungere Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Classificazione Classificazione in base al sistema produttivo • • • • • Macchina singola Macchine parallele (identiche o generiche) Open shop Flow shop Job shop Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Plant Layout Macch.1 Macch.2 Job A Job B Macch.3 Macch.4 ARCHITETTURA OPEN SHOP Ogni job ha un ciclo tecnologico che prevede TL su più macchine senza tuttavia che sia specificato l’ordine nell’esecuzione delle operazioni Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Plant Layout Macch.1 Macch.2 Job A Macch.3 Macch.4 ARCHITETTURA FLOW SHOP Job B Ogni job ha un ciclo tecnologico che prevede TL su più macchine e l’ordine nell’esecuzione delle operazioni è uguale per tutti i job Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Plant Layout Macch.1 Macch.2 Job A Job B Macch.3 Macch.4 ARCHITETTURA JOB SHOP Ogni job ha un ciclo tecnologico che prevede TL su più macchine e l’ordine nell’esecuzione delle operazioni dipende dai job Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Classificazione Classificazione in base agli obiettivi della programmazione • Massimizzazione del coefficiente di utilizzazione delle macchine, ovvero, con riferimento ad un definito portafoglio ordini, nella minimizzazione del suo tempo totale di completamento (Makespan) • Minimizzazione di una qualsivoglia funzione dei ritardi rispetto ai tempi di consegna Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Classificazione Ed ancora..... • Minimizzazione dei tempi di set-up • Minimizzazione del WIP (Work In Process ) • Ottimizzazione di una funzione obiettivo composita che comprenda più obiettivi precedenti, generalmente ottenuta con combinazioni lineari delle funzioni obiettivo sopra esposte Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Cause ed effetti La scelta di un obiettivo (o di più obiettivi) dipende dal contesto produttivo e dalle priorità derivanti dalla strategia di produzione adottata. In generale Non esiste un obiettivo migliore di altri Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Classificazione Criteri più comuni per misurare le prestazioni o la bontà di un algoritmo In relazione al completion time: Max flow time: FM = max {Fi} Max completion time: CM = max {Ci} Mean flow time: Fm = Fi / n Mean completion time: Cm = Ci / n In relazione alle due date: Max lateness: LM = max {Li} Max tardiness: TM = max {Ti} Mean lateness: Lm = Li / n Mean tardiness: Tm = Ti / n Numero di job in ritardo: Nt = (Ti) Con (Ti) =1 se Ti>0; =0 se Ti=0 Ritardo medio dei job in ritardo: Rm=Ti / Nt In relazione all’utilizzazione: Numero medio di job sotto processo: Nm,p = [ Np(t)] / T Max machine idle time: IM (tempo massimo di inutilizzo delle macchine) Mean machine idle time: Im (tempo medio di inutilizzo delle macchine) Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Classificazione Classificazione in base al tipo di tecnica utilizzata Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Definizioni Metodi di ottimizzazione analitici Garantiscono la miglior soluzione possibile in rapporto ai vincoli e agli obiettivi prefissati e sono sempre corredati da una dimostrazione che ne assicura l’ottimalità Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Definizioni Metodi di ottimizzazione euristici Si limitano a fornire una soluzione generalmente buona in relazione agli obiettivi considerati e dovrebbero essere accompagnati da una prova sperimentale della loro capacità di trovare soluzioni buone Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Definizioni Metodi di ottimizzazione analitici Forniscono una formula risolutiva che permette di calcolare il valore ottimale delle variabili decisionali. Apparentemente questi metodi sono solo di semplice e rapido impiego poiché la formula risolutiva non fornisce sempre la soluzione in forma esplicita ed esplicitarla spesso diventa alquanto difficoltoso. In base alla natura delle variabili in gioco è inoltre possibile differenziarli ulteriormente Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Definizioni Metodi di ottimizzazione algoritmici Non forniscono direttamente la formula risolutiva, ma indicano una serie di passi, cioè appunto un algoritmo, che permette ogni volta di costruire una soluzione Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Definizioni Metodi euristici per sostituzione di obiettivo Agiscono rimpiazzando l’obiettivo originario del problema con un altro opportunamente scelto in modo che la sua dipendenza dalle variabili decisionali sia meno complessa ed, inoltre, che ottimizzare il nuovo obiettivo porti ad ottenere una soluzione “buona” rispetto al vecchio, anche se subottima Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Definizioni Metodi euristici miopi Si basano sull’idea che trascurare alcune delle interazioni tra le variabili, pur portando ad una perdita di informazioni ed in particolare alla scomparsa della garanzia di ottimalità, non peggiori di molto il risultato trovato Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Definizioni Sistemi esperti Sono dei metodi euristici basati sull’intelligenza artificiale. Quello che è nuovo rispetto ai metodi precedenti è il modo di rappresentare e sfruttare la conoscenza euristica, la quale poi si riconduce ad una delle due categorie di euristiche già viste. Infatti, nelle tecniche di intelligenza artificiale la conoscenza non viene impiegata per costruire l’algoritmo, ma viene direttamente trasferita nel sistema che la usa di volta in volta per risolvere il problema; si parla in questo caso di knowledge based systems o, appunto, sistemi esperti. Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Definizioni Metodi interattivi Sono dei metodi euristici che si collocano all’estremo opposto rispetto ai metodi di ottimizzazione analitici: la soluzione, quasi certamente subottimale, viene ottenuta attraverso una serie di intuizioni, tentativi e correzioni da parte di un decisore umano e mediante l’uso di computer. Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Definizioni Release Date Il tempo di rilascio (indicato anche con la dicitura anglosassone release date) rj indica l’istante di tempo riferito ad un istante iniziale t0=0 prima del quale risulta impossibile iniziare l’esecuzione del job j. Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Strumenti È il valore maggiore fra zero e la differenza tra il tempo di completamento (Flow time) e la data di consegna (Due Date) di un job È un job che viene completato dopo la sua data di consegna Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Cause ed effetti Funzioni di penalità Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Definizioni Si riferisce alla differenza tra il tempo di completamento del job e la sua data di consegna e può essere MAGGIORE oppure MINORE di 0 Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Definizioni Flow time (Fi) o tempo di attraversamento del job i è il tempo che trascorre dall’inizio del primo job (Ii) sulla prima macchina fino al completamento del job i (Ci) Fi = Ci-Ii Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Definizioni Tempo di completamento Per tempo di completamento Cj si intende il tempo a cui l’ultimo task del job j (e, di conseguenza, l’intero job j) termina. Nel caso in cui non siano ammesse interruzioni, Cj risulta essere dato dalla somma dell’istante di inizio dell’ultimo task di quel job e del tempo di processamento dell’ultimo task. Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Definizioni Makespan Si definisce massimo tempo di completamento o makespan il valore massimo dell’insieme Cmax = max {C1, C2,…., Cn}, ossia il tempo di completamento del job che termina per ultimo; esso rappresenta la misura (rispetto al tempo di riferimento iniziale t 0) del tempo necessario ad ultimare tutte le attività. Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Definizioni IDLE TIME • è la media aritmetica del tempo di inattività per ogni macchina Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Definizioni Due Date Il tempo di consegna (anche detto due date) dj indica l’istante di tempo rispetto sempre ad un istante iniziale t0=0 entro il quale l’esecuzione del job j dovrebbe essere terminata. In genere, la violazione della data di consegna , determinata da un overtime di produzione comporta dei costi per penale, per perdita di fiducia da parte del cliente, di immagine, ecc… Si comprende che, mentre i costi per penale sono noti per contratto di fornitura, i restanti costi non sono facilmente ed immediatamente determinabili ma risultano, in genere, abbastanza cospicui più che della stessa penale Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Definizioni Tempi di Set-up I tempi di set-up sono i tempi tecnici necessari per attrezzare una macchina al fine di farle eseguire una lavorazione (job k) differente da quella precedentemente (job j) effettuata. Allora, tra il completamento del job j e l’inizio del job k è necessario riconfigurare la macchina, e tale operazione richiede un tempo sjk . In questo caso si assume che il tempo di set-up tra j e k sia comunque indipendente dai job precedenti j e seguenti k Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Metodi Metodo dell’assegnazione Rappresenta una tipica applicazione di programmazione lineare. Esso può essere applicato in quelle particolari situazioni in cui c’è una coincidenza del numero di job con il numero di macchine o di persone a cui assegnare i suddetti job Obiettivo minimizzare o massimizzare alcune misure di efficienza Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Metodi Metodo dell’assegnazione Condizioni • Ci sono n “job” da distribuire su n “macchine” • Ogni job deve essere assegnato ad una ed una sola destinazione • Solo un criterio può essere utilizzato (minimizzazione dei costi, massimizzazione dei profitti, o minimizzazione del tempo di completamento, per esempio) Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Metodi Metodo dell’assegnazione Si consideri un problema di minimizzazione (minim. dei costi o dei tempi di processamento) Cij rappresenta il tempo o il costo richiesto dalla persona o dalla macchina i per il job j Xij =1 se la persona o la macchina i sono assegnati al job j Xij = 0 se la persona o la macchina i non sono assegnati al job j Funzione obiettivo Vincoli Ing. Ferdinando Palazzo min ijxijcij ixij = 1 jxij = 1 (1) (2) (3) La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Metodi Metodo dell’assegnazione I due vincoli indicano che una persona o una macchina sono assegnate ad un unico job ed ogni job è processato da un unica macchina o un unica persona Il modello dell’assegnazione può essere anche espresso da una tabella in cui le righe rappresentano i job e le colonne rappresentano le macchine o i lavoratori a cui associare tali job. I valori interni alla tabella rappresentano il costo o il tempo impiegato per l’esecuzione di quel lavoro su quella macchina o per quel lavoratore Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Metodi Metodo dell’assegnazione Step •1) Sottrarre il numero più piccolo in ogni riga per ogni numero di quella riga e poi sottrarre il numero in ogni colonna per ogni numero in quella colonna. Questo step ha l’effetto di ridurre i numeri nella tabella fino ad ottenere una serie di zero, significando possibilità di costi zero. •2) Tracciare il numero minimo di linee verticali e orizzontali necessari a coprire tutti gli zeri della tabella. Se il numero di linee equivale al numero di righe o di colonne presenti nella tabella allora è possibile ottenere già la soluzione finale (procedere allo step 4). Se, invece, il numero di linee è minore del numero di righe o colonne, procedere allo step 3. •3) Sottrarre il numero più piccolo non coperto da una linea per ogni altro numero non non coperto e aggiungere esso ai numeri presenti all’intersezioni delle due linee. 4) L’assegnazione ottima sarà sempre localizzata nello zero. Per una valida assegnazione selezionare una riga o una colonna che contiene solo uno zero. L’assegnazione sarà eseguita relativamente alla riga e alla colonna che si intersecano in quello zero. Questo processo continuerà fin quando non sarà completata l’assegnazione di ogni job a persone o macchine Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Metodi Metodo dell’assegnazione ESEMPIO Step 1a. Sottrarre il numero più piccolo in ogni riga per ogni numero della riga stessa Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Metodi Metodo dell’assegnazione Step 1b. Eseguire la stessa operazione per le colonne Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Metodi Metodo dell’assegnazione Step 2. Tracciare il minimo numero di linee per coprire tutti gli zeri presenti in tabella. Nel caso in esame sono solo due le linee ad essere tracciate per cui la soluzione ottima ancora non è determinata Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Metodi Metodo dell’assegnazione Step 3. Sottrarre il numero più piccolo non coperto (2 nella tabella) ad ogni altro numero non coperto ed aggiungere esso al numero presente all’intersezione delle due righe Ing. Ferdinando Palazzo La Programmazione Operativa - Applicazioni delle tecniche di Scheduling Metodi Metodo dell’assegnazione Ritornare allo step 2. Coprire gli zeri con un numero minimo di righe Risultato finale L’assegnazione ottimale sarà in corrispondenza degli zeri, per cui partendo dal job S-66, l’unica assegnazione possibile sarà quella alla macchina B. Di conseguenza l’unica assegnazione possibile per T-50 sarà quella alla macchina A, e quella per R-34 sarà C. Quella trovata sarà la soluzione che minimizza i tempi, ed il tempo totale sarà di 25, pari alla somma di 6, 10, e 9, ovvero i tre termini corrispondenti alle tre assegnazioni Ing. Ferdinando Palazzo Fine I lezione sullo scheduling