3.2 Algoritmo di Moore per la minimizzazione dei lavori in ritardo

Massimo numero pezzi in tempo

Algoritmo di MooreAlgoritmo di Moore

J1 J2 J3 J4 Jn

d1 d2 d3=d4 dn

1) Si scelgono gli indici in ordine EDD

(non sempre è unico: es. J3 e J4 sopra)

J3JnJ1 J2 J4

d1 d2 d3=d4 dn

1’) La sequenza ottenuta è la sequenza corrente S1 (la prima) ; si pone i=1

2) Si individua il primo lavoro in ritardo Jl(i) nella sequenza corrente, se non esiste: stop

3) Si individua il lavoro più lungo Jr(i) con r l(i), nella sequenza corrente Si

4) Si ottiene una nuova sequenza corrente Si+1 escludendo Jr(i) e si torna al passo 2),

con i:= i+1

J3JnJ1 J2 J4

d1 d2 d3=d4 dn

Traduzione logica dell’intuizione

Moore costruisce una sequenza con il massimo numero di lavori terminati in tempo e con il minimo tempo totale di processamento Sn Moore e’ ottima.

sK : = { i1… ik } indici di una generica sequenza dei primi k lavori

Nk : = massimo numero di lavori in tempo, rispetto a tutte le possibili Sk

IP d1 d2 … dn ( i lavori sono ordinati secondo EDD )

Sk di Moore e’ tale che:

- il numero di lavori processati in tempo e’ pari ad Nk

- il tempo di processamento totale e’ minimo

Praticamente Moore trova l’ottimo per i primi k lavori

Dimostriamo per INDUZIONE che Sn e’ ottima

• S1 e’ banalmente ottima.

• Sk assumiamola ottima.

• Sk+1 e’ ottima?

• Sk+1 e’ ottima?

Costruiamo la sequenza Sk+1 a partire da Sk

- se jk+1 e’ processato in tempo ottengo ancora una sequenza ottima, in cui i lavori che arrivano in tempo sono ( Nk + 1 ).

- se jk+1 non e’ processato in tempo, elimino il lavoro con tempo di processamento più lungo, fra gli ( Nk + 1 ). Ottengo una sequenza di k+1 lavori, di cui Nk+1 = Nk arrivano in tempo, con tempo di processamento totale minimo.

Algoritmo di Moore min nT S

1968

nT numero di pezzi che vanno rifiutati(T: Tardiness)

Ipotesi di lavoro: S0 ottima

Sempre: S0: A0 R0

ammessi o in anticipo

rifiutatio in ritardo

Infatti se

Ja(1) Jr (k)... ... Ja (z)

... Jr ()Jr (1)

Si può posticipare Jr(k) mantenendo l’ottimalità

S0:

Sempre: S0: A0 R0

S0 : A0 R0

scelti gli indici dei lavori secondo una qualsiasi S EDD

i < j di dj

Si può sempre riordinare A0 come la EDD scelta: h<k a(h) < a(k)

Infatti in A0: Lmax 0, inoltre: EDDmin Lmax SIl riordino può essere

necessario solo se di = dj

Algoritmo di Moore min nT S

JJr(1) r(1) : max p: max phh = p = pr(1)r(1)

h=1,l(1)h=1,l(1)

S1:J1 Ja(1) Ja(2) Jr(1) Jl(1) Ja(z) Jl(i) Jn

dl(1)

Definizione di l(1):

Definizione ricorsiva di Jr (k) , da k=2

Ak:Jr(k-1)-1 Jr(k)

Jr(k-1)+1 dl(k)

k i

Jl (k) ultimo lavoro in Ak; unico in ritardo

Jr (k) Ak : max ph = pr (k)

h: Jh Ak

Jl(k)

Jr (h) con h < k non ci sono in Ak

presenti in A0

Ja(1)Ja(2) Jl(1) Ja(z)

1 := numero lavori di { J1 ....Jl(1) } = :A1

assenti in A0

1 > 0 (almeno uno è assente, altrimenti Jl(1) sarebbe presente e in ritardo, cosa impossibile, per definizione di A0)

assente in A0

S1

Algoritmo di Moore min nT S

pq(1) pr(1) Lavoro di peso massimo fra

quelli in J1 ....Jl(1) assenti in

A0

q(1) può coinciderecon r(1)

Jq(1) : max ph = pq (1)

