Torna alla pagina di Ricerca Operativa
:: Ricerca Operativa - PL - Trasmissioni da Marte - 10.10.06 ::
Testo del problema
I rover esploratori di Marte immagazzinano dati scientifici tramite i numerosi strumenti di cui sono dotati. Ogni strumento genera dati per un diverso banco di memoria. In dati intervalli di tempo è possibile trasmettere questi dati a Terra. Durante ognuno di questi intervalli le memorie possono essere lette – e quindi parzialmente svuotate – una sola per volta e con un bit-rate noto, che può essere diverso da intervallo ad intervallo. Il tempo disponibile per la trasmissione in ogni intervallo può essere distribuito a piacimento ai diversi banchi di memoria. Ogni banco di memoria, collegato ad un diverso dispositivo scientifico, ha capacità finita ed è gestito come un buffer first-in-first-out. Nel caso in cui la quantità di dati generati dallo strumento ad esso collegato ecceda la capacità del banco di memoria, i dati più antichi vengono sovrascritti da quelli più recenti ed ovviamente si vuole evitare – o per lo meno minimizzare la probabilità - che questo accada. Perciò l’obiettivo del pianificatore delle trasmissioni è di mantenere il più basso possibile in ogni banco di memoria il rapporto tra il livello di occupazione e la capacità. Questo serve a garantire la massima robustezza rispetto a possibili variazioni delle quantità di dati scientifici generati.
Formulare il problema, classificarlo e risolverlo con i dati del file MARTE.TXT. Discutere l’ottimalità della soluzione trovata.
Dati
Si consideri il problema con 6 banchi di memoria e 9 intervalli temporali.
Tab.1: Produzione dati (Mbit)
Strumento
Intervallo 1 2 3 4 5 6
1 4 11 31 3 18 27
2 6 8 34 4 19 23
3 7 23 38 5 21 19
4 3 31 35 6 15 18
5 3 14 37 7 14 23
6 8 8 35 6 14 24
7 1 10 31 5 14 25
8 3 20 40 4 18 20
9 4 13 28 5 19 13
Tab. 2: Capacità memoria (Mbit)
Strumento Capacità
1 32
2 60
3 100
4 30
5 50
6 80
Tab. 3: Livello iniziale di occupazione della memoria (Mbit)
Strumento Occupazione
1 8
2 15
3 25
4 5
5 16
6 23
Tab. 4: Tempo disponibile per la trasmissione (secondi)
Intervallo Durata Bit-rate
(Kbit/sec)
1 490 195
2 420 160
3 460 180
4 485 195
5 400 160
6 455 180
7 480 195
8 380 160
9 450 180
Formulazione del problema
Dati
- b = 6 (numero di banchi di memoria, intesi anche come strumenti)
- int = 9 (numero di intervalli temporali)
- prDatiij (produzione dati dallo strumento i=1..6 nell'intervallo j=1..9) [Mbit]
- capMemi (capacità memoria dello strumento i=1..6) [Mbit]
- occInii (occupazione iniziale memoria dello strumenti i=1..6) [Mbit]
- durIntj (durata dell'intervallo j=1..9) [secondi]
- brIntj (bit-rate dell'intervallo j=1..9) [Kbit / secondo]
Variabili
- xij (quantità dati trasmessi dallo strumento i=1..6 nell'intervallo j=1..9) [Mbit]
- yij (quantità di dati rimasti nello strumento i=1..6 dopo l'intervallo j=1..9) [Mbit]
Le variabili sono continue e non negative.
Funzione obiettivo
Vogliamo minimizzare il massimo livello di riempimento del banco di memoria dello strumento i. Dobbiamo quindi introdurre una variabile ausiliaria z, che definiremo poi nei vincoli.
min z
Vincoli
Nota prima di iniziare: poiché la soluzione sarà scritto in Lingo, non mi dovrò preoccupare di mettere variabili a sinistra e termini noti a destra o di linearizzare le espressioni.
Come prima cosa bisogna bilanciare i dati in ingresso con quelli in uscita. Definisco quindi due vincoli:
- un vincolo per la situazione iniziale (quindi l'indice che si riferisce all'intervallo dovrà essere sempre 1)
occInii + prDatii1 = xi1 + yi1 (per ogni i)
- un vincolo per tutte le altre situazioni. Per semplicità di notazione l'indice k è da intendersi come j-1, ovvero che fa riferimento all'intervallo precedente:
yik + prDatiij = xij + yij (per ogni i e per ogni intervallo con j diverso da 1)
Quest'ultimo vincolo si legge come “la somma tra la quantità di dati in memoria all'intervallo precedente e la quantità di dati prodotti, è uguale alla somma tra la quantità di dati trasmessi e la quantità di dati in memoria all'intervallo attuale”
Notare che il primo vincolo è praticamente identico al secondo, con la differenza che nel secondo caso la yik è nota: è il dato occInii
Altri vincoli:
- vincoli di capacità sulla quantità di dati che si possono trasmettere in ogni intervallo temporale:
(somma)i xij * 1000 <= brIntj * durataj (per ogni j)
Il motivo per cui moltiplico per 1000 il primo membro è perché il brIntj è espresso in Kbit/sec e non in Mbit/sec
- vincoli per definire la variabile ausiliaria z, quella che nella mia funzione obiettivo rappresenta il massimo livello di riempimento del banco di memoria dello strumento i:
z >= yij / capMemi (per ogni i e per ogni j)
Linghizzazione del problema
! esercizio - Trasmissioni da Marte;
model:
sets:
strumento /1..6/: capMem, occIni;
intervallo /1..9/: brInt, durInt;
coppia (strumento,intervallo): x, y,
prDati;
endsets
data:
prDati = 4 11 31 3 18 27
6 8 34 4 19 23
7 23 38 5 21 19
3 31 35 6 15 18
3 14 37 7 14 23
8 8 35 6 14 24
1 10 31 5 14 25
3 20 40 4 18 20
4 13 28 5 19 13;
capMem = 32 60 100 30 50 80;
occIni = 8 15 25 5 16 23;
durInt = 490 420 460 485 400 455 480 380 450;
brInt = 195 160 180 195 160 180 195 160 180;
enddata
! funzione obiettivo;
min = z;
! vincoli per il bilanciamento dei dati in ingresso con quelli in uscita;
! ...nel primo intervallo, con j = 1...;
@for(strumento(i): occIni(i) + prDati(i,1) = x(i,1) + y(i,1));
! ...e in tutti gli altri, con j != 1;
@for(strumento(i):
@for(intervallo(j) | j #GT# 1:
y(i,j-1) + prDati(i,j) = x(i,j) + y(i,j);
)
);
! vincoli di capacità sulla quantità di dati trasmessa;
@for(intervallo(j): @sum(strumento(i): x(i,j)) * 1000 <= brInt(j) * durInt(j));
! vincolo per definire la variabile ausiliaria z;
@for(strumento(i): @for(intervallo(j): z >= y(i,j) / capMem(i) ));
end
Torna alla pagina di Ricerca Operativa
