Programmation linéaire en nombres entiers pour l’ordonnancement modulo sous contraintes de ressources

7/26/2019 Programmation linaire en nombres entiers pour lordonnancement modulo sous contraintes de ressources.

1/75

Def. Problme Approche PLNE Dantzig-Wolfe Lagrange Hybride Conclusion

Programmation linaire en nombres entiers pourlordonnancement modulo sous contraintes de

ressources.

Maria Alejandra Ayala P.

Universit de Toulouse III, FranceLAAS - CNRS

15 Juin 2011

1/75


2/75


Contexte et motivation

Contexte industriel : problme dordonnancement cyclique

dinstructionsParalllisme dinstructions

Architectures VLIW : ST200 de STMicroelectronics

Proposer un ordonnancement des instructions pour terminer leprogramme en un temps minimal.

Optimiser lexcution des boucles : pipeline logiciel.

problme dordonnancement cyclique : ordonnancement modulo.2/75


3/75


Plan

1 Dfinition du problme RCMSP

2 Programmation linaire en nombres entiers

3 Dcomposition de Dantzig-Wolfe

4 Relaxation Lagrangienne

5 Mthode hybride

6 Conclusion et perspectives

3/75

D f P bl A h PLNE D W lf L H b d C l


4/75


Plan



3 Dcomposition de Dantzig-WolfeNouvelles formulationsGnration de colonnesSous-problmeRsultats exprimentaux

4 Relaxation LagrangienneDfinition et rsolution du sous-problme LagrangienHeuristique

Rsultats exprimentaux5 Mthode hybride

Mthode hybrideRsultats exprimentaux


4/75

D f P bl A h PLNE D t i W lf L H b id C l i


5/75


Ordonnancement cyclique

Un ensemble doprations gnriques : {Oi}1in rptes uneinfinit de fois (diffrentes occurrences ou instances).

Dure{pi}1in

la qime ocurrence de la tche gnrique i.

Ordonnancement : date de dbut qide chaque occurrence.

5/75

Def Problme Approche PLNE Dantzig Wolfe Lagrange Hybride Conclusion


6/75


Ordonnancement priodique

DfinitionLe temps de cycle moyen :

z() = limq

maxiO(qi +pi)

q

Problme : trouver un ordonnancement ralisable minimisant le tempsde cycle moyen z() tout en respectant des contraintes de prcdenceentre les tches.

Dfinition

Ordonnancement priodique avec une priode

iO, q1, qi =0i + q

La priode est gale au temps de cycle moyen z().

6/75

Def Problme Approche PLNE Dantzig Wolfe Lagrange Hybride Conclusion


7/75


Ordonnancement modulo sous contraintes de ressources(RCMSP)

Ordonnancement modulo : structure dordonnancement cyclique(1)-priodique avec priode entire.

Dures unitaires.Ensemble de mressources.

Chaque ressource a une disponibilit limite Bs.

Chaque tche demande bsiunits de chaque ressource s.

Ensemble Ede contraintes de prcdence (latence

j

i, distanceji) pour (i,j) E.

7/75

Def Problme Approche PLNE Dantzig-Wolfe Lagrange Hybride Conclusion


8/75

Def. Problme Approche PLNE Dantzig Wolfe Lagrange Hybride Conclusion


Variables de dcision : i {0...T}, o Test lhorizon de temps.Formulation du RCMSP :

min Lex(,n

i=1wii)

s.cji+

ji

ji, (i,j) E

iA(t) bsi Bs, s {1, . . . , m}, t N

i0, i=1, 2, ..., n

o A(t) ={i {1, . . . , n}|q N, qi =t} est lensemble des instancesdes tches excutes linstant t N

8/75



9/75

Def. Problme Approche PLNE Dantzig Wolfe Lagrange Hybride Conclusion

Contraintes de prcdence (ou de dpendance)

Graphe orient

Sommets : oprationsArcs(i,j) E ou Eensemble de prcdenceslatence ji: longueur de la dpendance.distance ji : nombre ditrations qui sparent les occurrences dei et j

9/75



10/75

pp g g g y

Contraintes de prcdence

Exemple de dpendance :Dpendance (i,j) avec j

i

=2, j

i

=1, = 2.

1 2 1 2

ji= 1

= 2

ji=

2

j; q

i; q

j; q+ 1 q+ ji itration de la tche j

Contrainte de prcdence entre et

q1, qi + ji

q+ji

j

q1, i+ ji i

j j

Problme polynomiale, ordonnancements priodiques,

algorithmes O(n3logn) de recherche de circuite critique.10/75



