Un modello di PLI e un'euristica risolutiva per un problema si scheduling a singola macchina soggetta a rotture e vincoli di precedenza

Dipartimento di ingegneria dell’informazione e scienze matematiche

Corso di Laurea in Ingegneria gestionale

Un modello di PLI e un’euristica risolutiva per un problema di scheduling su singola macchina soggetta a rotture e vincoli di precedenza

Relatore: Prof. Alessandro Agnetis

Candidato: Valentina Bonaccini

Anno accademico 2018-2019 A Giulia 2

Indice

Introduzione…………………………………………………………………………………5

Capitolo 1

1.1 Introduzione ai problemi di scheduling………………………………………………7

1.2 Breve introduzione alle euristiche……………………………………………………10

1.3 Breve introduzione alla PLI…………………………………………………………..10

Capitolo 2

2.1 Presentazione del problema…………………………………………………………...12

2.1.1 Analisi del problema………………………………………………………………..13

2.2 UJP(1): risoluzione del problema senza vincoli di precedenza…………………….14

2.2.1 Esempio UJP(1)…………………………………………………………………….15

Capitolo 3

Introduzione………………………………………………………………………………..16

3.1 Euristica1………………………………………………………………………………16

3.1.1 Esempio di applicazione dell’Euristica1………………………………………….17

3.2 Euristica2………………………………………………………………………………21

3.2.1 Esempio di applicazione dell’Euristica2………………………………………….22

3.3 Modello di PLI…………………………………………………………………………25

Capitolo 4

4.1 Introduzione…………………………………………………………………………....27

4.2 Implementazione delle Euristiche e della PLI……………………………………...28

4.2.1 Euristiche e C++…………………………………………………………………....29

4.2.2 PLI e CPLEX……………………………………………………………………….29

4.3 Caso1: probabilità uniformi…………………………………………………………..30

4.4 Caso2: rotture esponenziali………………………………………………………….36

3 4.5 Conclusioni………………………………………………………………………….43

Capitolo 5

Appendice………………………………………………………………………………….44

Bibliografia…………………………………………………………………………………61

Sitografia…………………………………………………………………………………...61

4

Introduzione

In questo elaborato si pone l’attenzione sulla risoluzione di un particolare problema di decision-making di scheduling. La schedulazione è un processo di “decision-making” che consiste nell'allocare risorse finite in modo tale che un dato obiettivo venga ottimizzato.

Nell’elaborato viene analizzato un problema di scheduling a macchina singola soggetto a rotture e vincoli di precedenza. Si tratta di un problema abbastanza complesso per il quale si introducono diversi metodi risolutivi con l’obiettivo di definire quale metodo è il migliore. Oltre alla comparazione dei diversi metodi in questa tesi viene analizzato il tempo di risoluzione impiegato dalla PLI per risolvere il problema in esame, testato al variare di alcuni parametri.

Il corpo dell’elaborato è così strutturato:

• Nel primo capitolo della tesi vengono introdotti i problemi di scheduling con una descrizione sulle diverse tipologie esistenti e sulle caratteristiche che ciascun problema può presentare. Si introducono inoltre i concetti di euristica e PLI fondamentali per comprendere i metodi risolutivi riportati in seguito;
• Nel secondo capitolo vi è la presentazione del problema in esame e si riporta la risoluzione dell’UJP(1). UJP(1) è la versione semplificata del problema in analisi la quale non presenta vincoli di precedenza. L’introduzione e la risoluzione di tale problema sarà fondamentale per la definizione delle euristiche nel capitolo successivo;
• Nel terzo capitolo i tre metodi risolutivi vengono presentati con relativi esempi. Vengono riportate due euristiche risolutive ed una formulazione di Programmazione Lineare Intera;
• 5 Nel quarto capitolo vengono riportati i metodi di implementazione delle euristiche e della PLI e i risultati ottenuti dai test in base alle diverse casistiche studiate. In particolare vengono analizzate due tipologie di problema: in un primo caso le rotture della macchina avvengono con probabilità uniformi, nel secondo si studia il comportamento dei metodi risolutivi quando la macchina è soggetta a rotture di tipo esponenziale.
• Nel quinto capitolo vengono riportati i codici utilizzati per implementare i metodi risolutivi.

6

Capitolo 1

1.1 Introduzione ai problemi di scheduling

