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

DENSITÀgrafo8: andamento dello scostamento per λ=0,001.

Come già fatto per il caso studiato precedentemente caratterizzato da probabilità uniformi anche in questo caso è riportata (grafo9) l’analisi dell’andamento del tempo di risoluzione della Programmazione Lineare Intera.

6000
5000
4000
3000 velocità PLI
2000
1000
0,1 0,183 0,208 0,217 0,242 0,243 0,25 0,29

densitàgrafo9: andamento del tempo di risoluzione della PLI nel caso λ=0,001

Il grafo riportato conferma i risultati ottenuti dall’analisi del caso con probabilità uniformi ovvero il progressivo aumento del tempo di risoluzione della PLI per valori sempre più bassi della densità del grafo delle precedenze. Per istanze caratterizzate da grafi con densità maggiori del 24% il tempo di risoluzione diminuisce notevolmente oscillando in un intervallo compreso tra i 10 ed i 30 secondi (grafo10).

3880
7060
6050
4030
2010
0,217 0,242 0,243

aumentanotevolmente.12001000800secondi 600 velocità PLI4002000 0,05 0,083 0,225 0,233 0,24 0,243 0,258 0,267 0,275densitàgrafo12: andamento del tempo di risoluzione per λ=0,01

Andando ad analizzare istanze con grafi caratterizzati da densità maggiori del 22,5% la PLI risulta particolarmente veloce nella risoluzione del problema.54,543,53secondi 2,521,510,50 0,225 0,233 0,24 0,243 0,258 0,267 0,275densità40grafo13: velocità di risoluzione nel caso λ=0,01 per densità maggiori del 22,5%

Caso3:Viene qui riportato l’ultimo caso studiato in questo elaborato ovvero quello in cui λ=0,1. Le istanze caratterizzate da questo valore di λ presentano probabilità e valori della funzione obiettivo molto bassi. Anche in questo caso viene riportatal’analisi dell’andamento dello scostamento e del tempo impiegato dalla PLI perla risoluzione del problema. Partendo con l’analisi dello scostamento, andando

analizzare il grafo14, si riscontra ancora una volta come le soluzioni trovate dall'Euristica1 non solo siano migliori (nella maggior parte dei casi) di quelle trovate dalla seconda ma sono inoltre molto vicine alla soluzione ottima ottenuta dalla PLI.

10,98

9,60

9,40

9,20

9,00

8,80

8,86

SECONDI

0,84

0,82

E1/PLI

0,80

0,78

E2/PLI

0,76

0,74

0,72

0,70

0,68

0,66

0,05

0,117

0,15

0,208

0,233

0,242

0,275

0,292

DENSITÀ

grafo14: andamento dello scostamento con λ=0,1

41

Essendo un problema caratterizzato da valori di π non elevati la velocità di risoluzione della PLI è molto alta. Si può notare come per istanze con grafi poco densi il tempo di risoluzione aumenta in modo impercettibile.

1,9

1,8

1,7

1,6

secondi

1,5

velocità PLI

1,4

1,3

1,2

0,05

0,117

0,15

0,208

0,233

0,242

0,275

0,292

densità

grafo15: andamento del tempo di risoluzione nel caso λ=0,14

24.5

Conclusioni

Scopo principale dell'elaborato era andare a definire ed analizzare dei metodi di risoluzione per

della Programmazione Lineare Intera dipende da due diversi fattori:

I valori delle probabilità π: il tempo di risoluzione aumenta per istanze caratterizzate da valori di π maggiori;

La densità del grafo delle precedenze: il tempo di risoluzione aumenta notevolmente per istanze caratterizzate da grafi delle precedenze poco densi.

La combinazione dei due fattori comporta un peggioramento significativo della velocità di risoluzione della PLI nella risoluzione del problema.

CAPITOLO 5

Appendice

Si riportano i codici in C++ e CPLEX utilizzati per l'implementazione delle euristiche e della PLI.

Implementazione delle euristiche, generazione dei dati e risultato ottenuto dalle euristiche (C++):

#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>
#include <chrono>
#include <random>
#include <algorithm>
#include <fstream>
#include <iomanip>
using namespace std;
class Process{
protected:
string

name;int NumeroPredecessori;float rj;float pj;float zj;vector<Process> ancestor;bool done=false;bool operator==(const Process &c){ return this->getName()==c.getName()&&this->zj==c.zj;}inline double prob(default_random_engine b){ std::uniform_real_distribution<double> distribution (0.1,1.0);return distribution(b);} 44public :Process(){ rj=rand() % 100;pj=0;zj=(rj*pj)/(1-pj);};Process(string name,default_random_engine a){ rj=rand() % 100;pj=prob(a);zj=(rj*pj)/(1-pj);setName(name);};Process(string name,float ri,float pi){ rj=ri;pj=pi;zj=(float)(rj*pj)/(float)(1-pj);setName(name);};Process(const Process& pro){ rj=pro.rj;pj=pro.pj;zj=pro.zj;name=pro.name;ancestor=pro.ancestor;done=pro.done;}~Process(){ ancestor.clear();}const bool isDone() {return done;} constvoid finished() {done= true;}void addAncestor(const Process p){ ancestor.push_back(p);NumeroPredecessori++;}inline vector<Process> getAncestor() const{ 45return this->ancestor;}float

vector<double> a;
std::uniform_real_distribution<double> distribution (0.0,1.0);
for(int i=0;i<l;i++)
    a.push_back(distribution(b));
return a;
}

inline vector<double> prob(int l,int lambda){
    vector<double> a;
    for(int i=0;i<l;i++)
        a.push_back(trunc((exp(-lambda))*100)/100);
    return a;
}

int maxindex(vector<Process> p,vector<Process> order){
    int maximum_zj;
    for(unsigned int k=0;k<p.size();k++){
        if(!checkName(p[k].getName(),order)){
            maximum_zj=k;
            break;
        }
    }
    for(unsigned int i=1;i<p.size();i++){
        if(p[i].getValues(2)>p[maximum_zj].getValues(2)&&!checkName(p[i].getName(),order)){
            maximum_zj=i;
        }
    }
    return maximum_zj;
}

public:
Generator (int dimensions,default_random_engine a){
    rng=a;
    dim=dimensions;
    elements=new Process*[dim];
    vector<double> valori;
    valori=prob(a,dim*dim);
    for(int i=0;i<dim;i++){
        elements[i]=new Process[dim];
    }
    for (int i=0;i<dim;i++){
        for(int j=0;j<dim;j++){
            elements[i][j].setValues(valori.back(),0);
            valori.pop_back();
            cout

<< elements[i][j].getValues(0)<<endl;
elements[i][j].setName(to_string((i*dim) + j));
}}}
Generatorv(int dimensions,double lambda){
    dim=dimensions;
    elements=new Process*[dim];
    for(int i=0;i<dim;i++){
        elements[i]=new Process[dim];
    }
    for (int i=0;i<dim;i++){
        for(int j=0;j<dim;j++){
            elements[i][j].setValues(exp(-lambda*elements[i][j].getValues(1)),0);
            cout<<elements[i][j].getValues(1)<<endl;
            cout << elements[i][j].getValues(0)<<endl;
            elements[i][j].setName(to_string((i*dim) + j));
        }
    }
}
inline vector<Process>