11/75


Exemple dutilisation des ressources :

Ressources R1 R2 R3 R4

Disponibilit 4 1 1 2

Oprations R1 R2 R3 R41 1 0 0 02 1 1 0 03 1 1 0 04 1 1 0 05 1 0 0 06 1 1 0 07 1 0 0 0

8 1 0 0 09 1 0 1 1

10 1 0 0 0

4.24.1

8.1

7.1

8.2

72 3 4 5 61 98

9.1

4.1 2.1 3.1 6.1 4.2

9.1

9.1

4.0 1.0 3.0 6.0

9.0

9.0

1.0

4.0

2.0

8.0 7.0

5.0 9.0

3.0

1.1

6.0 1 0. 0 2. 1

5.1

3.1 6.1 10.1

1.2

R1

R2

R3

R4

= 4, Cmax=5

11/75



12/75


1= 2=

Lallocation des ressources est conserve dune itration lautre en

ordonnancement modulo.12/75



13/75

Rsolution du RCMSP

Mthode classique dordonnancement modulo (Rau et al. 1981, 1996)

calcul dune borne infrieure pour la priodemin=max(

res, prec)

prec = max circuit de G

()()

res = max1sm

ni=1

bsi

Bs

Recherche pour la plus petite priode telle que le RCMSP estralisable.

13/75



14/75

Etat de lart pour le RCMSP

Ordonnancement cyclique sur processeurs paralleles. Hanen etMunier (1994)

Thorie classique dordonnancement modulo : Rau et al. (1981),

Lam (1988), Rau (1996)Pipeline logiciel dcompos (DSP) : Gasperoni et Schwiegelshohn(1991), Waung et Eisenbis (1994), Hanen et Benabid (2009,2011), Insertion Scheduling Dupont-de-Dinechin (1995).

Mthodes exactes et PLNE : Govindarajan et al. (1991),

Eichenberger et Davidson(1995), Dupont-de-Dinechin (2003)Mthodes sans une valeur de fixe. Lombardi et al. 2011.

14/75



15/75

Instances pour lexprimentation

Deux groupes dinstances :

36 instances dures unitaires provenant du processeur ST200 deSTMicroelectronics : consommation des ressourcesprincipalement unitaires

Groupe dinstances correspondants une modification dupremier ensemble dinstances : genration alatoire (U [1, 10])de la consommation de ressources.

Linstance la plus petite, gsm-st231.10.rcmsest compose de 10tches gnriques et 42 relations de prcdence.

Linstance la plus grande, gsm-st231.18.rcmsest compose de 214tches gnriques et 1063 relations de prcdence.

15/75



16/75


2=

Resource Capacity

ALU 4

MEM 1

CTL 1

ODD 2

RESERVATION A LU MEM CTL ODD

ALU 1 0 0 0

ALUX 2 0 0 1

MUL 1 0 0 1

MULX 2 0 0 1

MEM 1 1 0 0

MEMX 2 1 0 1

CTL 1 0 1 1

Exemple.

Cmax=716/75



17/75

Plan



3 Dcomposition de Dantzig-WolfeNouvelles formulationsGnration de colonnesSous-problmeRsultats exprimentaux

4 Relaxation LagrangienneDfinition et rsolution du sous-problme LagrangienHeuristiqueRsultats exprimentaux

5 Mthode hybrideMthode hybrideRsultats exprimentaux


17/75



18/75

PLNE pour le RCMSP

But dutilisation de la PLNE :

Calculer des bornes infrieures de la priode optimale et delobjectif secondaire.

Rsolution exacte si cest possible ou approche.

PLNE pour le RCMSP :Formulation directe :

date de dbut de la tche gnrique i, i[0, T 1]

Formulation dcompose :

i=ki+ i

o : ki[0, ..., T1

], kiest le numro du cycle dans lequelchaque tche est place. i=imod, date de dbut de la tchegnrique idans lintervalle [0, 1].

18/75



19/75

PLNE pour le RCMSP

Formulation dcompose :

1

2

3

4

5

6

7

8

9

10

1 32 10 2 3

0 1

i

Cmax= 4 = 4

ki

5=5+k5 avec5=2+0(4) =2

Formulation directe :

1

2

3

4

5

6

7

8

9

10

1 2 3 4 5 76

Cmax= 4 = 4

i

iest place dans lhorizon T.

19/75



20/75

PLNE pour le RCMSP

Formulation dcompose (Eichenberger et al1997) : i=ki + i

minn

i=1

wi(1=0

yi +ki)

1

=0

y

i =1, i[1, n]

