1. Introduzione: esempi, elementi di un problema di scheduling, notazione. Formulazioni PLM, PLB 2. Problemi a macchina singola

Pre-requisiti:

Classi di complessità

Programmazione Lineare (Intera)

Sistemi Organizzativi

docente: Stefano Smriglio stefano.smriglio@univaq.it

Programmazione Lineare (Intera) Metodo branch-and-bound

Cammini minimi su grafi Materiale didattico:

• M. Pinedo, Scheduling (Systems, Models and Algorithms) – Prentice Hall

• A. Agnetis, dispense http://www.dii.unisi.it/~agnetis/didattica

• Trasparenti dalle lezioni http://www.di.univaq.it/~oil

Parte I:

Scheduling a macchina singola

1. Introduzione: esempi, elementi di un problema di scheduling, notazione. Formulazioni PLM, PLB 2. Problemi a macchina singola

• 1// Σ Σ Σ Σ ^w

_j

^C

_j algoritmo WSPT

• 1/chain/ Σ Σ Σ Σ ^{w C}

algoritmo polinomiale

Indice

• 1/chain/ Σ Σ Σ Σ ^w

_j

^C

_j algoritmo polinomiale

• 1/prec/h

_max algoritmo di Lawler

• 1/r

_j

,prmp/L

_max regola preemptive EDD

• 1/r

_j

/L

_max complessità, branch-and-bound

• 1// Σ Σ Σ Σ ^U

_j algoritmo di Moore

• 1// Σ Σ Σ Σ ^h

_j Programmazione dinamica

• 1// Σ Σ Σ Σ ^T

_j algoritmo pseudo-polinomiale

• 1// Σ Σ Σ Σ ^w

_j

^T

_j branch-and-bound

Introduzione

problemi di scheduling esempi

classificazione

formulazioni PLM

Esempio

Silvia (S) e Francesca (F) giungono nello stesso momento ad una macchina fotocopiatrice. F deve fare 1 fotocopia, S ne deve fare 100.

Il galateo imporrebbe a S di lasciar passare per prima F, che ha un compito molto più breve.

È una buona idea?

Analisi. Supponiamo che l’esecuzione di una fotocopia richieda 3 secondi. Due casi:

S

Attesa totale = 300 + 303 = 603 F

precede

0 300

303 S

Attesa totale = 3 + 303 = 306 F precede

0 3

303

Esempio

E se Francesca F arrivasse all’istante r_f?

Attesa totale = 300 + 303 – r_f =

= 603 – r

0 300

S F 303

r = 603 – r_f

0 300

0 303

r_f

Di nuovo, il galateo imporrebbe a Silvia di interrompere le proprie copie in favore di Francesca:

r_f

Attesa totale = 3 + 303 = 306 r_f + 3

Ricapitolando

• Attività: 2 blocchi di fotocopie (di durata nota)

• Risorse: una macchina fotocopiatrice

• Vincoli:

Capacità: al più una fotocopia alla volta

(caso 2) F non può iniziare prima dell’istante rf

(caso 2) F non può iniziare prima dell’istante rf

• Misura: attesa complessiva presso la macchina fotocopiatrice

• Rappresentazione di una soluzione: diagramma di Gantt

S

0 300

303F

CPU scheduling

• Il sistema operativo disciplina l’accesso alla CPU dei diversi programmi di calcolo.

• tecnica time-sharing (Linux): il tempo di CPU è suddiviso in intervalli (definiti dal timer interrupt) e, in ogni intervallo, è possibile eseguire al più un processo.

possibile eseguire al più un processo.

• diversi obiettivi: rispondere prontamente a ciascun processo, evitare interruzioni prolungate, evitare ritardi nei processi più urgenti.

• Linux attribuisce dinamicamente una priorità ai processi.

Ad es., la priorità è proporzionale all’attesa del processo

CPU scheduling

• Attività: programmi

• Risorse: CPU

• Vincoli: Capacità: al più un programma in ciascun intervallo per ciascuna CPU

• Misure:

• tempo massimo di attesa di un programma

• tempo massimo di attesa di un programma

• tempo di completamento di tutti i programmi

• ritardi nei processi “urgenti”

Scheduling dei velivoli in atterraggio

• La torre di controllo (ATC) ha il compito di assegnare una pista ed un istante di atterraggio a ciascun velivolo nel proprio campo radar (area terminale)

• Ogni velivolo ha una finestra temporale [r,s] definita da due istanti di atterraggio estremi, a seconda che il due istanti di atterraggio estremi, a seconda che il velivolo viaggi:

- alla sua massima velocità (istante r)

- in modalità di minimo consumo (istante s)

• Un velivolo in atterraggio impegna la pista per un tempo noto ma genera turbolenza: quello successivo deve attendere un tempo di “separazione” (funzione delle dimensioni dei velivoli)

Scheduling dei velivoli in atterraggio

