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

D I I

IPARTIMENTO DI NGEGNERIA DELL’ NFORMAZIONE E

S M

CIENZE ATEMATICHE

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: Candidato:

Prof. Alessandro Agnetis Valentina Bonaccini

Anno accademico 2018-2019 A Giulia

2

Indice

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

Capitolo1

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

1.2 Breve introduzioni alle euristiche………………………………………………10

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

Capitolo2

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

Capitolo3

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

Capitolo4

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

Capitolo5

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

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

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

4

Introduzione

In questo elaborato si pone l’attenzione sulla risoluzione di un particolare

decision-making

problema di scheduling. La schedulazione è un processo di “ ”

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 i 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

CAPITOLO1

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à Agnetis, Introduzione

(fonte:

I problemi di scheduling hanno dunque il compito di

ai problemi di scheduling ).

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;

o scorrelate;

o uniformi ( hanno diversa velocità di processamento ma

o 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

ij

macchina i sulla quale il lavoro j viene processato);

Duedate d : rappresenta la data entro il quale il lavoro j deve essere

 j

;

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 rispetti agli altri lavori;

 j

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

 kj

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;

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

C >d C <d

positiva se (lavoro in ritardo) oppure una quantità negativa se

j j j j

(lavoro in anticipo);

Tardiness(T =max{0; C – d })

: misura di quanto è in ritardo il lavoro rispetto

 j j j C >d

alla 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. Minimmizare:

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 Programmazione

Nei prossimi capitoli l’elaborato fornisce una formulazione di

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:

T

min c x

Ax ≥ b

∈ n

x 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

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 i

l