1=0

yi +ki + ji

ji

1=0

yj +kj, (i,j) E

ni=1

yibsi Bs, sm, [0, 1]

yi {1, 0}, ki N

20/75



21/75

PLNE pour le RCMSP

Contrainte de dpendance structure : base sur rsultats deChaudhuri et al. (1994).

1x=

yix+

(+ji1)mod

x=0

yjx+kikj

ji

+ji1

+1, [0, 1], (i,j) E

Meilleure relaxation de programmation linaire.

21/75



22/75

PLNE pour le RCMSP

Formulation directe (Dupont de Dinechin 2004). i= Tt=0tx

ti.

minn

i=1

wi(Kt=0

txti)

K

t=0 xti =1Kt=0

txti + ji

ji

Kt=0

txtj, (i,j) E

ni=1

K

k=0

x+ki bsi Bs, [0, 1], s[1, m)

xti {0, 1}

22/75



23/75

PLNE pour le RCMSP

Contrainte de prcdence dsagrge : Christofides et al. (1987).

Kh=t

xhi +t+

j

ij

i1h=0

xhj 1, t[0, . . . , K 1], (i,j) E

Meilleure relaxation de la programmation linaire.

23/75


C d l d l


24/75

Comparaison des relaxations de programmation linairepour le RCMSP

But : tudier la qualite des relaxations PLNE des formulationsdecompose et directe.

Comparaison des valeurs thoriques des relaxations.

Comparaison exprimentalement les deux formulations PLNE.

Remarque : la formulation directe comporte plus de variables et decontraintes que la formulation dcompose.

24/75


C i d l i d i li i


25/75


Thorme

Soit z(decomp) la valeur optimale pour la relaxation de laformulation (decomp) et z(direct) la valeur optimale pour larelaxation de la formulation (direct). Nous avons

z(direct) = z(decomp)

Thorme

Soit z

(decomp+) la valeur optimale pour la relaxation de laformulation dcompose renforce et z(direct+) la valeur optimalepour la relaxation de la formulation directe renforce, alors

z(direct+) = z(decomp+)

25/75


C i d l ti d ti li i


26/75


Principe de la dmonstration :

T=K, avec T, K, N.

i=i+ki.

yi =

K1k=0

x+ki i {1, . . . , n}, {0, . . . , 1}

ki=K1

k=1K1

t=k xti i {1, . . . , n}Remplacement de variables et demonstration de lunimodularitdes matrices de contraintes.

26/75



27/75

Calcul de bornes infrieures et rsolution exacte

Borne infrieure pour la priode :

Mthode itrative = min=max(res, prec).

Contraintes dintgralit relches.

Si PL irralisable alors : (= +1).Borne infrieure pour le makespan (Cmax) :Cmaxmin=max(, Cmax), tel que ralisable.

Solution optimale :

Mme principe de calcul de borne infrieure avec rsolution

PLNE.

27/75


S l l d ll


28/75

Solutions optimales : instances industrielles

Instances min PLNE(decomp+) PLNE(direct+) Cmax CPUs Cmax CPUs

adpcm-st231.1 21 21 30 14400 21 30 16235adpcm-st231.2 38 40 42 582362 40 42 601000

gsm-st231.1 24 24 33 0.05 24 33 0.05gsm-st231.2 26 26 32 79362 26 32 83991gsm-st231.5 11 11 17 0.05 11 17 0.05gsm-st231.6 7 7 13 17 7 13 20gsm-st231.7 11 11 17 0.05 11 17 0.05gsm-st231.8 8 8 8 0.05 8 8 0.05gsm-st231.9 28 28 28 0.05 28 28 0.05

gsm-st231.10 4 4 4 0.05 4 4 0.05gsm-st231.11 20 20 21 0.05 20 21 0.05gsm-st231.12 8 8 8 0.05 8 8 0.05

gsm-st231.13 19 19 25 1856 19 25 2023gsm-st231.14 10 10 13 301.25 10 13 478gsm-st231.15 8 8 8 0.05 8 8 0.05gsm-st231.16 16 16 20 7520 16 20 8156gsm-st231.17 9 9 16 0.05 9 16 0.05gsm-st231.18 53 - - - - - -gsm-st231.19 8 8 9 0.05 8 9 0.05gsm-st231.20 6 6 10 0.05 6 10 0.05gsm-st231.21 18 18 22 0.05 18 22 0.05gsm-st231.22 18 18 22 0.05 18 22 0.05gsm-st231.25 16 16 25 3652 16 25 4001

