3.5.2.1 Formulation mathématique du
problème
· Les variables de décision :
xij =
|
{
|
1 si l'agent j est affecté à la tâche i ,
0 sinon
|
|
· -Page 29-
Les contraintes :
3.5 Quelques problèmes classiques d'optimisation
combinatoire 30
1. chaque agent j ne sera affecté qu'à
une et une seule tâche (parmi toutes les tâches
i = {1,...,n}) :
Xn xij = 1,?i = {1,...,n} i=1
2. chaque tâche i ne sera effectuée que
par un seul agent (parmi touts les agents
j = {1,...,n}) :
Xn xij = 1,?j = {1,...,n} j=1
· La fonction objectif: Elle est triviale
car le coût d'avoir affecté i à j est : cijxij , pour tout
i,j={1,. . .,n}.Le coût total de l'affectation globale est:
MinimiserZ =
|
Xn i=1
|
Xn j=1
|
cijxij
|
|
· Le modèle mathématique: Le
problème d'affectation est donné par le programme linéaire
en 0 - 1 (PL en 0 - 1) suivant:
Xn xij = 1,?j = {1,...,n} j=1
xij ? {0,1},?i = {1,...,n} et ?j = {1,...,n}
?
????????????? ?
??????????????
Minimiser Z =
|
Xn i=1
|
Xn j=1
|
cijxij
|
|
sous contraintes :
|
Xn i=1
|
xij = 1,?i = {1,...,n}
|
(3.2)
|
|
-Page 30-
3.5.3 Problème d'ordonnancement:
Le problème d'ordonnancement est un problème
difficile de l'optimisation,il consiste à organiser dans le temps la
réalisation d'un ensemble de tâches d'un projet donné,
compte tenu des contraintes temporelles (délais, contraintes
d'enchaînements,...) et de contraintes portant sur l'utilisation et la
disponibilité des ressources requises pour les tâches [16], et
visant à minimiser (respectivement maximiser) un certain
critère,financiers ou technologiques d'optimalité.De
manière plus précise, on parle d'ordonnancement lorsqu'on
parvient à fixer les dates de début et de fin de chacune des
activités du projet [19].
3.5 Quelques problèmes classiques d'optimisation
combinatoire 31
-Page 31-
3.5.3.1 Formulation mathématique du
problème
· Les variables de décision:
ti : la date de début d'exécution de la
tâche i; td : la date de début du projet; tf :
la date de fin de projet.
· La fonction objectif: L'objectif
principale en gestion est de minimiser la durée du réalisation du
projet qui représente l'écart entre la date de fin du projet et
sa date de début:
MinimiserZ = tf - td = tf
Avec td est fixé généralement
à td = 0
· Les contraintes:
1. Les contraintes de localisation temporelle:
Aucune tâche ne peut commencer avant la date de début de
projet:
ti = 0, i = 1,...,n
2. Les contraintes de succession temporelle:
Exprimer que tout tâche i ne peut pas débuter avant que
toutes ses tâches antérieures j ?
-(i) soient complètement
achevées:
tj + dj = ti, ?j ?
-(i)
3. Les contraintes de fin de projet: Toutes les
tâches du projet doivent terminées avant la date de fin du projet
tf :
ti + di = tf, i = 1,...,n
· Le modèle mathématique: Le
modèle mathématique formulant le problème courant
d'or-donnancement est le programme linéaire (PL) (3.3) :
3.5 Quelques problèmes classiques
d'optimisation combinatoire 32
-Page 32-
????????
?
???????? sous contraintes : tj + dj = ti,
?j E -(i), i = {1, . .
. , n}
Minimiser Z = tf
ti + di = tf, i =
{1,...,n}
ti = 0, i = {1,...,n} (3.3)
| 
