LA PROGRAMMAZIONE OPERATIVA APPLICAZIONE DELLE TECNICHE DI SCHEDULING Docente Consulente industriale...

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


Strumenti


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


OBIETTIVO DELLA RICERCA OBIETTIVO DELLA RICERCA INDUSTRIALEINDUSTRIALE


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 :


Introduzione


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


Introduzione


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


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?



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


Metodologie e strumenti


SCHEMA DEL FLUSSO DI INFORMAZIONESCHEMA DEL FLUSSO DI INFORMAZIONE

UI DBCPU

Acquisizione dei dati

Presentazionedel risultato

Connessione ed

ottenimentorisultato

Formattazionerisultato

ComposizioneStringa di ricerca



Tecnologia innovativa


Strumenti


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


Strumenti


DIAGRAMMA DIAGRAMMA WBSWBS


Strumenti


ATTIVITA’ DEL ATTIVITA’ DEL PROGETTOPROGETTO

Schema generico della fase Schema generico della fase

progettuale ed operativaprogettuale ed operativa


Strumenti



Strumenti


I

I

J

J

MACCHINA 1

MACCHINA 2

I

J I

JMACCHINA 1

MACCHINA 2



Strumenti


I

JI

JMACCHINA 1

MACCHINA 2

I

J I

JMACCHINA 1

MACCHINA 2


CARATTERISTICHE DEI PROTOTIPI CARATTERISTICHE DEI PROTOTIPI ATTUALMENTE VENDUTIATTUALMENTE VENDUTI



Introduzione

• VISIBILITA’VISIBILITA’

• SCALABILITA’SCALABILITA’

• ADOTTABILITA’ADOTTABILITA’

• FLESSIBILITA’FLESSIBILITA’

ESEMPI DI PROTOTIPIESEMPI DI PROTOTIPI



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


Definizioni


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


Definizioni


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


Definizioni


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


Definizioni


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


Cause ed effetti


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


Strumenti



• 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


Strumenti



• 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


Introduzione



Definizioni


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


Definizioni


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


Definizioni


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


Classificazione


• 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


Classificazione


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


Classificazione


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


Classificazione


ARCHITETTURAARCHITETTURAOPEN SHOPOPEN SHOP



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



Plant Layout


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



Plant Layout


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


Classificazione


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


Classificazione


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


Cause ed effetti



Classificazione


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


Classificazione


Metodi di ottimizzazione analiticiMetodi di ottimizzazione analitici


Definizioni


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


Definizioni


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


Definizioni


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


Definizioni


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


Definizioni


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


Definizioni


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


Definizioni


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


Definizioni


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


Definizioni


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.


Strumenti


È 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à


Cause ed effetti



Definizioni


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


Definizioni


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


Definizioni


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


Definizioni


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à.


Definizioni


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


Definizioni


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


Definizioni


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


Metodi


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



Metodi


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)



Metodi


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)



Metodi


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



Metodi


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



Metodi


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



Metodi


Step 1b. Eseguire la stessa operazione per le colonneStep 1b. Eseguire la stessa operazione per le colonne



Metodi


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



Metodi


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



Metodi


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

LA PROGRAMMAZIONE OPERATIVA APPLICAZIONE DELLE TECNICHE DI SCHEDULING Docente Consulente industriale...

Documents

Transcript of LA PROGRAMMAZIONE OPERATIVA APPLICAZIONE DELLE TECNICHE DI SCHEDULING Docente Consulente industriale...