gsm-st231.29 11 11 17 12.6 11 17 15gsm-st231.30 7 7 13 12 7 13 15gsm-st231.31 11 11 17 47 11 17 73gsm-st231.32 15 15 15 0.05 15 15 0.05gsm-st231.33 15 15 21 2365 15 21 2503gsm-st231.34 4 4 5 0.05 4 5 0.05gsm-st231.35 6 6 11 0.05 6 11 0.05gsm-st231.36 10 10 15 27 10 15 42gsm-st231.39 8 8 16 0.05 8 16 0.05gsm-st231.40 10 10 10 0.05 10 10 0.05gsm-st231.41 18 18 24 2356 18 24 2562gsm-st231.42 6 6 10 0.05 6 10 0.05gsm-st231.43 8 8 14 0.05 8 14 0.05 28/75


S l i i l i difi


29/75

Solutions optimales : instances modifies

Instances min PLNE(decomp+) PLNE(direct+) Cmax CPUs Cmax CPUs

adpcm-st231.1 52 - - - - - -adpcm-st231.2 82 - - - - - -

gsm-st231.1 24 25 42 250 25 42 375gsm-st231.2 59 - - - - - -gsm-st231.5 26 36 46 280 36 46 299.03gsm-st231.6 17 27 27 152 27 27 265gsm-st231.7 28 41 45 92 41 45 115gsm-st231.8 9 12 12 0.27 12 12 0.31gsm-st231.9 28 32 35 0.56 32 35 60

gsm-st231.10 6 8 8 0.10 8 8 0.11gsm-st231.11 20 24 24 0.37 24 24 0.39gsm-st231.12 10 13 13 12.65 13 13 19

gsm-st231.13 27 43 48 985.03 43 48 1236gsm-st231.14 20 33 45 220 33 45 252gsm-st231.15 9 12 12 12.36 12 12 13gsm-st231.16 38 - - - - - -gsm-st231.17 23 33 33 90 33 33 105gsm-st231.18 120 - - - - - -gsm-st231.19 12 15 15 38.23 15 15 43gsm-st231.20 13 20 27 123 20 27 137gsm-st231.21 20 30 30 42.03 30 30 59gsm-st231.22 18 29 29 80.36 29 29 112gsm-st231.25 37 56 (Gap=1.75%) 56 604800 - - -

gsm-st231.29 28 42 42 210 42 42 513gsm-st231.30 16 25 25 58 25 25 67gsm-st231.31 26 39 39 142 39 39 169gsm-st231.32 21 30 30 0.25 30 30 1.01gsm-st231.33 33 52(Gap=8%) 50 604800 - - -gsm-st231.34 7 7 7 5.05 7 7 8gsm-st231.35 12 14 16 52 14 16 53gsm-st231.36 18 24 28 230 24 24 403gsm-st231.39 15 21 25 95 21 25 168gsm-st231.40 12 17 21 15 17 21 29gsm-st231.41 33 - - - - - -gsm-st231.42 14 18 26 12 18 26 17gsm-st231.43 15 20 25 15 20 25 23 29/75


B i f i i t i d t i ll


30/75

Bornes infrieures : instances industrielles

Instances min Cmax CPU (s) (decomp+) CPU (s) (direct+)

adpcm-st231.1 21 21 29.5 498 536adpcm-st231.2 38 38 42 5326.37 6012

gsm-st231.1 24 24 33 0.02 0.02gsm-st231.2 26 26 31.5 586 614gsm-st231.5 11 11 15.2 0.02 0.02gsm-st231.6 7 7 11.2 0.02 0.02gsm-st231.7 11 11 15.2 0.02 0.02gsm-st231.8 8 8 8 0.02 0.02gsm-st231.9 28 28 28 0.02 0.02

gsm-st231.10 4 4 4 0.00 0.00gsm-st231.11 20 20 21 0.02 0.02gsm-st231.12 8 8 8 0.00 0.00gsm-st231.13 19 19 25 0.02 0.02

gsm-st231.14 10 10 12.63 0.02 0.02gsm-st231.15 8 8 8 0.00 0.00gsm-st231.16 16 16 16.97 3625.12 3812.03gsm-st231.17 9 9 15.25 0.02 0.02gsm-st231.18 53 53 53 7256 8002.03gsm-st231.19 8 8 8 0.00 0.00gsm-st231.20 6 6 10 0.00 0.00gsm-st231.21 18 18 22 15 15gsm-st231.22 18 18 21 17 20gsm-st231.25 16 16 24.52 789.26 814gsm-st231.29 11 11 15.2 7.52 7.84

