3.2 Algoritmo di Moore per la minimizzazione dei lavori in ritardo.
-
Upload
teodoro-carlucci -
Category
Documents
-
view
221 -
download
1
Transcript of 3.2 Algoritmo di Moore per la minimizzazione dei lavori in ritardo.
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’)