La classe dei problemi di scheduling è molto vasta e può contenere problemi di tipologia e complessità molto diverse, motivo per il quale la sua definizione risulta poco scontata. Facendo riferimento all’ambito applicativo in cui questi problemi sono nati possiamo affermare che i problemi di scheduling sono tutti quei problemi decisionali in cui riveste importanza il fattore tempo, visto come risorsa scarsa da allocare in modo ottimo a determinate attività fonte: Agnetis, Introduzione ai problemi di scheduling.

I problemi di scheduling hanno dunque il compito di assegnare le risorse per esempio le macchine ad un insieme di operazioni attività, lavori con il fine di determinare i tempi di inizio e fine di ogni attività su ogni macchina e con l’obiettivo di perseguire determinate misure di performance.

Possono essere elencate diverse tipologie di problemi di scheduling:

• A macchina singola: è disponibile solo una macchina per il processamento dei lavori;
• A macchine parallele: sono disponibili più macchine per il processamento dei lavori. Ogni lavoro viene processato da una sola macchina. A loro volta si dividono in: identiche; scorrelate; uniformi hanno diversa velocità di processamento ma stesso fattore di proporzionalità;
• 7 Flow shop: le macchine sono in serie, tutti i lavori visitano tutte le macchine nello stesso ordine;
• Job shop: le macchine non sono più in serie. I lavori possono visitare una o più macchine seguendo diversi percorsi.

Oltre alla caratterizzazione delle macchine in un problema di scheduling anche i lavori presentano determinate caratteristiche. Considerando il numero delle macchine pari a m e il numero dei lavori pari a n si può attribuire al lavoro j:

• Tempo di processamento p: rappresenta il tempo necessario al lavoro i j p per essere processato. Lo indichiamo con se caratteristico della macchina i sulla quale il lavoro j viene processato;
• Duedate d: rappresenta la data entro il quale il lavoro j deve essere terminato;
• Release date rj: rappresenta l’istante di rilascio del lavoro j. Prima della date di rilascio il lavoro j non può essere processato.;
• Peso w: rappresenta la priorità del lavoro j rispetto agli altri lavori;
• Vincoli di precedenza: in molti casi esistono vincoli di precedenza tra i lavori;
• Preemption: in alcuni problemi di scheduling esiste la possibilità di interrompere i lavori. Un lavoro può essere interrotto, per esempio, per permettere l’esecuzione di un altro lavoro più urgente;
• Tempo di set-up s: rappresenta il tempo necessario alla macchina per passare dal lavoro k al lavoro j.

Dunque l’obiettivo dei problemi di scheduling è quello di ottenere uno schedule dei lavori sulle macchine perseguendo determinate misure di performance. Per andare ad analizzare le più “famose” misure di performance per questa tipologia di problemi devono essere introdotte alcune misure di performance relative ai singoli lavori. Dato il lavoro j con duedate d e release date r: j j 8