gsm-st231.30 7 7 11.2 0.02 0.02gsm-st231.31 11 11 15.2 0.02 0.02gsm-st231.32 15 15 15 4.25 4.45gsm-st231.33 15 15 17.23 42 42gsm-st231.34 4 4 5 0.00 0.00gsm-st231.35 6 6 8.2 0.00 0.00gsm-st231.36 10 10 10 0.02 0.02gsm-st231.39 8 8 12.5 0.02 0.02gsm-st231.40 10 10 10 0.00 0.00gsm-st231.41 18 18 18 12 0.02gsm-st231.42 6 6 10 0.02 0.02gsm-st231.43 8 8 10.4 0.00 0.00

30/75


B i f i i t difi


31/75

Bornes infrieures : instances modifies

Instances min Cmax CPU (s) (decomp+) CPU (s) (direct+)

adpcm-st231.1 52 52 52 1800 1995.03adpcm-st231.2 82 82 82 7214 7327

gsm-st231.1 24 24 32 600 626gsm-st231.2 59 59 59 7200 7298.04gsm-st231.5 26 26 26 600 600gsm-st231.6 17 17 17 600 600gsm-st231.7 28 28 28 22 23gsm-st231.8 9 9 9 0.02 0.02gsm-st231.9 28 28 28 25 30

gsm-st231.10 6 6 6 0.0001 0.0001gsm-st231.11 20 20 21 0.15 0.152gsm-st231.12 10 10 10 0.0001 0.0001gsm-st231.13 27 27 27 48 52

gsm-st231.14 20 20 20 18 21gsm-st231.15 9 9 9 0.001 0.002gsm-st231.16 38 38 38 420 452gsm-st231.17 24 24 24 720 795gsm-st231.18 120 120 120 600 603gsm-st231.19 12 12 12 0.002 0.002gsm-st231.20 13 13 13 0.002 0.002gsm-st231.21 20 20 22 24 24gsm-st231.22 18 18 21 8 8gsm-st231.25 37 37 37 300 317gsm-st231.29 28 28 28 60 62

gsm-st231.30 16 16 16 0.25 0.253gsm-st231.31 26 26 26 58 60gsm-st231.32 21 21 21 3.02 3gsm-st231.33 33 33 33 52 51gsm-st231.34 6 6 6 0.001 0.001gsm-st231.35 11 11 11 0.002 0.002gsm-st231.36 18 18 18 8 8gsm-st231.39 15 15 15 0.06 0.08gsm-st231.40 12 12 12 0.0001 0.0001gsm-st231.41 34 34 34 47 49gsm-st231.42 14 14 14 4.03 6gsm-st231.43 15 15 15 0.026 0.02

31/75


Pl


32/75

Plan


2 Programmation linaire en nombres entiers3 Dcomposition de Dantzig-Wolfe

Nouvelles formulationsGnration de colonnesSous-problme

Rsultats exprimentaux




32/75


Dcomposition de Dantzig Wolfe pour le RCMSP


33/75

Dcomposition de Dantzig-Wolfe pour le RCMSP

Amliorer les bornes obtenues par relaxation de PLNE pour lapriode .

Proposer nouvelles formulations PLNE pour le RCMSP : grand

nombre de variables.Schma de gnration de colonnes de manire rsoudre larelaxation de ces formulations.

Utilisons lapproche de Vanderbeck (2000) pour proposer desnouvelles formulations pour le RCPSP bases sur la dcomposition de

Dantzig-Wolfe.

33/75


Plan


34/75

Plan








34/75


Formulations renforces pour le RCMSP


35/75


Dcomposition de Dantzig-Wolfe :P() : ensemble de solutions ralisables respectant les contraintes deressources linstant {0,...,}.

P() = y {0, 1}n | ni=1

yib

si Bs, s {1, . . . , m}

Correspondance bijective entre les points ralisables non-nuls deP() et lensemble R des ensembles doprations {i1, . . . , iq} tel

queqp=1bsip Bs, s {1, . . . , m}.Chaque ensemble de R est appel un ensemble ralisable.

35/75




36/75


Dcomposition de Dantzig-Wolfe :Le polydre P() peut tre reprsent par lnumration de tous seslments :

P() =y Rn | y = lR

z

l

Pl et lR

z

l

=1 pour tout z

l

{0, 1}, l RMatrice binaire atel que ali=1 si la tche iappartient lensemble ralisable Pl (a

li reprsente le i-me lment de Pl).

En remplaant yi parlR

alizl, tel que zl {0, 1}, lR.

36/75




37/75


4.24.1

8.1

7.1

8.2

