M W IS s u g ra fo in te rv a ll o

DipartimentodiInformatica UniversitàdegliStudi–L’Aquila –Italy salvatore.nocella@di.univaq.it http://www.oil.di.univaq.it

R il a ss a m e n to la g ra n g ia n o p e r u n p ro b le m a d i sc h e d u li n g ( II p a rt e )

Salvatore Nocella SistemiOrganizzativi(A.A. 2005-2006)

In te rm e z z o : u n p o ’ d i te o ri a d e i g ra fi

»Un grafoG=(V,E) sidiceintervallose: ›I verticicorrispondonoad intervallichiusi sull’assereale ›Ognicoppiadiverticiadiacenticorrispondead unacoppiadiintervallicon intersezionenon vuota »Il problemadiMaximum Weighted Independent Set, suun grafointervalloIIII, puòessererisoltoin tempo polinomiale O(|V|log|V|)

M W IS s u g ra fo in te rv a ll o

»SiaIun grafointervallo. Alloraèsemprepossibile definireun ordinamentodeiverticiV={v 1, …,v n} tale chevale la seguente: »Proprietà. Sia1 <q < r < s <|V|. Se (v q,v s)∈E, allora (v r,v s)∈E. »Definiamoinoltre: ›c(i) ilcostodell’i-esimoverticedel grafo ›δ(i) ilmassimovertice(secondol’ordinamentodefinito) precedentea ie ad essonon adiacente

()Wiα

M W IS s u g ra fo in te rv a ll o

»Datoun ordinamentocheverifichila precedente proprietà, ilseguentealgoritmodiprogrammazione dinamicadeterminal’insiemestabile dipeso massimoper I: »dove: ›èilvaloredel MWIS del sottografoindottodaiprimi iverticidell’ordinamento ›

( ) ( ) ( ) ( ) ( )

1 maxW W W

i i ciiα α αδ−  =  +

 

()00 Wα=

M W IS s u g ra fo in te rv a ll o : u n e se m p io

24 47 36 159 55

11

33

44 44

33

22 11

22

2748 36159

55 11

33

44 44 33

22 11 22

M W IS s u g ra fo in te rv a ll o : u n e se m p io

2748 36159 55 11

33

44 44 33

22 11 22

()() ()()()

1 maxW W W

i i ciiα α αδ− = +

 

4

4

4

7

9

9

9

9= 2 +α w(0)

4 +α w(0) 3 +α w(0)

3 +α w(1) 5 +α w(4)

1 +α w(3) 2 +α w(5)

1 +α w(5) α w(1) = 4 α w(2) =

αw(2) α w(3) =

αw(3) α w(4) =

α w(4) α w(5) =

α w(5) α w(6) =

α w(6) α w(7) =

α w(7) α w(8) =

α w(8) α w(9) =

…max(-, -)α w( -)

1 | r

j

| ΣΣΣΣ w

j

C

j

: d e sc ri z io n e d e l p ro b le m a

»J= {1, 2, …, n} insiemedijob »Preemption non ammessa »Per ciascunjob j ›r j: release date ›w j: indicedipriorità(maggioreèilvalore, superioreèla priorità) »Variabiledecisionale: ›C j: tempo dicompletamentodel job j »1|r j|Σw jC jèNP-hard anchecon w j=1 ∀j »Varianteancorapiùdifficile: 1|r j|Σw jF j: dove F j=C j-r j

1 | r

j

| ΣΣΣΣ w

j

C

j

: u n p o ’ d i le tt e ra tu ra

»Belouadahet al. 1992, hannopropostoun branch-and-bound basatosuun lower bound combinatorico »Van den Akkeret al. 1999, hannopropostoun algoritmodi branch-and-cut che, benchéfornissebuonirisultati, tuttavia era applicabilead istanzecon al più30 job e p max=10 »Van den Akkeret al. 2000, cercanodisuperarela precedente limitazioneproponendoun algoritmodibranch-and-price che permettedirisolvereistanzecon al più30 job e p max=100 »Hall et al. 1997, trovanoun algoritmodiapprossimazioneche costruiscela soluzioneprimalea partiredallasoluzionedel suo rilassamentolineare

1 | r

j

| ΣΣΣΣ w

j

C

j

: fo rm u la z io n e ti m e -i n d e x e d

[] () {}[]

11 1 1,

min 1 11, 0,1,1,

jj jj

nT jtjt jtrp T jt trp nt js jsjt jt

cx xjJ xtT xjJtT

γ

==+− =+− ==

=∈ ≤∈ ∈∈∈

∑ ∑ ∑ ∑ ∑

(1) (2)

»Variabiledidecisione: »Costoin cui siincorre terminandoiljob jall’istante t: » » 1)Ciascunjob deveessere processatoesattamenteuna voltasenzapreeption 2)Macchinaa capacitàunitaria

se il job termina il 1 processamento all'istante 0altrimenti

jt

j xt

  =  

jtjcwt= ()

( )

,max1,1 jjjjtrptpγ=+−−+

max jj jJ jJTpr ∈ ∈=+ ∑

U n e se m p io

323r j 112j 2 311j 3

512j 1