• C rappresenta il tempo di completamento del lavoro j;
• Tempo di attraversamento (F = C – r): rappresenta il tempo in cui il lavoro j j j j rimane nel sistema;
• Lateness (L = C – d): è una misura di quanto il lavoro viene completato in j j j anticipo o in ritardo rispetto alla data di consegna. Può essere una quantità positiva se C > d lavoro in ritardo oppure una quantità negativa se C < d lavoro in anticipo; j j j j
• Tardiness (T = max{0; C – d}): misura di quanto è in ritardo il lavoro rispetto j j j C > dalla duedate. Si tratta di una quantità positiva se dunque se il lavoro j j è in ritardo, se il lavoro è in anticipo la Tardiness va a zero. Non è mai negativa;
• Earliness (E = max{0; d – C): misura di quanto il lavoro j è in anticipo j j j rispetto alla duedate. Se il lavoro è in ritardo la earliness va a zero;

Possono dunque ora essere elencate quelle che sono le più utilizzate misure di prestazione per i problemi di scheduling. Minimizzare:

• Somma di completamento di tutti i lavori -> ∑ j;
• Flow time totale -> ∑ j;
• Makespan: rappresenta il tempo di completamento di tutto il sistema. Minimizzare il makespan significa minimizzare il tempo di completamento del lavoro che ci mette più tempo. -> C = max C; max j j
• Lateness -> L max L; max= j j
• Tardiness -> T max T. max= j j

9

1.2 Breve introduzione alle euristiche

Per poter introdurre le euristiche che verranno utilizzate per la risoluzione del problema di scheduling è doveroso dedicare una piccola parte di questo elaborato alla spiegazione di cosa si intende con il termine “euristica”.

“Eurìstico agg. [der. del gr. εὑρίσκω «trovare, scoprire»]: […] qualsiasi procedimento non rigoroso (a carattere approssimativo, intuitivo, analogico ecc..) che consente di prevedere o rendere plausibile un risultato, il quale in un secondo tempo dovrà essere controllato e convalidato per via rigorosa.” (fonte: Treccani).

Dal significato del termine “euristico” si deduce come le euristiche siano dei metodi che non garantiscono una soluzione ottima del problema ma permettono di avvicinarsi a quest’ultima fornendo delle soluzioni sperabilmente vicine all’ottimo. Per un problema nel quale si vuole massimizzare la funzione obiettivo come nel caso trattato le euristiche determinano un Lower Bound (≤) sul valore della soluzione ottima.

1.3 Breve introduzione alla PLI

Nei prossimi capitoli l’elaborato fornisce una formulazione di Programmazione Lineare Intera risolutiva per il problema in esame. Si riporta dunque, per completezza, una breve introduzione alla PLI.

La Programmazione Lineare Intera tratta il problema della minimizzazione massimizzazione di una funzione lineare di più variabili, soggetta a vincoli di 10 uguaglianza e disuguaglianza lineari ed alla restrizione che una o più variabili possano assumere soltanto valori interi. Si tratta dunque di problemi del tipo:

Tmin c x

Ax ≥ b

∈ nx Z

In figura1 si riporta la rappresentazione grafica del problema. Trattandosi di un problema di Programmazione Lineare Intera è facile intuire che la regione ammissibile sia costituita dai soli punti a coordinate intere rappresentati in rosso in figura. “Appunti di introduzione alla ricerca operativa”, Figura1 fonte: Federico Malucelli.

11

Capitolo 2

2.1 Presentazione del problema

Grazie alla panoramica effettuata nei paragrafi precedenti si è ora in grado di introdurre il problema preso in esame in questo elaborato. L’oggetto della trattazione è un problema di scheduling a macchina singola soggetta a rotture e vincoli di precedenza.

Sia n il numero dei lavori. Per ogni lavoro j si ha:

• π -> probabilità di successo del lavoro j indipendenti - j
• r -> guadagno ottenuto dall’esecuzione del lavoro j - j
• Vincoli di precedenza -

Obiettivo: trovare un sequenziamento dei lavori in grado di massimizzare il guadagno. σ

12

2.1.1 Analisi del problema

Osservazione: I lavori che caratterizzano il problema presentano release date nulle. Questo comporta che tutti i lavori presi in considerazione saranno disponibili all’istante iniziale e che il tempo di completamento del progetto corrisponde alla sommatoria dei tempi di processamento dei singoli lavori (P=∑ soluzione ottima del problema di scheduling presenterà dunque). La j a tutti i lavori sequenziati uno dopo l’altro senza periodi di inattività per la singola macchina.

L’obiettivo del problema in questione è quello di trovare una schedulazione dei lavori che rispetti ovviamente i vincoli di precedenza e massimizzi il guadagno finale. Si va ad analizzare la funzione obiettivo: essendo la macchina soggetta a rotture questa potrebbe rompersi durante il processamento di un lavoro. Se questo accade tutti i lavori successivi a quest’ultimo non saranno più processati almeno fino a quando la macchina non sarà sistemata. Per questo motivo la funzione obiettivo che possiamo andare ad analizzare è il valore atteso del guadagno ER[σ] con σ sequenza dei lavori associata alla macchina. Sia σ(j) il lavoro nella j-esima posizione nello schedule σ. Allora ER[σ] si ottiene dalla somma dei contributi dei lavori considerando il fatto che un lavoro viene svolto solo se la macchina non si blocca svolgendo i lavori che lo precedono nello schedule σ o svolgendo lui stesso. Avendo probabilità di successo indipendenti si ha: π r + π π r + … + π … π π r ER[σ]= σ(1) σ(1) σ(1) σ(2) σ(2) σ(1) σ(k-1) σ(k) σ(k) 13

2.2 UJP(1): risoluzione del problema senza vincoli di precedenza

Si studia un caso più semplice del problema in esame in cui i lavori che devono essere schedulati nella macchina non presentano vincoli di precedenza. Il problema così presentato prende il nome di UJP(1). L’analisi di questo problema risulterà fondamentale in seguito per la definizione dei metodi di risoluzione riportati per il problema di partenza.

Siano n i lavori i lavori da assegnare ad una singola macchina soggetta a rotture. Per ogni lavoro j si ha:

• π -> probabilità di successo del lavoro j indipendenti - j
• r -> guadagno ottenuto dall’esecuzione del lavoro j - j

Teorema: La sequenza ottima per il problema UJP(1) si ottiene processando il