72 3 4 5 61 98

9.1

4.1 2.1 3.1 6.1 4.2

9.1

9.1

4.0 1.0 3.0 6.0

9.0

9.0

1.0

4.0

2.0

8.0 7.0

5.0 9.0

3.0

1.1

6.0 1 0. 0 2. 1

5.1

3.1 6.1 10.1

1.2

R1

R2

R3

R4

= 4, Cmax=5

= 4, {0, 1}

l1 ={4, 8, 1} z0l1

= 1, z1l1

=0, z2l1

=0, z3l1

=0

l2 ={1, 7, 5, 2} z0l2

= 0, z1l2

= 1, z2l2

=0, z3l2

=0

l3 = {3} z0l3

=0, z1l3

=0, z2l3

=1, z3l3

= 0

l4 ={9, 6} z0l

=0, z1l4

= 0, z2l4

=0, z3l4

=1

37/75




38/75


Nouvelle formulation (M-decomp) pour le RCMSP.

min

ni=1

wi(ki+

1=0

lR

alizl )

lR1

=0a

liz

l =1 i {1, ...,n}

lR

zl 1, {0, . . . , 1}

1

=0

lR

a

l

jz

l lR

a

l

iz

l + (kjkj) jiji (i,j) Ezi {0, 1} l {R}, {0, . . . , 1}

ki {0, . . . ,K1}, i {1, . . . ,n}38/75




39/75


Contraintes de prcdence structures :

1

x=lRa

liz

xl +

(+ji1) mod

x=0 lRa

ljz

xl +kikj

ji

+ji1

+1,

{0, . . . , 1}, (i,j) E (1)

Une nouvelle formulation renforc appele (M-decomp+) est doncobtenue.

Remarque : mme schma pour (M-direct) et (M-direct+)

39/75


Plan


40/75

Plan




Rsultats exprimentaux4 Relaxation Lagrangienne

Dfinition et rsolution du sous-problme LagrangienHeuristiqueRsultats exprimentaux



40/75


Gnration de colonnes


41/75

Gnration de colonnes

PMR

RR

RR


42/75

ob e dua o u at o ( deco p)

Les contraintes duales associe la variable zl du problme matredonn par la formulation (M-decomp) :

n

i=1 alii+ (i,j)E ij(a

lja

li)

n

i=1 wiali, lR, {0, . . . , 1}

ce qui donne

n

i=1 F(i, )ali, lR, {0, . . . , 1}

o F(i, ) =i+

(j,i)Eji

(i,j)Eij+wi

.

42/75


Plan


43/75








43/75


Sous-problme


44/75

p

Il est possible de trouver une contrainte duale viole, cest--dire un

vecteuraitel queni=1w1(i, )ai.max

ni=1

F(i, )ai

ni=1

aibsi Bs, s {1, . . . , m}

ai {0, 1}, i {1, . . . , n}

Pour chaque =0,..., 1. Nous avons donc sous-problmes rsoudre.

Le problme matre est rsolu, puis les sous-problmes sontgalement rsolus.

44/75


Calcul des bornes infrieures


45/75

La plus petite valeur de ralisable obtenue avec la solution desrelaxations des nouvelles formulations proposes, en utilisant leschma de gnration de colonnes.

La borne pour le makespan est dfinie parCmaxmin=max(, Cmax), o Cmax correspond la valeurobtenue avec la rsolution des relaxations en utilisant le schmade gnration de colonnes, uniquement si le programme linaireadmet une solution ralisable pour une valeur de donne.

45/75


Plan


46/75








46/75




47/75

Figure:Bornes pour la priode . Instances modifies.

Relaxation (decomp+) GC(M-decomp+)

Nombre dinstances rsolues 36/36 34/36Test avec = opt 0/28 23/28Ecart maximal opt 16 1

Ecart moyen opt

7.10 0.5847/75




48/75

Figure:Bornes pour le Cmax. Instances modifies.

Relaxation (decomp+) GC (M-decomp+)Nombre dinstances rsolues 36/36 34/36Test avec Cmax=Cmaxopt 0/28 15/28Ecart maximal CmaxCmaxopt 25 12

Ecart moyen CmaxCmax

opt

9.57 2.5848/75


Plan


49/75








49/75


Relaxation Lagrangienne


50/75

But : Obtenir bornes suprieures pour la priode et pour le Cmax

Relaxation Lagrangienne sur la formulation PLNE directedesagrge.

Rsultats de Mhring et al. pour le RCPSP : solution desous-problme= coupe minimale dans un graphe oriente.

