Esercizio 1 Si consideri il problema 1/chain/

Sistemi Organizzativi a.a. 2006-2007

prova scritta 11-07-2007

Esercizio 1 Si consideri il problema 1/chain/

C

. Denotiamo con PrecSPT la seguente regola: ad ogni istante in cui la macchina ` e libera sequenzia il job disponibile (i.e., tale che tutti i suoi predecessori nel grafo delle precedenze siano gi` a stati sequenziati) con il minimo tempo di processamento. Si chiede di dimostrare o confutare la seguente affermazione: PrecSPT ` e ottima per 1/chain/

C

.

Esercizio 2 Calcolare una soluzione ottima della seguente istanza del problema 1/r

/

C

:

job 1 2 3 4 5

r

0 3 10 12 11

p

15 7 12 3 4

Descrivere in modo dettagliato i vari passi dell’algoritmo utilizzato. Suggeri-

mento: la versione preemptiva della regola WSPT ` e ottima per il problema 1/r

, prmp/

C

.

Esercizio 3 Si consideri la seguente istanza del problema di Job Shop (l’obiettivo considerato ` e il Makespan). L’insieme J = {1, 2, 3, 4} ` e l’insieme dei job. M = {A, B, C} ` e l’insieme delle macchine. Ciascun job consiste di tre task, da eseguirsi su una certa macchina, secondo la seguente tabella:

job M

M

M

1 A (2) B (3) C (4) 2 C (1) B (8) A (2) 3 A (3) C (1) B (5) 4 B (7) C (10) A (2)

in cui il numero fra parentesi rappresenta la durata delle operazioni. Si con- sideri la soluzione rappresentata nella seguente tabella, in cui per ogni macchina, ` e riportata la sequenza delle operazioni da effettuare :

Si chiede di verificare l’ottimalit` a di tale soluzione giustificando la risposta.

1

Macchina J

J

J

J

A 2 1 3 4

B 2 1 3 4

C 1 2 3 4

Domanda 1 Descrivere un algoritmo approssimato per il problema P

//C

dimostrandone il rapporto di approssimazione.

Domanda 2 Descrivere un rilassamento per il problema 1//

w

T

.

2