p jw jjob MIN 96 x1_8 + 108 x1_9 + 120 x1_10 + 132 x1_11 + 36 x2_3 + 48 x2_4 + 60 x2_5 + 72 x2_6 + 84 x2_7 + 96 x2_8 + 108 x2_9 + 120 x2_10 + 132 x2_11 + 66 x3_6 + 77 x3_7 + 88 x3_8 + 99 x3_9 + 110 x3_10 + 121 x3_11 x1_8 + x2_4 + x3_6 <1 x1_8 + x1_9 + x2_5 + x3_6 + x3_7 <1 x1_8 + x1_9 + x1_10 + x2_6 + x3_6 + x3_7 + x3_8 <1 x1_8 + x1_9 + x1_10 + x1_11 + x2_7 + x3_7 + x3_8 + x3_9 <1 x1_8 + x1_9 + x1_10 + x1_11 + x2_8 + x3_8 + x3_9 + x3_10 <1 x1_9 + x1_10 + x1_11 + x2_9 + x3_9 + x3_10 + x3_11 <1 x1_10 + x1_11 + x2_10 + x3_10 + x3_11 <1 x1_11 + x2_11 + x3_11 <1

(2)

x1_8 + x1_9 + x1_10 + x1_11 = 1 x2_3 + x2_4 + x2_5 + x2_6 + x2_7 + x2_8 + x2_9 + x2_10 + x2_11 =1 x3_6 + x3_7 + x3_8 + x3_9 + x3_10 + x3_11 = 1(1)

0 1 2 3 4 5 6 7 8 9 10 11

j 1 j 2 j 3

T

1 | r

j

| ΣΣΣΣ w

j

C

j

: ri la ss a m e n to la g ra n g ia n o [ ]

() {}

[ ]

11 1 1,

min 1 11, 0,1,1,

jj jj

nT jtjt jtrp T jt trp nt js jsjt jt

cx xjJ xtT xjJtT

γ

==+− =+− ==

=∈ ≤∈ ∈∈∈

∑ ∑ ∑ ∑ ∑

[ ]

()

{ } [ ]

11 1,

min 11, 0,1,1,

jj

nT jtjt jtrp nt js jsjt jt

cx xtT xjJtT

γ

==+− ==

    ≤∈ ∈∈∈



∑ ∑ ∑ ∑ ∑ ∑

1-1+1- jj

nT jjt j=t=r+pλx

λλλλ λλλλ ( ) [ ]

()

{ } [ ]

11 1,

min 11, 0,1,1,

jj

nT jtjt jtrp nt js jsjt jt

cx xtT xjJtT

γ

==+− ==

− ≤∈ ∈∈∈

∑ ∑ ∑ ∑

∑

1+

n jj j=λλ Attenzione! λλλλnon èvincolatoin segnoin quantosistanno rilassandovincolidiuguaglianza

R is o lu z io n e d e l ri la ss a m e n to

»Il modellomatematicodel precedente rilassamentocorrispondead un problemadi MWIS. »Cichiediamo: «Su qualegrafo?» ›Associamoad ognivariabileun vertice ›Il verticeassociatoallavariabilex jtavràpeso (c jt-λ j) ›Due variabili(vertici) x is, x ktsonoadiacentise compaionoentrambenellostessovincolo, ovverose (supponendos<t): t -p k< s

U n e se m p io : il g ra fo

3 4 5 6 7 8 9 10 11

C a ra tt e ri st ic h e d e l ri la ss a m e n to

»MWIS sugrafogenericoèNP-hard »Il nostrografoperòèintervallo »Il rilassamentopuòesserepertantorisolto con l’algoritmodiPD vistoin precedenza ›Per applicarel’algoritmoènecessariodefinireun ordinamentosui verticicheverifichila proprietà enunciataprecedentemente V = { j 1_1, j 2_1, …, j n_1, j 1_2, j 2_2, …, j n_2, … j 1_t, j 2_t, …, j n_t, … j 1_T, j 2_T, …, j n_T}

C a ra tt e ri st ic h e d e ll a so lu z io n e

»Valel’integralityproperty »Data unasoluzionedel rilassamentoX(

λ

) si possonoindividuaredue tipologiedijob: ›Missing-job ›Repeated-job »Se X(

λ

) non contienetalijob allorala soluzioneèammissibileper ilproblema originario

R is u lt a ti o ss e rv a ti

»L’esperienzacomputazionaleha mostrato che: ›I job-repeated occorronoraramente ›I job-missing sonocirca il10-15% del totale ›I job in J(λ) sononellastessoordineanchenella soluzioneottima

E sp e ri e n z a c o m p u ta z io n a le

»Classificazionedelleistanzein ›Optimal instances ›Hard instances »Optimal instances: ›w j= U[1,20] ›r j= U[0, 0.5Σp j] ›p j= U[1,p max] »Hard instances: ›p j∈{1,50}; ilvalore1 ègenerato, in media, 9 voltepiùfrequentementedel valore50.

A lc u n i ri su lt a ti

A lc u n i ri su lt a ti

A lc u n i ri su lt a ti

A lc u n i ri su lt a ti

R if e ri m e n ti b ib li o g ra fi c i

»H. Belouadah, M.E. Posner and C.N. Potts, “Scheduling with release dates on a single machinetominimize total weighted completion time”, Discrete Applied Mathematics 36, 1992, 213- 231. »J.M. van den Akker, C.P.M. van Hoeseland M.W.P. Savelsbergh, “A polyhedral approach to single-machine scheduling problems”, Mathematical Programming 85, 1999, 541-572. »L.A. Hall, A.S. Schulz, D.B. Shmoysand J. Wein, “Scheduling to minimize average completion time: off-line and on-line algorithms”, Mathematics of Operations Research 22, 1997, 513-544. »J.M. Venden Akker, C.Q.J. Hurkensand M.W.P. Savelsbergh,”A time-indexed formulation for single-machine scheduling problems: column generation”, INFORMS Journal on Computing 12/2, 2000, 111-124.