• Ad ogni velivolo è associato un orario di atterraggio predeterminato (e pubblicato nelle tabelle)

• “L’importanza” di un velivolo dipende da fattori quali la dimensione, la compagnia, la distanza percorsa…

• Attività: atterraggi

• Risorse: k piste

• Risorse: k piste

• Vincoli:

•Capacità: su ogni pista, al più un atterraggio in un certo istante

• finestre temporali di atterraggio

• separazione fra atterraggi consecutivi

• Misura:

• somma (pesata in base all’importanza) dei ritardi rispetto all’orario pubblicato

Ancora nella vita quotidiana…

Aldo (A), Bruno (B), Carlo (C), Duilio (D) condividono un appartamento e, ogni mattino, ricevono 4 giornali:

Financial Times (FT), Guardian (G), Daily Express (DE), Sun (S).

Ognuno ha i propri gusti…inizia la lettura ad una certa ora, legge i giornali nella sua sequenza preferita e ora, legge i giornali nella sua sequenza preferita e (ciascuno) per un tempo prefissato:

Aldo 8.30 FT(60) G (30) DE (2) S(5) Bruno 8.45 G(75) DE(3) FT(25) S(10)

Carlo 8.45 DE(5) G(15) FT(10) S(30) Duilio 9.30 S(90) FT(1) G(1) DE(1) lettore inizio Sequenza giornali (min.)

inoltre, ciascun lettore:

rilascia un giornale solo dopo averlo letto completamente.

termina la lettura di tutti i giornali prima di uscire.

Ancora nella vita quotidiana…

infine, i quattro lettori attendono che tutti abbiano terminato di leggere prima di uscire di casa

Problema:

A che ora A, B, C, D riescono (finalmente!) ad uscire?

Interpretazione

Aldo 8.30 FT(60) G (30) DE (2) S(5) Bruno 8.45 G(75) DE(3) FT(25) S(10)

Carlo 8.45 DE(5) G(15) FT(10) S(30) Duilio 9.30 S(90) FT(1) G(1) DE(1) lettore inizio Sequenza giornali (min.)

A G B

S

Duilio 9.30 S(90) FT(1) G(1) DE(1)

DE FT

D C

determinare in quale sequenza ciascun giornale “accetta” i lettori in modo da minimizzare il tempo di lettura totale.

Soluzioni

Aldo 8.30 FT(60) G (30) DE (2) S(5) Bruno 8.45 G(75) DE(3) FT(25) S(10)

Carlo 8.45 DE(5) G(15) FT(10) S(30) Duilio 9.30 S(90) FT(1) G(1) DE(1) lettore inizio Sequenza giornali (min.)

una possibile soluzione:

FT A D C B

G B C A D

DE C B A D

S D A C B

giornale Sequenza lettori

Duilio 9.30 S(90) FT(1) G(1) DE(1)

E^SERCIZIO:

valutare l’ora in cui A,B,C e D escono di casa

C

FT

A _B

ESERCIZIO:

data la soluzione in tabella valutare l’ora in cui A,B,C e D escono di casa

FT A D C B

G B C A D

DE C B A D

S D A C B

giornale Sequenza lettori

D C

FT

A

G

DE

S

8.30 9.09.00 10.00 11.00

11.51

B

B C A

D D C

B A

A

C B D

Enumerazione totale

• Il numero di soluzioni è (4!)⁴ = 331.776

• per un problema con n lettori e m giornali diventa (n!)^m.

