Swappa : Uni / Ricerca Operativa - PLI

 :: Ricerca Operativa - PLI - 3 novembre 2004 ::

Testo

Una macchina utensile deve svolgere una serie di operazioni (jobs). Di ogni job è nota la durata. I jobs ovviamente non si possono sovrapporre: per poterne iniziare uno dev’essere finito quello precedente.
Per ogni job sono noti gli istanti iniziale e finale di una finestra temporale all’interno della quale deve iniziare e terminare la lavorazione.
Sull’obiettivo i responsabili della pianificazione della produzione discutono; si vorrebbero considerare diverse possibilità.
* Un primo obiettivo è quello di minimizzare il tempo complessivo necessario ad eseguire tutti i jobs.

Un secondo obiettivo consiste nel minimizzare il tempo medio di completamento dei jobs.
Un terzo obiettivo consiste nel massimizzare l’anticipo con cui mediamente i jobs vengono completati rispetto alla loro scadenza, cioè all’istante finale della loro finestra temporale.

Formulare il problema, classificarlo e risolverlo nei tre casi indicati con i dati del file SCHEDULE.TXT.

I jobs sono 7.

========================================

Tabella 1: Tempi di lavorazione

 Job Tempo
  1   10  
  2   14  
  3   21  
  4   18  
  5    4  
  6   23  
  7   35

========================================

Tabella 2: Finestre temporali

 Job  Inizio   Fine
  1     15      50
  2      0      80
  3      0      95
  4     10      75
  5      5      30
  6     13     130
  7     18     120

Soluzione

Dati

Allora, quello che abbiamo sono:

N ~~blow~~jobs
d_j, j=1..N : durata di un job [misteriosa unità di tempo]
a_j, b_j, j=1..N : finestra temporale di ogni job, dove a è l'inizio e b la fine

Variabili

Quello che dobbiamo scoprire è in che istante far partire il j-esimo ~~Steve~~ jobs:

t_j, j=1..N : istante di inizio del j-esimo job, variabile continua non negativa.

È continua non negativa perché qualsiasi istante dopo lo 0 va bene.

Vincoli

Il primo vincolo riguarda la finestra temporale. Il testo ci dice che un job ha una finestra temporale che gli è stata assegnata, e deve iniziare e terminare dentro di essa. Quindi, l'istante iniziale del job deve essere >= all'istante di inizio della sua finestra temporale, e l'istante finale deve essere <= all'istante finale della sua finestra temporale:

t_j >= a_j, j=1..N : deve iniziare dopo l'inizio della sua finestra temporale
t_j + d_j <= b_j : deve finire entro l'istante temporale.

t_j + d_j mi dà l'esatto istante in cui finisce il job, perché sommo l'istante in cui comincia con la sua durata, la quale è un dato.

Ancora variabili...

Torniamo a parlare delle variabili. Quelle di sopra erano quelle più facilmente riconoscibili leggendo il testo. Però, approfondendo il discorso salta fuori che ci sono altre cose di cui occorre tenere traccia.

La prima è che i job non si possono sovrapporre. Qui entrano in ballo le variabili binarie: prendo una bella tabella N*N, in cui la casella (i,j) vale 1 se il job i precede il job j, 0 altrimenti. La tabella la chiamiamo y:

y_i,j binaria, i,j=1..N : il lavoro i precede il lavoro j se vale 1, 0 altrimenti

...e ancora vincoli

La nuova variabile y introduce un'altro problema: se il lavoro i precede il lavoro j, allora vuol dire che t_i + d_i <= t_j, cioè l'istante di fine del lavoro i deve precedere l'istante di inizio del lavoro j. Al contrario, se j precede i, allora t_j + d_j <= t_i:

se y_i,j = 1, t_i + d_i <= t_j
se y_i,j = 0, t_j + d_j <= t_i

Per rappresentare queste condizioni, usiamo un trucco barbino che non sarebbe mai venuto in mente in sede d'esame. Prendiamo una variabile M, di valore molto grande, e la usiamo in questo modo:

t_i + d_i <= t_j + M(1-y_i,j)
t_j + d_j <= t_i + M(y_i,j)

In pratica, moltiplicando M per il valore di y in corrispondenza di i e ''j, è come se dicessimo:

se y vale 1 (cioè i precede j), allora 1-y vale 0, e quindi M*0 = 0, e in questo caso diventa stringente il primo vincolo, che dice che l'istante finale di i deve essere minore dell'istante iniziale di j
se y vale 0 (cioè i segue j), allora 1-y vale 1, e quindi M*1 = M, e in questo caso diventa stringente il secondo vincolo, che dice che l'istante iniziale di j deve essere minore dell'istante iniziale di i

C'è anche un'altra cosa da dire: se il job i precede j, ovvero ha un 1 nella cella y_i,j, allora NON deve accadere che j preceda i, cioè che ci sia un 1 ANCHE nella cella y_j,i:

y_i,j + y_j,i = 1

Funzioni obiettivo

Minimizzare il massimo tempo impiegato

Il tempo impiegato è dato da SOMMA(j): t(j) + i(j), per ogni lavoro: istante iniziale più durata di ogni lavoro. Vogliamo che questa somma sia minima, e quindi:

min = delta;
delta >= t_j + d_j, per ogni j

Minimizzare il tempo medio di completamento

Per il tempo medio di completamento, prendo tutti i tempi di completamento e ne faccio la media:
min = 1/7 * @sum(jobs(j): t(j) + d(j));

Massimizzare l'anticipo medio con cui un job termina rispetto alla sua finestra massima

Un job deve terminare, come scritto nei vincoli, entro l'istante finale della sua finestra temporale. Qui vogliamo che la media delle differenze tra istante finale effettivo e istante finale massimo consentito (fine della finestra) sia massima:
max = 1/7 * @sum(jobs(i): b(i) - a(i) + t(i));

Codice Lingo

! 3 novembre 2004 - Scheduling;

model:

sets:
jobs /1..7/: durata, iniziowin, finewin, t;
schedule (jobs,jobs): y;

endsets

data:
durata = 10 14 21 18 4 23 35;
iniziowin = 15 0 0 10 5 13 18;
finewin = 50 80 95 75 30 130 120;
M = 1000;

enddata

! Ci sono 3 funzioni obiettivo:
! 1) minimizzare il tempo complessivo necessario al completamento di 
! tutti i job (min makespan)
! Si tratta di minimizzare il massimo tempo, quindi un min max.
! Introduco una variabile ausiliaria delta;
!min = delta;
!@for(jobs(j): delta >= t(j) + durata(j));

! 2) Minimizzare il tempo medio di completamento;
!min = 1/7 * @sum(jobs(i): t(i) +durata(i));

! 3) Massimizzare l'anticipo medio con cui i jobs terminano il loro lavoro;
max = 1/7 * @sum(jobs(i): finewin(i) - (iniziowin(i) + durata(i)));

! Vincoli sulle finestre temporali;
@for (jobs(j): t(j) >= iniziowin(j));
@for (jobs(j): t(j) + durata(j) <= finewin(j));

! Vincoli di non sovrapposizione;
! Ho un vincolo per ogni coppia di job => 2 cicli for innestati;
@for (jobs(i):
	@for(jobs(j) | i #NE# j: t(i) + durata(i) <= t(j) + M * (1 - y(i,j))
	)
);

@for (jobs(i):
	@for(jobs(j)  | i #NE# j: t(j) + durata(j) <= t(i) + M * y(i,j)
	)
);

@for (schedule(i,j)  | i #NE# j: y(i,j) + y(j,i) = 1);

! Per evitare di fare due volte lo stesso conto, scrivo LT: lesser than, così
! fa il giro una volta sola;
!@for (schedule(i,j)  | i #LT# j: y(i,j) = 1);


@for(schedule(i,j): @bin(y(i,j)));

end

Torna alla pagina di Ricerca Operativa