Heuristique : transformation de la formulation PLNE dcomposeen utilisant la relaxation lagrangienne.

50/75




51/75

Considerons

L,(x) =m

s=1

1=0

,s(n

i=1

t mod =

bsixti)

ms=1

1=0

,sBs.

le programme linaire

min{L,(x)| x ()}

,s 0 [0, 1].

() polydre dfini par les contraintes de prcdence de laformulation directe structure.

51/75




52/75

Proposition

() est vide si pour un0, () est vide ou L,>0.

Soit le problme Lagrangien dual

max0

min{L,(x)| x ()}

borne infrieure RL : plus petit telque L 0

Remarque : Nous ne sommes pas intresses par la valeur de la borneinfrieure por la priode .

52/75




53/75

Borne pour le Cmax.

Sous-problme Lagrangien : L,(x) =Cmax+L,(x) avec

Cmax=

Tt=0tx

tn+1.

Sous-problme Lagrangien :

min{L,(x)| x ()}

Borne pour le Cmax: solution du dual Lagrangien :

max0

min{L,

(x)| x ()}

53/75


Plan


54/75








54/75


Dfinition et rsolution du sous-problme Lagrangien


55/75

ralisable pour la relaxation de la formulation PLNE directe.

Borne pour le Cmax : sous problme Lagrangien

L

,(x) = Cmax+L,(x) =

Tt=0

txtn+1+

ms=1

1=0

,s (

ni=1

t mod =

bsix

ti)

ms=1

1=0

,s Bs

Dfinition de poids :

fi,t=

ms=1

bsi,s si i


56/75

Cas particulier du problme dordonnancement de projet avec cotsdpendant des dates de dbut dcrit par Mhring et al. (2003)