• esaminando 10.000 soluzioni al secondo (4 giornali e n

• esaminando 10.000 soluzioni al secondo (4 giornali e n lettori):

5 354 min

10 2 · 10¹⁷ giorni

n tempo

Elementi di un problema di scheduling:

job: attività da svolgere – insieme J = {1,…,n}

In generale

Con il termine scheduling si indica l’allocazione temporale di risorse scarse ad attività

job: attività da svolgere – insieme J = {1,…,n}

Fotocopia, esecuzione di un programma di calcolo Un job può rappresentare una singola attività o un insieme di attività (task) tecnologicamente legate

macchine: risorse che eseguono le attività – insieme M={1,…,m}

Fotocopiatrice, CPU, giornali

• tempo di processamento p

_ij

durata del processamento del job j sulla macchina i

• release date r

_j

tempo in cui j arriva nel sistema, rendendosi disponibile al processamento

Attributi dei job

rendendosi disponibile al processamento

• due date d

_j

tempo entro il quale si desidera che il job j sia completato (data di consegna)

• peso w

_j

indica l’importanza del job j

Classificazione

Il processamento di un job su una macchina è detto operazione.

I problemi di scheduling si classificano in base alle caratteristiche dei task e all’architettura delle macchine

Notazione a tre campi: α α α α/β β β/γγγγ: β α

α α

α descrive il sistema di macchine

β β β

β rappresenta vincoli e modalità di processamento (0, 1 o più componenti)

γγγγ indica l’obiettivo

macchine

Campo α

Macchina singola (1) : ciascun job richiede una singola operazione da eseguirsi sull’unica macchina disponibile

Macchine identiche parallele (P_m) : ciascun job richiede una singola operazione da eseguirsi su una qualunque delle m macchine identiche.

1 2

m

Campo α

Flow shop (F

_m

) : Ciascun job è composto di m task, ciscuno da eseguirsi su una macchina secondo una sequenza fissata, uguale per tutti i job.

1 2 m

Job shop (J

_m

) : Ciascun job j è composto di m(j) task,

ciscuno da eseguirsi su una macchina secondo una

sequenza fissata, dipendente da j

Campo β

• Release dates (r

_j

): il job j non può iniziare il processamento prima dell’istante r

_j

• Preemption (prmp): è ammesso interrompere un’operazione per iniziarne una nuova. Il processamento eseguito prima dell’interruzione non va perso: quando eseguito prima dell’interruzione non va perso: quando l’operazione viene ripresa, essa richiede solo il tempo rimanente di processamento

1 2 1

schedule ammissibile

job 1 2

p_j 3 4

1 5 7

Campo β

prec: è dato un grafo G = (N, A) diretto e aciclico che rappresenta una relazione di precedenza fra job. Un job j può iniziare solo se tutti i suoi predecessori sono stati completati

3 1

2 4

5

2

1 4 3 5

schedule non ammissibile

chain: caso speciale in cui ogni componente connessa

del grafo è un cammino orientato (catena)

Campo β

•Tempi di set-up (s

_jk

): tempo richiesto per il riattrezzaggio delle macchine fra i job j e k. Se dipende dalla macchina i, si esprime con s

ⁱ_jk

• breakdown (brkdwn): le macchine non sono sempre

• breakdown (brkdwn): le macchine non sono sempre

disponibili, ma hanno periodi fissati di interruzione del

servizio

Definizioni

C

_j

tempo di completamento del job j L

_j

= C

_j

–d

_j

lateness del job j

T

_j

= max(L

_j

,0) tardiness del job j U

_j

= 1 se C

_j

>d

_j

e 0 altrimenti

job 1 2

p_j 7 8 d_j 9 11

2 1

0 7 15

C

₁

= 7 L

₁

= −2

T

₁

= 0 U

₁

= 0

C

₂

= 15 L

₂

= 4 T

₂

= 4

U

₂

= 1

Campo γ: funzioni obiettivo

• Makespan (C

_max

) : max (C

₁

, …, C

_n

) tempo di completamento dell’ultimo job

• Massima Lateness (L

_max

) : L

_max

=max (L

₁

, …, L

_n

)

• Tempo totale pesato di completamento ( Σ Σ Σ Σ w

_j

C

_j

)

• Tempo totale pesato di completamento ( Σ Σ Σ Σ w

_j

C

_j

) o (weighted flow-time)

• Tardiness totale pesata ( Σ Σ Σ Σ w

_j

T

_j

)

• Numero di tardy job ( Σ Σ Σ Σ U

_j

)

tutte funzioni obiettivo regolari cioè non-decrescenti in C₁, …, C_n

Esempio

job 1 2

w_j 2 3 p_j 7 8 d_j 9 11

2 1

0 7 15

L

_max

= 4

Σ w

_j

C

_j

= 59

Σ w

_j

T

_j

= 12

Σ U

_j

= 1

d_j 9 11

Sequenze e schedule

• Si definisce sequenza una permutazione dei job che definisce l’ordine con cui i job sono processati su una certa macchina

• Si definisce schedule un assegnamento di un

istante di inizio a ciascuno dei task di ogni job (se

prmp, istanti di inizio di ciascuna delle parti in cui

viene suddiviso un task)

Schedule nondelay

uno schedule ammissibile è detto nondelay se nessuna macchina è ferma quando esiste un’operazione disponibile al processamento

In molti casi (sempre se prmp) le soluzioni ottime

sono nondelay. Ciò non è vero in generale

E ^SERCIZIO : schedule nondelay

dato il seguente problema P

₂

/prec/C

_max

1

2

10

job 1 2 3 4 5 6 7 8 9 10

3

4

5 8

6 7 9

job 1 2 3 4 5 6 7 8 9 10

p_j 7 6 6 1 2 1 1 7 7 14

costruire uno schedule nondelay

e verificarne l’ottimalità

1 2 9 5

46 7 8 3 10

32 M1

M2

Soluzione nondelay:

E ^SERCIZIO : schedule nondelay

0 10 20 30

0 10 20 30

1 2 9

5 4 6 7

8

3 10

27

M1 M2

fermo macchina “forzato”

Soluzione ottima:

Scheduling a macchina singola

Formulazioni di Programmazione

Lineare Intera e Mista (PLI-PLM)

Lineare Intera e Mista (PLI-PLM)

Formulazione disgiuntiva

Variabili decisionali “naturali”:

t _j ∈Rⁿ istante di inizio del job j, j = 1, …, n

i precede j ⇒ t ≥ t + p Macchina a capacità unitaria:







= 0 1 yij

se i precede j se j precede i i precede j ⇒

j precede i ⇒ t_i ≥ t _j + p_j t _j ≥ t_i + p_i

Variabili aggiuntive (binarie):

valgono in alternativa !!

Formulazione disgiuntiva (PLM)

i precede j ⇒ y_ij = 1 ⇒

j precede i ⇒ y_ij = 0 ⇒ t_i ≥ t _j + p_j t _j ≥ t_i + p_i

Formulazione disgiuntiva

J j

i p

t t

M

y_ij + _j − _i ≥ _i ∀ ∈

− ) ,