q(1) l(1) h=1,l(1)

h a () l(1)

Sk: J1 Ja(1) Ja(2) Jl(k) Jn

dl(k)

Jr (h) con h < k, rifiutati al passo h, non ci sono in Sk

Definizione ricorsiva di l(k), iniziando da k=2:

Jr(k-1)-1 Jr(k-1)+1

Passo i-esimo: 1 < k i

Sk : sequenza corrente al passo k

S (sequenza corrente) :J1 Ja(1) Jl() Jn

dn

Jr()-1 Jr()+1

Ultimo passo: i = S:

J1 Ja(1) Jl() Jn

dl()

Jr() Jr()+1

dnpr()

pr()pr()

Jr()-1

dl()

Se l() non esiste

Jq(k) è un lavoro di peso massimo tra i k in J1 … Jl(k) fuori da A0 , non già abbinati

J1 ....Jl(k)

A0

k : numero lavori in J1 ....Jl(k) assenti in A0

Jq(k)

Jq(k) : pq(k) = ph

q(k) l(k)

max h l(k)Jh

Definizione ricorsiva di Definizione ricorsiva di JJq(k)q(k) ::

abbinato a Jr(k)

J1 ....Jl(k)

A0

{Jq(1) ... Jq(k-1) }Jq(k) => A0 {Jq(1) ... Jq(k-1)}

Jq(k) => h l(k) Bk

Bk

Algoritmo di MooreAlgoritmo di Moore min nmin nTT

SS

Tesi: A) A) i+1 i+1 ii1 1

B) B) JJq(i+1)q(i+1) : p : pq (i+1) q (i+1) ppr r

(i+1)(i+1)

Ipotesi: i i iiJJq(1)q(1) ... J ... Jq(i)q(i) : p : pq(k)q(k)

ppr(k)r(k)

Passo i-esimo:

Tesi:A) A) i+1 i+1 ii1 1

B) B) JJq(i+1)q(i+1) : p : pq (i+1) q (i+1) ppr (i+1)r (i+1)

Se la tesi è dimostrata, 1 1 dimostra che l’algoritmo dà un ottimo

Se i >i i+1 ii1

Se i = i

iJq(1) ... Jq(i), abbinati a Jr (1) ... Jr(i)

q (k) l (k) pq(k) pr(k) k = 1,…,i

sono esattamente tutti i lavori

assenti in A0 tra J1 ... Jl(i)

Jl(i)

i = i

ritardati di ( ritardati di ( h h ppr (h)r (h) - - h h ppq (h)q (h)))

rispetto a Srispetto a Si+1i+1

A0

Ja(1) Ja(2) Jl(i) Ja(z)Jl(i+1)

1

i

1

i

Si

J1Ja(1) Ja(2) Jr(i) Jl(i) Ja(z)

dl(i) dl(i+1)

Jl(i+1)

J1Ja(1) Ja(2) Ja(z)

dl(i)

Jl(i+1)

Si+1

dl(i+1)

Tesi B) Jq(i+1) : pq (i+1) pr (i+1)

Ak:Jr (k-1)-1 Jr (k)

Jr (k-1)+1 dl(k)

Jl(k)

Jr (h) con h < k non ci sono in Ak

con l (i) < q(i+1) l (i+1)perché i = i

Jr (h’) “nasconde” Jq(i+1) = Jr (h’)

A i+1 Jq (i+1)

Jq(i+1)A i+1 pq(i+1) pr(i+1)

tempo di processo massimo dei lavori in A i+1

Jq(k) è un lavoro di peso massimo tra i k

in J1 ....Jl(k) fuori da A0 ,non già abbinati

A i+1

Jr (i+1)

Jq (h)

pq (h) =

Jq (h’’)

pq (h’’) =

sono indicati solo i lavori rifiutati in Ak o assenti in A0

A h”

Jr (h’’)

A h’’’

Jr (h’’’)

Jq(h’) A i+1

h’’’ < h’’ < h’ i

Jq(h”) A i+1

allora Jq(h) A i+1

pq(i+1) = pq(h) pr(i+1)

Jq (h’)

pq (h’) =

A h’

pq(i+1) pq(h’) pr(h’) =

pq(i+1)

q(i+1) l(h’)

Sia h il valore per cui Jr =Jq(h)

( h sempre,perché i Jq sono più dei Jr):

pq (i+1)

Jq (i+1)

Jr (h’)