Introduction a l Ordonnacement Ordonnacement Et Planification Cours 15-12-10

5/15/2018 Introduction a l Ordonnacement Ordonnacement Et Planification Cours 15-12-10 - slidepdf.com

http://slidepdf.com/reader/full/introduction-a-l-ordonnacement-ordonnacement-et-planification-cours-15-12-10 1/28

Introduction à l’ordonnancement

Nizar El Hachemi

15 décembre 2010

Nizar El Hachemi Introduction à l’ordonnancement

http://find/

http://goback/



Plan du cours

Définition et formulation du problème d’ordonnancement

Introduction à CometExemples


http://find/



Définition et formulation du problème d’ordonnancement

C’est quoi l’ordonnancement ?

Quelques domaines concernés par la fonction ordonnancement

La fonction ordonnancement dans la gestion de la production

Contraintes rencontrées en ordonnancement

Formulation mathématique


http://find/



Ordonnancer ?

Définition

Le problème d’ordonnancement consiste à organiser dans le tempsla réalisation d’un ensemble de tâches, compte tenu de contraintestemporelles (délais, contraintes d’enchaînement, ...) et decontraintes portant sur l’utilisation et la disponibilité des ressources

requises.

Un ensemble de tâches

Un environnement de ressources pour effectuer les tâches

Des contraintes sur les tâches et les ressourcesUn critère d’optimisation

⇒ Déterminer les dates d’execution des tâches


http://find/



Domaines concernés

Gestion de projets

Administration : gestion des ressources humaines + emplois du

temps ...Production

Informatique (exécution des programmes, optimisation decode)


http://find/



La gestion de la production

La gestion de production a pour objet la recherche d’uneorganisation efficace de la production des biens et des services

3 catégories pour classer les décisions en gestion de la

production :1 Les décisions stratégiques : politique long terme de l’entreprise2 Les décisions tactiques : décisions à moyen terme (planification

de la production, planification de transport)3 Les décisions opérationnelles : court terme (gestion des stocks,

ordonnancement, pilotage informatique en temps réel)


http://find/

http://goback/



Contraintes rencontrées en ordonnancement

Technologiques : une tâche ne peut débuter que lorsqued’autres sont achevées

Commerciales : certaines dates doivent être achevées pour une

date fixéeMatérielles : une machine ne peut traiter qu’une machine à lafois

Main d’oeuvre : effectif limité

Financières : budget limité


http://find/

http://goback/



Formalisation des contraintes

Contraintes potentielles (ou de potentiels)

Contraintes disjonctivesContraintes cumulatives


http://find/

http://goback/



Contraintes potentielles

Notation : t j : date de début de la tâche j , p j sa duréeForme générale : t j − t i >= aij

Localisation temporelle : j ne peut débuter avant une certainedate (livraison de matière première, conditions climatiquees,...)

Contrainte de délai : j doit être terminée avant une certainedate

Contrainte de succession1 succession simple2 succession avec attente3 succession avec chevauchement4 succession immédiate


C d

http://find/

http://goback/



Contraintes disjonctives

Deux tâches i et j sont en disjonction si elles ne peuvent êtreexécutées simultanément

