LA PROGRAMMAZIONE OPERATIVALA PROGRAMMAZIONE OPERATIVA APPLICAZIONE DELLE TECNICHE DI SCHEDULINGAPPLICAZIONE DELLE TECNICHE DI SCHEDULING
DocenteDocente Consulente industriale Consulente industriale
Prof. Ing. Prof. Ing. Liberatina C. SantilloLiberatina C. Santillo Dott. Ing.Dott. Ing.Ferdinando PalazzoFerdinando PalazzoCollaboratori Collaboratori
Dott.Ing. Dott.Ing. Teresa MurinoTeresa Murino
Dott. Ing. Dott. Ing. Sergio GalloSergio Gallo
Anno Accademico 2001/2002Anno Accademico 2001/2002
Università degli Studi di NapoliUniversità degli Studi di NapoliFacoltà di IngegneriaFacoltà di Ingegneria
Corso di Laurea in Ingegneria Meccanica - GestionaleCorso di Laurea in Ingegneria Meccanica - Gestionale
Cattedra diCattedra di
GESTIONE DELLA PRODUZIONE INDUSTRIALEGESTIONE DELLA PRODUZIONE INDUSTRIALE
BibliografiaBibliografia
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Strumenti
Ing. Ferdinando Palazzo
[1] Brandolese, [1] Brandolese, Gestione della produzione industrialeGestione della produzione industriale, HOEPLI, Milano, 1991., HOEPLI, Milano, 1991.[2] Levy, [2] Levy, MRP II logica e implementazioneMRP II logica e implementazione, Franco Angeli, Milano 1993., Franco Angeli, Milano 1993.[3] Baker, [3] Baker, Introduction to sequencing & schedulingIntroduction to sequencing & scheduling, John Wiley & Sons, New , John Wiley & Sons, New York, 1974.York, 1974.[4] Johnson S. M., [4] Johnson S. M., Optimal two and three stage production schedules with setup Optimal two and three stage production schedules with setup times includedtimes included, Naval Research Logistics Quarterly, vol. 1, 1954., Naval Research Logistics Quarterly, vol. 1, 1954.[5] Campbell H.G., Dudek R.A., Smith M.L., [5] Campbell H.G., Dudek R.A., Smith M.L., A heuristic algorithm for the n job A heuristic algorithm for the n job machine sequencing problemmachine sequencing problem, Management Science., Management Science.[6] Bongaerts L., Valkenaers P., Wyns J.,1995.[6] Bongaerts L., Valkenaers P., Wyns J.,1995.[7] A. Grando, [7] A. Grando, Produzione e logisticaProduzione e logistica, UTET, Milano, 1996., UTET, Milano, 1996.[8] Masturzi. [8] Masturzi. Organizzazione e gestione della produzione industrialeOrganizzazione e gestione della produzione industriale ,vol.III. ,vol.III. Liguori editore,1990Liguori editore,1990
Lettura di approfondimentoLettura di approfondimento
SchedulingScheduling di Michael Pinedo di Michael Pinedo
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Strumenti
Ing. Ferdinando Palazzo
Problem solvingProblem [email protected]@libero.it
Tel. 3381884886Tel. 3381884886
OBIETTIVIOBIETTIVI • Ridurre il tempo di raccolta datiRidurre il tempo di raccolta dati
• Aumentare il tempo e la correttezza delle decisioniAumentare il tempo e la correttezza delle decisioni
• Aumentare gli standard qualitativi dei servizi e/o dei Aumentare gli standard qualitativi dei servizi e/o dei prodottiprodotti
• Realizzare report efficaciRealizzare report efficaci
Introduzione
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
OBIETTIVO DELLA RICERCA OBIETTIVO DELLA RICERCA INDUSTRIALEINDUSTRIALE
Ing. Ferdinando Palazzo
Sviluppo ed applicazione di sistemi Software basati su Sviluppo ed applicazione di sistemi Software basati su tecnologia WEB e tecniche innovative di schedulingtecnologia WEB e tecniche innovative di scheduling
DECISION SUPPORT SYSTEMDECISION SUPPORT SYSTEM
L’obiettivo è quello di migliorare l’L’obiettivo è quello di migliorare l’efficaciaefficacia della della decisionedecisione
Un DSS è un sistema software che richiede una Un DSS è un sistema software che richiede una stretta interazione on-line con l’utente per stretta interazione on-line con l’utente per assisterlo in processi decisionali complessi e assisterlo in processi decisionali complessi e vincolati vincolati senza sostituirsi ad essosenza sostituirsi ad esso
• di gestione dei datidi gestione dei dati• di gestione dei modelli di gestione dei modelli • di interfaccia utentedi interfaccia utente
Generalmente include tre sottosistemi :Generalmente include tre sottosistemi :
Ing. Ferdinando Palazzo
Introduzione
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Situazione Decisionale Decisione
Modello Risultati
RUOLO DELL’ANALISTA E DEL DECISORERUOLO DELL’ANALISTA E DEL DECISORE
Mondo reale
Mondo simbolicoA
stra
zion
e
Inte
rpre
tazi
one
Analisi
Intuizione
Decision Maker
Analista
Ing. Ferdinando Palazzo
Introduzione
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
STRUTTURA CONCETTUALE DI UN DSSSTRUTTURA CONCETTUALE DI UN DSS
DecisoreDecisore
DomandaDomanda
DSSDSS
RisultatoRisultato
Linguaggio Raccolta di informazioni
Riconoscimento del problema
Formulazione del modello
Analisi
………
Informazioni memorizzate circa il dominio del problema
(1)(1) (2)(2) (3)(3)
(1) Linguaggio del sistema(1) Linguaggio del sistema
(2) Sistema di risoluzione del problema(2) Sistema di risoluzione del problema
(3) Sistema di conoscenza(3) Sistema di conoscenzaIng. Ferdinando Palazzo
Introduzione
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
IL DATAWAREHOUSEIL DATAWAREHOUSE
E’ un nuovo sistema di supporto decisionale ed E’ un nuovo sistema di supporto decisionale ed in questo si colloca non solo come una novità in questo si colloca non solo come una novità tecnologica ma anche strategicatecnologica ma anche strategica
Rivoluzionando l’attività di analisi, permette di Rivoluzionando l’attività di analisi, permette di navigare attraverso differenti viste di dati navigare attraverso differenti viste di dati elaborate da altrettante diverse modalità di elaborate da altrettante diverse modalità di aggregazioneaggregazione
In che modo?In che modo?
Ing. Ferdinando Palazzo
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Metodologie e strumenti
L’AMBIENTE INFORMATIVO L’AMBIENTE INFORMATIVO STRATEGICO ED INTEGRATOSTRATEGICO ED INTEGRATO
MagazzinoMagazzino
ProdottiProdotti
OrdiniOrdini
ContattiContatti
CassaCassa
Situazione precedente/Situazione precedente/Aree di Business Aree di Business Metadati Tecnici e di BusinessMetadati Tecnici e di Business
Ambiente Operativo Ambiente Operativo Ambiente WarehouseAmbiente Warehouse
Data WarehouseData WarehouseAziendaleAziendale
Dati esterni Dati esterni e non strutturatie non strutturati
Data MartsData Martssettorialisettoriali
FinanzaFinanza
Data Marts Data Marts Personalizzati Personalizzati
VenditeVendite
MarketingMarketing
Ing. Ferdinando Palazzo
Metodologie e strumenti
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
SCHEMA DEL FLUSSO DI INFORMAZIONESCHEMA DEL FLUSSO DI INFORMAZIONE
UI DBCPU
Acquisizione dei dati
Presentazionedel risultato
Connessione ed
ottenimentorisultato
Formattazionerisultato
ComposizioneStringa di ricerca
Ing. Ferdinando Palazzo
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Tecnologia innovativa
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Strumenti
Ing. Ferdinando Palazzo
DIAGRAMMA DIAGRAMMA DI GANTTDI GANTT
La durata delle singole attività è indicata dalla lunghezza delle barre, La durata delle singole attività è indicata dalla lunghezza delle barre, mentre le relazioni di dipendenza tra due attività sono solitamente mentre le relazioni di dipendenza tra due attività sono solitamente rappresentate da frecce, gli eventi significativi del progetto sono evidenziati rappresentate da frecce, gli eventi significativi del progetto sono evidenziati infine da contrassegni di forma romboidaleinfine da contrassegni di forma romboidale
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Strumenti
Ing. Ferdinando Palazzo
DIAGRAMMA DIAGRAMMA WBSWBS
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Strumenti
Ing. Ferdinando Palazzo
ATTIVITA’ DEL ATTIVITA’ DEL PROGETTOPROGETTO
Schema generico della fase Schema generico della fase
progettuale ed operativaprogettuale ed operativa
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Strumenti
Ing. Ferdinando Palazzo
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Strumenti
Ing. Ferdinando Palazzo
I
I
J
J
MACCHINA 1
MACCHINA 2
I
J I
JMACCHINA 1
MACCHINA 2
DIAGRAMMA DIAGRAMMA DI GANTTDI GANTT
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Strumenti
Ing. Ferdinando Palazzo
I
JI
JMACCHINA 1
MACCHINA 2
I
J I
JMACCHINA 1
MACCHINA 2
DIAGRAMMA DIAGRAMMA DI GANTTDI GANTT
CARATTERISTICHE DEI PROTOTIPI CARATTERISTICHE DEI PROTOTIPI ATTUALMENTE VENDUTIATTUALMENTE VENDUTI
Ing. Ferdinando Palazzo
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Introduzione
• VISIBILITA’VISIBILITA’
• SCALABILITA’SCALABILITA’
• ADOTTABILITA’ADOTTABILITA’
• FLESSIBILITA’FLESSIBILITA’
ESEMPI DI PROTOTIPIESEMPI DI PROTOTIPI
Ing. Ferdinando Palazzo
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Strumenti
• TECNICA DRAG AND DROPTECNICA DRAG AND DROP
TENDENZA INDUSTRIALE TENDENZA INDUSTRIALE ATTUALE : ATTUALE :
• MONITORAGGIO RISORSEMONITORAGGIO RISORSE
• SPEECH ENGINESPEECH ENGINE
La programmazione operativaLa programmazione operativa
• loadingloading
• sequencingsequencing
• schedulingscheduling
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Definizioni
Ing. Ferdinando Palazzo
Si articola in tre momenti principali :Si articola in tre momenti principali :
Fa riferimento al breve periodoFa riferimento al breve periodo
Fase di loadingFase di loading
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Definizioni
Ing. Ferdinando Palazzo
Nella fase di allocazioneNella fase di allocazione ( (loadingloading) delle operazioni sulle ) delle operazioni sulle singole risorse disponibili, nota l’entità di ciascun singole risorse disponibili, nota l’entità di ciascun ordine e, quindi, il relativo fabbisogno di macchine e di ordine e, quindi, il relativo fabbisogno di macchine e di attrezzature, si verifica la possibilità di soddisfare tale attrezzature, si verifica la possibilità di soddisfare tale fabbisogno con le risorse disponibili ripartendo fabbisogno con le risorse disponibili ripartendo l’insieme degli ordini tra le singole stazioni di lavoro l’insieme degli ordini tra le singole stazioni di lavoro
Significa l’assegnare i job ai centri di processamento.Significa l’assegnare i job ai centri di processamento.Una corretta assegnazione è tale da minimizzare i costi, Una corretta assegnazione è tale da minimizzare i costi,
l’idle time ed i tempi di completamentol’idle time ed i tempi di completamento
In sintesiIn sintesi
Fase di sequencingFase di sequencing
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Definizioni
Ing. Ferdinando Palazzo
Nella fase di Nella fase di sequencing sequencing si ricerca, si ricerca, per ogni centro di lavoro, la sequenza per ogni centro di lavoro, la sequenza secondo la quale conviene che secondo la quale conviene che vengano eseguiti gli ordini in vengano eseguiti gli ordini in precedenza attribuiti a tale centroprecedenza attribuiti a tale centro
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Definizioni
Ing. Ferdinando Palazzo
Fase di schedulingFase di scheduling
Nella fase di Nella fase di scheduling scheduling vero e proprio, a vero e proprio, a ciascun ordine, oramai assegnato ad uno ciascun ordine, oramai assegnato ad uno specifico centro ed al quale compete una specifico centro ed al quale compete una specifica posizione nella sequenza specifica posizione nella sequenza produttiva, viene associato un istante di produttiva, viene associato un istante di inizio ed uno di fine lavorazione inizio ed uno di fine lavorazione
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Cause ed effetti
Ing. Ferdinando Palazzo
Non sempre è necessario affrontare tutte le Non sempre è necessario affrontare tutte le fasi sopra riportate. fasi sopra riportate.
Ad esempio è evidente che se il sistema è Ad esempio è evidente che se il sistema è costituito da un’unica macchina, la fase 1 non costituito da un’unica macchina, la fase 1 non esisteesiste !!!!!!
IN PRATICA…IN PRATICA…
Ipotesi alla base dei modelli di Ipotesi alla base dei modelli di schedulingscheduling
• Le risorse da utilizzare sono note e non è possibile Le risorse da utilizzare sono note e non è possibile decidere a questo livello eventuali aumenti di decidere a questo livello eventuali aumenti di macchinario o di orario macchinario o di orario
• In genere, la risorsa critica (considerata nel modello) è In genere, la risorsa critica (considerata nel modello) è una sola ed è costituita dalle macchine del sistemauna sola ed è costituita dalle macchine del sistema
• Gli operatori sono considerati sempre disponibili e con Gli operatori sono considerati sempre disponibili e con perfetta intercambiabilità di mansioniperfetta intercambiabilità di mansioni
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Strumenti
Ing. Ferdinando Palazzo
Ipotesi alla base dei modelli di Ipotesi alla base dei modelli di schedulingscheduling
• I job sono completamente definiti (routing, entità di I job sono completamente definiti (routing, entità di lotti, ecc.); non è detto però che i job siano tutti lotti, ecc.); non è detto però che i job siano tutti simultaneamente noti e disponibili per la lavorazione, simultaneamente noti e disponibili per la lavorazione, ma possono pervenire in tempi successivi. In ogni caso ma possono pervenire in tempi successivi. In ogni caso quando un job è pervenuto al sistema, la sua data di quando un job è pervenuto al sistema, la sua data di possibile inizio lavorazione e la sua data di consegna possibile inizio lavorazione e la sua data di consegna sono fissate e notesono fissate e note
• I tempi di trasporto sono trascurabili I tempi di trasporto sono trascurabili • Non si considera la presenza di buffer interoperazionali Non si considera la presenza di buffer interoperazionali
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Strumenti
Ing. Ferdinando Palazzo
Ipotesi alla base dei modelli di Ipotesi alla base dei modelli di schedulingscheduling
• Una macchina non può lavorare più di un job alla volta Una macchina non può lavorare più di un job alla volta • un job non può essere lavorato contemporaneamente su un job non può essere lavorato contemporaneamente su
più macchine, non vengono quindi modellati processi di più macchine, non vengono quindi modellati processi di assemblaggio in cui i sottoinsiemi diversi di uno stesso assemblaggio in cui i sottoinsiemi diversi di uno stesso job sono montati contemporaneamente in stazioni job sono montati contemporaneamente in stazioni diverse diverse
• Data la brevità dell’orizzonte temporale considerato, Data la brevità dell’orizzonte temporale considerato, vengono trascurati “i costi di mantenimento a scorta”, vengono trascurati “i costi di mantenimento a scorta”, cioè non viene associata nessuna penalità all’anticipo di cioè non viene associata nessuna penalità all’anticipo di un job purché la sua lavorazione avvenga tra la data di un job purché la sua lavorazione avvenga tra la data di possibile inizio e la data di consegna possibile inizio e la data di consegna
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Introduzione
Ing. Ferdinando Palazzo
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Definizioni
Ing. Ferdinando Palazzo
Tecniche di schedulingTecniche di scheduling
Una differenziazione riguardante le tecniche Una differenziazione riguardante le tecniche di scheduling è quella relativa alla differenza di scheduling è quella relativa alla differenza esistente fra forward scheduling e backward esistente fra forward scheduling e backward scheduling.scheduling.
Forward SchedulingForward Scheduling
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Definizioni
Ing. Ferdinando Palazzo
Metodologia di schedulazione secondo la quale lo Metodologia di schedulazione secondo la quale lo schedulatore comincia con una prestabilita data di schedulatore comincia con una prestabilita data di inizio per la prima operazione e procede con le inizio per la prima operazione e procede con le operazioni successive, calcolando i tempi in avanti operazioni successive, calcolando i tempi in avanti rispetto alla data da cui si è partitirispetto alla data da cui si è partiti
VantaggiosoVantaggioso quando il consumatore, esterno o quando il consumatore, esterno o interno, chiede il completamento interno, chiede il completamento di un particolare ordine entro una di un particolare ordine entro una determinata data determinata data
Backward SchedulingBackward Scheduling
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Definizioni
Ing. Ferdinando Palazzo
Metodologia di schedulazione secondo la quale lo Metodologia di schedulazione secondo la quale lo schedulatore comincia con una data prestabilita della schedulatore comincia con una data prestabilita della fine dell’ultima operazione e da questa calcola le date fine dell’ultima operazione e da questa calcola le date delle operazioni precedenti effettuando un calcolo delle operazioni precedenti effettuando un calcolo all’indietro fino a giungere alla prima operazione della all’indietro fino a giungere alla prima operazione della listalista
VantaggioVantaggio • si può rinviare il più possibile il rilascio di un ordine si può rinviare il più possibile il rilascio di un ordine cominciando la sua lavorazione solo quando un cominciando la sua lavorazione solo quando un ulteriore rinvio potrebbe compromettere il rispetto ulteriore rinvio potrebbe compromettere il rispetto della data di consegna dell’ordine stessodella data di consegna dell’ordine stesso• si evita il sovraccarico dell’impianto di produzione si evita il sovraccarico dell’impianto di produzione evitando di effettuare una lavorazione prima del evitando di effettuare una lavorazione prima del necessarionecessario
Classificazione dei modelli utilizzabili Classificazione dei modelli utilizzabili per la programmazione operativaper la programmazione operativa
• Classificazione in base al sistema produttivoClassificazione in base al sistema produttivo
• Classificazione in base agli obiettivi della Classificazione in base agli obiettivi della programmazioneprogrammazione
• Classificazione in base al tipo di tecnica Classificazione in base al tipo di tecnica utilizzatautilizzata
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Classificazione
Ing. Ferdinando Palazzo
• in quali realtà produttive il modello è in quali realtà produttive il modello è utilizzabileutilizzabile
• quali parametri di prestazione esso quali parametri di prestazione esso ottimizzaottimizza
• quali sono le sue concrete possibilità di quali sono le sue concrete possibilità di applicazione in relazione ai tempi di applicazione in relazione ai tempi di ottenimento della soluzione ottenimento della soluzione
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Classificazione
Ing. Ferdinando Palazzo
Permette di conoscere:Permette di conoscere:
A cosa serve la classificazione ?A cosa serve la classificazione ?
Simbologia Simbologia ((proposta da Graham e Blazewiczproposta da Graham e Blazewicz))
• J rappresenta il numero di jobs nel sistemaJ rappresenta il numero di jobs nel sistema
• M è il numero di macchine nel sistema M è il numero di macchine nel sistema
• P è il tipo di processo produttivo (flowshop, P è il tipo di processo produttivo (flowshop, jobshop, etc) jobshop, etc)
• O è l’obiettivo che si vuole raggiungere O è l’obiettivo che si vuole raggiungere
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Classificazione
Ing. Ferdinando Palazzo
J | M | P | O
Classificazione in base al sistema Classificazione in base al sistema produttivoproduttivo
• Macchina singola Macchina singola
• Macchine parallele (Macchine parallele (identicheidentiche o generiche) o generiche)
• Open shop Open shop
• Flow shop Flow shop
• Job shop Job shop
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Classificazione
Ing. Ferdinando Palazzo
ARCHITETTURAARCHITETTURAOPEN SHOPOPEN SHOP
Ing. Ferdinando Palazzo
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Plant Layout
Macch.1 Macch.2 Macch.3 Macch.4
Job A
Job B
Ogni job ha un ciclo tecnologico che prevede TL su più macchine Ogni job ha un ciclo tecnologico che prevede TL su più macchine senza tuttavia che sia specificato l’ordine nell’esecuzione delle senza tuttavia che sia specificato l’ordine nell’esecuzione delle operazionioperazioni
ARCHITETTURAARCHITETTURAFLOW SHOPFLOW SHOP
Ing. Ferdinando Palazzo
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Plant Layout
Macch.1 Macch.2 Macch.3 Macch.4
Job A
Job B
Ogni job ha un ciclo tecnologico che prevede TL su più macchine Ogni job ha un ciclo tecnologico che prevede TL su più macchine e l’ordine nell’esecuzione delle operazioni è uguale per tutti i jobe l’ordine nell’esecuzione delle operazioni è uguale per tutti i job
ARCHITETTURAARCHITETTURAJOB SHOPJOB SHOP
Ing. Ferdinando Palazzo
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Plant Layout
Macch.1 Macch.2 Macch.3 Macch.4
Job A
Job B
Ogni job ha un ciclo tecnologico che prevede TL su più macchine Ogni job ha un ciclo tecnologico che prevede TL su più macchine e l’ordine nell’esecuzione delle operazioni dipende dai jobe l’ordine nell’esecuzione delle operazioni dipende dai job
Classificazione in base agli obiettivi della Classificazione in base agli obiettivi della programmazioneprogrammazione
• Massimizzazione del coefficiente di utilizzazione delle Massimizzazione del coefficiente di utilizzazione delle macchine, ovvero, con riferimento ad un definito macchine, ovvero, con riferimento ad un definito portafoglio ordini, nella minimizzazione del suo tempo portafoglio ordini, nella minimizzazione del suo tempo totale di completamento (totale di completamento (MakespanMakespan))
• Minimizzazione di una qualsivoglia funzione dei Minimizzazione di una qualsivoglia funzione dei ritardi rispetto ai tempi di consegna ritardi rispetto ai tempi di consegna
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Classificazione
Ing. Ferdinando Palazzo
Ed ancora.....Ed ancora.....
• Minimizzazione dei tempi di set-up Minimizzazione dei tempi di set-up
• Minimizzazione del WIP (Minimizzazione del WIP (Work In ProcessWork In Process ) )
• Ottimizzazione di una funzione obiettivo Ottimizzazione di una funzione obiettivo composita che comprenda più obiettivi precedenti, composita che comprenda più obiettivi precedenti, generalmente ottenuta con combinazioni lineari generalmente ottenuta con combinazioni lineari delle funzioni obiettivo sopra esposte delle funzioni obiettivo sopra esposte
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Classificazione
Ing. Ferdinando Palazzo
La scelta di un obiettivo (o di più obiettivi) dipende La scelta di un obiettivo (o di più obiettivi) dipende dal contesto produttivo e dalle priorità derivanti dal contesto produttivo e dalle priorità derivanti dalla strategia di produzione adottata.dalla strategia di produzione adottata.
In generaleIn generale
Non esiste un obiettivo migliore di altriNon esiste un obiettivo migliore di altri
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Cause ed effetti
Ing. Ferdinando Palazzo
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Classificazione
Ing. Ferdinando Palazzo
Criteri più comuni per misurare le prestazioni o la Criteri più comuni per misurare le prestazioni o la bontà di un algoritmobontà di un algoritmoIn relazione al In relazione al completion timecompletion time::Max flow time:Max flow time: FM = max {Fi} FM = max {Fi}Max completion time:Max completion time: CM = max {Ci} CM = max {Ci}Mean flow time:Mean flow time: Fm = Fm = Fi / n Fi / nMean completion time:Mean completion time: Cm = Cm = Ci / n Ci / nIn relazione alle In relazione alle due datedue date::Max lateness:Max lateness: LM = max {Li} LM = max {Li}Max tardiness:Max tardiness: TM = max {Ti} TM = max {Ti}Mean lateness:Mean lateness: Lm = Lm = Li / n Li / nMean tardiness:Mean tardiness: Tm = Tm = Ti / n Ti / nNumero di job in ritardo: Numero di job in ritardo: Nt = Nt = (Ti) Con (Ti) Con (Ti) =1 se Ti>0; =0 se Ti=0 (Ti) =1 se Ti>0; =0 se Ti=0 Ritardo medio dei job in ritardoRitardo medio dei job in ritardo: Rm=Ti / Nt: Rm=Ti / NtIn relazione all’utilizzazione:In relazione all’utilizzazione:Numero medio di job sotto processoNumero medio di job sotto processo: Nm,p = [: Nm,p = [ Np(t)] / T Np(t)] / TMax machine idle timeMax machine idle time: IM: IM(tempo massimo di inutilizzo delle macchine)(tempo massimo di inutilizzo delle macchine)Mean machine idle timeMean machine idle time:: Im Im(tempo medio di inutilizzo delle macchine)(tempo medio di inutilizzo delle macchine)
Classificazione in base al tipo di tecnica Classificazione in base al tipo di tecnica utilizzatautilizzata
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Classificazione
Ing. Ferdinando Palazzo
Metodi di ottimizzazione analiticiMetodi di ottimizzazione analitici
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Definizioni
Ing. Ferdinando Palazzo
Garantiscono la miglior soluzione possibile in Garantiscono la miglior soluzione possibile in rapporto ai vincoli e agli obiettivi prefissati e rapporto ai vincoli e agli obiettivi prefissati e sono sempre corredati da una dimostrazione sono sempre corredati da una dimostrazione che ne assicura l’che ne assicura l’ottimalitàottimalità
Metodi di ottimizzazione euristiciMetodi di ottimizzazione euristici
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Definizioni
Ing. Ferdinando Palazzo
Si limitano a fornire una soluzione generalmente Si limitano a fornire una soluzione generalmente buona in relazione agli obiettivi considerati e buona in relazione agli obiettivi considerati e dovrebberodovrebbero essere accompagnati da una prova essere accompagnati da una prova sperimentale della loro capacità di trovare sperimentale della loro capacità di trovare soluzioni soluzioni buonebuone
Metodi di ottimizzazione analiticiMetodi di ottimizzazione analitici
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Definizioni
Ing. Ferdinando Palazzo
Forniscono una formula risolutiva che permette Forniscono una formula risolutiva che permette di calcolare il valore ottimale delle variabili di calcolare il valore ottimale delle variabili decisionali. Apparentemente questi metodi sono decisionali. Apparentemente questi metodi sono solo di semplice e rapido impiego poiché la solo di semplice e rapido impiego poiché la formula risolutiva non fornisce sempre la formula risolutiva non fornisce sempre la soluzione in forma esplicita ed esplicitarla spesso soluzione in forma esplicita ed esplicitarla spesso diventa alquanto difficoltoso. diventa alquanto difficoltoso. In base alla natura delle variabili in gioco è In base alla natura delle variabili in gioco è inoltre possibile differenziarli ulteriormenteinoltre possibile differenziarli ulteriormente
Metodi di ottimizzazione algoritmiciMetodi di ottimizzazione algoritmici
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Definizioni
Ing. Ferdinando Palazzo
Non forniscono direttamente la formula Non forniscono direttamente la formula risolutiva, ma indicano una serie di passi, risolutiva, ma indicano una serie di passi, cioè appunto un algoritmo, che permette cioè appunto un algoritmo, che permette ogni volta di costruire una soluzioneogni volta di costruire una soluzione
Metodi euristici per sostituzione di Metodi euristici per sostituzione di obiettivoobiettivo
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Definizioni
Ing. Ferdinando Palazzo
Agiscono rimpiazzando l’obiettivo originario Agiscono rimpiazzando l’obiettivo originario del problema con un altro opportunamente del problema con un altro opportunamente scelto in modo che la sua dipendenza dalle scelto in modo che la sua dipendenza dalle variabili decisionali sia meno complessa ed, variabili decisionali sia meno complessa ed, inoltre, che ottimizzare il nuovo obiettivo inoltre, che ottimizzare il nuovo obiettivo porti ad ottenere una soluzione “buona” porti ad ottenere una soluzione “buona” rispetto al vecchio, anche se rispetto al vecchio, anche se subottimasubottima
Metodi euristici miopiMetodi euristici miopi
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Definizioni
Ing. Ferdinando Palazzo
Si basano sull’idea che trascurare alcune delle Si basano sull’idea che trascurare alcune delle interazioni tra le variabili, pur portando ad interazioni tra le variabili, pur portando ad una perdita di informazioni ed in particolare una perdita di informazioni ed in particolare alla scomparsa della garanzia di ottimalità, alla scomparsa della garanzia di ottimalità, non peggiori di molto il risultato trovatonon peggiori di molto il risultato trovato
Sistemi espertiSistemi esperti
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Definizioni
Ing. Ferdinando Palazzo
Sono dei metodi euristici basati sull’intelligenza Sono dei metodi euristici basati sull’intelligenza artificiale. Quello che è nuovo rispetto ai metodi artificiale. Quello che è nuovo rispetto ai metodi precedenti è il modo di rappresentare e sfruttare la precedenti è il modo di rappresentare e sfruttare la conoscenza euristica, la quale poi si riconduce ad conoscenza euristica, la quale poi si riconduce ad una delle due categorie di euristiche già viste. una delle due categorie di euristiche già viste. Infatti, nelle tecniche di intelligenza artificiale la Infatti, nelle tecniche di intelligenza artificiale la conoscenza non viene impiegata per costruire conoscenza non viene impiegata per costruire l’algoritmo, ma viene direttamente trasferita nel l’algoritmo, ma viene direttamente trasferita nel sistema che la usa di volta in volta per risolvere il sistema che la usa di volta in volta per risolvere il problema; si parla in questo caso di problema; si parla in questo caso di knowledge based knowledge based systemssystems o, appunto, o, appunto, sistemi espertisistemi esperti..
Metodi interattiviMetodi interattivi
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Definizioni
Ing. Ferdinando Palazzo
Sono dei metodi euristici che si collocano Sono dei metodi euristici che si collocano all’estremo opposto rispetto ai metodi di all’estremo opposto rispetto ai metodi di ottimizzazione analitici: la soluzione, quasi ottimizzazione analitici: la soluzione, quasi certamente subottimale, viene ottenuta certamente subottimale, viene ottenuta attraverso una serie di intuizioni, tentativi e attraverso una serie di intuizioni, tentativi e correzioni da parte di un decisore umanocorrezioni da parte di un decisore umano e e mediante l’uso di computer.mediante l’uso di computer.
Release DateRelease Date
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Definizioni
Ing. Ferdinando Palazzo
Il Il tempo di rilasciotempo di rilascio (indicato anche con la (indicato anche con la dicitura anglosassone release date) rdicitura anglosassone release date) r
j j
indica l’istante di tempo riferito ad un indica l’istante di tempo riferito ad un istante iniziale tistante iniziale t
00=0 prima del quale risulta =0 prima del quale risulta
impossibile iniziare l’esecuzione del job j.impossibile iniziare l’esecuzione del job j.
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Strumenti
Ing. Ferdinando Palazzo
È il valore maggiore fra zero e la differenza tra il tempo di È il valore maggiore fra zero e la differenza tra il tempo di completamento (Flow time) e la data di consegna (Due Date) di un jobcompletamento (Flow time) e la data di consegna (Due Date) di un job
È un job che viene completato dopo la sua data di consegnaÈ un job che viene completato dopo la sua data di consegna
Funzioni di penalitàFunzioni di penalità
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Cause ed effetti
Ing. Ferdinando Palazzo
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Definizioni
Ing. Ferdinando Palazzo
Si riferisce alla differenza tra il tempo di Si riferisce alla differenza tra il tempo di completamento del job e la sua data di consegna e completamento del job e la sua data di consegna e può essere MAGGIORE oppure MINORE di 0può essere MAGGIORE oppure MINORE di 0
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Definizioni
Ing. Ferdinando Palazzo
FlowFlow timetime (F (Fii) o ) o tempo di attraversamentotempo di attraversamento
del job del job ii è il tempo che trascorre è il tempo che trascorre dall’inizio del primo job (Idall’inizio del primo job (Iii) sulla ) sulla
prima macchina fino al prima macchina fino al completamento del job completamento del job ii (C (Cii))
FFii = C = Cii-I-Iii
Tempo di completamentoTempo di completamento
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Definizioni
Ing. Ferdinando Palazzo
Per Per tempo di completamentotempo di completamento C Cjj si intende il si intende il
tempo a cui l’ultimo task del job j (e, di tempo a cui l’ultimo task del job j (e, di conseguenza, l’intero job j) termina. conseguenza, l’intero job j) termina. Nel caso in cui non siano ammesse Nel caso in cui non siano ammesse interruzioni, Cinterruzioni, C
jj risulta essere dato dalla risulta essere dato dalla
somma dell’istante di inizio dell’ultimo task somma dell’istante di inizio dell’ultimo task di quel job e del tempo di processamento di quel job e del tempo di processamento dell’ultimo task.dell’ultimo task.
MakespanMakespan
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Definizioni
Ing. Ferdinando Palazzo
Si definisce Si definisce massimo tempo di massimo tempo di completamentocompletamento o o makespanmakespan il valore il valore massimo dell’insiememassimo dell’insieme
CCmaxmax = max {C = max {C11, C, C
22,…., C,…., Cnn}, },
ossia il tempo di completamento del job ossia il tempo di completamento del job che termina per ultimo; esso che termina per ultimo; esso rappresenta la misura (rispetto al tempo rappresenta la misura (rispetto al tempo di riferimento iniziale tdi riferimento iniziale t
0 0) del tempo ) del tempo
necessario ad ultimare tutte le attività.necessario ad ultimare tutte le attività.
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Definizioni
Ing. Ferdinando Palazzo
IDLE TIMEIDLE TIME
• è la media aritmetica del tempo è la media aritmetica del tempo di di inattivitàinattività per ogni macchina per ogni macchina
Due DateDue Date
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Definizioni
Ing. Ferdinando Palazzo
Il Il tempo di consegnatempo di consegna (anche detto due date) (anche detto due date) ddjj indica l’istante di tempo rispetto sempre indica l’istante di tempo rispetto sempre
ad un istante iniziale tad un istante iniziale t00=0 entro il quale =0 entro il quale
l’esecuzione del job j dovrebbe essere l’esecuzione del job j dovrebbe essere terminata.terminata.In genere, la violazione della data di In genere, la violazione della data di consegna , determinata da un consegna , determinata da un overtimeovertime di di produzione comporta dei costi per produzione comporta dei costi per penalepenale, , per perdita di fiducia da parte del cliente, di per perdita di fiducia da parte del cliente, di immagine, ecc…immagine, ecc…Si comprende che, mentre i costi per penale sono Si comprende che, mentre i costi per penale sono noti per contratto di fornitura, i restanti costi non noti per contratto di fornitura, i restanti costi non sono facilmente ed immediatamente determinabili ma sono facilmente ed immediatamente determinabili ma risultano, in genere, abbastanza cospicui più che risultano, in genere, abbastanza cospicui più che della stessa penaledella stessa penale
Tempi di Set-upTempi di Set-up
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Definizioni
Ing. Ferdinando Palazzo
I I tempi di set-uptempi di set-up sono i tempi tecnici necessari per sono i tempi tecnici necessari per attrezzare una macchina al fine di farle eseguire attrezzare una macchina al fine di farle eseguire una lavorazione (job k) differente da quella una lavorazione (job k) differente da quella precedentemente (job j) effettuata.precedentemente (job j) effettuata.Allora, tra il completamento del job j e l’inizio del Allora, tra il completamento del job j e l’inizio del job k è necessario riconfigurare la macchina, e tale job k è necessario riconfigurare la macchina, e tale operazione richiede un tempo soperazione richiede un tempo s
jk jk ..
In questo caso si assume che il tempo di set-up tra In questo caso si assume che il tempo di set-up tra j e k sia comunque indipendente dai job precedenti j e k sia comunque indipendente dai job precedenti j e seguenti kj e seguenti k
Metodo dell’assegnazioneMetodo dell’assegnazione
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Metodi
Ing. Ferdinando Palazzo
Rappresenta una tipica applicazione di programmazione Rappresenta una tipica applicazione di programmazione lineare. Esso può essere applicato in quelle particolari lineare. Esso può essere applicato in quelle particolari situazioni in cui c’è una coincidenza del numero di job situazioni in cui c’è una coincidenza del numero di job con il numero di macchine o di persone a cui assegnare con il numero di macchine o di persone a cui assegnare i suddetti jobi suddetti job
minimizzare o massimizzare alcune misure di efficienza minimizzare o massimizzare alcune misure di efficienza ObiettivoObiettivo
Metodo dell’assegnazioneMetodo dell’assegnazione
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Metodi
Ing. Ferdinando Palazzo
CondizioniCondizioni
• Ci sono Ci sono n n “job” da distribuire su “job” da distribuire su n n “macchine”“macchine”
• Ogni job deve essere assegnato ad una ed una Ogni job deve essere assegnato ad una ed una sola destinazione sola destinazione
• Solo un criterio può essere utilizzato Solo un criterio può essere utilizzato (minimizzazione dei costi, massimizzazione dei (minimizzazione dei costi, massimizzazione dei profitti, o minimizzazione del tempo di profitti, o minimizzazione del tempo di completamento, per esempio)completamento, per esempio)
Metodo dell’assegnazioneMetodo dell’assegnazione
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Metodi
Ing. Ferdinando Palazzo
Si consideri un problema di minimizzazione (minim. dei Si consideri un problema di minimizzazione (minim. dei costi o dei tempi di processamento)costi o dei tempi di processamento)
CCij ij rappresenta il tempo o il costo richiesto dalla persona rappresenta il tempo o il costo richiesto dalla persona
o dalla macchina o dalla macchina i i per il jobper il job j j
XXij ij =1 se la persona o la macchina =1 se la persona o la macchina i i sono assegnati al job sono assegnati al job jj
XXij ij = 0 se la persona o la macchina = 0 se la persona o la macchina ii non sono assegnati al non sono assegnati al
job job jj
Funzione obiettivo Funzione obiettivo min min iijjxxijijccij ij (1) (1)
Vincoli Vincoli iixxij ij == 1 (2) 1 (2)
jjxxij ij = 1 (3)= 1 (3)
Metodo dell’assegnazioneMetodo dell’assegnazione
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Metodi
Ing. Ferdinando Palazzo
I due vincoli indicano che una persona o una I due vincoli indicano che una persona o una macchina sono assegnate ad un unico job ed ogni macchina sono assegnate ad un unico job ed ogni job è processato da un unica macchina o un unica job è processato da un unica macchina o un unica personapersona
Il modello dell’assegnazione può essere anche Il modello dell’assegnazione può essere anche espresso da una tabella in cui le righe rappresentano espresso da una tabella in cui le righe rappresentano i job e le colonne rappresentano le macchine o i i job e le colonne rappresentano le macchine o i lavoratori a cui associare tali job. lavoratori a cui associare tali job. I valori interni alla tabella rappresentano il costo o il I valori interni alla tabella rappresentano il costo o il tempo impiegato per l’esecuzione di quel lavoro su tempo impiegato per l’esecuzione di quel lavoro su quella macchina o per quel lavoratorequella macchina o per quel lavoratore
Metodo dell’assegnazioneMetodo dell’assegnazione
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Metodi
Ing. Ferdinando Palazzo
Step
•1)1) Sottrarre il numero più piccolo in ogni riga per ogni numero di quella riga e poi 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 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, ha l’effetto di ridurre i numeri nella tabella fino ad ottenere una serie di zero, significando significando possibilità di costi zeropossibilità di costi zero..
•2)2) Tracciare il numero minimo di linee verticali e orizzontali necessari a coprire tutti 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 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 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, step 4). Se, invece, il numero di linee è minore del numero di righe o colonne, procedere allo step 3.procedere allo step 3.
•3)3) Sottrarre il numero più piccolo non coperto da una linea per ogni altro numero 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.non non coperto e aggiungere esso ai numeri presenti all’intersezioni delle due linee.
4)4) L’assegnazione ottima sarà sempre localizzata nello zero. Per una valida L’assegnazione ottima sarà sempre localizzata nello zero. Per una valida assegnazione selezionare una riga o una colonna che contiene solo uno zero. 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 L’assegnazione sarà eseguita relativamente alla riga e alla colonna che si intersecano in quello zero. Questo processo continuerà fin quando non sarà completata in quello zero. Questo processo continuerà fin quando non sarà completata l’assegnazione di ogni job a persone o macchinel’assegnazione di ogni job a persone o macchine
Metodo dell’assegnazioneMetodo dell’assegnazione
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Metodi
Ing. Ferdinando Palazzo
ESEMPIO
Step 1a. Step 1a. Sottrarre il numero più piccolo in ogni riga per ogni numero della riga stessaSottrarre il numero più piccolo in ogni riga per ogni numero della riga stessa
Metodo dell’assegnazioneMetodo dell’assegnazione
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Metodi
Ing. Ferdinando Palazzo
Step 1b. Eseguire la stessa operazione per le colonneStep 1b. Eseguire la stessa operazione per le colonne
Metodo dell’assegnazioneMetodo dell’assegnazione
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Metodi
Ing. Ferdinando Palazzo
Step 2. Tracciare il Step 2. Tracciare il minimo minimo numero di linee per coprire tutti gli zeri numero di linee per coprire tutti gli zeri presenti in tabella. Nel caso in esame sono solo due le linee ad essere presenti in tabella. Nel caso in esame sono solo due le linee ad essere tracciate per cui la soluzione ottima ancora non è determinatatracciate per cui la soluzione ottima ancora non è determinata
Metodo dell’assegnazioneMetodo dell’assegnazione
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Metodi
Ing. Ferdinando Palazzo
Step 3. Sottrarre il numero più piccolo non coperto (2 nella Step 3. Sottrarre il numero più piccolo non coperto (2 nella tabella) ad ogni altro numero non coperto ed aggiungere esso al tabella) ad ogni altro numero non coperto ed aggiungere esso al numero presente all’intersezione delle due righenumero presente all’intersezione delle due righe
Metodo dell’assegnazioneMetodo dell’assegnazione
La Programmazione Operativa - Applicazioni delle tecniche di Scheduling
Metodi
Ing. Ferdinando Palazzo
Ritornare allo step 2. Coprire gli zeri con un numero minimo di righeRitornare allo step 2. Coprire gli zeri con un numero minimo di righe
L’assegnazione ottimale sarà in corrispondenza degli zeri, per cui L’assegnazione ottimale sarà in corrispondenza degli zeri, per cui partendo dal job S-66, l’unica assegnazione possibile sarà quella alla partendo dal job S-66, l’unica assegnazione possibile sarà quella alla macchina B. Di conseguenza l’unica assegnazione possibile per T-50 macchina B. Di conseguenza l’unica assegnazione possibile per T-50 sarà quella alla macchina A, e quella per R-34 sarà C. sarà quella alla macchina A, e quella per R-34 sarà C. Quella trovata sarà la soluzione che minimizza i tempi, ed il tempo 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 totale sarà di 25, pari alla somma di 6, 10, e 9, ovvero i tre termini corrispondenti alle tre assegnazionicorrispondenti alle tre assegnazioni
Risultato finale
Fine I lezione sullo schedulingFine I lezione sullo scheduling