1 (

J j

i p

t t

M

y

_ij

+

_i

−

_j

≥

_j

∀ , ∈

t _j ≥ 0 ∀ ∈j J

J j

i

y

_ij

∈ { 0 , 1 } ∀ , ∈

M costante grande (quanto?)

Problemi minsum: 1// ∑ ∑ ∑ ∑

_j

_w

_j

_C

_j

min ∑ ∑ ∑

∈

∈

∈

+

= +

J j

j j J

j

j j J

j

i i

j

t p w t w p

w ( )

J j

i p

t t

M

y_ij + _j − _i ≥ _i ∀ ∈

− ) ,

1 (

J j

i p

t t

M

y

_ij

+

_i

−

_j

≥

_j

∀ , ∈

t _j ≥ 0 ∀ ∈j J

J j

i

y

_ij

∈ { 0 , 1 } ∀ , ∈

n²+n variabili 2n² vincoli

Esercizio

Formulare come problema di PLM la seguente istanza del problema

1/r

_j

/ ∑

_j

_w

_j

_C

_j

job 1 2 3

p_j 3 1 2

r_j 0 2 0

w_j 3 2 4

Problemi minsum: 1// ∑

_j

_w

_j

_T

_j

} 0 , max{

min

_j

J j

j j

j

t p d

w + −

∑

∈

J j

i p

t t

M

y_ij + _j − _i ≥ _i ∀ ∈

− ) ,

1

(1− y_ij)M + t_j − t_i ≥ p_i ∀i, j ∈ J (

J j

i p

t t

M

y

_ij

+

_i

−

_j

≥

_j

∀ , ∈

t _j ≥ 0 ∀ ∈j J

J j

i

y

_ij

∈ { 0 , 1 } ∀ , ∈

R

^ICHIAMO

: Funzioni convesse lineari a tratti

è il più piccolo valore z per cui

1 1x d c +

T

x d

c

z ≥ + i = 1 ,..., m

2 2x d c +

3

3x d

c +

) (

max

1,..., i

T m i

i

c x + d

=

x

b Ax ≥

) (

max

min

1,..., i

T m i

i

c x + d

=

b Ax ≥

z min

m i = 1 ,..., z

d x

c

_i^T

+

_i

≤

i T

i

x d

c

z ≥ + i = 1 ,..., m

Formulazione PLM

} 0 , max{ t

_j

+ p

_j

− d

_j

j

j

p

0 d −

t

j

j j

f

∑ w min

j

j

p

0 d −

} 0 , max{

min

_j

J j

j j

j

t p d

w + −

∑

∈

f

_j

≥ t

_j

+ p

_j

− d

_j

, j ∈ J

≥ 0

f

j

Formulazione PLM

j j

f

∑ w min

J j

d p

f

t

_j

−

_j

≤ −

_j

+

_j

, ∈

≥ 0 f

j

J j

i p

t t

M

y_ij + _j − _i ≥ _i ∀ ∈

− ) ,

1 (

J j

i p

t t

M

y

_ij

+

_i

−

_j

≥

_j

∀ , ∈

t _j ≥ 0 ∀ ∈j J

J j

i

y

_ij

∈ { 0 , 1 } ∀ , ∈

Problemi min-max: L

_max

f min

J j

d p

t

f −

_j

≤

_j

−

_j

, ∈

≥ 0 f

J j

i p

t t

M

y_ij + _j − _i ≥ _i ∀ ∈

− ) ,

1 (

J j

i p

t t

M

y

_ij

+

_i

−

_j

≥

_j

∀ , ∈

t _j ≥ 0 ∀ ∈j J

J j

i

y

_ij

∈ { 0 , 1 } ∀ , ∈

Formulazioni Time-indexed

Variabili binarie: x_jt = 1se j inizia nel periodo t; 0 altrimenti

L’orizzonte temporale T ( ) è discretizzato in periodi di durata unitaria. Il periodo t concide con l’intervallo di [t –1 , t]

∑

=

≥

n

j

pj

T

1

n j

x

pj

T

,..., 1

, 1

1

=

∑

⁺

=

−

Completezza

x j n

t jt

1 , 1 ,...,

1

=

∑ =

=

T t

x

t p t

s js

n

j _j

,..., 1

, 1

1 1

=

∑ ≤

∑

+

−

=

=

1 ,...,

1

; ,..., 1

}, 1 , 0