Arcs daffectation { } { }....0,...1),( 1,, Ttnivv titi +

arcs temporels { }....0,),(),( )(,, TtEjivv jijititi +

sommets { } { }....0,...1, Ttniv ti

,tif

capacits.,tif

n

a b

T210 . . .

1

2

.

.

.

56/75


Dfinition et rsolution du sous-problme Lagrangien


57/75

Thorme

Il existe une correspondance une une entre la coupe minimale a bet la paire(X, X) G avec exactement n arcs avant et une solutionoptimale x pour le probleme Lagrangien obtenu par xi,t=1 si

(vi,t, vi,t+1) est un arc sortant de la coupe(X, X), et xi,t=0 sinon.La valeur w(x) dune solution optimale du problme Lagrangien estgale la capacit c(X, X) de la coupe minimale(X, X) de G.

Mhringet al. (2003).

Rsolution de dual Lagrangien : Sous-gradient

57/75


Plan


58/75








58/75


Heuristique


59/75

Le vecteur xobtenu par lalgorithme du dual Lagrangien estentier (0 1)

Construction des solutions ralisables.

Heuristique :Formulation dcompose.i=i+kiValeurs de ki fonction du vecteur xtrouv par la relaxationLagrangienne.Solution de PLNE avec les valeurs ki fixes.

59/75


Plan


60/75


2

Programmation linaire en nombres entiers3 Dcomposition de Dantzig-Wolfe






60/75




61/75

Nombre dinstances rsolues 36/36Test avec = opt 28/36Ecart maximal opt 8Ecart moyen opt 0.55Test avec Cmaxsup = Cmax

opt 21/28Ecart maximal Cmaxopt Cmaxsup 5Ecart moyen Cmaxopt Cmaxsup 0.68

Table:Rcapitulatif des bornes suprieures obtenues pour la priode etpour le Cmax. Instances industrielles

Nombre dinstances rsolues 33/36Test avec sup =

opt 14/28Ecart maximal opt sup 3Ecart moyen opt sup 0.64

Test avec Cmaxsup = Cmaxopt

12/14Ecart maximal Cmaxopt Cmaxsup 5Ecart moyen Cmaxopt Cmaxsup 1.21

Table:Rcapitulatif des bornes suprieure obtenues pour la priode etpour le Cmax. Instances modifies

61/75


Plan


62/75


2







62/75


Plan


63/75


2







63/75


Mthode hybride


64/75

But : bornes suprieures ou solutions ralisables en tempsraisonnables.Mthode hybride :

Collaboration avec Abir BENABID et Claire HANEN (LIP6).

Pipeline logiciel dcomposTransformation du vecteur colonne dinstructions (i) en unematrice deux dimensions.Les lignes : la date de dbut idans la priode Les colonnes : litration dans la boucle dorigine (i.e. le numro

de la priode k

i).

64/75


Pipeline logiciel dcompos


65/75

()

()

()

' ()

' ()

65/75


DSP : Dcalage des instructions


66/75

Dcalage des instructions : circuit retimingG= (O, E, , ), un vecteur retiming (i) est une fonction qui affecteles poids des arcs du graphe G.

(i,j) E, : (i,j) Z tel que i,j=(ji) =

ji+ j i

Dfinition

Un retiming lgal est un retiming tel que

(i,j)

E, : (i,j)

Z tel que

i,j=(j

i) =j

i+

j

i0

66/75


Mthode hybride


67/75

()

* '

()

nikii

,...,1, =

nii

,...,1=

67/75


Mthode hybride

Al ith 1 Mth d h b id


68/75

Algorithme 1: Mthode hybride1 Calculer un retiming lgal pour G2 Trouver ralisable (mthode itrative) et une solution ralisable du systeme suivant :

min

ni=1

wi(

1=0

yi +i)

1=0

yi = 1, i[1, n]

1

x=y

ix+

(+ji1)mod

x=0y

jx+ij

ji

+ji1

+1, [0, ), (i,j) E

ni=1

yi b

si ms, s {1, . . . , m}, [0, )

yi {0, 1}

3 Dfinir un ordonnancement i i=1..n, i = i+i

68/75


Plan


69/75



3 Dcomposition de Dantzig-WolfeNouvelles formulationsGnration de colonnesSous-problme





69/75




70/75

HybrideHD HybrideGS DSP iFLAT Rellag

Nombre dinstances rsolues 36/36 36/36 36/36 33/33 36/36Test avec = opt 34/36 32/36 30/36 26/33 28/36Ecart maximal opt 1 3 3 3 8Ecart moyen opt 0.005 0.22 0.25 0.24 0.55

Table:Comparaison de la mthode hybride avec des autres mthodes pourla recherche des solutions ralisables. Instances industrielles

HybrideHD HybrideGS DSP iFLAT RellagNombre dinstances rsolues 34/36 32/36 36/36 25/25 33/36Test avec = opt 21/28 20/28 20/28 16/25 14/28Ecart maximal opt 4 3 5 3 3Ecart moyen opt 0.39 0.42 0.82 0.64 0.64

Table:Comparaison de la mthode hybride avec des autres mthodes pourla recherche des solutions ralisables. Instances modifies

70/75


Plan


71/75



3 Dcomposition de Dantzig-WolfeNouvelles formulationsGnration de colonnesSous-problme





71/75


Conclusion et perspectives


72/75

Problme dordonnancement modulo sous contraintes de

ressources : application lordonnancement dinstructions VLIW.Formulations PLNE pour le RCMSP :

Formulations dcompose et directe + version structure etdsagrge.Comparaison des valeurs thoriques des relaxations.Comparaison exprimentale des formulations presentes.Bornes faibles pour la priode .

Dcomposition de Dantzig-Wolfe :

Nouvelles formulations rnforces : grand nombre de variables.Schma de gnration de colonnes : solution des relaxations desnouvelles formulations.

Amelioration des bornes pour les instances avec consommation deressources non unitaires.

Rsultats publis : PMS 2010 et Article sumis Discrete AppliedMathematics (2 revision)

72/75




73/75

Relaxation Lagrangienne :

Relaxation Lagrangienne sur la formulation directe structure.Solution du sous-problme partir dune coupe minimale :rsultats de Mhring.Heuristique : relaxation Lagrangienne + formulation PLNEdcompose.Bornes suprieures de bonne qualit pour la priode et pour le

Cmax.Temps de calcul importants.Rsultats publis : ISCO 2010. Electronic Notes in DiscreteMathematics, Vol.36, pp.191-198, Aot 2010

Mthode hybride :

Combinaison de DSP + formulation PLNE structureNouvelles bornes suprieures pour la priode .Amlioration des temps de calcul.Rsultats publis : article sumis Computational OptimizationAnd Applications

73/75




74/75

Gnration de colonnes : inclure rgles pour rduire lespace dessous ensembles ralisables (coupes).

Heuristique base sur la relaxation Lagrangienne pour larecherche des solutions ralisables (sans PLNE) .

Amlioration de limplmentation du code de programmation dela gnration de colonnes et relaxation Lagrangienne.

Extension des mthodes et techniques proposes pour desproblmes dordonnancement stochastiques en considrant ladure des oprations ou dautres paramtres du problme comme

des variables alatoires.

74/75



75/75

Merci de votre attention.

75/75

Documents

Programmation linéaire en nombres entiers pour l’ordonnancement modulo sous contraintes de ressources