Si formuli il modello in AMPL con i dati relativi all’istanza sotto.

Un cluster di calcolo di m macchine riceve n processi. I tempi (in minuti) stimati per l’esecuzione di ogni processo j ≤ n su ciascuna macchina i ≤ m sono dati da p ij . Si consideri un orizzonte di programmazione temporale T . In ogni periodo temporale che inizia al tempo t, con t ∈ {0, . . . , T − 1}, ogni macchina i ≤ m pu`o lavorare al pi` u su un processo j ≤ n. Si sa inoltre che per ogni coppia ordinata di processi (j, k) in un dato insieme A `e necessario che il processo j termini prima del processo k. Il problema `e quello di trovare un assegnamento dei processi alle varie macchine in modo che il tempo totale di completamento di tutti sia minimo (e che tutti i vincoli siano rispettati).

Si formuli il modello in AMPL con i dati relativi all’istanza sotto.

m = 3, n = 6, T = 10 A = {(1, 2), (2, 3), (1, 5), (2, 6)}

p _ij 1 2 3 4 5 6

1 3 4 2 7 8 3

2 6 8 4 9 3 4

3 4 1 5 6 7 4

Soluzione

Formulazione .

• Indici:

– sia i un indice sull’insieme delle macchine (i ≤ m);

– sia j un indice sull’insieme dei processi (j ≤ n);

– sia t un indice sui periodi temporali (t ∈ {0, . . . , T − 1).

• Parametri: sia p ij il tempo di esecuzione del processo j sulla macchina i.

• Variabili:

– sia x ^t _ij = 1 se il processo j `e assegnato alla macchina i e inizia al tempo t, e 0 altrimenti (x ^t _ij ∈ {0, 1});

– sia C j il tempo di completamento del processo j.

• Funzione obiettivo:

min max

j≤n C _j

• Vincoli:

– (ogni processo assegnato a esattamente una macchina in un periodo temporale):

per ogni j ≤ n:

T P −1 t=0

P m i=1

x ^t _ij = 1;

– (ogni macchina esegue al massimo un lavoro in ogni periodo temporale): per ogni i ≤ m, t ∈ {0, . . . , T − 1}:

P n j=1

t−1 P

s=max{t−p

,0}

x ^s _ij ≤ 1;

– (tempo di completamento): per ogni j ≤ n: C j =

T P −1 t=0

P m i=1

(t + p ij )x ^t _ij ;

– (precedenze): per ogni (j, k) ∈ A, i ≤ m, t ∈ {0, . . . T − 1}: x ^t _ik ≤ P m h=1

t−p P

s=0

x ^s _hj .

# scheduling.mod param m >= 0;

param n >= 0;

param T > 0;

set Macchine := 1..m;

set Processi := 1..n;

set Orizzonte := 0..T-1;

set A within {Processi, Processi};

param useless {A};

param p {Macchine, Processi} >= 0;

var x {Macchine, Processi, Orizzonte} binary;

var C {Processi} >= 0;

var maxt >= 0;

minimize tempo: maxt;

subject to riformulazionemax {j in Processi} : maxt >= C[j];

subject to assegnamento {j in Processi} :

sum{t in Orizzonte, i in Macchine} x[i,j,t] = 1;

subject to limitemacchina {i in Macchine, t in Orizzonte} : sum{j in Processi, s in max(t-p[i,j],0)..(t-1)} x[i,j,s] <= 1;

subject to completamento {j in Processi} :

sum{t in Orizzonte, i in Macchine} (t + p[i,j])*x[i,j,t] = C[j];

subject to precedenze {(j,k) in A, i in Macchine, t in Orizzonte} : x[i,k,t] <= sum{h in Macchine, s in 0..t-p[h,j]} x[h,j,s];

File dati in AMPL

# scheduling.dat

param m := 3;

2 3 0 1 5 0 2 6 0 ;

Soluzione

CPLEX 8.1.0: optimal integer solution; objective 9 196 MIP simplex iterations

42 branch-and-bound nodes tempo = 9.0000

x [1,*,*] (tr)

: 1 2 3 4 5 6 :=

0 0.0000 0.0000 0.0000 1.0000 0.0000 0.0000 1 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 2 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 3 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 4 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 5 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 6 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 7 0.0000 0.0000 1.0000 0.0000 0.0000 0.0000 8 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 9 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000

[2,*,*] (tr)

: 1 2 3 4 5 6 :=

0 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 1 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 2 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 3 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 4 0.0000 0.0000 0.0000 0.0000 1.0000 0.0000 5 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 6 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 7 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 8 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 9 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000

[3,*,*] (tr)

: 1 2 3 4 5 6 :=

0 1.0000 0.0000 0.0000 0.0000 0.0000 0.0000

1 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000

2 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000

3 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000

4 0.0000 1.0000 0.0000 0.0000 0.0000 0.0000

5 0.0000 0.0000 0.0000 0.0000 0.0000 1.0000

6 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000

7 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000

8 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000

C [*] :=

1 4.0000 2 5.0000 3 9.0000 4 7.0000 5 7.0000 6 9.0000

;