{ = = − +

∈

_j

jt

j n t T p

x

nT variabili; n + T vincoli Completezza

Capacità

Funzioni obiettivo

c costo di assegnazione

j p

T

t

jt

j

tx p

C

j

+

=

⁻

∑

⁺

= 1

1

forma generale:

∑ ∑

^{n T −pj +}

^c

¹

^x

min

∑_{j wjCj} ⇒

∑_j w_jT_j ⇒

c

_jt

= max{ 0 , t + p

_j

− d

_j

}

c_jt costo di assegnazione del job j all’istante t

∑

∑

^{− +}

=

=

+

1

1 1

) (

pj

T

t

jt j

n

j

j

t p x

w

∑ ∑

= =

j t

jt jt

x c

1 1

min

min-sum:

1.1 Tempo totale pesato di completamento Σ Σ

Σ Σ w

_j

C

_j

nondelay schedule

Proprietà 0.1 Dato un problema del tipo 1// γ con γ

funzione obiettivo regolare, esiste uno schedule

ottimo in cui la macchina processa ininterrottamente

dall’istante 0 all’istante C

_max

= Σp

_j

Tempo totale pesato di completamento 1// Σ Σ Σ Σ w

_j

C

_j

Definiamo Weighted Shortest Processing Time (WSPT) una regola che ordina i job per valori non crescenti del rapporto w

_j

/p

_j

Sussiste il seguente

Teorema 1.1 La regola WSPT calcola una soluzione ottima del problema 1// Σ w

_j

C

_j

Sussiste il seguente

Dimostrazione. (Per contraddizione)

Assumiamo che S sia uno schedule ottimo e che non

rispetti WSPT

Dimostrazione

Allora devono esserci in S due job adiacenti, diciamo j seguito da k tali che

w

_j

/p

_j

< w

_k

/p

_k

Assumiamo che il job j inizi all’istante t.

Eseguiamo uno scambio dei job j e k ottenendo un Eseguiamo uno scambio dei job j e k ottenendo un nuovo schedule S'

S

S′

k

j t

k j

t+p

_j

t+p

_k

t+p

_j

+p

_k

Dimostrazione

S

S ′

k j t

k j

t+p

_j

+p

_k

Il tempo totale (pesato) di completamento dei job che precedono e seguono la coppia (j,k) non è modificato dallo scambio. Il contributo dei job j e k in S è:

(t+p

_j

)w

_j

+ (t+p

_j

+p

_k

)w

_k

mentre in S' è:

(t+p

_k

)w

_k

+ (t+p

_k

+p

_j

)w

_j

Dimostrazione

in S] (t+p

_j

)w

_j

+ (t+p

_j

+p

_k

)w

_k

in S'] (t+p

_k

)w

_k

+ (t+p

_k

+p

_j

)w

_j

Eliminando i termini uguali:

in S] p

_j

w

_k

in S'] p

_k

w

_j

Quindi, se w

_j

/p

_j

< w

_k

/p

_k

, risulta p

_k

w

_j

< p

_j

w

_k

, cioè il

tempo totale pesato in S' è strettamente inferiore a quello

in S, contraddizione

Vincoli di precedenza 1/prec/ Σ w

_j

C

_j

Nel caso generale il problema è NP-Hard.

Consideriamo invece il caso in cui le precedenze sono rappresentate da un insieme di catene in parallelo:

1/chain/ Σ Σ Σ Σ w

_j

C

_j

Per questo caso esiste un algoritmo di soluzione polinomiale.

Catene non interrompibili

Date due catene:

1 → 2 → … → k

k+1 → k+2 → … → n

Minimizziamo Σ w

_j

C

_j

con il vincolo che i job di ciascuna catena debbano essere processati consecutivamente.

catena debbano essere processati consecutivamente.

Lemma 1.2 Se

allora la catena 1, …,k precede la catena k+1, …, n

∑

∑

>

∑

∑

+

= +

=

=

=

n k

j j

n k

j j

k

j j

k

j j

p w p

w

1 1

1 1

Dimostrazione

• Per la sequenza 1,2,…,k,k+1,k+2,…,n ( S1 ) il tempo totale di completamento è

∑ + + + ∑

∑ + +

+

= + =

= +

k j

n

j j

n k

j k

j j k

k

p w p p w p

w p

w

1 1 1

1 1

1

1

K ( ) K

• Per la sequenza k+1,k+2,…,n,1,2,…,k ( S2 ) il tempo totale di completamento è