⇒ Les intervalles d’exécution des tâches disjonctives sontdisjoints : ]t i , t i + p i [∩]t j , t j + p j [= ∅

Disjonction d’inégalités de potentiels1 t j − t i ≥ p i ou t i − t j ≥ p j


C i l i

http://find/

http://goback/



Contraintes cumulatives

C’est une généralisation des contraintes disjonctives

Exemple : On a deux grues et 5 tâches nécessitant une grue

Soit1 w k (t ) la quatité disponible de la ressource k à l’instant t 2 w ik (t ) la quantité nécessaire de la ressource k pour exécuter i

à t

Si1

i ∈S w ik (t ) ≤ w k (t )

2 alors les tâches de S peuvent être exécutées simultanément à t 3 sinon les tâches de S sont en disjonction


F l i hé i

http://goforward/

http://find/

http://goback/




n tâches à exécuter + 2 tâches fictives 0 et n + 1 de duréesnulles

Déterminer (t 0, t 1, ..., t n, t n+1) de manière à

Minimiser f (t 0, t 1, ..., t n, t n+1)

sujet à1 Contraintes de potentiel : t j − t i >= aij

2 Contraintes disjonctives : t j − t i ≥ p i ou t i − t j ≥ p j 3 Contraintes cumulatives (idem)4 Contraintes de non négativité : t 0, t 1, ..., t n, t n+1

par exemple : f (t 0, t 1, ..., t n, t n+1) = t n+1 − t 0


O d t d j t

http://goforward/

http://find/

http://goback/



Ordonnancement de projet

Problème central de l’ordonnancement : ressources illimitées1 Définition2 Modélisation avec un graphe potentiels-tâches3 Recherche d’ordonnancement admissible

Cas général : ressources limitées1 Problématique2 Résolution exacte3 Approche simple de résolution : algorithme de liste

Cas de ressources financières1 Problématique2 L’offre et la demande3 Algorithme de décalage


C t t

http://find/



Context

Un projet consiste en un ensemble de n tâches liées par descontraintes de succession ou de précédence

Objectif 1

Calculer la durée minimale du projet, les ressources étantsupposées illimitées2 ⇒ Minimiser (t n+1 − t 0) sous les contraintes de potentiels3 Déterminer les dates de début au plus tôt et au plus tard des

tâches4 Déterminer les tâches critiques


Form lation mathématiq e

http://find/

http://goback/




Déterminer (t 0, t 1, ..., t n, t n+1) de manière à

Minimiser t n+1 − t 0

sujet à1 Contraintes de potentiel : t j − t i >= aij

2 Contraintes de non négativité : t 0, t 1, ..., t n, t n+1



http://goforward/

http://find/




les modèles qu’on a vu sont des PL (des modèles linéaires)

Y a t-il une autre manière de modéliser ces problèmesd’ordonnancement ?

Oui, en utilisant la programmation par contraintes


Comet

http://find/



Comet

Un modèle riche pour la recherche locale

Une recherche riche

Séparation entre la modélisation et la recherche

Fléxibiliter


Solveurs de Comet

http://find/



Solveurs de Comet

Un solveur CP (constraint programming)

Un solveur LP (programmation linéaire)

Un solveur MIP (programmation en nombres entiers)

Un solveur LS (recherche locale basée sur les contraintes)


Déclaration de solveurs en Comet

http://find/



Déclaration de solveurs en Comet

import cotls ;

1 Solver< LS > m();

import cotln ;

2 Solver< LP > lp();import cotln ;

3 Solver< MIP > mip() ;

import cotfd ;

4 Solver< CP > m();


Déclaration de variables

http://find/



Déclaration de variables

var{int } queen[Size](m,Size) := distr.get() ;

var< LP > {float } cut[Configs](lp) ;

var< MIP > {int } x[Columns](mip,0..maxValue) ;

var< CP > {int } q[i in S](m,S) ;


Déclaration de contraintes

http://find/



Déclaration de contraintes

Constraint< LP >meet[Shelves] ;1 forall(i in Shelves) meet[i] = lp.post(sum(j in Configs)

C{ j }.getShelf(i) * cut[j] >= demand[i]) ;

2 forall(i in Rows) mip.post(sum(j in Columns) coef[i,j] * x[j]

<= b[i]) ;ConstraintSystem< LS >S(m);

3 forall(i in Teams) S.post(x[i,i,nbRounds-1]+x[i,0,nbRounds-1]+ x[i,i,nbRounds]+x[i,0,nbRounds] >= 1) ;

Solver< CP > m();

4 m.post(alldifferent(q),onBounds) ;


Cas d’étude simple : une seule machine

http://find/



Cas d étude simple : une seule machine

L’ensemble des tâches à réaliser est fait par une seule machine

On peut rencontrer ce genre de problème dans un système de

production possédant une machine goulotL’ordonnancement consiste à choisir le temps d’exécusion dechaque tâche


Exemple : une seule machine

http://find/




On considère une usine possédant une chargeuse

L’usine recevra 10 chargement pendant une journée donnée

Chaque déchargement opéré par la chargeuse prend 30 minutes3 chargements arrivent à 8h du matin, 4 arrivent à 13h et lereste arrive à 16h.



http://find/



e p e u e seu e ac e

Proposer un modèle CP

Ecrire le modèle CP en language CometRésoudre le problème



http://find/



p

On enrichit le modèle avec les contraintes suivantes :

Pas de plus que deux chargements en 90 minutesFinir avant 8h du soir


Exemple : deux machines en paralléle

http://find/



p p

On considère le même problème mais avec deux chargeuses

L’usine recevra 10 chargement pendant une journée donnée

Chaque déchargement opéré par la chargeuse prend 30 minutes3 chargements arrivent à 8h du matin, 4 arrivent à 13h et lereste arrive à 16h.

Finir avant 18h du soir


Jobshop Scheduling

http://find/



p g

Le problème consiste en un ensemble de n Jobs

Un ensemble de m machines

Un Job est une séquence d’activités (t 1, t 2, ..., t l )Chaque activité doit être exécuter sur une machine donnée mi

sans interruption


Contraintes du Jobshop Scheduling

http://find/



g

Contrainte de précédence1 (t i precedes t i +1)

Contrainte disjonctive1 Soit v et w deux activités qui s’exécutent sur la même

machine alors :2 Soit v precedes w ou Soit w precedes v


http://find/

Documents

Introduction a l Ordonnacement Ordonnacement Et Planification Cours 15-12-10