cerca
Ricerca Operativa - PLI - 3 novembre 2004
modifica cronologia stampa login logout

Wiki

UniCrema


Materie per semestre

Materie per anno

Materie per laurea


Help

Uni.3Novembre2004-RO-PLI-3novembre2004 History

Show minor edits - Show changes to output

Changed line 53 from:
Quello che dobbiamo scoprire è in che istante far partire il j-esimo {-Steve-} job{-s-}:
to:
Quello che dobbiamo scoprire è in che istante far partire il j-esimo [[{-Steve-} job{-s-} -> http://uncyclopedia.wikia.com/wiki/Steve_Jobs]]:
Changed lines 122-123 from:
! 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;
to:
! 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;
Changed lines 64-66 from:
!!!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
to:
!!!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
Changed line 162 from:
[[Torna alla pagina di Ricerca Operativa -> Ricerca Operativa]]
to:
[[Torna alla pagina di Ricerca Operativa -> Ricerca Operativa]]
Added lines 3-44:

!! 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&#8217;essere finito quello precedente.\\
Per ogni job sono noti gli istanti iniziale e finale di una finestra temporale all&#8217;interno della quale deve iniziare e terminare la lavorazione.\\
Sull&#8217;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&#8217;anticipo con cui mediamente i jobs vengono completati rispetto alla loro scadenza, cioè all&#8217;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

@]
Changed lines 3-23 from:
!!...da sistemare...
to:
!!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-} job{-s-}:
* 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
Added lines 1-65:
(:title Ricerca Operativa - PLI - 3 novembre 2004:)
%titolo%''':: Ricerca Operativa - PLI - 3 novembre 2004 ::'''
!!...da sistemare...

[@
! 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 -> Ricerca Operativa]]