∑ + + + ∑

∑ +

+ +

+

= =

+ + =

+

n k j

n

j j

k j

n k

j j

n k

k

p w p w p p w p

w

1 1 1

1 1

1

1

K ( ) K

Semplificando

• S1

) )(

(

1 1

1 1

1

∑ ∑ ∑ ∑

= +

=

= =

+

+ + =

k j

j n

k j

j k

j

k j

j n

j

k

p w p w p

w K

• S2

∑ = ∑ ∑

∑ + +

+

= = = +

+

=

n k j

n k

j j

k

j j

j n

k

j

p

j

w

k

p w p

w

1 1 1

1 1

K ( )( )

+

= = = +

+

=k j k j j k

j 1 1 1 1

• Quindi, ricordando l’ipotesi:

> ⇒

∑

∑

∑

∑

+

= +

=

=

=

n

k j

j n

k j

j k

j

j k

j

j

p w p

w

1 1

1

1

( )( ) ( )( )

1 1

1 1

∑

∑

∑

∑

+

=

=

= +

=

<

n

k j

j k

j

j k

j

j n

k j

j

p w p

w

cioè, S1migliore di S2

Coefficiente ρ di una catena

L’idea chiave dell’algoritmo è ricondurre 1/chain/ Σ w

_j

C

_j

al problema di sequenziare catene non-interrompibili, in modo da utilizzare il Lemma 1.2.

Definizione 1.3 Data una catena 1 → 2 → … → k Definizione 1.3 Data una catena 1 → 2 → … → k definiamo coefficiente ρ della catena il seguente rapporto:

 

 





 

 





∑

∑

≤

= ≤

∑

∑

= ρ

=

=

=

=

l

j j

l

j j

l

j j

l

j j

p w k

p l w k

1 1

* 1

* 1

1 ) max

, ,

1

( K

Esempio

1 2 3 4

job 1 2 3 4

p_j 3 4 2 6

w_j 10 4 17 8

1 2 3 4

l* = 3

 



 

= 

 

 





 

 





≤

= ≤ ρ

∑

∑

=

=

15 , 39 9

, 31 7

, 14 3

10 4

1 ) max 4

, ,

1 (

1 1 l

j j

l

j j

p w l

K

Proprietà del coefficiente ρ

Proprietà 1.4 Se un job l* determina il coefficiente ρ(1,...,k) allora per qualunque 1<u<l* risulta:

∑

∑

^l*

w

^u

w

∑

∑

>

∑

∑

=

=

+

= +

=

u

j j

j j

l u

j j

u

j j

p w p

w

1 1

* 1 1

Dimostrazione

Per definizione:

∑

∑

∑

∑

=

=

=

=

>

u j

j u

j

j l

j

j l

j

j

p w

p w

1 1

* 1

* 1

∑

∑

∑

∑ + + > + +

u

j l

u

j l

j u

l

j

p w p w p w

w

p

_{1 *}

*

*

1

K K

da cui:

∑

∑

∑

∑

=

=

=

=

+ +

>

+ +

j

j l

j

j j

j u

j

j

p w p w p w

w p

1

* 1

1 1

1

1

K K

∑

∑

∑

∑

=

= +

+

= +

=

+ +

>

+ +

u j

j l

u j

j u

l u j

j u

l u j

j

p w p w p w

w p

1

* 1

1

* 1

* 1

1

K K

) )(

( ) )(

(

1

* 1

* 1 1

∑

∑

∑

∑

= +

= +

=

=

>

^u

j

j l

u j

j l

u j

j u

j

j

w p w

p

Proprietà dello schedule ottimo

Lemma 1.5 Si consideri una generica catena (1, ..., k) e sia l* il job che determina il suo coefficiente ρ(1,...,k).

Allora esiste uno schedule ottimo che processa i job 1, …, l* consecutivamente.

Dimostrazione. (per contraddizione) Assumiamo che in una sequenza ottima la sequenza 1,…,l* sia interrotta da un job v ∉∉∉∉(1,...,k), cioè, contenga la sottosequenza

(S) 1,…,u,v,u+1,…l*

Proprietà dello schedule ottimo

(S) 1,…,u,v,u+1,…l*.

Consideriamo le sottosequenze:

(S') v,1,…,u,u+1,…,l*

(S') v,1,…,u,u+1,…,l*

(S'') 1,…,u,u+1,…l*,v

Mostriamo che per almeno una fra S' e S'' il tempo di completamento è non superiore a quello di S.

Dimostrazione

• Applicando il Lemma 1.2 alle catene (v) e (1,…,u) si ha che se il valore (∑w_jC_j) di S è inferiore a quello di S', allora:

u u v

v

p p

p

w w

w p

w

+ +

+

+ +

< +

K K

2 1

2 1

u

v

p p p

p + + K +

2 1

• Applicando il Lemma 1.2 alle catene (v) e (u+1,…,l*) si ha che se il valore (∑w_jC_j) di S è inferiore a quello di S'', allora:

* 2

1

* 2

1

l u

u

l u

u v

v

p p

p

w w

w p

w

+ +

+

+ +

> +

+ +

+ +

K

K

Dimostrazione

• Per la Proprietà 1.4 risulta inoltre:

u u l

u u

l u

u

p p

p

w w

w p

p p

w w

w

+ +

+

+ +

> + +

+ +

+ +

+

+ +

+ +

K K K

K

2 1

2 1

* 2

1

* 2

1

• Quindi, se S è meglio di S'', allora:

• Quindi, se S è meglio di S'', allora:

u u l

u u

l u

u v

v

p p

p

w w

w p

p p

w w

w p

w

+ +

+

+ +

> + +

+ +

+ +

> +

+ +

+ +

K K K

K

2 1

2 1

* 2

1

* 2

1

Contraddizione (avendo assunto S meglio di S'). Lo stesso argomento si applica quando la catena è interrotta da molteplici job.

Algoritmo

I due lemmi precedenti sono il fondamento di un algoritmo polinomiale:

Algoritmo 1.6

In ogni istante in cui la macchina è libera, seleziona fra le In ogni istante in cui la macchina è libera, seleziona fra le rimanenti catene quella con il massimo coefficiente ρ e la processa senza interruzione fino al job che definisce ρ (incluso)

L’algoritmo ha complessità O(n²)

Esempio

1 2 3 4

job 1 2 3 4 5 6 7

w_j 6 18 12 8 8 17 18

p_j 3 6 6 5 4 8 10

5 6 7

step1.

ρ (1,2,3,4) = (6+18)/(3+6) = 24/9, l

^*

=2

ρ (5,6,7) = (8+17)/(4+8) = 25/12, l

^*

=6 2

1

Esempio

3 4

job 1 2 3 4 5 6 7

w_j 6 18 12 8 8 17 18

p_j 3 6 6 5 4 8 10

5 6 7

step2.

ρ(3,4) = 12/6, l

^*

=3

ρ(5,6,7) = (8+17)/(4+8) = 25/12, l

^*

=6

1 2 5 6

Esempio

3 4

job 1 2 3 4 5 6 7

w_j 6 18 12 8 8 17 18

p_j 3 6 6 5 4 8 10

7

step3.

ρ(3,4) = 12/6, l

^*

=3 ρ(7) = 18/10, l

^*

=7

1 2 5 6 3

Esempio

job 1 2 3 4 5 6 7

4

w_j 6 18 12 8 8 17 18

p_j 3 6 6 5 4 8 10

7

step4.

ρ(4) = 8/5, l

^*

=4

ρ(7) = 18/10, l

^*

=7

2 4

1 5 6 3 7

Release date e preemption

L’introduzione delle release date complica il problema. Nel caso in esame, il problema 1/r_j/Σw_jC_j è NP-hard. [Ex1]

Richiamo. Dato un problema di ottimizzazione P =(z,S) (di Richiamo. Dato un problema di ottimizzazione P =(z,S) (di minimo), si definisce rilassamento di P un nuovo problema RP=(w,Φ) tale che:

(i) S ⊆ Φ

(ii) ∀ x ∈ S risulta w(x) ≤ z(x)

Rilassamento preemptivo

Il problema1/r_j, prmp/Σw_jC_j si dice rilassamento (perché lo è?) preemptivo.

Per esso è interessante valutare il comportamento della naturale estensione della regola WSPT:

Preemptive WSPT: in ogni istante (intero) di tempo, si processa il job disponibile con il massimo rapporto

peso / tempo residuo di processamento

Esempio

job 1 2 3 4 5

w_j 1 4 3 5 3

p_j 2 3 3 2 1

r_j 0 2 3 1 4

8

1 4 4 2 5 2 2 1 3 3 3

15

15

28 33

Z_PWSPT=99

PWSPT non è ottima per 1/r

_j

,prmp / ∑ _w

_j

_C

_j

108

1 2 3

2

1 2 2 2 2 2 2 2 2 2 3

job 1 2 3

w_j 1 9 8

p_j 2 10 2

r_j 0 1 11

1 2 3

112 Z_PWSPT=222

1 2 2 2 2 2 2 2 2 2 3

104 1

2 3

99

14 Z_OPT=217

1 2 2 2 2 2 2 2 2 2 3

Si mantiene la lista ordinata per valori decrescenti del rapporto w_j/p_j(t) e la lista ordinata dei job per release date crescenti.

Complessità

PWSPT si esegue in tempo O(n log n)

crescenti.

Gli eventi significativi sono di due tipi: (i) completamento di un job e (ii) rilascio di un nuovo job. Quindi, ci sono O(n) eventi.

In corrispondenza di ciascun evento si deve:

• aggiornare la lista, richiede tempo O(log n)

• calcolare l’evento successivo, calcolando min(t + p_j(t), r_j1), che richiede tempo costante

Pesi unitari

Si ha il seguente:

Nel caso di pesi tutti unitari PWSPT schedula, in ogni istante (intero) di tempo, il job disponibile con il minimo tempo residuo di processamento (Shortest Remaining Processing Time, SRPT)

Si ha il seguente:

Lemma 1.6

La regola SRPT è ottima per 1/r_j, prmp/ΣC_j

Dimostrazione. Mostriamo che, comunque preso uno schedule S che non rispetta SRPT, ne esiste uno S' che la rispetta con un tempo di completamento non peggiore.

Dimostrazione

Se S non rispetta SRPT, deve esserci un istante t in cui è processata una unità del job j pur esistendo k tale che

p_j(t) > p_k(t)

Costruiamo un nuovo schedule S' in cui le rimanenti p_k(t) unità del job k sono scambiate con le prime p (t) del job j.

del job k sono scambiate con le prime p_k(t) del job j.

S

S ′

t

j k

t'

k

Dimostrazione

S

S ′

j k

k

• i job diversi da j e k non subiscono alcuna variazione;

• primo caso: C_k(S ) > C_j(S )

− Essendo p_j(t) > p_k(t) si ha che C_k(S ′) ≤ C_j(S);

− inoltre, per costruzione, C_j(S ′) = C_k(S );

Quindi: C_k(S ′) + C_j(S ′) ≤ C_k(S ) + C_j(S )

t t'

Dimostrazione

S

S ′

j k

k

• secondo caso: C_k(S) < C_j(S)

− C_k(S ′) ≤ C_k(S);

− C_j(S ′) = C_j(S);

Quindi: C_k(S′) + C_j(S ′) ≤ C_k(S) + C_j(S )

t t'

Esercizi

Esercizio 1

Dimostrare che la regola SPT non è ottima per il problema 1/r

_j

/ ∑ _C

_j

1 2

z(SPT) = 12 1

3 4 8

2

1

1 4 5 5

2 z(OPT) = 9

job 1 2

r

_j

3 0

p

_j

1 4

Esercizio 2

Dimostrare che la regola WSPT non è ottima per il problema 1/brkdwn/∑ _{wj Cj}

1 2

z(WSPT) = 85 1

1 2 3 4 5

2

10 75

1

1 2 3 4 5

2

30 40

z(OPT) = 70

job 1 2

w_j 10 15 p_j 1 2

Esercizio 3

Dimostrare o confutare che la regola SPT è ottima per il problema 1/brkdwn/∑ _Cj

job 1 2 3

p_j 3 2 4

2

2

1

4 5 8 12

z(SPT) = 22

2 1

4 5 7 10

z(OPT) = 21

3

3

1.2 Problemi min-max

(Massima Lateness L

_max

)

(Massima Lateness L

_max

)

1/prec/h

_max

Forma della funzione obiettivo:

h_max = max (h₁(C₁), …, h_n(C_n))

h_j(C_j) è una arbitraria funzione non decrescente di C_j Esempi:

h_j(C_j)= C_j – d_j = L_j ⇒ h_max = L_max

h_j(C_j) = max (0,L_j) = T_j ⇒ h_max = T_max Precedenza: G_P generico grafo aciclico.

• Dato che le soluzioni ottime sono nondelay, l’ultimo job termina all’istante C_max = ∑ⁿ_j=1 p_j

Costruisce lo schedule a partire dal fondo

• J job già schedulati nell’intervallo

• J^c = {1, …, n} \ J

• J′ job schedulabili immediatamente prima di J (= tutti i successori sono in J)

Algoritmo di Lawler

Inizializzazione:

] ,

[ C

_max

− ∑

_j∈J

p

_j

C

_max

Inizializzazione:

J = ∅, J^c = {1, …, n}, J′ insieme dei job privi di successori Loop: while (J^c ≠ ∅ )

Schedula in ultima posizione il job j* tale che

J := J ∪{j*}, J^c := J^c \{j*}, aggiorna J′

Endloop.

)) (

min ( )

*

( ∑ = ∑

′ ∈

∈ ^c ∈ j J^c

j J j

J j j

j

j

p h p

h

Dimostrazione. Ad una generica iterazione è selezionato il job j**∈∈∈J∈ ′ che non induce il minimo costo di completamento.

Cioè, ∃ j* (schedulabile) tale che

Corretezza

Teorema 1.7 L’algoritmo di Lawler restituisce uno schedule ottimo per 1/prec/h_max

Cioè, ∃ j* (schedulabile) tale che

Quindi, j* è schedulato prima di j**

) (

)

(

_**

*

∑ < ∑

∈

∈ ^c j J^c

j j

J j

j

j

p h p

h

j* j**

S

Ipotesi: S è uno schedule ottimo

J