Cours 4
Cours 4
UNIVERSITÉ DE BATNA 2
Faculté de Technologie
Département de Génie Industriel
Laboratoire d’Automatique et Productique
THÈSE
Présentée par
T OUFIK B ENTRCIA
En vue d’obtenir le grade de
DOCTEUR EN SCIENCES
Thème
Jury
Prof. Kinza Nadia M OUSS , Université de Batna 2, Algérie Président
Prof. Daoud A IT-K ADI , Université Laval, Canada Membre
Prof. Mohammed M OSTEFAI , Université de Sétif 1, Algérie Membre
Prof. Leila Hayet M OUSS , Université de Batna 2, Algérie Directrice de thèse
Prof. Zaki S ARI , Université de Tlemcen, Algérie Membre
Prof. Farouk YALAOUI , Université de Technologie de Troyes, France Membre
T
H
Thèse soutenue publiquement le 22 Octobre 2017
È
S
E
ii
iii
iv
Remerciements
L ou an ge à Alla h, qu e la p aix et la bén édi cti on s oi ent sur s on
Pr op h ète M oh amm ed, ain si qu e sur s a famille et s es C om p a gn on s.
E n r es p ectant la con si gn e du pr op h ète (Paix et bén édi cti on sur
lui) qui di s ait : ¿ C elui qui n e r em er ci e p a s les gen s n' aur a p a s
r em er ci é Alla h.À , je vou dr ai s a dr es s er m es plu s vifs r em er ci em ents
à certain es p er s onn es. Fr an c h em ent, la pr és ente t h ès e n' aur ait p a s
vu le jour s an s leur s su p p ort et ori entati on.
C e tr avail d e t h ès e a été r éali s é au s ein du L abor atoir e d'Auto -
m ati qu e et Pr odu cti qu e à lU niver sité d e M ostefa B enboulaï d B atn a
2.
M es tou s pr emi er s r em er ci em ents vont n atur ellem ent à M a d am e
L eila H ayet M ou s s, Pr ofes s eur à lU niver sité B atn a 2 et dir ectri ce
d e cette t h ès e, p our s es con s eils p ertin ents et s a di s p onibilité.
Je ti en s à r em er ci er M a d am e Na di a Kinza M ou s s, Pr ofes s eur
à lU niver sité B atn a 2, d' avoir a ccepté la lour d e r es p on s abilité d e
Je r em er ci e vivem ent M on si eur D a ou d Ait-K a di, Pr ofes s eur à
lU niver sité L aval C an a d a, d' avoir a ccepté d' êtr e p armi n ou s. Je
sui s vr aim ent h on or é p ar s a pr és en ce d an s m on jury.
Je ti en s à exprim er m a gr atitu d e à M on si eur M oh amm ed M os-
tefai, Pr ofes s eur à lU niver sité Sétif 1, qui a bi en voulu examin er
Je r em er ci e égalem ent M on si eur Z a ki Sari, Pr ofes s eur à lU ni-
ver sité d e Tlem cen, p our s a gentilles s e et lintér êt qu'il a p orté à
Je sui s p arti culi èr em ent r econn ai s s ant à M on si eur Far ou k Ya-
v
la oui, Pr ofes s eur à lU niver sité d e T ec hn ologi e d e Tr oyes Fr an ce,
p our les di s cu s si on s fru ctu eu s es et p our l a cceptati on d e p arti ci p er
à ce jury.
Je gar d e un e pla ce s p éci ale d an s m es r em er ci em ents à m es pr oc h es
n otam ent m a famille et m es ami s p our leur s s outi ent et en cour a-
gem ent, comm e d' h abitu d e ! ! !. Peu im p orte l or dr e d e m es r em er ci e-
m ents, tou s ceux qu e j' ai m enti onn é et s an s oubli er les p er s onn es
d an s l ombr e m' ont a p p orté tout au lon g d es ann ées p a s s ées un e
ai d e pr éci eu s e et d éci sive p our l abouti s s em ent à cette t h ès e.
vi
Dédicaces
À tou s ceux qu e j' aim e et qui m' aim ent, je d édi e
vii
viii
Table des matières
Introduction générale 1
ix
Table des matières
x
Table des matières
xi
Table des matières
xii
Liste des figures
4.1 Situations possibles de projection de deux fronts non dominés obtenus par
des métaheuristiques différentes. . . . . . . . . . . . . . . . . . . . . . . . . . 139
4.2 Représentation des meilleurs fronts obtenus par les deux approches avec
considération simultanée des règles de dominance Pareto et Lorenz (L’ins-
tance numero 17 de la configuration n=20). . . . . . . . . . . . . . . . . . . . 144
xiii
Liste des figures
xiv
Liste des tableaux
2.1 Valeurs des bornes inférieures et supérieures des paramètres utilisées lors
de la procédure de génération des instances . . . . . . . . . . . . . . . . . . . 61
2.2 Valeurs des paramètres de configuration utilisées dans les approches d’op-
timisation proposées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
2.3 Évolution des performances des approches proposées en fonction du
nombre de tâches n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
2.4 Évolution des performances des approches proposées pour différentes va-
leurs de la graine aléatoire η . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
2.5 Influence de la taille de la population p Si ze sur les performances de l’algo-
rithme génétique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
2.6 Évolution des performances des approches proposées avec la réduction du
taux d’actualisation flou r˜ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
2.7 Performances des approches proposées utilisées séparément . . . . . . . . . 65
2.8 Performances des approches proposées après hybridation . . . . . . . . . . 65
xv
Liste des tableaux
4.1 Valeurs des différents paramètres nécessaires à la génération des instances 137
4.2 Valeurs des paramètres de configuration associées aux métaheuristiques
proposées. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
4.3 Variation des performances (la moyenne des cardinaux des fronts générés)
des approches proposées en fonction du nombre de tâches avec règle de
dominance de Pareto (Le f f = 0, TF = 0.5 et RDD = 0.5). . . . . . . . . . . . . . 141
4.4 Variation des performances (la moyenne des proportions des ordonnance-
ments dominés) des approches proposées en fonction du nombre de tâches
avec règle de dominance de Pareto (Le f f = 0, TF = 0.5 et RDD = 0.5). . . . . . 142
4.5 Variation des performances (la moyenne des distances modifiées normali-
sées) des approches proposées en fonction du nombre de tâches avec règle
de dominance de Pareto (Le f f = 0, TF = 0.5 et RDD = 0.5). . . . . . . . . . . . 142
4.6 Variation des performances des approches proposées en fonction de la
gamme et du facteur d’étroitesse avec règle de dominance de Pareto (Le f f =
0 et n = 20). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
4.7 Variation des performances des approches proposées en fonction du coef-
ficient d’apprentissage avec règle de dominance de Pareto (n = 10, TF = 0.5
et RDD = 0.5). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
4.8 Variation des performances (la moyenne des cardinaux des fronts générés)
des approches proposées en fonction du nombre de tâches avec considé-
ration simultanée des règles de dominance de Pareto et Lorenz (Le f f = 0,
TF = 0.5 et RDD = 0.5). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
4.9 Variation des performances (la moyenne des proportions des ordonnance-
ments dominés) des approches proposées en fonction du nombre de tâches
avec considération simultanée des règles de dominance de Pareto et Lorenz
(Le f f = 0, TF = 0.5 et RDD = 0.5). . . . . . . . . . . . . . . . . . . . . . . . . . . 146
4.10 Variation des performances (la moyenne des distances modifiées normali-
sées) des approches proposées en fonction du nombre de tâches avec consi-
dération simultanée des règles de dominance de Pareto et Lorenz (Le f f = 0,
TF = 0.5 et RDD = 0.5). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
xvi
Liste des algorithmes
xvii
Liste des algorithmes
xviii
Introduction générale
Aristoclès Platon
1
Introduction générale
2
Introduction générale
Introduction générale
De nos jours, les tendances actuelles dans le domaine industriel sont orientées vers
l’amélioration des performances des systèmes manufacturiers en termes d’adaptation ra-
pide vu les fluctuations du marché et les perturbations internes. Une telle vision est étroi-
tement sollicitée par la mondialisation exacerbant une concurrence acharnée désormais
internationale.
En effet, la production devient de plus en plus diversifiée et les entreprises cherchent
régulièrement à accroître leurs parts de marché ainsi que les marges de profit. Sous ces
conditions, la fonction ordonnancement est considérée incontestablement dans la hié-
rarchie décisionnelle de l’entreprise comme un pilier solide pour prendre les décisions
les plus appropriées tant pour les investisseurs et producteurs que pour les consomma-
teurs.
Les problèmes d’ordonnancement à une machine constituent une cible très appré-
ciée par la communauté des chercheurs malgré que cette structure connaisse peu de dé-
bauchées directes en pratique. Une telle focalisation sur ce type de problèmes peut être
argumentée par la possibilité d’utiliser les modèles résultants pour implémenter des ex-
tensions valables à d’autres classes particulières de problèmes d’ordonnancement. Par
ailleurs, la formalisation des problèmes d’ordonnancement à une machine est basée sur
deux paradigmes de modèles largement utilisés : les approches déterministes et les ap-
proches stochastiques. Dans le premier cas, les valeurs associées aux paramètres des
tâches sont des données précises permettant la simplification du cadre de description
du problème d’ordonnancement. Cependant, cette vision déterministe est trop restrictive
dans le sens où les valeurs de ces paramètres sont mal connues et même avec la consul-
tation de l’avis des experts, il est fort probable que les informations obtenues soient su-
jettes à de nombreuses altérations. Pour les modèles élaborés sur une base stochastique,
les paramètres des tâches sont exprimés par des distributions de probabilité. Ceci résulte
souvent en des formulations très difficiles à manipuler. En outre, l’hypothèse stochas-
tique peut être mise en doute car dans plusieurs situations les données statistiques sont
manquantes. Aussi, la recherche de formalismes plus fiables devient nécessaire et l’idée
la plus naturelle semble d’opter pour des outils mathématiques dédiés à la représentation
d’incertitude dans le contexte de la théorie d’ordonnancement.
Dans cette thèse, nous nous intéressons à la résolution de problèmes d’ordonnan-
cement à une machine avec la prise en compte des sources d’incertitude au niveau du
système de production. Sous telle condition, la modélisation et l’optimisation de l’exécu-
tion des tâches par les approches d’ordonnancement conventionnelles sont remises en
question. Notre objectif réside dans un premier temps de proposer des approches basées
sur la théorie des nombres flous pour une représentation fidèle des problèmes d’ordon-
nancement avec paramètres incertains et par la suite d’implémenter des méthodes d’op-
timisation efficaces. Cette intégration entre la modélisation et l’optimisation se révèle une
méthodologie intéressante pour remédier à la complexité des problèmes traités.
Contribution de la thèse
Les travaux de recherche présentés dans cette thèse portent particulièrement sur les
problèmes d’ordonnancement à une machine tenant compte des paramètres incertains.
Plusieurs approches de résolution sont implémentées notamment les métaheuristiques à
base de solution unique et à base de population de solutions. Nos contributions portent
sur plusieurs aspects à savoir la proposition de modèles d’ordonnancement, analyse de
3
Introduction générale
Organisation de la thèse
Notre travail de thèse est structuré en quatre chapitres. Le premier chapitre est réservé
à l’état de l’art des problèmes d’ordonnancement conventionnels et les trois chapitres
suivants sont destinés à la présentation de nos contributions.
Dans le premier chapitre, nous essayons de positionner notre travail de recherche
dans le cadre de l’ordonnancement des ateliers de production. Nous présentons d’abord
l’importance de la fonction ordonnancement au sein du système décisionnel de l’entre-
prise. Nous rappelons ensuite les différentes composantes élémentaires constituant un
problème d’ordonnancement. Nous dévoilons par la suite la classification des problèmes
d’ordonnancement ainsi que les outils graphiques de base nécessaires à la représentation
des solutions. Nous focalisons nos intérêts sur la criticité des contraintes lors du proces-
sus de modélisation. Nous donnons un aperçu global sur la théorie de complexité pour
4
Introduction générale
bien cerner les classes des problèmes d’ordonnancement dépendamment du coût de ré-
solution. Finalement, nous clarifions les principes sur lesquels sont fondées les grandes
catégories des approches d’optimisation.
Nous nous intéressons dans le deuxième chapitre à la nécessité de la mise en oeuvre
de critères adéquats dans le contexte de la théorie de possibilité pour l’évaluation de l’op-
timalité d’une séquence fixe dans l’ordonnancement à une machine avec des paramètres
incertains et coûts actualisés. Aussi, nous dressons une présentation de la terminologie de
la théorie de possibilité. Nous généralisons par la suite le problème conventionnel d’or-
donnancement à une machine avec coûts actualisés au cas flou où plusieurs propriétés
sont proposées et prouvées. Nous introduisons deux méthodes approchées : algorithme
génétique et recherche par motifs, pour la résolution de la version floue du problème
traité. Nous clôturons ce chapitre en exposant les résultats des simulations numériques
où la robustesse des deux méthodes est validée statistiquement.
Dans le troisième chapitre, nous considérons le problème d’ordonnancement à une
machine avec des paramètres incertains et effet d’apprentissage à base de position. L’ob-
jectif est de minimiser la somme pondérée des temps d’achèvement des tâches. Par la
suite et en raison des données mal connues dans le modèle, nous proposons deux pro-
cédures de résolution pour le problème d’ordonnancement flou résultant. La première
procédure est basée sur l’extension
¡ de la règle
¢ de Smith, ce qui donne un algorithme po-
lynômial avec une complexité O n × log (n) . Cependant, la contrainte d’agréabilité floue
doit être satisfaite dans ce cas. La deuxième procédure basée sur des méthodes d’opti-
misation repose sur l’hypothèse d’existence des dates de disponibilité floues différentes,
en plus de l’élimination de la contrainte d’agréabilité floue. Nous implémentons et ap-
pliquons trois métaheuristiques à base de trajectoire notamment le recuit simulé, la re-
cherche tabou et la recherche kangourou pour résoudre le problème considéré. Pour les
méthodes proposées tout au long du chapitre, plusieurs expérimentations numériques
conjointement avec des déductions statistiques sont illustrées.
Dans le dernier chapitre, nous abordons un problème d’ordonnancement bi-objectif
à une machine dans lequel la ressource subit l’effet d’apprentissage à base de position.
Nous supposons que les durées opératoires et les dates d’échéance sont représentées
par des nombres flous plats (intervalles flous) d’allure parabolique. Nous développons
des formules compactes pour exprimer les fonctions objectifs élaborées à la base des
concepts de classement et de possibilité, où notre objectif est de minimiser la magni-
tude de la somme pondérée des temps d’exécution, simultanémen avec la somme pon-
dérée des possibilités de retard. Nous montrons ensuite que ce problème est NP-difficile
au sens fort. Par conséquent, nous proposons un algorithme génétique de tri non do-
miné (NSGA II) et la recherche coucou (CS) comme outils de résolution. Nous intégrons
dans ces métaheuristiques deux types de critères de dominance à savoir la règle de do-
mination de Pareto et la règle de domination de Lorenz. Nous examinons les mesures de
performance statistiques pour affirmer que l’approche d’optimisation coucou proposée
est plus efficace et très compétitive en termes d’identification du front et diversité des
solutions. Enfin, nous terminons cette thèse par une conclusion générale concernant les
modèles proposés, les résultats de complexité associés et les performances des approches
de résolutions implémentées suivies de quelques perspectives pour tracer nos directions
futures de recherche.
5
Introduction générale
6
Chapitre 1
Sanford I. Weill
Sommaire
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2 Contexte de l’ordonnancement . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3 Description du problème d’ordonnancement . . . . . . . . . . . . . . . . 13
1.3.1 Définition du terme ordonnancement . . . . . . . . . . . . . . . . . 13
1.3.2 Concepts et notations de base en ordonnancement . . . . . . . . . . 13
1.3.3 Objectifs d’optimisation dans l’ordonnancement . . . . . . . . . . . 14
1.4 Classification des problèmes d’ordonnancement . . . . . . . . . . . . . . 16
1.5 Outils de modélisation pour l’ordonnancement . . . . . . . . . . . . . . . 17
1.5.1 Diagramme de Gantt . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.5.2 Approche géométrique . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.5.3 Graphe disjonctif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.5.4 Réseau de Petri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.6 Importance des contraintes dans les problèmes d’ordonnancement . . . 22
1.7 Complexité des problèmes d’ordonnancement à une machine . . . . . . 24
1.7.1 Complexité du problème d’ordonnancement standard . . . . . . . . 26
1.7.2 Complexité du problème d’ordonnancement à une machine avec
considération de contraintes . . . . . . . . . . . . . . . . . . . . . . . 26
1.8 Approches de résolution des problèmes d’ordonnancement . . . . . . . 29
1.8.1 Méthodes polynômiales éfficaces . . . . . . . . . . . . . . . . . . . . 29
1.8.2 Méthodes énumératives éxactes . . . . . . . . . . . . . . . . . . . . . 30
1.8.3 Techniques approchées . . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
1.10 Références . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
7
Chapitre 1. Problèmes d’ordonnancement dans les systèmes de production
8
Chapitre 1. Problèmes d’ordonnancement dans les systèmes de production
1.1 Introduction
Avec l’évolution accrue de l’environnement caractérisé par des marchés affectés for-
tement par la concurrence et la sévérité des attentes de la clientèle, la nécessité de refor-
muler les outils d’aide à la décision pour les gestionnaires devient de plus en plus une exi-
gence urgente afin de remédier aux limites des disciplines traditionnelles [M ARTINSONS
et D AVISON, 2007]. L’ordonnancement occupant une position focale dans le système de
gestion informatisée des flux de production constitue la liaison vitale entre deux niveaux
de la décision hiérarchique au sein de l’entreprise : le niveau tactique et le niveau opé-
rationnel. En effet, la fonction ordonnancement assure le pilotage de l’ensemble des res-
sources disponibles avec la résolution des conflits causés par la réalisation des gammes
de produits sur l’horizon de temps estimé. La fonction ordonnancement est délimitée au
sein d’une structure hiérarchisée par les fonctions planification en amont et lancement
en aval. L’estimation des besoins en composants ainsi que la détermination des plans
d’approvisionnement et de charge sont assurées par la fonction planification. La fonction
lancement est responsable de la validation des ordres de fabrication à travers le regrou-
pement et le dimensionnement de ces ordres en lots de production. Un mécanisme de
contrôle vertical est adopté pour garantir la consistance des décisions entre différents ni-
veaux. Par exemple, la non faisabilité du plan de production au niveau ordonnancement
vis-à-vis les volumes demandés peut être justifiée comme due à une estimation erronée
des capacités des ressources dans les ateliers [E SQUIROL et L OPEZ, 1999].
En comparaison avec les systèmes de production basés sur un paradigme de produc-
tion mono produit ou bien gérée par la méthode kanban pour lesquels les flux de produit
s’écoulent naturellement et doivent en principe s’autoréguler, la vision d’ordonnance-
ment joue un rôle crucial dans tous les ateliers traitants des produits divers en flux poussé
[K AABI -H ARRATH, 2004]. Ceci peut être interprété par le fait que les gestionnaires dans de
tels ateliers sont obligés de manipuler des informations relatives à différentes gammes
de production simultanément avec l’objectif de maximiser le profit. De plus, comme la
production dans un marché très compétitif est gouvernée par les ordres de fabrication
issus de la fonction planification, la contrainte temps doit être impérativement considé-
rée dans le contexte de la décision. Cependant, il est à noter que l’importance du concept
d’ordonnancement n’est pas limitée uniquement à l’aspect industriel car un nombre im-
pressionnant de problèmes d’ordonnancement existe dans d’autres domaines parmi les-
quels nous pouvons citer :
• Le domaine informatique : le noyau d’un système d’exploitation contient la compo-
sante ordonnanceur pour l’utilisation maximale des capacités de l’environnement
telles que des processeurs en parallèle ou bien le respect des contraintes temps réel
dans les systèmes embarqués ;
• Le domaine hospitalier : l’ordonnancement des salles opératoires vise à la réa-
lisation d’interventions sous des conditions de travail adéquates pour les res-
sources humaines (infirmiers, anesthésistes, chirurgiens...) et techniques (instru-
ments médicaux-chirurgicaux, salles d’opération et de réveil...) ;
• Le domaine de transport : l’ordonnancement permet d’avoir les itinéraires d’une
flotte de véhicules de transport pour satisfaire l’ensemble de requêtes des clients
(problème de tournées de véhicule) ;
• Le domaine de l’éducation : avec la croissance rapide du nombre d’étudiants d’une
année à l’autre, il est nécessaire d’exploiter d’une façon optimale les ressources pé-
dagogiques. Des contraintes particulières sont souvent présentes dans ce cadre par
exemple les préférences des enseignants.
9
Chapitre 1. Problèmes d’ordonnancement dans les systèmes de production
Dans tous ces cas, la réalisation d’un travail exprimé par une série de tâches interdépen-
dantes nécessite un mécanisme de coordination pour implémenter ces tâches (allocation
des ressources adéquates).
Ce premier chapitre est réservé à la présentation des concepts de base concernant les
problèmes d’ordonnancement. Dans ce contexte, nous faisons notre mieux pour aborder
les différents aspects du thème d’une façon formelle sans lier ces notions à un domaine
bien particulier. Ce chapitre est divisé en neuf sections. La Section 1.2 est destinée à la
présentation du contexte de l’ordonnancement au sein de l’entreprise. La Section 1.3
décrit le problème d’ordonnancement notamment la définition, les notations et les ob-
jectifs d’optimisation. Les différentes typologies des problèmes d’ordonnancement ainsi
que les outils de modélisation associés sont illustrés dans les Sections 1.4 et 1.5. L’impor-
tance des contraintes dans la modélisation des problèmes d’ordonnancement est accen-
tuée dans la Section 1.6. La complexité des problèmes d’ordonnancement à une machine
est traitée sous formulation standard et avec considération de quelques contraintes dans
la Section 1.7. Les grandes familles des approches de résolution des problèmes d’ordon-
nancement sont exposées d’une façon succincte dans la Section 1.8. Quelques remarques
et conclusions sont délivrées dans la Section 1.9.
10
Chapitre 1. Problèmes d’ordonnancement dans les systèmes de production
Le type d’informations requis pour la prise de décision dans une organisation dé-
pend directement du niveau décisionnel et de la structuration des situations de déci-
sion confrontées. Il est essentiel de comprendre que le contexte classique de gestion sous
forme pyramidale reste valable pour les organisations d’aujourdui. Le processus de déci-
sion est toujours structuré à la base de niveaux hiérarchique mais avec modification de
quelques attributs comme la forme et les participants qui continuent de changer avec
l’évolution des structures organisationnelles. L’interdépendance entre les trois niveaux
décisionnels et les types d’informations est illustrée sur la Figure 1.1 ( [O’B RIEN et M A -
RAKAS , 2011]).
11
Chapitre 1. Problèmes d’ordonnancement dans les systèmes de production
12
Chapitre 1. Problèmes d’ordonnancement dans les systèmes de production
souvent achevé interactivement via un système d’aide à la décision installé sur un ordina-
teur personnel ou station de travail connectée au système de planification des ressources
de l’entreprise. Les terminaux distribués à des points fixes donnent aux départements de
l’entreprise un accès sécurisé en temps réel à toutes les informations d’ordonnancement.
D’autre part, ces départements alimentent le système d’ordonnancement avec les infor-
mations récentes relatives aux états des tâches et des machines.
En partant de ces trois définitions, les propriétés élémentaires d’un problème d’ordon-
nancement découlent directement. Un problème d’ordonnancement fait évoquer géné-
ralement les points suivants :
• Existence d’un nombre fini de tâches ;
• Partage de ressources limitées entre ces tâches ;
• Détermination de la date de début d’exécution pour chaque tâche ;
• Respect des contraintes imposées sur les tâches et les ressources.
Les concepts et les notations de base sont présentés avec plus de détails dans les sous
sections suivantes.
13
Chapitre 1. Problèmes d’ordonnancement dans les systèmes de production
14
Chapitre 1. Problèmes d’ordonnancement dans les systèmes de production
TABLEAU 1.2 Présentation des critères élémentaires utilisés dans le domaine d’ordonnan-
cement
TABLEAU 1.3 Classification des critères de performances utilisés dans le domaine d’or-
donnancement
Une propriété très utile dans l’obtention de l’optimum d’un problème d’ordonnance-
ment est attachée à la notion de régularité du critère d’optimalité introduite par Conway
et ses collègues [C ONWAY et collab., 1967]. La définition suivante donne une interpréta-
tion rigoureuse de cette notion.
opt
Définition 1.4. Soient C = [C1 , C2 , ..., Cn ] le vecteur des dates de fin des tâches et FC : C → R
un critère d’optimalité.
h Le critèreiest dit régulier si et ³ seulement
´ si pour tout autre vecteur
0 0 0 0 opt 0 opt
des dates de fin C = C1 , C2 , ..., Cn , nous avons FC C ≥ FC (C) est vérifié si et seulement
0
si ∃k ∈ {1, 2, ..., n} tel que Ck ≥ Ck .
D’une façon équivalente, un critère est régulier si et seulement s’il est une fonction non-
décroissente des dates de fin d’exécution des tâches.
15
Chapitre 1. Problèmes d’ordonnancement dans les systèmes de production
Théorème 1.1. Dans le problème standard d’ordonnancement à une machine avec critère
d’optimalité régulier, les ordonnancements sans temps d’oisiveté constituent un ensemble
dominant.
Démonstration.
Soit A l’ensemble des ordonnancements sans temps d’oisiveté. Supposons que l’or-
donnancement optimal n’appartient pas à cet ensemble, donc il contient au moins un
temps d’oisiveté. Par hypothèse, le critère d’optimalité est régulier d’où la possibilité
de réduire sa valeur pour le cas de l’ordonnancement optimal en éliminant les temps
d’oisiveté par décalage des tâches localisées en aval. Mais ceci contredit l’optimalité de la
solution d’où la solution optimale appartient forcement à l’ensemble A. Ce qui signifie
que l’ensemble des ordonnancements sans temps d’oisiveté constitue un ensemble
dominant lorsque le critère d’optimalité est régulier.
©φ, p i++=ªp, p − ≤ p i ≤ p +
© ª
Durées opératoires (β5 )
Dates de fin impérative (β6 ) ©φ, d i
φ, n i ≤ n max
ª
Nombre maximum d’opérations
par tâche (β7 )
φ, no − w ai t
© ª
Propriété d’attente (β8 )
Objectif (γ) / Un des critères d’optimalité
du Tableau 1.2
Les valeurs prises par le sous champ α1 sont décrites dans le Tableau 1.5. Pour le champ
β, uniquement les valeurs de la propriété de précédence (sous champ β3 ) sont interpré-
tées dans le Tableau 1.6 comme les valeurs affectées aux autres sous champs signifient la
presence ou l’absence de la propriété considérée.
Bien que les valeurs affectées aux champs permettent de modéliser un très grand
nombre de problèmes d’ordonnancement, multitudes extensions ont été proposées en
16
Chapitre 1. Problèmes d’ordonnancement dans les systèmes de production
Valeur Description
φ ou 1 Environement à une seule machine
P Environement à machines identiques parallèles
Q Environement à machines parallèles uniformes
R Environement à machines parallèles quelconques
O Système open shop
F Système Flow shop
J Système Job shop
FH Système flow shop hybride
Valeur Description
φ Tâches indépendentes
pr ec Tâches avec contraintes de précédence générales
uan Tâches formant un réseau d’activités uniconnexe
t r ee Tâches formant un arbre
chai ns Tâches formant union de chaînes
17
Chapitre 1. Problèmes d’ordonnancement dans les systèmes de production
• Le diagramme à base de produit où une ligne est affectée à chaque tâche pour per-
mettre de déterminer le chaînage de ses opérations et le temps d’attente entre deux
opérations consécutives.
Il est possible également de considérer des diagrammes de Gantt dans un espace à trois
dimensions avec les axes orthogonaux représentant les machines, les tâches et le temps.
Ce genre de diagrammes est devenu ces dernières années plus pratique en particulier
avec l’évolution d’outils dédiés de traitement graphique de données. Dans la figure 1.2,
l’exécution de tâches sur trois machines est visualisée ( [J ONES, 1988]).
F IGURE 1.2 Visualisation d’un ordonnancement sur trois machines utilisant un dia-
gramme de Gantt à trois dimensions.
L’utilisation des diagrammes de Gantt est généralement basée sur l’analyse des re-
lations de précédence entre tâches dans un ordonnancement et la réorganisation des
opérations pour comparer les performances de différentes configurations. Dans un en-
vironnement distribué, plusieurs usines d’attributs différents peuvent être sélectionnées
pour le traitement des tâches d’où des plans de production multiples. La génération d’une
séquence adéquate nécessite une intégration efficace du diagramme de Gantt dans le
contexte d’une méthode d’optimisation telle que les algorithmes génétiques [J IA et col-
lab., 2007].
18
Chapitre 1. Problèmes d’ordonnancement dans les systèmes de production
F IGURE 1.3 Exemple générique illustrant les éléments de base de l’approche géométrique.
19
Chapitre 1. Problèmes d’ordonnancement dans les systèmes de production
• Les noeuds : Ces noeuds représentent soit des débuts des opérations, ou bien des
opérations fictives correspondantes à la fin de chaque travail, ou bien les dates du
début et de la fin de l’ordonnancement ;
• Les arcs : Nous distinguons deux types d’arcs. Les arcs conjonctifs sont associés aux
contraintes de précédence entre deux opérations consécutives et valués par la du-
rée opératoire de la première opération. Les arcs disjonctifs exprimant les conflits
d’utilisation de ressources où deux opérations ne peuvent pas s’exécuter en même
temps si elles sont reliées par un tel arc.
On dit que l’ordonnancement est parfaitement défini si toutes les disjonctions sont ar-
bitrées sans génération de circuits dans le graphe [P ENZ, 1994]. Le développement d’ap-
proches d’optimisation (par exemple recherche locale ou recuit simulé) à base de graphe
disjonctif peut conduire à des procédures plus performantes en termes de qualité de so-
lutions et de temps de calcul en particulier en tenant compte des contraintes complexes
20
Chapitre 1. Problèmes d’ordonnancement dans les systèmes de production
et/ou objectifs multiples comme c’est le cas de l’industrie des composants à base de se-
miconducteur [Y UGMA et collab., 2012].
21
Chapitre 1. Problèmes d’ordonnancement dans les systèmes de production
F IGURE 1.5 Modélisation par réseau de Petri de l’exécution de deux travaux sur un atelier
à deux machines.
22
Chapitre 1. Problèmes d’ordonnancement dans les systèmes de production
23
Chapitre 1. Problèmes d’ordonnancement dans les systèmes de production
Définition 1.5. Une machine de Turing est un modèle abstrait simulant l’exécution d’une
procédure sur une machine de calcul. Elle se compose de deux éléments de base :
• Unité de commande : responsable de la mise à jour et les transitions entre les états
possibles supposés finis ;
• Unité de mémoire : exprimée par un ruban de stockage constitué de nombre infini de
cases consécutives.
La communication entre ces deux éléments se fait par une tête de lecture/écriture qui balaye
les symboles sur le ruban, et a la possibilité de se déplacer aux deux sens du ruban.
Une machine de Turing est appelée déterministe si à chaque état est associée au plus
une seule transition (le prochain état est unique). Si plusieurs transitions sont permises
pour certains états, on dit que la machine de Turing est non déterministe (existence de
plusieurs états prochains candidats).
La machine de Turing universelle représente un outil plus avancé car elle est capable
de simuler le comportement de n’importe quelle autre machine de Turing. Il en résulte
que la machine de Turing universelle est dotée de la capacité de calculer des expressions
complexes (fonction récursive, langage récursif, langage partiellement décidable).
La thèse de Church-Turing affirme l’existence d’une équivalence entre les problèmes
résolubles par une machine de Turing universelle et les problèmes résolubles par un algo-
rithme ou par une méthode concrète de calcul. Un problème de décision est un prédicat
logique admettant deux solutions (Oui ou Non). La structure standard d’un problème de
décision contient deux parties élémentaires : l’instance générique du problème en termes
des différentes composantes et la question posée sur cette instance. La déduction du for-
mat décisionnel associé à un problème de minimisation peut être achevée en considérant
une borne supérieure dans la partie question afin d’examiner l’existence d’une instance
24
Chapitre 1. Problèmes d’ordonnancement dans les systèmes de production
ayant un coût qui ne dépasse pas cette borne. En se basant sur le concept de la machine
de Turing avec considération de contrainte de temps, les deux classes suivantes (P et NP)
sont les plus usuelles [G OLDREICH, 2008].
Définition 1.6. La classe P est l’ensemble des langages reconnus par une machine de Turing
deterministe en temps polynômial.
Les problèmes appartenant à cette classe sont souvent considérés comme des problèmes
faciles pour lesquels il est possible de développer un algorithme efficace de résolution
optimale.
Définition 1.7. La classe NP est l’ensemble des langages reconnus par une machine non
déterministe en temps polynômial.
Les problèmes appartenant à cette classe peuvent être également reconnus par une ma-
chine de Turing deterministe mais avec un temps d’ordre exponentiel.
Dans la théorie de la complexité, nous nous intéressons à la reconnaissance des pro-
blèmes les plus durs de la classe NP. Deux notions sont d’une importance cruciale dans
la théorie de la complexité notamment celle de la NP-Complétude et celle de La NP-
difficulté [A RORA et B ARAK, 2009].
Définition 1.8. Un problème de décision X est dit NP-Complet s’il appartient à la classe NP
et il est possible de réduire tout autre problème Y de la classe NP à X en temps polynômial.
Définition 1.9. Un problème X est dit NP-difficile s’il est au moins aussi difficile que tous
les problèmes appartenant à la classe NP.
Il en découle de cette définition qu’un problème NP-difficile n’est pas forcément un élé-
ment de la classe NP ni même un problème de décision.
Pour permettre une classification assez précise des problèmes d’ordonnancement, la
réduction polynômiale est utilisée pour prouver d’une façon formelle qu’un problème
est plus difficile à résoudre qu’un autre. Ceci permet l’élaboration d’une hiérarchie par-
tielle d’où la possibilité de réutilisation des approches de résolutions développées pour
un problème après quelques modifications mineures pour d’autres problèmes. La Figure
1.6 présente un arbre de réduction des critères d’optimisation en ordonnancement.
Ce graphe de réduction s’interprète de la manière suivante : Pour un environnement
d’atelier donné et pour des contraintes et un critère donnés, si un problème est NP-
difficile, tous ses successeurs dans l’arbre le sont également. Afin d’alléger la mission
de classification des problèmes combinatoires selon leur complexité, un logiciel nommé
MSPCLASS a été développé avec une bibliothèque de 4536 problèmes parmi lesquels une
classe de 120 problèmes d’ordonnancement à une machine [L AGEWEG et collab., 1982].
L’utilisateur fournit une liste de problèmes de complexité connue (P ou NP) et en se ba-
sant sur les relations d’ordre partiel dans la classe considérée, le logiciel génère automati-
quement la nature de chaque problème (facile, ouvert ou difficile). L’ensemble des ordres
partiels entre les classes des problemes d’ordonnancement dans un graphe de réduction
permet de bien cerner les critères d’optimalités pouvant être simultanément employés
dans le cadre d’une optimisation multi-objectif.
25
Chapitre 1. Problèmes d’ordonnancement dans les systèmes de production
F IGURE 1.6 Présentation de quelques réductions élémentaires entre les critères de perfor-
mance d’ordonnancement.
26
Chapitre 1. Problèmes d’ordonnancement dans les systèmes de production
27
Chapitre 1. Problèmes d’ordonnancement dans les systèmes de production
Le processus de réglage comprend les travaux liés à une multitude d’opérations telles
que l’obtention des outils, le positionnement des pièces, le nettoyage, l’inspection et la
configuration des machines ...etc. Le temps/coût associé à une opération de réglage a été
considéré pour longtemps comme négligeable ou faisant partie de la durée opératoire.
Bien que ceci est justifié pour certains problèmes d’ordonnancement, de nombreuses
autres situations nécessitent un traitement séparé pour les temps (coûts) de réglage [A L -
LAHVERDI et collab., 1999]. Dans ce cas, nous distinguons entre le réglage dépendant uni-
quement de la tâche en cours et le réglage dépendant de la tâche en cours ainsi que la
tâche précédente. Le temps de réglage pour le premier cas est dit indépendant de la sé-
quence (s si ), cependant le temps dans le deuxième cas est dit dépendant de la séquence
(s sd ) avec la possibilité de dépendance à plusieurs tâches précédentes (s psd ).
L’importance et les avantages de prise en compte des temps/coûts de réglage dans les
axes de recherches d’ordonnancement ont été abordés par plusieurs chercheurs depuis
les années 1960s où une moyenne de 40 articles publiés par an est ajoutée à la littérature.
Le Tableau 1.10 résume la complexité de quelques problèmes d’ordonnancement avec
considération du temps de réglage et le lecteur intéressé pour une description plus de-
taillée peut consulter les références [A LLAHVERDI et collab., 2008] et [A LLAHVERDI, 2015].
28
Chapitre 1. Problèmes d’ordonnancement dans les systèmes de production
29
Chapitre 1. Problèmes d’ordonnancement dans les systèmes de production
iP
=n
résoudre à l’optimalité quelques problèmes d’ordonnancement à une machine (1 || Ci
i =1
iP
=n
et 1 || (ωi × Ci )) [S MITH, 1956]. La règle de Moore est une autre méthode polynômiale
i =1
efficace permettant de minimiser le nombre de tâches en retard pour le problème d’or-
iP
=n
donnancement à une machine (1 || Ui ) [M OORE, 1968]. Mais il est à mentionner qu’un
i =1
tel formalisme n’est disponible que pour un nombre très réduit de problèmes d’ordon-
nancement (machine unique, flow shop et job shop) et de critères de performance.
La procédure par séparation et évaluation (en anglais Branch and Bound) est considé-
rée parmi les méthodes exactes les plus reconnues dans la résolution optimale des pro-
blèmes combinatoires. Cette méthode repose comme son nom l’indique sur deux notions
clés : la séparation et l’évaluation. Lors de l’exécution de la procédure, une arborescence
avec la racine correspond à l’espace de solutions du problème initial est créée d’une façon
incrémentale [L AWLER et W OOD, 1966]. Ceci est achevé à travers la dissociation d’un som-
met exprimant une sous classe en une partition de sous-sous classe. Cette opération de
division est combinée avec la comparaison du sommet traité avant l’exploration à un ma-
jorant dans le cas des problèmes de minimisation. La stratégie de calcul de ces bornes doit
être le plus simple possible pour ne pas introduire des coûts supplémentaires au temps
global de calcul. Si la valeur de la fonction objectif correspondante au sommet dépasse la
borne alors l’arbre est élagué. Sinon, un autre tour de la décomposition du sommet est re-
lancé. Il est à noter que les bornes sont améliorées chaque fois qu’une nouvelle meilleure
solution est trouvée [M ORRISON et collab., 2016].
30
Chapitre 1. Problèmes d’ordonnancement dans les systèmes de production
31
Chapitre 1. Problèmes d’ordonnancement dans les systèmes de production
un compromis entre ces deux principes doit être établi dans la sélection des meilleures
solutions afin d’améliorer le taux de convergence et assurer l’obtention d’un optimum
global.
Les approches métaheuristiques sont généralement inspirées de la nature et utilisent
une solution unique ou une population de solution pour l’exploration de l’espace de
recherche. Les méthodes utilisant une solution unique englobent les techniques de re-
cherche locale comme la recherche tabou et le recuit simulé. Les méthodes à base d’une
population explorent l’espace à travers l’évolution d’un ensemble de solutions telles que
les algorithmes génétiques [S HELOKAR et collab., 2014]. De plus, ces approches peuvent
être caractérisées par l’inclusion d’une mémoire pour le stockage et l’échange d’informa-
tions entre les individus de la même population ou bien entre plusieurs populations dans
le contexte d’une métaheuristique parallèle.
1.9 Conclusion
Tout au long de ce chapitre, nous avons présenté les concepts de base nécessaires à
mieux cerner les problèmes d’ordonnancement en particulier dans les ateliers de pro-
duction. En premier, nous avons mis en évidence la criticité de la fonction ordonnan-
cement au sein de l’hiérarchie de l’entreprise. Puis, nous nous somme intéressés par
les caractéristiques générales des problèmes d’ordonnancement comprenant les forma-
lismes mathématiques adoptés pour la description et la classification des problèmes
d’ordonnancement sans oublier quelques outils de modélisation graphique largement
utilisés pour la représentation des solutions ou bien la résolution proprement dite du
problème considéré. Nous avons ensuite donné un bref aperçu sur l’importance des
contraintes dans le contexte d’ordonnancement, ceci ne permet pas uniquement d’ap-
préhender les contraintes technologiques liées au processus de fabrication mais égale-
ment les contraintes imposées par des sources de perturbations externes à l’entreprise.
Dans un second temps, nous avons élaboré un survol de la complexité des pro-
blèmes d’ordonnancement à une machine les plus abondants dans la littérature ainsi
que quelques problèmes considérant l’effet d’apprentissage et/ou les temps de réglage.
L’étude de la complexité constitue le fil conducteur vers le choix de la méthodologie de
resolution adéquate et pour cela nous avons exposé une taxinomie des approches de re-
solution (exactes et approchées) en dernière partie de ce chapitre. En se basant sur la litté-
rature abordée, nous pouvons observer que la majorité des modèles les plus couramment
utilisés pour formaliser un problème d’ordonnancement sont de nature déterministe. Dès
lors des données incertaines sont présentes comme propriété intrinsèque de l’environne-
ment, ces modèles déterministes deviennent rigides et incapables de supporter tel aspect
d’imprécision. Par conséquent, nous nous intéressons dans les trois chapitres suivants
aux implications de la prise en compte des paramètres incertains dans quelques pro-
blèmes d’ordonnancement. Nous justifions aussi l’adaptation de plusieurs outils de mo-
délisation et d’optimisation pour des problèmes incluant des contraintes d’incertitude au
niveau des paramètres d’ordonnancement.
1.10 Références
VAN DER A ALST, W. M. P. 1996, «Petri net based scheduling», OR Spektrum, vol. 18, no 4,
p. 219–229. 21
32
Chapitre 1. Problèmes d’ordonnancement dans les systèmes de production
A GGOUNE , R. et M.-C. P ORTMANN. 2006, «Flow shop scheduling problem with limited
machine availability : A heuristic approach», International Journal of Production Eco-
nomics, vol. 99, no 1-2, p. 4–15. 19
A NTHONY, R. N. 1965, Planning and control systems : a framework for analysis, Division
of Research, Graduate School of Business Administration, Harvard University. 10
B RUCKER , P. 1988, «An efficient algorithm for the job-shop problem with two jobs», Com-
puting, vol. 40, no 4, p. 353–359. 19
33
Chapitre 1. Problèmes d’ordonnancement dans les systèmes de production
C HENG , T. C. E. et G. WANG. 2000, «Single machine scheduling with learning effect consi-
derations», Annals of Operations Research, vol. 98, no 1, p. 273–290. 26
C LARK , W. 1923, The Gantt chart a working tool of management, Ronald Press. 17
34
Chapitre 1. Problèmes d’ordonnancement dans les systèmes de production
J ONES , C. V. 1988, «The three-dimensional gantt chart», Operations Research, vol. 36, no 6,
p. 891–903. 18
L EUNG , J. Y.-T. 2004, Introduction and Notation, chap. 1, in J. Y-T. Leung. (eds.), Hand-
book of scheduling algorithms, models, and performance analysis, CRC. 13
M ATI , Y., N. R EZG et X. X IE. 2001, «A taboo search appraoch for deadlock-free scheduling
of automated manufacturing systems», Journal of Intelligent Manufacturing, vol. 12,
no 5, p. 535–552. 19
35
Chapitre 1. Problèmes d’ordonnancement dans les systèmes de production
M OORE , L. J. 1968, «An n-job, one-machine sequence algorithm for minimizing the num-
ber of late jobs», Management Science, vol. 15, no 1, p. 102–109. 30
M URATA , T. 1989, «Petri nets : properties, analysis and applications», Proceedings of the
IEEE, vol. 77, no 4, p. 541–580. 21
R OTHLAUF, F. 2011, Design of modern heuristics principles and application, Springer Press.
31
S MITH , W. E. 1956, «Various optimizers for single stage production», Naval Research Lo-
gistics Quarterly, vol. 3, no 1-2, p. 59–66. 30
36
Chapitre 1. Problèmes d’ordonnancement dans les systèmes de production
Z HOU , K.-Q. et A. M. Z AIN. 2016, «Fuzzy petri nets and industrial applications : a review»,
Artificial Intelligence Review, vol. 45, no 4, p. 405–446. 21
37
Chapitre 1. Problèmes d’ordonnancement dans les systèmes de production
38
Chapitre 2
Proverbe polonais
Sommaire
2.1 Introduction et état de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.2 Terminologie de base sur la théorie de possibilité . . . . . . . . . . . . . . 44
2.3 Formulation du problème d’ordonnancement . . . . . . . . . . . . . . . . 47
2.3.1 Optimalité ordinaire dans le problème d’ordonnancement à une
machine avec coûts actualisés . . . . . . . . . . . . . . . . . . . . . . 47
2.3.2 Mesures possibilistes d’optimalité pour le problème d’ordonnan-
cement à une machine avec coûts actualisés et paramètres incertains 49
2.4 Conception du cadre d’expérimentations numériques . . . . . . . . . . . 55
2.4.1 Support des contraintes non linéaires . . . . . . . . . . . . . . . . . 55
2.4.2 Approche basée sur l’algorithme génétique . . . . . . . . . . . . . . 56
2.4.3 Approche basée sur la recherche par motifs . . . . . . . . . . . . . . 58
2.4.4 Génération des instances . . . . . . . . . . . . . . . . . . . . . . . . . 59
2.5 Simulation et résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
2.5.1 Effet du nombre de tâches . . . . . . . . . . . . . . . . . . . . . . . . . 62
2.5.2 Effet de la graine aléatoire η . . . . . . . . . . . . . . . . . . . . . . . . 62
2.5.3 Effet de la taille de la population de l’algorithme génétique . . . . . 63
2.5.4 Effet de la réduction du taux d’actualisation flou r˜ . . . . . . . . . . 64
2.5.5 Effet de l’hybridation des approches algorithme génétique et re-
cherche par motifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
2.7 Références . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
39
Chapitre 2. Problèmes d’ordonnancement à une machine avec coûts
actualisés et paramètres incertains
40
Chapitre 2. Problèmes d’ordonnancement à une machine avec coûts
actualisés et paramètres incertains
41
Chapitre 2. Problèmes d’ordonnancement à une machine avec coûts
actualisés et paramètres incertains
système. Par exemple, dans la production des transistors à couches minces pour affichage
à cristaux liquides, il est difficile d’identifier l’état courant des ressources ou attributs d’un
produit car cet état est dépendant du temps [L IU et Y IH, 2013]. Dans la spécialité de pro-
duction de peinture, le temps de configuration entre les séquences des tâches est d’une
importance particulière dans l’obtention des spécificités d’une couleur. Les conditions de
l’environnement comme la température peuvent aussi générer des incertitudes ayant un
impact sur le processus de production en particulier la durée opératoire totale [S CHULT-
MANN et collab., 2006]. Dans les raffineries de pétrole situées au bord de la mer, le pro-
blème d’ordonnancement du pétrole brut contient plusieurs tâches telles que le vidange
du pétrole brut à partir de navires pétroliers aux citernes de stockages, transfert des ci-
ternes de stockages vers les citernes de chargements et finalement le passage aux unités
de distillation. Sous les contraintes des temps d’arrivée des navires pétroliers, capacités
limitées, climat et demande imprévue, l’objectif final devient une mission fortement per-
turbée [C AO et collab., 2009]. Dans d’autres situations où le processus de modélisation est
influencé par l’aspect flou des paramètres, le lecteur peut consulter ( [N IKULIN et D REXL,
2010], [O LARU et S MITH, 2005] et [P ETROVIC et collab., 2011]).
Dans la littérature, le travail de Prade est parmi les premiers papiers publiés dans
le cadre de l’utilisation des concepts flous pour un problème d’ordonnancement réel
[P RADE, 1979]. Par la suite, l’aspect flou est diffusé sur plusieurs niveaux de décision sti-
mulé par les contraintes sévères dans le monde réel. Han et ses collègues ont exploité le
problème d’ordonnancement à une machine avec des dates échues floues. Les auteurs
ont considéré une fonction d’appartenance linéaire ainsi que des hypothèses simplifica-
trices pour permettre la résolution du problème généralisé du maximum de retard en un
temps polynômial [H AN et collab., 1994]. Stanfield et ses collègues ont considéré un pro-
blème plus général où les temps de services et les dates échues sont des quantités vagues.
Un algorithme par séparation et évaluation a été appliqué au modèle flou et une com-
paraison avec des modèles probabilistes a été réalisée [S TANFIELD et collab., 1996]. Un
problème d’ordonnancement par lots à une machine avec des temps de configuration,
durées opératoires et dates échues floues a été étudié par Harakrishnan et Ishii [H ARI -
KRISHNAN et I SHII , 2005]. Une approche polynômiale a été établie, elle est basée sur des
formulations de programmation linéaire avec l’objectif de maximiser le degré minimal
de satisfaction. Duenas et Petrovic ont développé une approche d’optimisation multi-
objectif pour le problème d’ordonnancement à une machine avec des dates échues in-
certaines. La minimisation du maximum ainsi que la minimisation de la moyenne des
temps de retard des tâches sont définies comme des fonctions objectifs. Une approche
hybride basée sur les algorithmes génétiques et la recherche locale a été proposée et vali-
dée pour une société de fabrication de poterie [D UENAS et P ETROVIC, 2008]. Liao et Liao
ont utilisé des ensembles flous triangulaires et trapézoïdaux pour modéliser l’incertitude
des dates échues et durées opératoires des tâches. Ils ont démontré la possibilité d’obte-
nir une séquence optimale des tâches maximisant le ¡degré minimum de satisfaction en
2
¢
utilisant un algorithme polynômial de complexité O n × log (G) [L IAO et L IAO, 1998].
Wang et ses collègues ont appliqué la programmation par contraintes stochastiques pour
la construction du profil de vraisemblance de la fin d’une tâche, ce qui permet un clas-
sement adéquat des solutions obtenues. Ils ont présenté également les conditions né-
cessaires d’optimalité des solutions, ce qui permet de réduire la taille de l’espace de re-
cherche [WANG et collab., 2002]. Wu et ses collègues ont traité le problème d’ordonnance-
ment de groupe à une machine avec les hypothèses de l’existence des temps de configura-
tion entre les groupes et la nature floue des durées opératoires. Une méthodologie flexible
de classement basée sur la méthode des valeurs centrales a été adoptée pour résoudre ce
42
Chapitre 2. Problèmes d’ordonnancement à une machine avec coûts
actualisés et paramètres incertains
problème. Ces auteurs ont prouvé que les résultats obtenus restent valables pour d’autres
fonctions de deffuzification ayant une allure lineaire [W U et L EE, 2005]. Mahrabadi et
Pahlavani ont manipulé une extension du problème d’ordonnancement à une machine
avec la somme pondérée des temps de retard qui est un problème NP-difficile. Ils ont
supposé que les durées opératoires et les dates échues des tâches sont données par des
nombres flous triangulaires. Les auteurs ont proposé aussi trois métaheuristiques pour
conduire des expérimentations sur le problème [S AIDI M EHRABAD et PAHLAVANI, 2009].
Les concepts d’avance et de retard absolus flous ont été decrits en détail dans [W U, 2010],
ces critères sont basés sur les opérateurs de soustraction et maximum appliqués aux du-
rées opératoires et dates échues floues. La somme pondérée de l’avance et de retard abso-
lus flous a été minimimisée par un algorithme génétique où l’effet de l’allure des nombres
flous a été également discuté par les auteurs. Ahmadizar et Hosseini ont proposé un algo-
rithme polynômial pour le problème d’ordonnancement à une machine avec effet d’ap-
prentissage de position et durées opératoires floues. La procédure de minimisation du
temps total opératoire est basée sur l’application de la règle Délai de Fabrication le plus
Court (en anglais SPT rule) pour les durées opératoires floues triangulaires [A HMADIZAR
et H OSSEINI, 2011]. Les mêmes auteurs ont présenté deux algorithmes polynômiaux pour
la résolution du problème d’ordonnancement à une machine avec effet d’apprentissage
de position et durées opératoires floues où l’objectif est de minimiser la durée totale de
l’ordonnancement i.e. le makespan. La première approche est basée sur la programma-
tion par contraintes stochastiques floues tandis que la deuxième est basée sur une mé-
thode de classement de nombres flous [A HMADIZAR et H OSSEINI, 2013]. Il est à souligner
que l’aspect flou est souvent introduit dans les modèles d’ordonnancement sans justifier
l’optimalité des fonctions objectifs choisies lorsque les versions floues des règles d’ordon-
nancement classiques sont utilisées. Özelkan et ses collègues ont étudié l’optimalité dans
le cas flou de quelques règles d’ordonnancement telles que la règle Délai de livraison le
plus proche (en anglais EDD). Ils ont illustré que la procédure de démonstration basée sur
la permutation des tâches reste valable sous certaines conditions. Les auteurs ont conclu
que la fuzzification des règles classiques et l’utilisation d’une fonction de classement ar-
bitraire ne donnent pas toujours une règle optimale dans le contexte d’ordonnancement
flou [Ö ZELKAN et D UCKSTEIN, 1999]. En suivant le même chemin, Chung a proposé une
procédure sous l’acronyme "LARGE" pour trouver le plus grand ensemble de sous en-
sembles flous discrétisés. Cette procédure a été utilisée pour développer un algorithme
basé sur la règle Délai de livraison le plus proche dans le cas de durée opératoire, dates
de disponibilité et dates échues floues [C HUANG, 2004]. Malgré le nombre élevé des tra-
vaux consacrés aux modèles d’ordonnancement flous, seulement une partie limitée de
la littérature aborde la signification des coupes gamma (d’une façon equivalente alpha
dans plusieurs références) des paramètres flous dans le modèle d’ordonnancement en
particulier que l’information fournie par les différents niveaux des coupes peut être dif-
férente. Ainsi il sera intéressant d’exploiter au maximum les données introduites comme
paramètres flous dans le modèle d’ordonnancement. Chanas et Kasperski ont introduit la
notion de fonction floue monotone pour généraliser l’algorithme de Lawler. Les auteurs
ont appliqué cette extension pour la maximisation du degré de possibilité que le maxi-
mum de la somme pondérée des retards algébriques ne dépasse pas la valeur seuil d’un
certain objectif flou [C HANAS et K ASPERSKI, 2001]. Par la suite, les mêmes auteurs ont
élaboré les concepts d’optimalité possible et d’optimalité nécessaire des solutions et ont
présenté un calcul détaillé des paramètres dans le problème d’ordonnancement à une
machine avec la somme pondérée des ¡ temps d’exécution
¢ et durées opératoires floues. La
complexité de leur approche est O n × log (ε) [C HANAS et K ASPERSKI, 2004]. Kasperski
43
Chapitre 2. Problèmes d’ordonnancement à une machine avec coûts
actualisés et paramètres incertains
Définition 2.1. Une fonction ũ : R → [0, 1] est dite un nombre flou si elle satisfait :
i) ũ est normale, i.e. ∃x 0 ∈ R avec ũ (x 0 ) = 1 ;
44
Chapitre 2. Problèmes d’ordonnancement à une machine avec coûts
actualisés et paramètres incertains
R, ∀λ ∈ [0, 1]) ;
iii) ũ est semi continue supérieure sur R ;
iv) {x 0 ∈ R : ũ (x) > 0} est un ensemble compact, avec {} est la fermeture de l’ensemble.
Il est plus convenable de représenter les nombres flous en utilisant un ensemble d’inter-
valles fermés générés selon la définition suivante.
Définition 2.2. Soit γ un nombre réel tel que γ ∈ [0, 1]. L’ensemble des coupes (niveaux) γ
de ũ est l’ensemble réel [ũ]γ défini par :
x ∈ R : ũ (x) ≥ γ si γ > 0
© ª
γ
[ũ] = (2.1)
{x ∈ R : ũ (x) > 0} si γ = 0
Par conséquent, l’intervalle fermé et borné [ũ]γ peut s’écrire sous forme paramétrique
[ũ]γ = u γ , u γ avec ū u est une fonction bornée continue à gauche croissante (dé-
£ ¡ ¢ ¡ ¢¤ ¡ ¢
1 − a−x si a − α ≤ x < a
¡ ¢
α
1 si a ≤ x ≤ b
ũ (x) = ³ ´ (2.2)
x−b
1− β si b < x ≤ b + β
0 aut r ement
On dit que ũ est un nombre flou trapezoidal avec intervalle de tolérance [a, b],
¢ de
largeur à gauche α et largeur à droite β. Pour le nombre flou trapezoidal ũ = a, b, α, β , les
¡
γ
fonctions u : £[0, 1]¡→ R et ¢ [ũ] , γ ∈ [0, 1],
¢ u : [0,¡ 1] →¢R ¤définissant les bornes¡des intervalles
ont la forme a − 1 − γ α, b + 1 − γ β . Le support de ũ est a − α, b + β .
Dans le but de généraliser les opérations arithmétiques ordinaires ainsi que les fonc-
tions composées, le théorème suivant est utilisé pour calculer les ensembles de niveau
γ des nombres flous obtenus comme résultat de l’application de ces opérations sur des
opérandes de même type [N GUYEN, 1978].
En se basant sur ce Théorème, les opérations généralisées suivantes peuvent être déduites
pour tous nombres flous positifs ( Ã et B̃) et scalaire λ, respectivement :
45
Chapitre 2. Problèmes d’ordonnancement à une machine avec coûts
actualisés et paramètres incertains
¤γ £ ¤γ £ ¤γ h ¡ ¢ ¡ ¢i
i) Ã ⊕ B̃ = Ã + B̃ = a γ + b γ , a γ + b γ ;
£ ¡ ¢ ¡ ¢
|λ| × a γ , |λ| × ā γ si λ ≥ 0
£ ¡ ¢ ¡ ¢¤
¤γ
ii) λ × Ã = £
£
;
|λ| × ā γ , |λ| × a γ si λ < 0
¡ ¢ ¡ ¢¤
¤γ h ¡ ¢ ¡ ¢i
iii) Ã ⊗ B̃ = a γ ×b γ , a γ ×b γ pour γ ∈ [0, 1].
£ ¡ ¢ ¡ ¢
Définition 2.4. Une mesure floue sur Ω est une fonction m : P (Ω) → [0, 1] telle que :
i) m φ = 0 ;
¡ ¢
ii) m (Ω) = 1 ;
iii) ∀D1 , D2 ∈ P (Ω) : (D1 ⊆ D2 ) ⇒ (m (D1 ) ≤ m (D2 )).
À la base de cette Définition, les mesures de possibilité et de nécessité sont illustrées par
les Définitions 2.5 et 2.6, respectivement.
Définition 2.5. Une mesure de possibilité sur Ω est une fonction Π : P (Ω) → [0, 1] satisfai-
sant les conditions suivantes :
i) Π φ = 0 ;
¡ ¢
ii) Π (Ω) = 1 ;
µ ¶
iii) Π ∪ Di = sup Π (Di ), pour chaque famille {Di }i ∈I de sous ensembles de Ω.
i ∈I i ∈I
Définition 2.6. Une mesure de nécessité sur Ω est une fonction N : P (Ω) → [0, 1] telle que
les propriétés suivantes sont vérifiées :
i) N φ = 0 ;
¡ ¢
ii) N (Ω) = 1 ;
µ ¶
iii) N ∩ Di = inf Π (Di ) pour chaque famille {Di }i ∈I de sous ensembles de Ω.
i ∈I i ∈I
Définition 2.7. Soit Π une mesure de possibilité sur Ω et µ : Ω → [0, 1] une distribution de
possibilité. Les applications µΠ : Ω → [0, 1] et Pos µ : P (Ω) → [0, 1] sont définies par µΠ (x) =
Π ({x}) ∀x ∈ Ω et Pos µ (D) = sup µ (x) ∀D ∈ P (Ω) respectivement.
x∈D
46
Chapitre 2. Problèmes d’ordonnancement à une machine avec coûts
actualisés et paramètres incertains
47
Chapitre 2. Problèmes d’ordonnancement à une machine avec coûts
actualisés et paramètres incertains
F IGURE 2.1 Application de l’argument de permutation pour les tâches aux positions k et
k + 1.
48
Chapitre 2. Problèmes d’ordonnancement à une machine avec coûts
actualisés et paramètres incertains
iP
=n iP
=n
ωi 1 − e −r Ci et la version non actualisée 1| | ωi Ci est donnée par le Lemme 2.1.
¡ ¢
1| |
i =1 i =1
Lemme 2.1. Pour des valeurs très petites du taux d’actualisation (r → 0), le problème
iP
=n iP
=n
ωi 1 − e −r Ci se réduit au problème 1| | ωi Ci .
¡ ¢
1| |
i =1 i =1
Démonstration.
En considérant la fonction objectif comme fonction du taux d’actualisation f (r ) =
iP
=n
ωi 1 − e −r Ci , le développement limité de Taylor de la fonction f au voisinage du zéro
¡ ¢
i =1
f (k) (0)r k
donne f (r ) = f (0)+ f 0 (0) r +...+ k! +Rk (r ). Nous pouvons limiter la série de Taylor au
deux premiers termes car r est très proche de zéro et nous obtenons f (r ) ∼= f (0)+ f 0 (0) r =
iP
=n
r ωi Ci . Le résultat obtenu diffère de la somme pondérée des dates de fin uniquement
i =1
par une constante positive de multiplication qui n’influe pas sur l’optimalité de la fonc-
iP
=n iP
=n
ωi 1 − e −r Ci se réduit au problème 1| | ωi Ci pour des
¡ ¢
tion. D’où le problème 1| |
i =1 i =1
valeurs faibles de r.
Définition 2.8. On dit qu’un ordonnancement fixe π est possiblement optimal si et seule-
ment s’il existe une configuration τ pour laquelle l’ordonnancement π est optimal au sens
ordinaire. Cette définition peut être
¢ formulé ¡ mathématiquement par : ¢
π est possi bl ement opt i mal ⇔ ∃τ ∈ Γ γ /π est opt i mal pour τ
¡ ¡ ¢
L’optimalité possible est notée par Pos Γ(γ) et nous écrivons Pos Γ(γ) π est opt i mal =
¡ ¢
lité possible.
¡ 2.1. En considérant
Propriété un ordonnancement donné π et un réel γ ∈ [0, 1], nous avons
Pos Γ(γ) π est opt i mal = 1 si et seulement si le système d’inégalités suivant est faisable :
¢
49
Chapitre 2. Problèmes d’ordonnancement à une machine avec coûts
actualisés et paramètres incertains
γ γ
p ≤ p π(i ) ≤ p̄ π(i ) i = 1, n
π(i )
γ γ
ωπ(i ) ≤ ωπ(i ) ≤ ω̄π(i ) i = 1, n
(2.4)
r γ ≤ r ≤ r¯γ
e r p π(i ) −1 e r p π(i +1) −1
ω
≤ ω i = 1, n − 1
π(i ) π(i +1)
Démonstration.
Necessité des conditions¡ (⇒)
Supposons que Pos Γ(γ) π est opt i mal = 1 pour un certain γ ∈ [0, 1]. Alors, de la Défi-
¢
rème 2.2). Alors, π est optimal pour τ ∈ Γ γ . De la Définition 2.8, nous obtenons
Pos Γ(γ) π est opt i mal = 1
¡ ¢
Définition 2.9. Pour un ordonnancement fixe π, le degré d’optimalité possible Pos est défini
comme suit :
Le problème de calcul de Pos π est opt i mal peut être simplifié en supposant que les
¡ ¢
paramètres d’ordonnancement
³ sont
´ donnés par des nombres flous trapézoïdaux. Nous
p p
supposons que p̃ i = p , p i , αi , βi , ω̃i = ωi , ωi , αω , βω et r˜ = r , r , αr , βr pour i = 1, n. Il
¡ ¢ ¡ ¢
i i i
en résulte de la Définition 2.9 et la Propriété 2.1 que Pos π est opt i mal est égale à la
¡ ¢
50
Chapitre 2. Problèmes d’ordonnancement à une machine avec coûts
actualisés et paramètres incertains
max γ
¡ ¢
0≤γ≤1
Su j et à
p ¡ p ¡
− απ(i ) 1 − γ ≤ p π(i ) ≤ p̄ π(i ) + βπ(i ) 1 − γ
¢ ¢
p i = 1, n
π(i )
(2.6)
ωπ(i ) − αω 1 − γ ≤ ωπ(i ) ≤ ω̄π(i ) + βω
1−γ
¡ ¢ ¡ ¢
i = 1, n
π(i ) π(i )
r − αr 1 − γ ≤ r ≤ r¯ + βr 1 − γ
¡ ¢ ¡ ¢
e r p π(i ) −1 ≤ e r p π(i +1) −1 i = 1, n − 1
ω π(i ) ω π(i +1)
Si ce problème n’est pas faisable, alors nous aurons Pos π est opt i mal = 0. Le concept
¡ ¢
d’optimalité nécessaire d’un ordonnancement fixe est donné par la Définition ci-dessous.
Définition 2.10. On dit qu’un ordonnancement fixe π est nécessairement optimal si
et seulement si l’ordonnancement π est optimal au sens ordinaire pour toutes les
configurations. La formulation mathématique
¡ ¢ de cette définition est¢ exprimée par :
π est nécessai r ement opt i mal ⇔ ∀τ ∈ Γ γ /π est opt i mal pour τ .
¡ ¢ ¡
L’optimalité nécessaire est notée par Nec Γ(γ) et nous écrivons Nec Γ(γ) π est opt i mal =
¡ ¢
Nec Γ(γ) π est opt i mal = 0. La propriété suivante est satisfaite par la mesure d’op-
¢
timalité nécessaire.
Propriété 2.2. Pour un ordonnancement ¢ donné π et un certain réel γ ∈ [0, 1], la condition
suffisante pour Nec Γ(γ) π est opt i mal = 1 est que le système non linéaire suivant soit
¡
satisfait pour i = 1, n − 1 :
γ γ
r γ p π(i ) r γ p π(i +1)
e −1 e −1
γ ≤ (2.7)
ωπ(i ) ωπ(i +1)
Démonstration.
Necessité des conditions (⇒)
Nous démontrons¡ en premier que ¢ ces conditions ne sont pas nécessaires. Nous suppo-
sons que Nec Γ(γ) π est opt i mal = 1 pour une valeur fixe de γ ∈ [0, 1], à partir de la Défi-
nition 2.10, π est optimal pour toutes les configurations p 1 , ..., p n , ω1 , ..., ωn , r ∈ Γ γ . Si
¡ ¢ ¡ ¢
γ
r γp
e π(i ) −1
ces conditions ne sont pas satisfaites, il existe k ∈ {1, ..., n − 1} tel que la valeur de γ
ωπ(i )
γ
r γp
e π(i +1) −1
est strictement supérieure à ω . Cette inégalité implique que pour des valeurs
π(i +1)
γ γ γ¤
arbitraires de p i ∈ p γ , p i ,ωi ∈ ωi , ωi et r ∈ r γ , r γ , nous obtenons les inégalités
h i £ £ ¤
i
suivantes :
γ γ
r¯ p̄ r p π(k)
e π(k) −1
≥ e ω −1
γ
ωπ(k)
π(k)
γ
r γp
r p π(k+1) π(k+1) −1
e e
−1
≥
ωπ(k+1) ω̄π(k+1)
51
Chapitre 2. Problèmes d’ordonnancement à une machine avec coûts
actualisés et paramètres incertains
γ γ
rp r p π(k+1) rp r p π(k+1)
e π(k) −1 e −1 e π(k) −1 e −1
Nous distinguons deux cas ωπ(k) > ωπ(k+1) ouDans le cas
ωπ(k) ≤ ωπ(k+1) .
de la dernière inégalité, pour toute configuration τ = p 1 , ..., p n , ω1 , ..., ωn , r ∈ Γ γ ,
¢ ¡¡ ¢
nous concluons du Théorème 2.2 que π est optimal pour toutes les configurations (les
conditions nécessaires d’optimalité sont¢ vérifiées indépendamment de la valeur de γ), ce
qui signifie que Nec Γ(γ) π est opt i mal = 1 même si ces conditions ne sont pas vérifiées.
¡
Définition 2.11. Pour un ordonnancement fixe π, le degré d’optimalité nécessaire Nec est
exprimé par :
L’extension du Lemme 2.1 au cas flou où tous les paramètres sont représentés par des
nombres flous trapézoïdaux est illustrée par le Lemme suivant.
Lemme 2.2. Dans le cas des valeurs très petites du taux d’actualisation flou, le problème
¯ iP
=n ¯ iP
=n
1 ¯ω̃i , p̃ i , r˜¯ ωi 1 − e −r Ci se réduit au problème 1 ¯ω̃i , p̃ i ¯ ωi Ci .
¯ ¡ ¢ ¯
i =1 i =1
Démonstration.
Si le taux d’actualisation flou prend des valeurs faibles (r → 0), nous pouvons l’approxi-
mer par un nombre réel (r˜ ∼ = (r, r, 0, 0)). Dans ce cas, la fonction objectif devient elle même
une fonction floue notée par f˜.hEn utilisant la notation des coupes γ, nous obtenons pour
¤γ ¡ ¢ ¡ ¢i
˜
γ ∈ [0, 1] l’expression f (r ) = f r, γ , f r, γ avec
£
¡ ¢ iP =n
¡ ¢ ³ −r Ci (γ)
´
f r, γ = ω i γ × 1 − e
i =1
¡ ¢ iP =n ¡ ¢ ³ ´
ωi γ × 1 − e −r Ci (γ)
f r, γ =
i =1
Comme ces bornes sont des fonctions réelles de r, le Lemme 2.1 peut être appli-
qué pour arriver à :
52
Chapitre 2. Problèmes d’ordonnancement à une machine avec coûts
actualisés et paramètres incertains
iP
=n
γ ∼ ω γ γ
¡ ¢ ¡ ¢ ¡ ¢
f r, = r i × C i
i =1
iP
=n
f r, γ ∼ ωi γ × C i γ
¡ ¢ ¡ ¢ ¡ ¢
=r
i =1
iP=n ¡ ¢ iP
=n
· ¸
¤γ
∼ f˜ (r )
ωi γ × C i γ , ωi γ × C i γ .
£ ¡ ¢ ¡ ¢ ¡ ¢
ou bien sous forme plus compacte = r
i =1 i =1
iP
=n ¡ ¢ iP
=n
· ¸
ωi γ × Ci γ , ωi γ × Ci γ pour γ ∈ [0, 1] peuvent
¡ ¢ ¡ ¢ ¡ ¢
Sachant que les intervalles r
i =1 i =1
être identifiés à une constante de multiplication près au coupes γ de la fonction
¯ iP
=n
objectif associée au problème 1 ¯ω̃i , p̃ i ¯ ωi Ci , nous déduisons que le problème
¯
i =1
¯ iP
=n ¯ iP
=n
1 ¯ω̃i , p̃ i , r˜¯ ωi 1 − e −r Ci coïncide bien avec le problème 1 ¯ω̃i , p̃ i ¯ ωi Ci pour les
¯ ¡ ¢ ¯
i =1 i =1
valeurs très faibles du taux d’actualisation r˜.
¯ iP
=n
Quelques résultats asymptotiques pour le problème 1 ¯ω̃i , p̃ i , r˜¯ ωi 1 − e −r Ci sont
¯ ¡ ¢
i =1
obtenus si les hypothèses suivantes sont imposées sur le taux d’actualisation comme in-
diqué par les Corollaires suivants.
Corollaire 2.1. Si le taux d’actualisation prend des valeurs réelles i.e. r˜ = (r, r, 0, 0), l’en-
semble des conditions suffisantes sont aussi des conditions nécessaires pour l’optimalité
nécessaire
¡ d’un ordonnancement. Dans ce cas, le degré d’optimalité nécessaire est donné
par Nec π est opt i mal = 1 − γ avec γ∗ est la valeur minimale de la fonction objectif du
∗
¢
γ
¡ ¢
min
0≤γ≤1
Su j et à
(2.9)
p p
h i h i
π(i +1) π(i +1) (
1−γ)
π(i ) (
1−γ)
r p̄ π(i ) +β r p −α
e e
h
i≤h i i = 1, n − 1
ωπ(i ) −αω π(i ) (
1−γ) ω̄π(i +1) +βωπ(i +1) (
1−γ)
Démonstration.
Supposons que Nec Γ(γ) π est opt i mal = 1 pour une valeur donnée de γ ∈ [0, 1]. Donc,
¡ ¢
de¡ la¢ Définition 2.10, π est optimal pour toutes les configurations p 1 , ..., p n , ω1 , ..., ωn , r ∈
¡ ¢
Γ γ . Si les conditions ne sont pas satisfaites alors il existe k ∈ {1, ..., n − 1} tel que
γ γ
r γp r γp
e π(k) −1 e π(k+1) −1
. Nous considérons une configuration τ = p 1 , ..., p n , ω1 , ..., ωN , r ∈
¡ ¢
γ > γ
ω ωπ(k+1)
¡ π(k) γ γ γ γ
Γ γ telle que p π(k) = p π(k) , p π(k+1) = p π(k+1) , ωπ(k) = ωπ(k) , ωπ(k+1) = ωπ(k+1) et r = r γ = r γ . À
¢
partir de la Propriété 2.2 et Théorème 2.2, nous concluons que π n’est pas optimal pour τ
(les conditions nécessaires¡pour l’optimalité ¢ ne sont pas satisfaites), ce qui contredit notre
hypothèse initiale Nec Γ(γ) π est opt i mal = 1. Donc, pour une valeur réelle du taux d’ac-
tualisation r˜, les conditions suffisantes sont également des conditions nécessaires. Dans
ce cas, par application de la Définition 2.11 et la Propriété 2.2 nous obtenons le problème
de minimisation ( 2.9).
Corollaire 2.2. Pour des petites valeurs du taux d’actualisation flou r˜, les assertions sui-
vantes sont valides :
53
Chapitre 2. Problèmes d’ordonnancement à une machine avec coûts
actualisés et paramètres incertains
γ
p γ ≤ p i ≤ p̄ i i = 1, n
i
γ γ
ωi ≤ ωi ≤ ω̄i i = 1, n (2.10)
p π(i ) ≤ p π(i +1) i = 1, n − 1
ω π(i )ω π(i +1)
γ
p π(i ) pγ
π(i +1)
γ ≤ γ i = 1, n − 1 (2.11)
ωπ(i ) ωπ(i +1)
Démonstration.
¯ iP
=n
i) Par la réduction de notre problème flou 1 ¯ω̃i , p̃ i , r˜¯ ωi 1 − e −r Ci utilisant le
¯ ¡ ¢
i =1
¯ iP
=n
Lemme 2.2 au problème 1 ¯ω̃i , p̃ i ¯ ωi Ci et en suivant la même procédure de
¯
i =1
démonstration de la Propriété 2.1, nous déduisons que la faisabilité du système
d’inégalités :
γ
p γ ≤ p i ≤ p̄ i i = 1, n
i
γ γ
ωi ≤ ωi ≤ ω̄i i = 1, n
p π(i ) ≤ p π(i +1) i = 1, n − 1
ω ω
π(i ) π(i +1)
est une condition nécessaire et suffisante pour l’optimalité possible d’un or-
donnancement.
ii) Nous utilisons les mêmes procédures comme pour Propriété 2.2 et Corollaire 2.1
¯ iP
=n
pour le problème réduit 1 ¯ω̃i , p̃ i ¯ ωi Ci , nous déduisons que la faisabilité du
¯
i =1
système d’inégalités :
γ γ
p π(i ) p π(i +1)
γ ≤ γ i = 1, n − 1
ωπ(i ) ωπ(i +1)
En se basant sur les modèles compacts associés aux mesures d’optimalité possible
et nécessaire, nous pouvons observer que ces modèles représentent des problèmes
d’optimisation continue avec contraintes non linéaires. Comme dans plusieurs cas, ce
type de problème est difficile à résoudre à cause de la présence des régions faisables
non connexes dans l’espace de recherche ainsi que la présence de minimum locaux,
54
Chapitre 2. Problèmes d’ordonnancement à une machine avec coûts
actualisés et paramètres incertains
il est commode d’opter pour des techniques plus fiables telles que les approches évo-
lutionnaires émergentes ces dernières années comme outils puissants pour la résolu-
tion et l’analyse des problèmes d’optimisation ( [C ASTILLO et M ELIN, 2009] et [K ROLL
et S CHULTE, 2014]).
• Une solution exacte peut être obtenue ce qui est faux pour les méthodes basées sur
des fonctions de pénalités simples ;
• La fonction objectif originale n’est pas distorsée, au lieu elle est décalée de telle
sorte que l’optimum se déplace du minimum sans contraintes vers le minimum
sous contraintes ;
• La valeur du multiplicateur de Lagrange est donnée pour chaque contrainte. Cette
possibilité de calculer le multiplicateur de Lagrange offre plus de flexibilité par rap-
port aux autres algorithmes d’optimisation.
Cependant, parmi les critiques des méthodes à base du Lagrangien augmenté nous
trouvons la nécessité d’un nombre d’itération important (méthodes gourmandes en
temps de calcul) ainsi que la dépendance des phases d’optimisation actuelles de la
précision des phases précédentes. Pour un problème d’optimisation continue avec des
contraintes non linéaires, linéaires et de bornes, la formulation mathématique générique
est donnée par :
55
Chapitre 2. Problèmes d’ordonnancement à une machine avec coûts
actualisés et paramètres incertains
min F (x)
x
Su j et à
i neq
Ci (x) ≤ 0, i = 1, M
eq (2.12)
Ci (x) = 0, i = 1, N
Ai neq x ≤ Bi neq
eq eq
A x =B
Lb ≤ x ≤ U b
i neq eq
où Ci (x) représente M contraintes d’inégalité non linéaires, Ci (x) représentent N
contraintes d’égalité non linéaires, Ai neq la matrice des coefficients des contraintes d’in-
égalité linéaires, Aeq la matrice des coefficients des contraintes d’égalité linéaires, Lb et
U b sont les vecteurs des bornes inférieures et supérieures.
Un sous problème est formulé par la définition d’une nouvelle fonction objectif de la
somme pondérée de la fonction objectif originale et les contraintes non linéaires utilisant
les paramètres de Lagrange et de pénalité. La formulation compacte du sous problème
résultant est donnée par [C ONN et collab., 1997] :
M ³
i neq
´ X N
eq ρX N ¡
eq ¢2
Ψ x, λ, s, ρ = F (x) − λi s i log s i − Ci (x) + λi Ci (x) +
¡ ¢ X
Ci (x) (2.13)
i =1 i =1 2 i =1
Donc, nous commençons par l’affectation d’une valeur initiale au paramètre de pénalité,
une séquence de sous problèmes (qui sont des approximations du problème original) est
minimisée selon une méthode itérative appropriée ou une heuristique de telle sorte que
les contraintes linéaires et de bornes soient satisfaites et traitées séparément. À chaque
itération, si la précision nécessaire du minimum du sous problème est atteinte, les élé-
ments estimés du vecteur de multiplicateur de Lagrange sont mis à jour. Sinon, le para-
mètre de pénalité est augmenté par un facteur de pénalité. Ceci donne un nouveau sous
problème à minimiser suivant la même stratégie. Ces étapes sont réitérées jusqu’à l’une
des conditions d’arrêt imposées sur le nombre de générations, violation de contraintes ou
l’erreur sur la fonction objectif soit vérifiée.
56
Chapitre 2. Problèmes d’ordonnancement à une machine avec coûts
actualisés et paramètres incertains
Dans leur forme standard, les algorithmes génétiques ont plus de chance pour évi-
ter les optimums locaux en comparaison avec les techniques de programmation déter-
ministes comme ces algorithmes ne nécessitent pas le calcul du gradient de la fonction
objectif. Mais d’autre part, ces algorithmes supportent uniquement les contraintes de
bornes et les individus qui violent ces contraintes peuvent être éliminés sans difficultés.
57
Chapitre 2. Problèmes d’ordonnancement à une machine avec coûts
actualisés et paramètres incertains
Ceci est inefficace dans le cas où les solutions faisables sont difficilement déterminées.
En se basant sur les bonnes performances des métaheuristiques intégrées avec des fonc-
tions de pénalité à base du lagrangien augmenté, des approches très prometteuses ont
été développées pour des applications industrielles ( [D EB et S RIVASTAVA, 2012], [R AHIM
et collab., 2012], [R OCHA et collab., 2011] et [TALBI, 2013]).
avec
58
Chapitre 2. Problèmes d’ordonnancement à une machine avec coûts
actualisés et paramètres incertains
Il est à mentionner que pour des problèmes continus sous contraintes, les contraintes
de bornes peuvent être supportées par l’élimination des points testés non faisables où la
fonction objectif est évaluée uniquement aux points faisables respectant les contraintes
de bornes. D’autres parts, la délimitation de la région faisable lorsque des contraintes non
linéaires compliquées sont présentes nécessite plus d’efforts et peut être dans certains cas
une tâche fastidieuse. Aussi, la considération d’une fonction objectif basée sur une péna-
lité du lagrangien augmenté peut aider à surmonter cet obstacle et présenter une bonne
alternative pour la résolution du problème d’optimisation non linéaire avec contraintes
( [A RTIGUES et collab., 2008] et [C OSTA et collab., 2012]).
59
Chapitre 2. Problèmes d’ordonnancement à une machine avec coûts
actualisés et paramètres incertains
z i ← η × zi , zi
£ ¤
z̄ i ← z i , 1 + η × z i
£ ¡ ¢ ¤
60
Chapitre 2. Problèmes d’ordonnancement à une machine avec coûts
actualisés et paramètres incertains
TABLEAU 2.1 Valeurs des bornes inférieures et supérieures des paramètres utilisées lors
de la procédure de génération des instances
TABLEAU 2.2 Valeurs des paramètres de configuration utilisées dans les approches d’op-
timisation proposées
61
Chapitre 2. Problèmes d’ordonnancement à une machine avec coûts
actualisés et paramètres incertains
• Y : le nombre de tâches ;
• Z : l’indice de l’instance.
Quatre critères statistiques sont utilisés pour l’évaluation des performances des deux
approches : la meilleure valeur de la fonction objectif trouvée après n r ep exécutions
(FBest ), la valeur moyenne de toutes les valeurs de la fonction objectif (F¡ Mean¢ ), l’erreur
moyenne entre les valeurs de la fonction objectif et sa meilleure valeur FAv g et finale-
ment l’écart type des valeurs de la fonction objectif (FSt d ). Les formulations mathéma-
tiques de ces critères sont données par :
¡ ¢
FBest = max fj (2.16)
j =1,n r ep
n r ep
P
fj
j =1
FMean = (2.17)
n r ep
n r ep ¯ ¯
P ¯
f j − FBest ¯
j =1
FAv g = (2.18)
n r ep
n r ep ¡ ¢2
P
f j − FMean
j =1
FSt d = (2.19)
n r ep
62
Chapitre 2. Problèmes d’ordonnancement à une machine avec coûts
actualisés et paramètres incertains
* : Valeur optimale
de η est strictement inférieure à celle associée aux valeurs faibles de η. Ceci peut être jus-
tifié par l’aspect stochastique de l’algorithme en plus de l’intervalle étroit des valeurs des
paramètres d’ordonnancement lorsque η prend des petites valeurs. Alors, il est possible
d’obtenir de meilleures solutions en comparaison avec le cas où les valeurs de η sont éle-
vées. La méthode de recherche par motifs conserve sa stabilité même pour des valeurs
élevées du paramètre η où la meilleure valeur et la valeur moyenne de la fonction objectif
sont égales.
TABLEAU 2.4 Évolution des performances des approches proposées pour différentes va-
leurs de la graine aléatoire η
* : Valeur optimale
63
Chapitre 2. Problèmes d’ordonnancement à une machine avec coûts
actualisés et paramètres incertains
* : Valeur optimale
TABLEAU 2.6 Évolution des performances des approches proposées avec la réduction du
taux d’actualisation flou r˜
64
Chapitre 2. Problèmes d’ordonnancement à une machine avec coûts
actualisés et paramètres incertains
* : Valeur optimale
* : Valeur optimale
65
Chapitre 2. Problèmes d’ordonnancement à une machine avec coûts
actualisés et paramètres incertains
2.6 Conclusion
Dans ce chapitre, nous avons presenté le problème d’ordonnancement à une machine
avec des coûts actualisés et des paramètres incertains. Ce problème diffère des autres
problèmes d’ordonnancement conventionnels dans le fait que la notion d’optimalité or-
dinaire est remplacée par les degrés possible et nécessaire pour évaluer l’optimalité d’un
ordonnancement fixe. Le calcul du degré d’optimalité possible a été achevé en utilisant
deux approches d’optimisation basées sur un algorithme génétique et une méthode de
recherche par motifs. Dans ces approches, le formalisme lagrangien augmenté est intégré
pour supporter les contraintes non linéaires dans le contexte de la fonction objectif ori-
ginale. Cette intégration permet une meilleure gestion de la procédure de recherche dans
les régions des solutions faisables.
L’évaluation des performances des approches proposées a été caractérisée par l’ana-
lyse de l’effet de quelques paramètres sur la qualité des solutions obtenues. En effet, nous
avons trouvé que la majorité du temps de calcul est consommée dans la recherche de ré-
gion faisable, ce qui reflète la difficulté de satisfaire les contraintes non linéaires. Les ap-
proches proposées peuvent être considérées comme des candidates prometeuses pour la
résolution des problèmes d’ordonnancement plus compliqués lorsque les données sont
sujettes à des sources d’incertitude.
Dans cette recherche, nous avons focalisé les efforts sur la quantification de la notion
d’optimalité pour un ordonnancement bien défini dans un contexte flou. Il serait intéres-
sant de pousser l’analyse vers la considération d’aspect combinatoire de l’ordonnance-
ment et d’exploiter l’existence de problèmes ayant une complexité polynômiale. Un autre
axe de recherche qui mérite d’être entamer est de voir le comportement des solutions
optimales sous l’effet de contraintes agissant sur les durées opératoires des tâches sans
négliger les conséquences sur les procédures de simulation associées.
2.7 Références
A HMADIZAR , F. et L. H OSSEINI. 2011, «Single-machine scheduling with a position-based
learning effect and fuzzy processing times», The International Journal of Advanced Ma-
nufacturing Technology, vol. 56, no 5, p. 693–698. 43
C AO, C., X. G U et Z. X IN. 2009, «Chance constrained programming models for refinery
short-term crude oil scheduling problem», Applied Mathematical Modelling, vol. 33,
no 3, p. 1696–1707. 42
66
Chapitre 2. Problèmes d’ordonnancement à une machine avec coûts
actualisés et paramètres incertains
C ASTILLO, O. et P. M ELIN. 2009, Soft computing models for intelligent control of non-linear
dynamical systems,, chap. 4, in W. Mitkowski et J. Kacprzyk (eds.), Modelling dynamics
in processes and systems, Springer. 55
C HUANG , T. N. 2004, «The edd rule for fuzzy job time», Journal of Information and Opti-
mization Sciences, vol. 25, no 1, p. 1–20. 43
C ONN , A. R., N. G OULD et P. L. T OINT. 1997, «A globally convergent lagrangian barrier al-
gorithm for optimization with general inequality constraints and simple bounds», Ma-
thematics of Computation, vol. 66, no 217, p. 261–288. 56
D ONG , Y. 2003, «One machine fuzzy scheduling to minimize total weighted tardiness, ear-
liness, and recourse cost», International Journal of Smart Engineering System Design,
vol. 5, no 3, p. 135–147. 41
67
Chapitre 2. Problèmes d’ordonnancement à une machine avec coûts
actualisés et paramètres incertains
G UPTA , S. K. et J. K YPARISIS. 1987, «Single machine scheduling research», Omega The In-
ternational Journal of Management Science, vol. 15, no 3, p. 207–227. 41
H AN , S., H. I SHII et S. F UJI. 1994, «One machine scheduling problem with fuzzy due
dates», European Journal of Operational Research, vol. 79, no 1, p. 1–12. 42
H ARE , H. et H. S ONG. 2016, «On the cardinality of positively linearly independent sets»,
Optimization Letters, vol. 10, no 4, p. 649–654. 58
K LIR , G. J. et B. Y UAN. 1995, Fuzzy sets and fuzzy logic theory and applications, Prentice
Hall Press. 44
L EWIS , R. M. et V. T ORCZON. 1999, «Pattern search algorithms for bound constrained mi-
nimization», SIAM Journal on Optimization, vol. 9, no 4, p. 1082–1099. 58
L EWIS , R. M., V. T ORCZON et M. W. T ROSSET. 2000, «Direct search methods :then and
now», Journal of Computational and Applied Mathematics, vol. 124, no 1-2, p. 191–207.
58
L I , J., X. Y UAN, E. S. L EE et D. X U. 2011, «Setting due dates to minimize the total weighted
possibilistic mean value of the weighted earliness-tardiness costs on a single machine»,
Computers and Mathematics with Applications, vol. 62, no 11, p. 4126–4139. 44
L IAO, L. M. et C. J. L IAO. 1998, «Single machine scheduling problem with fuzzy due date
and processing time», Journal of the Chinese Institute of Engineers, vol. 21, no 2, p. 189–
196. 42
68
Chapitre 2. Problèmes d’ordonnancement à une machine avec coûts
actualisés et paramètres incertains
N GUYEN , H. T. 1978, «A note on the extension principle for fuzzy sets», Journal of Mathe-
matical Analysis and Applications, vol. 64, no 2, p. 369–380. 45
O LARU , D. et B. S MITH. 2005, «Modelling behavioural rules for daily activity scheduling
using fuzzy logic», Transportation, vol. 32, no 4, p. 423–441. 42
P RADE , H. 1979, «Using fuzzy set theory in a scheduling problem : a case study», Fuzzy
Sets and Systems, vol. 2, no 2, p. 153–165. 42
S CHULTMANN , F., M. F RÖHLING et O. R ENTZ. 2006, «Fuzzy approach for production plan-
ning and detailed scheduling in paints manufacturing», International Journal of Pro-
duction Research, vol. 44, no 8, p. 1589–1612. 42
69
Chapitre 2. Problèmes d’ordonnancement à une machine avec coûts
actualisés et paramètres incertains
T ORCZON , V. 1997, «On the convergence of pattern search algorithms», SIAM Journal on
Optimization, vol. 7, no 1, p. 1–25. 58
WANG , C., D. WANG, W. H. I P et D. W. Y UEN. 2002, «The single machine ready time sche-
duling problem with fuzzy processing times», Fuzzy Sets and Systems, vol. 127, no 2, p.
117–129. 42
W ONGA , B. K. et V. S. L AI. 2011, «A survey of the application of fuzzy set theory in pro-
duction and operations management : 1998-2009», International Journal of Production
Economics, vol. 129, no 1, p. 157–168. 60
Z ADEH , L. A. 1978, «Fuzzy sets as a basis for a theory of possibility», Fuzzy Sets and Sys-
tems, vol. 1, p. 3–28. 46
70
Chapitre 3
Albert Einstein
Sommaire
3.1 Introduction et état de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
3.2 Présentation du cadre de modélisation floue . . . . . . . . . . . . . . . . . 77
3.3 Métaheuristiques à base de trajectoire . . . . . . . . . . . . . . . . . . . . 80
3.3.1 Recherche tabou . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
3.3.2 Recuit simulé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
3.3.3 Recherche kangourou . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
3.4 Algorithme polynômial pour le problème d’ordonnancement à une ma-
chine avec effet d’apprentissage et durées opératoires floues . . . . . . . 86
3.4.1 Optimalité du problème d’ordonnancement à une machine avec
effet d’apprentissage . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
3.4.2 Optimalité du problème d’ordonnancement à une machine avec
effet d’apprentissage et durées opértoires floues . . . . . . . . . . . 89
3.5 Approches d’optimisation pour le problème d’ordonnancement à une
machine avec dates de disponibilité floues, durées opératoires floues et
effet d’apprentissage à base de position . . . . . . . . . . . . . . . . . . . . 93
3.5.1 Formulation du problème d’ordonnancement . . . . . . . . . . . . . 93
3.5.2 Procédure de génération des jeux tests . . . . . . . . . . . . . . . . . 94
3.5.3 Évaluation des résultats . . . . . . . . . . . . . . . . . . . . . . . . . . 94
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
3.7 Références . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
71
Chapitre 3. Problèmes d’ordonnancement à une machine avec effet
d’apprentissage et paramètres incertains
72
Chapitre 3. Problèmes d’ordonnancement à une machine avec effet
d’apprentissage et paramètres incertains
Il n’y a pas de doute qu’un grand nombre de travaux est publié relativement au pro-
blèmes d’ordonnancement déterministes et en particulier les problèmes d’ordonnance-
ment à une machine. Malgré que le traitement de ces problèmes date de plusieurs dé-
cennies [P INEDO, 2012], plusieurs améliorations continuent d’avoir lieu en considérant
les nouvelles contraintes technologiques de nos jours. Cette tendance peut être expliquée
d’un point de vue théorique par le fait que les connaissances cumulées sur les modèles
d’ordonnancement à une machine permettent une compréhension profonde pour les
problèmes d’ordonnancement plus compliqués tels que les environnements job shop ou
à machines parallèles. Donc, les propositions disponibles peuvent être étendues et ouvrir
de futurs axes de recherche. D’un point de vue pratique, les systèmes de production dans
certaines industries se comportent comme une ressource unique de service qui opère sur
un produit à la fois mais d’une façon séquentielle pour le plan de production composé de
plusieurs produits. En outre, dans quelques situations, où plusieurs machines existent,
l’une de ces machines connue sous le nom de goulot d’étranglement domine les autres
phases du processus. Toute procédure d’amélioration doit être concentrée en premier sur
cette machine si les performances globales sont à augmenter. Sachant que plusieurs pro-
blèmes d’ordonnancement existant en pratique sont des problèmes NP-difficiles, dans
le sens que la complexité de calcul de résolution croît exponentiellement en fonction de
la taille du problème, plus d’efforts sont réservés à l’élaboration d’heuristique où d’ap-
proches évolutionnaires permettant d’avoir des solutions proches de l’optimale [G LOVER
et KOCHENBERGER, 2003].
Dans plusieurs configurations d’ordonnancement réelles, la capacité de production
des différentes ressources (en particulier les ressources humaines) à exécuter des tâches
bien déterminées (planification de la maintenance, manipulation de logiciel) augmente
d’une façon continue avec le temps. Souvent ceci peut être observé dans les compagnies
avec des tâches similaires exécutées sur une machine ou machines parallèles identiques
pour un nombre de clients. À un niveau de base, ceci est reflété par des durées opé-
ratoires qui se réduisent lorsque les tâches associées sont placées en aval qu’en amont
dans le plan d’ordonnancement. Mathématiquement, ce phénomène connu sous le nom
d’effet d’apprentissage est exprimé par une fonction décroissante pour les durées opéra-
toires. Une représentation graphique nommée par les courbes d’apprentissage a été in-
troduite par Wright en 1936 pour analyser les coûts directs de production dans l’industrie
des avions, où les coûts de travail par unité diminuent avec l’augmentation du nombre
d’avions produits [W RIGHT, 1936]. Ces courbes décrivent l’amélioration de performance
comme une fonction de la reoccurrence de la même tâche. Par la suite, les courbes d’ap-
prentissage ont été utilisées dans multitudes domaines d’applications ( [Y ELLE, 1979] et
[W OODS et collab., 1992]). La première étude intégrant l’effet d’apprentissage dans les
problèmes d’ordonnancement est due à Meilzson et Tamir, où ils ont considéré un en-
semble de tâches avec des unités décroissantes à exécuter sur des processeurs parallèles
identiques [M EILIJSON et TAMIR, 1984]. Le travail pionnier de Biskup était le premier à
présenter l’effet d’apprentissage dans le contexte d’ordonnancement à une machine en
supposant que le temps de production d’un composant décroit en fonction de la posi-
tion de la tâche dans la séquence. Il a également prouvé que la minimisation de la somme
des durées de séjour des tâches ainsi que la minimisation de la somme des déviations
des dates de fin des tâches par rapport à une date échue connue sont toutes les deux
de complexité polynômiale [B ISKUP, 1999]. Par contre, Mosheiov a démontré à travers
des exemples numériques que plusieurs règles classiques d’ordonnancement telles que
73
Chapitre 3. Problèmes d’ordonnancement à une machine avec effet
d’apprentissage et paramètres incertains
l’algorithme de Smith ou Moore ne donne pas des solutions optimales sous l’hypothèse
d’effet d’apprentissage. Donc, il est possible de développer des heuristiques pour les pro-
blèmes modifiés en se basant sur les solutions optimales du problème classique comme
solution initiale [M OSHEIOV, 2001]. Bachman et Janiak ont montré que quelques cas par-
ticuliers du problème de minimisation de la somme pondérée des dates de fin des tâches
avec effet d’apprentissage sont polynômiaux. Par exemple, lorsque toutes les tâches ont
la même durée opératoire ou lorsque les poids sont un multiple de la durée opératoire.
Ils ont prouvé aussi que le problème de minimisation du makespan avec des dates de
disponibilité est au moins NP-difficile mais la procédure de démonstration reste à vé-
rifier car quelques commentaires ont été mentionnées après par Rudek ( [B ACHMAN et
J ANIAK, 2004] et [RUDEK, 2013]). Par la suite, les efforts sont concentrés sur les cas polynô-
miaux des problèmes d’ordonnancement où plusieurs auteurs ont proposé des nouveaux
modèles d’effet d’apprentissage et ont déterminé l’ensemble des conditions à satisfaire
par les paramètres de configuration de telle sorte que l’application des règles conven-
tionnelles reste une procédure de résolution valide. Kuo et Yang ont introduit un effet
d’apprentissage qui dépend du temps comme étant une fonction de la somme des durés
opératoires des tâches ordonnancées en amont. Ils ont montré que la minimisation de la
somme des dates de fin sur une machine admet la séquence obtenue par la règle Délai de
Fabrication le plus Court comme solution optimale [K UO et YANG, 2006]. Wu et Lee ont
présenté un modèle d’apprentissage où la durée opératoire de la tâche actuelle dépend de
sa position ainsi que de la somme des durées opératoires des tâches déjà ordonnancées.
Le makespan et la somme des dates de fin d’exécution peuvent être résolues à l’optima-
lité si les durées opératoires et les poids sont liés par une contrainte d’agréabilité [W U
et L EE, 2008]. Janick et Rudek ont proposé un effet d’apprentissage à multi-capacité dans
lequel le processeur obtient seulement les capacités ou bien les expériences. Les auteurs
ont étudié le problème de minimisation du makespan et ont élaboré un algorithme de
résolution de complexité polynômiale [J ANIAK et RUDEK, 2010]. Yin et ses collègues ont
développé un modèle d’ordonnancement général avec effet d’apprentissage dépendant
de la position et effet de détérioration dépendant du temps. Plusieurs critères d’ordon-
nancement à une machine ont été considérés par les auteurs et quelques règles ont été
prouvées d’être optimales sous quelques conditions spécifiques. Des algorithmes d’ap-
proximations ont été également proposés pour la classe des problèmes à complexité ou-
verte [Y IN et collab., 2012]. Dans [L AI et L EE, 2013], un nouveau modèle considérant les
effets d’apprentissage et d’oublie a été décrit. Les auteurs ont prouvé que l’application de
la règle Délai de Fabrication le plus Court donne des solutions optimales pour le makes-
pan et la somme des dates de fin d’exécution. De plus, la règle Délai de Fabrication le plus
Court Pondéré (en anglais WSPT) donne une solution optimale pour la somme pondé-
rée des dates de fin et la règle Délais de Livraison le plus Proche (en anglais EDD) donne
une solution optimale pour les critères maximum retard algébrique, maximum retard ab-
solu et somme des retards absolus sous quelques contraintes d’agréabilité. Néanmoins,
il est à noter qu’il existe moins de travaux dédiés à l’étude des versions NP-difficiles de
ce type de problème. Eren a développé un modèle de programmation non linéaire pour
le problème d’ordonnancement à une machine avec dates de disponibilité différentes et
effet d’apprentissage. Il a montré en utilisant des tests numériques que le modèle pro-
posé peut résoudre des instances de taille allant jusqu’à trente tâches d’une façon effi-
cace [E REN, 2009]. Wu et ses collègues ont considéré un problème d’ordonnancement
à une machine avec effet d’apprentissage basé sur la somme des durées opératoires et
données de disponibilité pour minimiser la somme pondérée des dates de fin d’exécu-
tion. Les auteurs ont développé des approches par séparation et évaluation et algorithme
74
Chapitre 3. Problèmes d’ordonnancement à une machine avec effet
d’apprentissage et paramètres incertains
génétique pour obtenir des solutions acceptables où les résultats ont montré que l’ap-
proche par séparation et évaluation a des bonnes performances jusqu’à quinze tâches et
l’erreur relative moyenne de l’algorithme génétique est tolérable [W U et collab., 2011].
Yin et ses collègues ont abordé la minimisation de la somme des retards avec des dates de
disponibilité arbitraires et effet d’apprentissage de position. Comme ce problème est NP-
difficile, un modèle de programmation linéaire mixte en nombres entiers et une procé-
dure par séparation et évaluation avec des règles de dominance et bornes inférieures ont
été proposés pour obtenir une solution optimale [Y IN et collab., 2014]. Pour une étude
détaillée sur la complexité des problèmes d’ordonnancement avec différents types d’effet
d’apprentissage, le lecteur peut consulter la référence [B ISKUP, 2008].
Un autre facteur qui peut altérer non pas seulement les durées opératoires des tâches
mais aussi la totalité de la stratégie d’ordonnancement est l’existence de plusieurs sources
d’incertitudes internes et externes du système de production. Dans la pratique, les durées
opératoires sont souvent estimées relativement à deux règles : les durées opératoires as-
sociées à des tâches de même type et si ce type n’existe pas (nouveau produit) il faut opter
pour l’estimation basée sur des tâches un peu similaires. Le problème majeur confronté
dans ce cas réside dans le fait que les durées opératoires des tâches dépendent de plu-
sieurs éléments contenant l’aspect subjectif qu’on ne peut pas évaluer d’une façon pré-
cise. Par exemple, les temps de configurations dépendant de la séquence dans la produc-
tion de peintures ont une influence importante sur la conformité de la couleur aux be-
soins. Plusieurs contraintes environnementales comme la régulation de la température
peuvent aussi générer des incertitudes avec impact sur le processus de production et en
particulier sa durée [S CHULTMANN et collab., 2006]. Pour cela, la théorie des ensembles
flous a été adoptée par plusieurs chercheurs comme le pilier de construction d’un nou-
veau paradigme représenté par les modèles d’ordonnancement flous. Ce type d’ordon-
nancement avec durées opératoires floues a été abordé initialement par Prade qui a pu-
blié un article dans ce domaine. Il a affecté des nombres flous triangulaires aux durées
des cours pour élaborer le calendrier trimestriel dans une grande école française [P RADE,
1979]. Après, le concept flou a été diffusé aux différents niveaux motivé par les pertur-
bations dans les marchés de nos jours. Liao et Liao ont considéré un problème d’ordon-
nancement à une machine avec durées opératoires et dates échues floues représentées
par des nombres flous triangulaires et trapézoïdaux respectivement. Ils ont proposé des
algorithmes de complexité polynômiale pour maximiser le degré minimum de satisfac-
tion [L IAO et L IAO, 1998]. Dans [C HANAS et K ASPERSKI, 2001], il a été illustré que si la
fonction coût est F-monotone, la généralisation de l’algorithme de Lawler peut être uti-
lisée pour résoudre plusieurs problèmes d’ordonnancement avec des durées opératoires
ou dates échues floues. Le problème de maximisation du degré de possibilité que le maxi-
mum flou du retard algébrique n’est pas supérieure à un certain seuil flou donné par des
experts a été également introduit. Wang et ses collègues ont utilisé le principe d’extension
et le concept de profil d’achèvement probable de tâche pour maximiser le temps de dis-
ponibilité commun avec durées opératoires floues et sous des conditions particulières.
Ils ont établit une condition nécessaire que la solution optimale doit satisfaire lorsque les
tâches ont différentes dates échues et intervalles de confiances [WANG et collab., 2002].
L’article de Dong a été consacré à une approche d’ordonnancement à deux phases pour
résoudre un problème à une machine avec l’objectif de minimiser une combinaison de
la somme pondérée des retards absolus, la somme pondérée des avances et la somme
pondérée des coûts de recours. Il a représenté les durées opératoires incertaines par des
nombres flous triangulaires et les a interprété comme étant des distributions de possibi-
lité [D ONG, 2003]. Chanas et Kasperski ont supposé que les paramètres des problèmes
75
Chapitre 3. Problèmes d’ordonnancement à une machine avec effet
d’apprentissage et paramètres incertains
76
Chapitre 3. Problèmes d’ordonnancement à une machine avec effet
d’apprentissage et paramètres incertains
heuristiques sont décrites avec une analyse statistique dans la Section 3.5. La dernière
Section est destinée à la discussion des résultats obtenus sans oublier quelques sugges-
tions pour des futurs développements.
Un nombre flou est un sous ensemble flou de la ligne réelle R avec des fonctions d’ap-
partenance continues et convexes. L’espace des nombres flous est noté par F. En général,
un nombre flou est défini uniquement sur un sous ensemble X ⊆ R connu sous le nom de
l’univers de discours.
µ (x) si a ≤ x ≤ b
L
Ã
1 si b ≤ x ≤ c
µÃ (x) = (3.1)
µR (x) si c ≤ x ≤ d
Ã
0 aut r ement
À cause de la tendance monotone des deux fonctions, leurs fonctions inverses existent et
sont aussi monotones.
Définition 3.2. Pour tout nombre réel γ ∈ [0, 1], la coupe γ de à notée par A γ est donnée
¡ ¢
par :
A γ = x ¯µÃ (x) ≥ γ ∀x ∈ X
¡ ¢ © ¯ ª
(3.2)
La ¢ ¡ γ¢¤résultante est
£ ¡coupe ¡ ¢un intervalle compact
ª exprimé sous
© ¯forme paramétrique
par A γ , Ā γ ⊆ R avec A γ = inf x µÃ (x) ≥ γ et Ā γ = sup x ¯µÃ (x) ≥ γ . Ici, nous
© ¯ ¡ ¢ ª
¯
x∈X x∈X
distinguons deux cas limites lorsque γ = 0 et γ = 1. Le premier cas limite est le support
de à défini par supp à = x ¯µÃ (x) ≥ 0 avec {} signifie la fermeture de l’ensemble
¡ ¢ © ¯ ª
77
Chapitre 3. Problèmes d’ordonnancement à une machine avec effet
d’apprentissage et paramètres incertains
x ¯µÃ (x) ≥ 0 . Le deuxième cas limite est le noyau de à défini par ker à = x ¯µÃ (x) = 0 .
© ¯ ª ¡ ¢ © ¯ ª
∪ γA γ
¡ ¡ ¢¢
à = (3.3)
γ∈[0, 1]
avec
¡ ¢ γ si x∈A γ
¡ ¢
γA γ =
x∉A γ
¡ ¢
0 si
Nous concluons de ce Théorème que si toutes les coupes γ d’un nombre flou peuvent
être déterminées, le nombre flou est complètement défini. Donc, il y a une équivalence
entre un nombre flou et ses coupes γ pour γ ∈ [0, 1].
Dans [M ATARAZZO et M UNDA, 2001], il a été mentionné que la représentation L-R
des nombres flous est la forme générale la plus adoptée à cause de sa précision et faible
complexité de calcul lorsqu’elle est appliquée à des instances des problèmes réelles.
Définition 3.3. Un nombre flou noté par à = a, a, αà , βà L−R est de type L-R si sa fonction
¡ ¢
avec les paramètres αà et βà expriment les déviations gauche et droite, respectivement. Les
fonctions L et R sont des fonctions décroissantes avec L (0) = R (0) = 1.
Les nombres flous trapézoïdaux sont caractérisés par des fonctions linéaires L (R) et
a < a, tandis que les nombres flous triangulaires permettent la linéarité des fonctions L et
R avec a = a. Les£ coupes γ du nombre flou¤trapézoïdal à sont données par l’ensemble des
intervalles Aγ = a − αà + αà γ, a + βà − βà γ . En utilisant le principe d’extension de Zadeh,
il est possible de généraliser le concept d’application définie sur des ensembles réels à une
application définie sur des ensembles flous. Par conséquent les opérations arithmétiques
élémentaires peuvent être également déduites à partir des opérations simples.
Définition 3.4. Soient M, N ∈ F (R) deux nombres flous et ◦ : R × R → R une opération bi-
naire. Si nous notons par ◦˜ l’opération généralisée sur l’espace des nombres flous, alors par
application du principe d’extension, M˜◦N est donnée par un ensemble flou de R avec la
fonction d’appartenance :
si (◦)−1 (z) 6= φ
© ¡ ¢ª
sup min M (x) , N y
z=x◦y
(M˜◦N) (z) = ∀z ∈ R (3.5)
0 si (◦)−1 (z) = φ
78
Chapitre 3. Problèmes d’ordonnancement à une machine avec effet
d’apprentissage et paramètres incertains
³ ´
• à + B̃ = a + b, a + b, αà + αB̃ , βà + βB̃
L−R
Au contraire des nombres réels pour lesquelles il existe un ordre total, il est très difficile
de comparer les nombres flous représentés par des distributions de possibilité car il est
possible d’avoir un chevauchement. Mais un outil efficace consiste à utiliser les fonctions
de classement [J AIN, 1976], qui associe à chaque nombre flou un point sur la ligne réelle
R et la comparaison est rendue naturelle après cette transformation. Dépendamment de
la position relative des nombres flous, deux relations de dominance sont établies. Une
dominance forte caractérisant les nombres flous séparés et la dominance faible caracté-
risant les nombres flous avec chevauchement en utilisant une fonction de classement.
Leurs définitions formelles sont représentées ci-dessous [Ö ZELKAN et D UCKSTEIN, 1999].
Soit E : F → R une fonction de classement, Ã et B̃ sont deux nombres flous.
¡ ¢ ¡ ¢
Définition 3.5. On dit que à domine faiblement B̃© si Eª à ≥ E B̃ . La dominance faible est
notée par à ≥w B̃ et dans ce cas nous avons maxw Ã, B̃ = Ã.
les valeurs
© ªde γ ∈ [0, 1]. La dominance forte est notée par à ≥s B̃ et dans ce cas nous avons
maxs Ã, B̃ = Ã.
Une condition plus simple pour la dominance forte est écrite a − αà ≥ b + βB̃ , ou d’une
façon equivalente A (0) ∩ B (0) = φ.
Pour remédier les inconvénients des fonctions de classement existantes qui sont dans
certains cas en contradiction avec l’intuition humaine ou ne sont pas discriminantes,
Abasabandy et Hajjari ont proposé une nouvelle approche de classement des nombres
flous trapézoïdaux basée sur les déviations gauche et droite à une certaine coupe γ des
nombres flous trapézoïdaux [A BBASBANDY et H AJJARI, 2009]. Le principe de cette mé-
thode est décrit ci-dessous.
Zr =1³
¡ ¢ 1 ´
A γ + A γ + a + a f (r ) d r
¡ ¢ ¡ ¢
Mag à = (3.6)
2
r =0
avec la fonction f est une fonction croissante sur [0, 1] avec f (0) = 0, f (1) = 1 et
rR=1
f (r ) d r = 21 .
r =0
Il est à mentionner que si f est prise égale à 1 et seulement les bornes des coupes γ sont
79
Chapitre 3. Problèmes d’ordonnancement à une machine avec effet
d’apprentissage et paramètres incertains
Dans ce qui suit, nous démontrons que la propriété de linéarité est valable pour la
fonction de classement magnitude dans le cas des nombres flous trapézoïdaux et coeffi-
cients réels positifs.
Propriété 3.1. La fonction de classement exprimée par la magnitude est linéaire pour tous
les nombres flous Ã, B̃ ∈ F et les réels c 1 , c 2 ∈ R dans le sens de :
©¡ ¢ ¡ ¢ª ¡ ¢ ¡ ¢
Mag c 1 ⊗ à ⊕ c 2 ⊗ B̃ = c 1 Mag à + c 2 Mag B̃ (3.7)
Démonstration.
En se basant sur les expressions floues pour la somme et la multiplication par un scalaire,
nous pouvons écrire :
©¡ ¢ ¡ ¢ª
Mag c 1 ⊗ Ã ⊕ c 2 ⊗ B̃ =
n³ ´ o
Mag c 1 a + c 2 b, c 1 a + c 2 b, c 1 αà + c 2 αB̃ , c 1 βà + c 2 βB̃
L−R
³ ´
= 21 c 1 a + c 2 b + c 1 a + c 2 b − 12
1
c 1 αà + c 2 αB̃ − c 1 βà − c 2 βB̃
¡ ¢
©1 ¡ ¢ 1 ¡ n ³ ´ ¢o
1
αà − βà + c 2 21 b + b − 12 αB̃ − βB̃
¢ª ¡
= c1 2 a + a − 12
80
Chapitre 3. Problèmes d’ordonnancement à une machine avec effet
d’apprentissage et paramètres incertains
de voisinage pour obtenir les solutions candidates, elle génère un sous ensemble de so-
lutions et évalue leurs fonctions objectifs correspondantes. Le meilleur candidat non ta-
bou ou tabou mais satisfaisant le critère d’aspiration est sélectionné comme une nou-
velle solution courante et le mouvement associé est ajouté à la liste tabou gérée selon la
stratégie Premier Entré Premier Sorti (en anglais FIFO) pour que le même mouvement
soit interdit pendant un nombre fini des prochaines itérations. Sinon, choisir le premier
mouvement non tabou et le considérer comme la nouvelle solution courante. Si cette so-
lution est meilleure que la meilleure solution courante, elle est enregistrée comme nou-
velle meilleure solution. Cette procédure est répétée pour un nombre fixe d’itérations.
À la fin, la meilleure solution obtenue est la solution du problème d’optimisation [A L -
T URKI et collab., 2001]. L’Algorithme 3.1 est une description de différentes phases de la
recherche tabou.
81
Chapitre 3. Problèmes d’ordonnancement à une machine avec effet
d’apprentissage et paramètres incertains
82
Chapitre 3. Problèmes d’ordonnancement à une machine avec effet
d’apprentissage et paramètres incertains
liorée alors la solution associée est toujours acceptée. Mais même pour des solutions non
améliorées, il y a une probabilité d’acceptation dépendente d’un facteur de température.
Ce mécanisme est adopté pour éviter d’être piégé dans les optimums locaux pendant le
processus de recherche. La probabilité d’acceptation est donnée par :
f (x 0 )− f (x k )
µ ¶
− T
f x 0 − f (x k ) > 0
¡ ¢
k
e si
P Accept er x 0 comme pr ochai ne sol ut i on =
¡ ¢
f x 0 − f (x k ) ≤ 0
¡ ¢
1 si
(3.8)
SINON
Générer un nombre aléatoir q ∈ [0, 1]
f (x 0 )− f (x k ))
à !
−
(
Tk
SI ( q< e ) ALORS
FIN SI
FIN SI
Mettre
¡ à jour¢ la température à chaque époch utilisant la loi de refroidissement
Tk+1 = g (Tk )
FIN POUR
Retourner la solution x ∗ comme la meilleure solution correspondante au minimum de
la fonction objectif f
FIN
83
Chapitre 3. Problèmes d’ordonnancement à une machine avec effet
d’apprentissage et paramètres incertains
84
Chapitre 3. Problèmes d’ordonnancement à une machine avec effet
d’apprentissage et paramètres incertains
85
Chapitre 3. Problèmes d’ordonnancement à une machine avec effet
d’apprentissage et paramètres incertains
La notation de Graham à trois champs α ¯β¯ γ est utilisée pour décrire les différents pro-
¯ ¯
86
Chapitre 3. Problèmes d’ordonnancement à une machine avec effet
d’apprentissage et paramètres incertains
p
les tâches dans l’ordre décroissant du rapport ωi connu aussi sous le nom de la règle
i
WSPT [S MITH, 1956]. Si l’effet d’apprentissage est introduit, la règle reste valide mais
sous quelques conditions comme il est indiqué par le Théorème suivant [Z HAO et col-
lab., 2004].
¯ iP
=n
Théorème 3.1. Pour le problème 1 ¯p i ,r = p i r a ¯ ωi Ci , si les tâches ont des poids agréables
¯
i =1
i.e. p j ≤ p k implique ω j ≥ ωk pour toutes les tâches j et k, alors un ordonancement ∆ est
optimal si et seulement si les conditions suivantes sont satisfaites :
p ∆(i ) p ∆(i +1)
≤ , i = 1, ..., n − 1 (3.9)
ω∆(i ) ω∆(i +1)
Démonstration.
Necessité des conditions (⇒)
Nous considérons un ordonnancement optimal π pour lequel la règle WSPT n’est pas ap-
p p
plicable. Alors, il existe au moins i ∈ {1, ..., n − 1} tel que ωπ(i ) > ωπ(i +1) , ce qui implique
π(i ) π(i +1)
p π(i ) > p π(i +1) à cause de l’hypothèse d’agréabilité. En effectuant une permutation adja-
cente des tâches π (i ) et π (i + 1) dans π, nous obtenons un nouvel ordonnancement π0 .
Les dates de fin d’exécution ne sont pas affectées par la permutation des tâches comme
indiqué sur la Figure 3.1.
F IGURE 3.1 Application de l’argument de permutation pour les tâches aux positions i et
i + 1.
87
Chapitre 3. Problèmes d’ordonnancement à une machine avec effet
d’apprentissage et paramètres incertains
Nous calculons la différence des deux dates de fin d’exécution de tâche dans la po-
sition (i + 1) pour les deux ordonnancements :
Comme p π(i +1) − p π(i ) < 0 et i a − (i + 1)a > 0 alors Ci +1 π0 < Ci +1 (π), ce qui garan-
¡ ¢
tie que toutes les tâches ordonnancées après la position (i + 1) dans π0 ont des dates de
fin non supérieures à leurs dates de fin dans π. Maintenant, nous calculons la somme
pondérée des deux tâches aux positions (i ) et (i + 1) pour les deux ordonnancements :
que la contribution à la somme pondérée des dates de fin des tâches aux positions (i ) et
(i + 1) dans l’ordonnancement π0 est inférieure à leur contribution dans l’ordonnance-
ment π.
Il résulte des deux inégalités que la somme pondérée des dates de fin sous π0 est stricte-
ment inférieure à celle sous π, ce qui contredit l’optimalité de π. Donc, les conditions de
la règle WSPT sont des conditions nécessaires pour l’optimalité.
Suffisance des conditions (⇐)
Supposons qu’il existe un ordonnancement arbitraire violant l’ensemble des conditions
WSPT. Alors, il existe aux moins deux tâches consécutives dans l’ordonnancement qui
violent aussi ces conditions. Si nous effectuons une permutation locale de ces tâches,
une amélioration de la somme pondérée des dates de fin de l’ordonnancement original
aura lieu. En répétant cette procédure pour toutes les tâches non ordonnancées selon
la règle WSPT jusqu’à la stabilité de l’amélioration, nous obtenons un ordonnancement
optimal. La procédure de classement nécessite un temps de O(n × l og (n)). D’où l’en-
semble des conditions considérées sont des conditions suffisantes pour l’optimalité d’un
88
Chapitre 3. Problèmes d’ordonnancement à une machine avec effet
d’apprentissage et paramètres incertains
¯ iP
=n
ordonnancement dans le problème 1 ¯p i ,r = p i r a ¯ ωi Ci .
¯
i =1
Définition 3.8. On dit que des tâches ont des poids agréables flous si p̃ j ≥w p̃ i implique
que ωi ≥ ω j pour toutes les tâches i et j . On écrit mathématiquement :
∀ i , j ∈ J × J p̃ j ≥w p̃ i ⇒ ωi ≥ ω j
¡ ¢ ¡ ¢ ¡ ¢
(3.10)
Si
¡ la fonction¢ ¡de classement
¡ ¢ est ¡identifiée
¢¢ à la fonction magnitude, nous avons
p̃ j ≥w p̃ i ⇔ Mag p̃ j ≥ Mag p̃ i .
Nous proposons le théorèmeµsuivant présentant une approche polynômiale pour le pro-
iP
=n
¶
blème 1 ¯p̃ i , p i ,r = p i r a ¯ Mag ωi ⊗ C̃i . Ce théorème peut être considérée comme une
¯ ¯
i =1
extension du Théorème 3.1 lorsque le modèle d’ordonnancement est sujet à des données
incertaines.
Théorème 3.2. Si les tâches ont des poids agréables flous i.e. p̃ k ≥w p̃ j implique que
ω j ≥ ωk pour toutes tâches arbitraires j et k, alors, l’ordonnancement Φ est optimal si et
seulement si les conditions suivantes sont satisfaites :
Démonstration.
Necessité des conditions (⇒)
Nous démontrons la nécessité de ces conditions par contradiction. Nous supposons
qu’un ordonnancement donné π est optimal sans satisfaire ces conditions. Donc, il existe
p̃ p̃
au moins deux tâches adjacentes avec ωπ(i ) >w ωπ(i +1) , ce qui implique p π(i ) >w p π(i +1)
π(i ) π(i +1)
due à l’agréabilité floue des tâches. Si nous effectuons une permutation locale des tâches
π (i ) et π (i + 1) dans π, nous obtenons un nouvel ordonnancement :
Les dates de fin floues des tâches ordonnancées en amont de la tâche i ne sont pas
affectées par l’opération de permutation. Nous adoptons la même méthodologie que
dans le cas réel pour la vérification de la dominance de l’ordonnancement π0 par rapport
à l’ordonnancement π.
Sous l’ordonnancement π nous avons :
89
Chapitre 3. Problèmes d’ordonnancement à une machine avec effet
d’apprentissage et paramètres incertains
¡ a ¢
C̃i (π) = t̃ ⊕ i ⊗ p̃ π(i )
et pour l’ordonnancement π0 :
¡ a
C̃i π = t̃ ⊕ i ⊗ p̃ π(i +1)
¡ 0¢ ¢
Dans le but d’assurer que toutes les tâches ordonnancées en aval de la position
(i + 1) dans π0 ont une magnitude des dates de fin pas supérieure à leur magnitude de
dates de fin dans π, nous calculons la différence :
i a Mag p̃ π(i +1) + (i + 1)a Mag p̃ π(i ) − i a Mag p̃ π(i ) + (i + 1)a Mag p̃ π(i +1)
¡ ¢ ¡ ¢ ¡ ¢ ¡ ¢
i − (i + 1)a
¡ ¡ ¢ ¡ ¢¢ ¡¡ a ¢¢
= Mag p̃ π(i +1) − Mag p̃ π(i )
a a
¡ p̃ π(i
Comme ¢¢w p̃ π(i +1)¡ et i − (i¢ + 1) > 0 alors nous déduisons l’inégalité ci-dessous :
¡ )0>
Mag C̃i +1 π < Mag C̃i +1 (π) .
Mag (ωπ(i +1) ⊗C̃i (π0 )⊕ωπ(i ) ⊗C̃i +1 (π0 ))−Mag (ωπ(i ) ⊗C̃i (π)⊕ωπ(i +1) ⊗C̃i +1 (π))
i a (ωπ(i +1) +ωπ(i ) )Mag (p̃ π(i ) )
=
Comme p̃ π(i ) ≥w p̃ π(i +1) et ωπ(i +1) ≥ ωπ(i ) , nous déduisons que cette différence est
strictement inférieure à zéro. Il en résulte de ces deux inégalités que la magnitude de
la somme pondérée des dates de fin sous π0 est strictement inférieure à celle sous π,
ce qui contredit l’optimalité de π. Donc, les conditions considérées sont des conditions
nécessaires pour l’optimalité.
Suffisance des conditions (⇐)
Pour un ordonnancement arbitraire non optimal π, il existe au moins deux tâches
adjacentes dans l’ordonnancement qui viole ces conditions. Nous pouvons améliorer
la valeur de magnitude de la somme pondérée des dates de fin en permutant ces
tâches. Si cette procédure est itérée pour toutes les tâches non respectant la règle WSPT
90
Chapitre 3. Problèmes d’ordonnancement à une machine avec effet
d’apprentissage et paramètres incertains
Poids ωi
¡ ¢
Ji =1,5 Durée opératoire floue p̃ i Magnitude Mag p̃ i
1 (31,35,3,2) 1.49 22
2 (9,18,1,0) 0.45 30
3 (28,54,1,2) 4.11 10
4 (31,42,0,3) 2.63 14
5 (24,38,1,2) 1.35 23
La Figure 3.2 illustre les durées opératoires floues des tâches où le chevauchement des
nombres flous rend l’élaboration d’un classement au sens conventionnel impossible. Le cal-
cul de la fonction magnitude pour les différents ordonnancements utilisant une recherche
exhaustive donne la solution optimale π∗ = (2, 5, 1, 4, 3), qui correspond bien au résultat de
l’application du Théorème 3.2.
Dans la Figure 3.3, l’évolution de la fonction magnitude de la somme pondérée des
dates de fin pour la solution optimale est représentée. Comme attendu, la fonction objectif
a une allure décroissante en fonction de la valeur absolue du taux d’apprentissage, ce qui
confirme la réduction des coûts à cause de l’amélioration de la capacité de la ressource à
réaliser les tâches allouées.
Mais l’hypothèse d’agréabilité floue est une contrainte très forte et n’est pas satisfaite
dans la majorité des situations pratiques. Pour cette raison, il est plus approprié de concen-
trer les efforts sur le développement d’outils génériques ayant la capacité de résoudre une
multitude de problèmes sophistiqués sans avoir une connaissance approfondie sur les pro-
priétés intrinsèques de ces problèmes.
91
Chapitre 3. Problèmes d’ordonnancement à une machine avec effet
d’apprentissage et paramètres incertains
F IGURE 3.3 Évolution de la magnitude de la somme pondérée des dates de fin en fonction
du taux d’apprentissage.
92
Chapitre 3. Problèmes d’ordonnancement à une machine avec effet
d’apprentissage et paramètres incertains
pour i = 1, n sont affectées aux tâches. Dans ce cas, la date fin floue de chaque tâche i
peut être calculée utilisant l’opérateur de somme floue, multiplication avec un scalaire et
la dominance faible pour la détermination du maximum de deux nombres flous. Comme
fonction de classement, nous adoptons la magnitude d’un nombre flou proposée par
Abasabandy et Hajjeri [A BBASBANDY et H AJJARI, 2009], qui est également utilisée dans
la comparaison entre différentes ordonnancements. La date fin floue d’une tâche i dans
un ordonnancement π est calculée utilisant la formule de récurrence suivante :
C̃1 (π) = r˜1 (π) ⊕ p̃ 1 (π)
© ª (3.12)
r˜i (π) , C̃i −1 (π) ⊕ p̃ i (π) pour i = 2, n
C̃i (π) = maxw
La fonction objectif à optimiser est la magnitude de la somme pondérée des dates de fin
floues des tâches. En adoptant la notation à trois champs, nous notons ce problème par
iP
=n
µ ¶
1 ¯r˜i , p̃ i , p i ,r = p i r a ¯ Mag ωi ⊗ C̃i . Si l’effet d’apprentissage n’est pas considéré et tous
¯ ¯
i =1
iP
=n
les paramètres ont des valeurs réelles, ce problème se réduit au problème 1 |r i | ωi Ci
i =1
qui est prouvé NP-difficile au sens fort [L ENSTRA et collab., 1977]. Donc, notre version
93
Chapitre 3. Problèmes d’ordonnancement à une machine avec effet
d’apprentissage et paramètres incertains
p ← £ p , ¡1 + ρ ¢ p ¤
i i 1 i
iP
=n
· ¸
r = 0, ρ2 p
i
i =1 i
iP
=n iP
=n
· ¸
r¯i = ρ2 p , ρ2
p̄ i
i =1 i i =1
94
Chapitre 3. Problèmes d’ordonnancement à une machine avec effet
d’apprentissage et paramètres incertains
TABLEAU 3.2 Valeurs des différents paramètres utilisées lors de la procédure de génération
des instances
/ : Non applicable
95
Chapitre 3. Problèmes d’ordonnancement à une machine avec effet
d’apprentissage et paramètres incertains
thodes d’optimisation utilisées dans ce chapitre : la moyenne des erreurs relatives, l’écart
type des erreurs relatives et le pourcentage des meilleures solutions trouvées pour les 40
instances. Ces critères sont notés par Av g , St d et POB respectivement. L’erreur relative
est définie pour chaque métaheuristique dans le cas de petites instances (n ≤ 10) par :
µ ¡ ¢ ¡ ¢¶
f Mét aheur i st i que − f Opt i mal e
Er r eur = 100 × ¡ ¢ (3.14)
f Opt i mal e
iP
=n
µ ¶
avec f représente la fonction objectif Mag ωi ⊗ C̃i .
i =1
Dans le Tableau 3.4, les trois métaheuristiques à base de trajectoire sont exploitées
avec variation du nombre de tâches. Nous pouvons déduire que ces méthodes s’adaptent
bien à l’ensemble des instances car la moyenne des erreurs relatives obtenue pour 40 ins-
tances est inférieure à 1%, ce qui reflète de bonnes solutions proches de l’optimale. En
outre, la recherche kangourou donne les meilleures performances en fonction du pour-
centage des meilleures solutions obtenues, tandis que le recuit simulé est classé deuxième
avant la recherche tabou. La performance supérieure de la recherche kangourou est jus-
tifiée par l’efficacité de sa méthode de recherche locale à deux phases combinée avec un
opérateur 2-opt de saut, permettant un équilibre entre l’intensification et la diversifica-
tion dans l’espace de recherche.
La Figure 3.4 résume le temps CPU moyen (en seconde) de l’exécution des trois mé-
taheuristiques. Comme indiqué sur cette figure, les temps CPU moyens des recherches
tabou et kangourou sont prèsque superposés et donnent approximativement des résul-
tats identiques tandis que le recuit simulé montre une petite différence relativement aux
deux approches précédentes avec des grandes valeurs pour un nombre de tâches supé-
rieur à 25. Pour les valeurs inférieures à 15 tâches, il n’y a pas de différance remarquable
entre les temps CPU des trois métaheuristiques.
96
Chapitre 3. Problèmes d’ordonnancement à une machine avec effet
d’apprentissage et paramètres incertains
Le Tableau 3.5 reporte les variations des performances des métaheuristiques en fonc-
tion du coefficient d’apprentissage. Il est à noter dans ce cas que la recherche kangou-
rou dépasse les deux autres techniques en fonction de pourcentage des meilleures so-
lutions obtenues. Pour des petites valeurs du coefficient d’apprentissage, la majorité
des meilleures solutions est associée à cette méthode avec des valeurs très faibles de la
moyenne des erreurs relatives et l’écart type des erreurs relatives. En effet, le problème
d’ordonnancement considéré a l’allure de devenir plus facile à résoudre lorsque le coef-
ficient d’apprentissage est augmenté en valeur absolue résultant en une réduction signi-
ficative des durées opératoires floues des tâches. Pour cette raison, les performances des
trois métaheuristiques s’améliorent avec la valeur absolue du coefficient d’apprentissage.
Les performances de recherche tabou et le recuit simulé restent inférieures à la recherche
kangourou à cause de l’efficacité de la recherche locale hybride utilisée par cette dernière
métaheuristique.
Les Figures 3.5, 3.6 et 3.7 clarifient la variation de la moyenne des erreurs relatives
en fonction des graines aléatoires (ρ1 et ρ2 )pour les trois méthodes proposées avec n = 20
et Le f f = 0. Toutes les deux graines sont variées de 0.1 à 1 avec un pas de 0.1. Une ca-
ractéristique intéressante commune à toutes les courbes est reliée à la complexité de ré-
soudre les instances générées utilisant différentes configurations des graines peut être
observée. Les courbes de contour projetées sur le plan formé de ρ1 et ρ2 permettent de
détecter les valeurs élevées (en rouge) et les valeurs faibles (en bleu) de la moyenne des
erreurs relatives. Les configurations associées avec des valeurs élevées indiquent des ins-
tances difficiles tandis que celles associées avec des valeurs faibles indique les instances
faciles à résoudre. À partir de ces courbes, les instances difficiles sont situées en géné-
97
Chapitre 3. Problèmes d’ordonnancement à une machine avec effet
d’apprentissage et paramètres incertains
98
Chapitre 3. Problèmes d’ordonnancement à une machine avec effet
d’apprentissage et paramètres incertains
rale au voisinage des valeurs centrales de ρ1 et ρ2 . Tandis que les instances faciles sont
localisées aux petites valeurs de ρ2 . Cette dernière remarque est expliquée par le fait que
les valeurs faibles de la deuxième graine aléatoire mène à des dates de disponibilité très
serrées proches du zero comme indiqué dans la procédure de génération des instances.
Ce problème est connu dans le cas avec paramètres réels comme étant un problème de
complexité polynômiale.
F IGURE 3.5 Variation de la moyenne des erreurs relatives en fonction des valeurs des
graines aléatoires dans le cas de la recherche tabou.
Le même comportement concernant les instances difficiles et faciles peut être ob-
servé en fonction de l’écart type des erreurs relatives pour les métaheuristiques propo-
sées comme indiquée par les Figures 3.8, 3.9 et 3.10. Mais avec l’existence des régions
des deux types d’instances le long du plan de projection.
Pour une analyse plus fiable des performances de la recherche tabou et le recuit si-
mulé, nous conduisons un test d’hypothèse pour comparer ces deux méthodes. La re-
cherche kangourou n’est pas prise en compte car elle donne dans la majorité des cas les
meilleurs résultats. Mais avant d’entamer ce test, nous avons besoin de vérifier l’hypo-
thèse de normalité qui est primordiale dans plusieurs méthodes de test paramétrique
telles que t-test et F-test [L EHMANN et R OMANO, 2005]. Nous effectuons le test de Lil-
liefors sur l’échantillon formé par les erreurs relatives au Tableau 3.4 pour la recherche
tabou et le recuit simulé, ce qui donne deux échantillons chacune contient 400 observa-
tions. Les valeurs p des deux méthodes sont inférieures au niveau de signification (1%)
et l’hypothèse nulle de normalité est rejetée à 1% de niveau de signification. Alors, nous
concluons que les deux échantillons ne peuvent pas être considérés comme issus de la
même population avec distribution normale. Il est possible de valider ce résultat par un
diagramme de probabilité normale utilisant les données des deux échantillons comme re-
présenté dans la Figure 3.11, où une différence claire peut être observée entre l’ensemble
99
Chapitre 3. Problèmes d’ordonnancement à une machine avec effet
d’apprentissage et paramètres incertains
F IGURE 3.6 Variation de la moyenne des erreurs relatives en fonction des valeurs des
graines aléatoires dans le cas du recuit simulé.
des données et l’interpolation linéaire des ordres statistiques des échantillons des deux
métaheuristiques.
Comme l’hypothèse de normalité n’est pas satisfaite, nous proposons d’utiliser un
test d’hypothèse non paramétrique. La médiane est utilisée au lieu de la moyenne comme
paramètre statistique de comparaison et les deux hypothèses suivantes sont considérées :
Donc, nous utilisons le test de la somme des rangs de Wilcoxon pour évaluer la si-
gnification statistique de l’hypothèse nulle H0 que les échantillons sont extraits des po-
pulations avec des médianes égales contre l’hypothèse alternative H1 que les médianes
sont différentes [G IBBONS et C HAKRABORTI, 2003]. La valeur calculée de p est trouvée
supérieure au niveau de signification (0.02 > 0.01), ce qui reflète que le test a échoué de
rejeter l’hypothèse nulle à un niveau de signification de 1%. Nous concluons de ce test
d’hypothèse que la recherche tabou et le recuit simulé sont statistiquement très proches
en termes de qualité de solutions.
100
Chapitre 3. Problèmes d’ordonnancement à une machine avec effet
d’apprentissage et paramètres incertains
F IGURE 3.7 Variation de la moyenne des erreurs relatives en fonction des valeurs des
graines aléatoires dans le cas de la recherche kangourou.
F IGURE 3.8 Variation de l’écart type des erreurs relatives en fonction des valeurs des
graines aléatoires dans le cas de la recherche tabou.
101
Chapitre 3. Problèmes d’ordonnancement à une machine avec effet
d’apprentissage et paramètres incertains
F IGURE 3.9 Variation de l’écart type des erreurs relatives en fonction des valeurs des
graines aléatoires dans le cas du recuit simulé.
F IGURE 3.10 Variation de l’écart type des erreurs relatives en fonction des valeurs des
graines aléatoires dans le cas de la recherche kangourou.
102
Chapitre 3. Problèmes d’ordonnancement à une machine avec effet
d’apprentissage et paramètres incertains
3.6 Conclusion
103
Chapitre 3. Problèmes d’ordonnancement à une machine avec effet
d’apprentissage et paramètres incertains
3.7 Références
A BBASBANDY, S. et T. H AJJARI. 2009, «A new approach for ranking of trapezoidal fuzzy
numbers», Computers and Mathematics with Applications, vol. 57, no 3, p. 413–419. 79,
93
A L -T URKI , U., C. F EDJKI et A. A NDIJANI. 2001, «Tabu search for a class of single-machine
scheduling problems», Computers and Operations Research, vol. 28, no 12, p. 1223–
1230. 81
A LLAHVERDI , A. et F. A L -A NZI. 2006, «A pso and a tabu search heuristics for the assembly
scheduling problem of the two-stage distributed database application», Computers and
Operations Research, vol. 33, no 4, p. 1056–1080. 95
D ONG , Y. 2003, «One machine fuzzy scheduling to minimize total weighted tardiness, ear-
liness, and recourse cost», International Journal of Smart Engineering System Design,
vol. 5, no 3, p. 135–147. 75
E REN , T. 2009, «Minimizing the total weighted completion time on a single machine sche-
duling with release dates and a learning effect», Applied Mathematics and Computa-
tion, vol. 208, no 2, p. 355–358. 74
104
Chapitre 3. Problèmes d’ordonnancement à une machine avec effet
d’apprentissage et paramètres incertains
G LOVER , F. 1989, «Tabu search-part i», ORSA Journal on Computing, vol. 1, no 3, p. 190–
206. 80
G LOVER , F. 1990, «Tabu search-part ii», ORSA Journal on Computing, vol. 2, no 1, p. 4–32.
80
K LIR , G. J. et B. Y UAN. 1995, Fuzzy sets and fuzzy logic theory and applications, Prentice
Hall Press. 77
KOÇ , E. 2010, The bees algorithm theory, improvements and applications, thèse de docto-
rat, Université de Wales. 86
105
Chapitre 3. Problèmes d’ordonnancement à une machine avec effet
d’apprentissage et paramètres incertains
L IAO, L. M. et C. J. L IAO. 1998, «Single machine scheduling problem with fuzzy due date
and processing time», Journal of the Chinese Institute of Engineers, vol. 21, no 2, p. 189–
196. 75
M ATARAZZO, B. et G. M UNDA. 2001, «New approaches for the comparison of l-r fuzzy
numbers : a theoretical and operational analysis», Fuzzy Sets and Systems, vol. 118, no 3,
p. 407–418. 78
P RADE , H. 1979, «Using fuzzy set theory in a scheduling problem : a case study», Fuzzy
Sets and Systems, vol. 2, no 2, p. 153–165. 75
RUDEK , R. 2013, «A note on proving the strong np-hardness of a scheduling problem with
position dependent job processing times», Optimization Letters, vol. 7, no 3, p. 613–616.
74
S ALHI , S. 2002, «Defining tabu list size and aspiration criterion within tabu search me-
thods», Computers and Operations Research, vol. 29, no 1, p. 67–86. 82
S CHULTMANN , F., M. F RÖHLING et O. R ENTZ. 2006, «Fuzzy approach for production plan-
ning and detailed scheduling in paints manufacturing», International Journal of Pro-
duction Research, vol. 44, no 8, p. 1589–1612. 75
S MITH , W. E. 1956, «Various optimizers for single stage production», Naval Research Lo-
gistics, vol. 3, no 1-2, p. 59–66. 87
106
Chapitre 3. Problèmes d’ordonnancement à une machine avec effet
d’apprentissage et paramètres incertains
WANG , C., D. WANG, W. H. I P et D. W. Y UEN. 2002, «The single machine ready time sche-
duling problem with fuzzy processing times», Fuzzy Sets and Systems, vol. 127, no 2, p.
117–129. 75
W ONGA , B. K. et V. S. L AI. 2011, «A survey of the application of fuzzy set theory in pro-
duction and operations management : 1998-2009», International Journal of Production
Economics, vol. 129, no 1, p. 157–168. 95
W OODS , J. R., R. M. S AYWELL et A. W. N YHUIS. 1992, «The learning curve and the cost of
heart transplantation», Health Services Research, vol. 27, no 2, p. 219–238. 73
W RIGHT, T. P. 1936, «Factors affecting the cost of airplanes», Journal of the Aeronautical
Sciences, vol. 3, no 4, p. 122–128. 73
W U , C. C., P. H. H SU, J. C. C HEN et N.-S. WANG. 2011, «Genetic algorithm for minimi-
zing the total weighted completion time scheduling problem with learning and release
times», Computers and Operations Research, vol. 38, no 7, p. 1025–1034. 75
YAGER , R. R. 1981, «A procedure for ordering fuzzy subsets of the unit interval», Informa-
tion Sciences, vol. 24, no 2, p. 143–161. 80
Y ELLE , L. E. 1979, «The learning curves : historical review and comprehensive survey»,
Decision Sciences, vol. 10, no 2, p. 302–328. 73
Z ADEH , L. A. 1971, «Similarity relations and fuzzy orderings», Information Sciences, vol. 3,
no 2, p. 177–200. 78
Z HAO, C. L., Q. L. Z HANG et H. Y. TANG. 2004, «Machine scheduling problems with lear-
ning effects», Dynamics of Continuous, Discrete and Impulsive Systems, Series A : Ma-
thematical Analysis, vol. 11, no 5-6, p. 741–750. 87
107
Chapitre 3. Problèmes d’ordonnancement à une machine avec effet
d’apprentissage et paramètres incertains
108
Chapitre 4
Blaise Pascal
Sommaire
4.1 Introduction et état de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
4.2 Présentation du cadre de modélisation floue . . . . . . . . . . . . . . . . . 116
4.2.1 Nombres flous . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
4.2.2 Mesures de possibilité . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
4.3 Déscription du problème d’ordonnancement . . . . . . . . . . . . . . . . 121
4.4 Présentation des métaheuristiques multi-objectifs à base de population 127
4.4.1 Algorithme génétique élitiste de tri non dominé . . . . . . . . . . . . 128
4.4.2 Algorithme recherche coucou . . . . . . . . . . . . . . . . . . . . . . 130
4.4.3 Stratégies de tri non dominé . . . . . . . . . . . . . . . . . . . . . . . 135
4.5 Expérimentation numérique et résultats . . . . . . . . . . . . . . . . . . . 136
4.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
4.7 Références . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
109
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
110
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
Dans le but d’avoir un taux de production élevé, les stratégies d’ordonnancement ont
été le sujet d’une analyse condensée comme elles constituent la liaison entre les stocks
de la matière première, les outils de fabrication et la clientèle ciblée [P INEDO, 2009].
En effet, les problèmes d’ordonnancement ont déclenché pendant ces dernières années
un nombre colossal de travaux de recherche à cause de leur adaptabilité au traitement
mathématique. Les efforts initiaux dédiés à la résolution des problèmes d’ordonnance-
ment faciles ont élargi la vision sur des problèmes plus sophistiqués avec des critères et
contraintes plus sévères [G UPTA et K YPARISIS, 1987]. Le problème d’ordonnancement à
une machine a joué un rôle clé sur le niveau théorique que pratique pour les raisons sui-
vantes : abondance de cas réels avec une seule ressource, possibilité d’agrégation des ma-
chines multiples en une seule machine et facilitation de la compréhension des problèmes
plus compliqués à machines multiples [A L -T URKI et collab., 2001].
Traditionnellement, les problèmes d’ordonnancement à une machine ont été intro-
duits en pratique avec l’hypothèse de satisfaire un objectif unique. Mais sous la pression
des contraintes des marchés de nos jours, il est primordial de prendre des décisions à
multiples facettes, ce qui a stimulé les gestionnaires à utiliser plus qu’une seule mesure de
performance dans l’évaluation des ordonnancements dans un contexte plus vaste connu
sous le nom de problèmes d’ordonnancement multi-objectifs. Dans ce cas, il est très rare
qu’une configuration optimise à la fois tous les objectifs et pour cela, un compromis entre
les critères de performance devient inévitable. Comme résultat, plusieurs solutions opti-
males sont offertes aux gestionnaires pour un choix flexible dépendant de la situation
économique rencontrée [H OOGEVEEN, 2005]. Dans le modèle standard d’ordonnance-
ment à une machine, la classification la plus répondue est celle basée sur la considération
des dates échues dans la formulation de la fonction objectif. Dans la première classe, les
objectifs sont fonction des durées opératoires des tâches. La minimisation de ces critères
conduit à une meilleure utilisation des ressources de système. Par exemple, la minimisa-
tion de la somme pondérée des dates de fin est un problème classique résolu à l’optima-
lité en classant les tâches selon la règle WSPT. Le poids d’une tâche peut exprimer un coût
de maintien par unité de temps dans le stock. La deuxième classe des objectifs dépendant
des dates échues des tâches est perçue comme une mesure des coûts associés aux ser-
vices fournis aux clients. Par conséquent, en considérant la minimisation conjointe des
critères appartenant à des classes différentes, il sera plus raisonnable d’établir des outils
d’ordonnancement fiables.
Avec l’accroissement des marchés actuels aux niveaux national et international, la ma-
jorité des systèmes de production sont sujets à des hautes pressions pour réduire le dé-
lai de mise en oeuvre et pour respecter les délais spécifiés par les clients [L I et collab.,
2011]. Les transactions de ventes sont influées par la capacité du producteur à livrer la
marchandise au client à une date bien définie. Cette vision étroitement liée au paradigme
Juste À Temps (en anglais JIT) motive les gestionnaires à se concentrer sur des nouvelles
approches d’ordonnancement plus efficaces en termes de la manipulation des coûts re-
latifs à l’indemnisation des clients suite à la violation des dates échues. Une étude sur les
pratiques de fabrication a démontré que la satisfaction des dates échues en gardant un
niveau faible de stock est l’objectif le plus important ciblé par les entreprises [S INGH et
A HUJA, 2012]. Parmi les critères basés sur la date échue nous trouvons la somme pondérée
du nombre de tâches en retard qui est considérée une mesure flexible comme elle est uti-
lisée pour différencier les clients. La satisfaction des tâches en retard engendre des coûts
supplémentaires au niveau de l’entreprise à cause du payement des frais élevés pour les
111
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
employées hors les horaires de travail normaux. De plus, la productivité peut être réduite
en raison de la surexploitation des ouvriers pendant leurs jours de repos. Il a été démon-
tré par Karp que la minimisation de cette mesure est NP-difficile au sens ordinaire [K ARP,
1972]. Donc, ce problème est pseudo polynômial ce qui¡ permet¢ sa résolution par une
P
méthode de programmation dynamique en un temps O n p j ¡. Par contre, ¢ la version
non pondérée du problème peut être résolue à l’optimalité en O n × log (n) utilisant le
fameux algorithme de Moore-Hodgson [L AWLER et M OORE, 1969]. Malgré la simplicité
apparente de ce problème d’ordonnancement à une machine, il a été traité sous plu-
sieurs situations. Par exemple, Potts et Wassenhove ont relaxé la contrainte d’intégrité
à une formulation avec variables binaires et ont résolu¡ le problème
¢ de programmation
linéaire résultant par un algorithme de complexité O n × log (n) . La borne inférieure cal-
culée est adoptée dans une procédure de réduction pour élaborer une approche par sé-
paration et évaluation efficace même lorsque appliquée aux grandes instances [P OTTS
et VAN WASSENHOVE, 1988]. Dauzère-Pérès a étudié le cas général où les dates de dis-
ponibilité et différentes dates échues sont incluses. Une borne inférieure efficace basée
sur la relaxation de la formulation du programme linéaire mixte en nombres entiers du
problème a été proposée. L’auteur a proposé également une nouvelle heuristique et a
comparé ses performances avec la procédure de la borne inférieure où l’heuristique a
indiqué des meilleures performances en termes de qualité et temps de calcul [D AUZÈRE -
P ÉRÈS, 1995]. Dans [B RUCKER et KOVALYOV, 1996], la somme pondérée du nombre de
retards a été étudié par Brucker et Kovalyov sous l’hypothèse que la totalité des tâches
est partitionnée en lots. Les auteurs ont présenté un algorithme ¡ 3de
¢ programmation dy-
namique résolvant le problème avec poids égaux en temps O n . L’application de cet
algorithme au problème avec poids échelonnés donne un schéma d’approximation po-
lynômial pour le problème original. Dauzère-Pérès et Sevaux ont introduit la notion de
la séquence maître pour dériver une formulation originale de la programmation linéaire
mixte en nombres entiers. Ils ont donné un algorithme de relaxation lagrangienne per-
mettant d’obtenir les bornes supérieures et inférieures où les expériences numériques
ont montré que l’approche proposée est capable de résoudre le problème avec une taille
de 100 tâches [D AUZÈRE -P ÉRÈS et S EVAUX, 2003]. En outre, M’Hallah et Bulfine ont pro-
posé une heuristique ainsi qu’un algorithme exact basé sur la procédure de séparation et
évaluation avec les bornes obtenues par une représentation à base du problème de sac à
dos. Les expérimentations réalisées ont indiqué que toutes les deux approches résultent
en des performances très compétitives avec des instances allant jusqu’à 2500 tâches dans
un temps réduit [M’H ALLAH et B ULFIN, 2003]. Sevaux et Dauzère-Pérès ont conçu un
algorithme génétique où trois stratégies différentes pour l’évaluation de la fonction ob-
jectif des individus, quatre types d’opérateurs de croisement et trois types d’opérateurs
de mutation ont été employés pour obtenir la meilleure configuration de l’algorithme.
L’algorithme génétique obtenu est amélioré par application d’une recherche locale et ini-
tialisation de la population avec des solutions de bonne qualité [S EVAUX et D AUZÈRE -
P ÉRÈS, 2003]. Cheng et ses collègues ont étudié un modèle de faisabilité d’ordonnance-
ment multi-agent où la fonction objectif de chaque agent est de minimiser la somme pon-
dérée du nombre des tâches en retards. Ils ont montré que lorsque le nombre d’agents est
fixé, le problème peut être résolu dans un temps pseudo polynômial pour des poids en-
tiers et dans un temps polynômial pour des poids unitaires [C HENG et collab., 2006]. Le
travail de M’Hallah et Bulfine a montré que l’heuristique proposée est bonne et très rapide
pour les problèmes non pondérés. La méthode exacte proposée résout rapidement tous
les problèmes non pondérés non résolus au préalable. Elle permet également de résoudre
les grands problèmes exploités à nos jours. Leurs résultats ont prouvé que l’algorithme est
112
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
robuste en termes du type de problème ainsi que les niveaux de ses paramètres [M’H AL -
LAH et B ULFIN , 2007]. Shabtay et Steiner ont étudié des modèles d’ordonnancement bi-
critères avec des durées opératoires contrôlables convexes, coûts de consommation de
ressources et des dates échues affectées par les méthodes CON et SLK. Pour chaque mé-
thode d’affectation des dates échues, les auteurs ont fourni une analyse bi-critère. Le pre-
mier critère est de minimiser la somme pondérée du nombre de retards plus les coûts
d’affectation des dates échues et le deuxième critère est de minimiser la somme pon-
dérée des consommations des ressources [S HABTAY et S TEINER, 2011]. Dans le contexte
de la gestion des chaînes logistiques, Rasti-Barzoki et Hejazi ont étudié un modèle d’or-
donnancement qui considère à la fois l’affectation des dates échues, ordonnancement
de la production et livraison du produit. Le problème de minimiser la somme des coûts
de livraison en lots dans une chaîne d’approvisionnement est modélisé comme un pro-
gramme en nombre entier, une heuristique et une approche par séparation et évaluation
ont été présentées pour la résolution où les performances sont sensibles à quelques pa-
ramètres du problème, sa structure et sa taille [R ASTI -B ARZOKI et H EJAZI, 2013]. De plus,
Dauzère-Pérès et Mönch ont considéré une machine unique opérant en lots avec des fa-
milles de tâches incompatibles où deux formulations différentes à base de la program-
mation linéaire mixte en nombres entiers ont été développées. La première formulation
a comme inconvénient la nécessité d’introduire un coefficient M ayant une grande va-
leur (méthode du grand M). Les expérimentations ont montré que les deux formulations
sont capables de trouver des solutions proches de l’optimale en un temps raisonnable
pour les instances de petites et moyennes tailles mais le gap peut être aussi grand dans
le cas des instances de grande taille. La deuxième formulation est capable de trouver des
meilleures bornes inférieures en comparaison avec la première approche tandis que cette
dernière donne des meilleures bornes supérieures [D AUZÈRE -P ÉRÈS et M ÖNCH, 2013].
Malgré qu’un grand nombre de travaux cumulé concernant les problèmes d’ordonnan-
cement avec différentes contraintes est disponible, le nombre d’articles réservé à l’état
de l’art de minimisation de la somme pondérée du nombre de retards dans le cas des
paramètres réels est limité. Les lecteurs intéressés peuvent consulter ( [M UNDT et W ICH,
2007] et [A DAMU et A DEWUMI, 2014]). Une analyse vigilante de la structure interne des
systèmes de production permet de distinguer deux ressources de variabilité dans les don-
nées d’ordonnancement : variation déterministe et variation stochastique. La variation
déterministe est produite en générale à cause d’un effet ayant un comportement mo-
notone telle que le phénomène de vieillissement ou d’apprentissage. L’effet d’apprentis-
sage a été présenté pour la première fois par Wright qui a démontré que le coût unitaire
dans l’industrie d’avions décroît lorsque les firmes produisent plus d’unités ou acquirent
d’avantage d’expérience [W RIGHT, 1936]. Il est à mentionner qu’une littérature riche sur
les problèmes d’ordonnancement polynômiaux à une machine avec effet d’apprentissage
est disponible ( [Y IN et collab., 2012], [W U et L EE, 2008], [J ANIAK et RUDEK, 2010], [L AI et
L EE, 2011] et [WANG et collab., 2012]). En général, les papiers traitant les approches po-
lynômiales de ces problèmes partagent un aspect commun dans le sens de proposer une
nouvelle formule d’apprentissage et par la suite déterminer les conditions sous lesquelles
les règles d’optimalité conventionnelles restent valables. Le travail récent de Rudek a été
consacré au problème d’ordonnancement à une machine avec effet d’apprentissage basé
sur la somme des durées opératoires. L’auteur a prouvé que ce problème est fortement
NP-difficile en utilisant le problème de Partition et il a implémenté un algorithme par
séparation et évaluation pour traiter de manière optimale des instances modérées ayant
jusqu’à 25 tâches [RUDEK, 2017]. Quelques études relatives à la classification et la résolu-
tion des problèmes d’ordonnancement avec durées opératoires variables sont présentées
113
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
114
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
sur une vision unique d’incertitude dans le sens que l’incertitude des paramètres et l’ef-
fet d’apprentissage sont manipulés séparément. Malgré que nous sommes au courant de
l’existence de quelques études intégrant ces deux aspects dans le même contexte de mo-
délisation, ces contributions sont établies dans un cadre mono objectif, ce qui limite leur
application en pratique. Par exemple, Ahmadizar et Hosseini ont proposé un problème
d’ordonnancement à une machine avec la considération des durées opératoires floues et
effet d’apprentissage à base de position. Les valeurs affectées aux durées opératoires sont
supposées d’allure triangulaire. Comme l’objectif est de minimiser la somme des dates
de fin, la procédure de solution est basée sur l’extension de la règle SPT pour supporter
les durées opératoires incertaines [A HMADIZAR et H OSSEINI, 2011]. Les mêmes auteurs
ont étudié le problème d’ordonnancement à une machine avec effet d’apprentissage à
base de position et durées opératoires floues où l’objectif est de minimiser le makespan.
Deux algorithmes polynômiaux ont été développés pour ce problème en se basant sur la
programmation par contraintes stochastiques floues et une méthode de classement de
nombres flous. Les simulations numériques résultent en des performances équivalentes
[A HMADIZAR et H OSSEINI, 2013]. Dans [B ENTRCIA et M OUSS, 2015], les auteurs ont ex-
ploité l’effet d’apprentissage et les paramètres flous avec l’objectif de minimiser la somme
pondérée des dates de fin d’exécution des tâches. Dans ce contexte, ils ont généralisé la
règle de Smith au cas flou en redéfinissant le concept d’agréabilité ordinaire. En outre,
trois métaheuristiques à base de trajectoire ont été implémentées et appliquées pour ré-
soudre le cas avec dates de disponibilité floues différentes. Les tests statistiques non para-
métriques ont été adoptés dans la comparaison des performances des métaheuristiques
proposées. Aydilek et al ont considéré un système de fabrication à machine unique dans
le but de minimiser le nombre de tâches en retard pour lesquelles les durées opératoires
sont données dans certains intervalles pour exprimer l’incertitude. Sur la base d’une re-
lation de dominance globale, plusieurs alternatives de résolution ont été évaluées et les
expérimentations numériques ont révélé que l’algorithme Updated Sequence (US) est le
plus approprié par rapport aux autres versions [AYDILEK et collab., 2017].
Dans ce chapitre, nous conduisons une analyse comparative basée sur les perfor-
mances de deux métaheuristiques : l’algorithme génétique élitiste de tri non dominé et la
recherche coucou combinée avec une procédure de recherche locale. Le problème d’or-
donnancement est formulé comme un problème d’optimisation bi-objectif où les critères
de performances sont notés par la magnitude de la somme pondérée des dates de fin flous
et la somme pondérée des possibilités des retards des tâches. Même avec des données
réelles, ce problème a une importance cruciale car le premier objectif exprime la configu-
ration efficace des ressources internes du système de production et le deuxième objectif
reflète l’état de satisfaction du client envers la qualité de service délivré. Dans ce contexte,
nous considérons l’effet d’apprentissage ainsi que l’aspect flou au niveau des durées opé-
ratoires et dates échues dans le même modèle. À notre connaissance, ce problème est
introduit pour la première fois. Dans le but de générer les instances, nous proposons une
extension de la méthode conventionnelle pour le support des nombres flous. L’améliora-
tion de la recherche coucou par des procédures de recherche locale et vol de Lévy a été
utilisée pour garantir un compromis entre l’intensification et la diversification de la re-
cherche. Le reste de ce chapitre est organisé comme suit. Dans la Section 4.2, quelques
définitions formelles associées aux concepts de base des nombres flous et théorie de pos-
sibilité sont illustrées. La Section 4.3 est dédiée à la formulation du problème ainsi que sa
complexité intrinsèque. Nous décrivons dans la Section 4.4 les deux approches à base de
population utilisées dans ce chapitre. Nous présentons dans la Section 4.5 les expérimen-
tations numériques pour évaluer les performances des stratégies proposées et nous com-
115
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
parons leur signification statistique. La Section 4.6 résume les principales contributions
et énumère quelques recommandations potentielles pour des futures améliorations.
Définition 4.1. Un nombre flou est un ensemble flou ũ : R → [0, 1] ayant les propriétés
suivantes :
i) ũ est normal, i.e. ∃x 0 ∈ R avec ũ (x 0 ) = 1 ;
ii) ũ est un ensemble flou convexe (i.e. ũ λx + (1 − λ) y ≥ min ũ (x) , ũ y ∀x, y ∈
¡ ¢ © ¡ ¢ª
R, ∀λ ∈ [0, 1]) ;
iii) ũ est semi continu supérieur sur R ;
iv) {x 0 ∈ R : ũ (x) > 0} est un ensemble compact, avec {} est la fermeture de l’ensemble.
Définition 4.2. Un nombre flou à est dit de type L-R si sa fonction d’appartenance a la
forme :
³ a−x ´
L αÃ
pour x ≤ a
µÃ (x) = 1 pour a ≤ x ≤ ā (4.1)
³ ´
R x−ā
pour x ≥ ā
βÃ
116
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
1. Les paramètres αà et βà , connus sous le nom de déviations gauche et droite de la fonction
d’appartenance, sont des nombres réels non négatifs.
Une forme spéciale de l’allure des fonctions L et R est donnée par la loi de puissance :
p
© ª
L (z) = max 0, 1 − z 1
(4.2)
R (z) = max 0, 1 − z p 2
© ª
avec p 1 , p 2 ≥ 1.
Si p 1 = p 2 = 1, les fonctions deviennent linéaires et donnent les nombres flous trapé-
zoïdaux connus également sous le nom des intervalles flous. Cette définition est très
générale et permet la modélisation de plusieurs types d’information :
(a, a, 0, 0)L−R ∀L, ∀R pour un nombr e r éel a
à = ¡ ¢ £ ¤
a, ā, 0, 0 ∀L, ∀R pour un i nt er v al l e r éel a, ā
L−R
Le principe d’extension introduit par Zadeh joue un rôle prépondérant dans la géné-
ralisation des applications définies sur R vers des applications définies sur des ensembles
flous F. Les opérations arithmétiques élémentaires dans le cas flou peuvent être déduites
des opérations classiques opérant sur des nombres réels [T ZAFESTAS et V ENETSANOPOU -
LOS , 1994].
Définition 4.3. Soit X le produit cartésien des espaces X 1 , X 2 ,..., X r et A1 , A2 ,..., Ar sont r
ensemble flous de X 1 , X¡ 2 ,...,
¢ ©X r respectivement.
ª Soit f une application de X sur l’espace Y, i.e.
y = f (x 1 , ..., x r ) et f −1 y = x ∈ X/ f (x) = y . Alors, le principe d’extension permet d’induire
des r ensembles flous Ai , un ensemble flou B de Y par f comme suit :
f −1 y 6= φ
¡ ¢
sup min {A1 (x 1 ) , ..., Ar (x r )} si
¡ ¢
y= f (x 1 ,x 2 ,..,x r )
B y = ∀y ∈ Y (4.3)
f −1 y = φ
¡ ¢
0 si
Il est possible de généraliser les opérations unaires et binaires sur les nombres flous
en concentrant sur les cas particuliers r = 1 et r = 2. Soient M, N ∈ F (R) deux élements
de l’espace des nombres flous F et ◦ : R × R → R une opération binaire. Si nous notons
l’opération généralisée par ◦˜ , la relation M˜◦N represente un ensemble flou de R avec la
fonction d’appartenance :
si (◦)−1 (z) 6= φ
© ¡ ¢ª
sup min M (x) , N y
z=x◦y
(M˜◦N) (z) = ∀z ∈ R (4.4)
0 si (◦)−1 (z) = φ
117
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
Au contraire à la structure de l’ensemble des réels R pour lequel un ordre total existe,
il est très difficile de comparer des nombres flous représentés par des distributions de
possibilité car ils peuvent se chevaucher. Cependant, une alternative efficace consiste
en l’utilisation des fonctions de classement pour établir un ordre comme proposée dans
[J AIN, 1976]. Cette approche attache à chaque nombre flou un point sur la ligne réelle R,
ce qui rend la comparaison possible. Deux relations de dominance sont élaborées dépen-
damment de la localisation relative des nombres flous. La dominance forte caractérise
des nombres flous complètement distincts tandis que la dominance faible caractérise
des nombres flous chevauchés en utilisant les fonctions de classement. Une définition
formelle de la dominance faible est présenté ci-dessous [Ö ZELKAN et D UCKSTEIN, 1999].
En réponse aux limites des fonctions de classement existantes qui sont dans certains
cas en contradiction avec l’intuition humaine ou bien ne sont pas discriminantes, Aba-
sabandy et Hajjari ont proposé une nouvelle approche pour le classement des nombres
flous trapézoïdaux en se basant sur les déviations gauche et droite à une certaine coupe γ
du nombre flou trapézoïdal [A BBASBANDY et H AJJARI, 2009]. Le calcul de cette méthode
est détaillé dans la définition suivante.
Définition 4.5. La magnitude d’un nombre flou arbitraire à = a, ā, αà , βà L−R avec forme
¡ ¢
γ=1
paramétrique A γ , Ā γ est donnée par Mag à = 12 A γ + Ā γ + a + ā f γ d γ où
£ ¡ ¢ ¡ ¢¤ ¡ ¢ R ¡ ¡ ¢ ¡ ¢ ¢ ¡ ¢
γ=0
γ=1
f γ d γ = 12 .
R ¡ ¢
la fonction f est une fonction décroissante sur [0, 1] avec f (0) = 0, f (1) = 1 et
γ=0
Il est à noter que si f est égale à 1 (au sens des fonctions) et seulement les bornes des
coupes γ sont considérées, alors l’expression de la magnitude se réduit à la formule pro-
posée initialement par Yager [YAGER, 1981].
Comme la capacité des nombres flous plats (intervalles flous) ayant des fonctions
d’appartenance non linéaires à représenter les variables linguistiques est plus grande
[B OJADZIEV et B OJADZIEV, 1996], le Corollaire suivant donne l’expression explicite de la
magnitude d’un nombre flou plat avec p 1 = p 2 = 2 pour les fonctions L et R.
Démonstration.
En substituant les bornes de la forme paramétrique dans l’expression générale de la
Définition 4.5, nous obtenons :
γ=1
Mag à = 12 a − αà 1 − γ + ā + βà 1 − γ + a + ā f γ d γ
¡ ¢ R ¡ p p ¢ ¡ ¢
γ=0
Si nous considérons la forme simple de f ( f γ = γ) nous pouvons écrire :
¡ ¢
118
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
γ=1
Mag à = 12 2a + 2ā − αà − βà 1 − γ γd γ
¡ ¢ R ¡ ¡ ¢p ¢
γ=0
γ=1 ¢ γ=1
Mag à = 12 2a + 2ā γd γ − 12 αà − βà γ 1 − γ dγ
¡ ¢ R ¡ ¢ ¡ R ¡ p ¢
γ=0 γ=0
γ=1 µ 3 ¶¯γ=1
2(3γ+2)(1−γ) 2 ¯¯
Mag à = 12 2a + 2ā γd γ − 1
αà − βÃ
¡ ¢ R ¡ ¢ ¡ ¢
2
− 15
γ=0 γ=0
¯
Mag à = 12 a + ā − 15
¢ 2 ¡
αà − βÃ
¡ ¢ ¡ ¢
Définition 4.6. Soient X un ensemble universel et ξ une famille des sous ensembles de X
non vide, la mesure floue sur 〈X, ξ〉 est une fonction g : ξ → [0, 1] qui satisfait les conditions
suivantes :
i) g φ = 0 ∧ g (X) = 1 ;
¡ ¢
Définition 4.7. Soit Pos une ¶ floue sur 〈X, ξ〉. Alors, Pos est dite une mesure de possi-
µ mesure
bilité si et seulement si Pos ∪ Ak = sup Pos (Ak ) pour toute famille {Ak /k ∈ K} dans ξ telle
k∈K k∈K
que ∪ Ak ∈ ξ, où K est un ensemble d’indices arbitraires.
k∈K
Théorème 4.1. Toute mesure de possibilité Pos sur l’ensemble puissance fini P (X) est uni-
quement detrminée par une fonction de distribution de possibilité r : X → [0, 1] via la for-
mule Pos (A) = max r (x) pour tout A ∈ P (X).
x∈A
La mesure de possibilité est directement liée aux ensembles flous à travers les fonc-
tions de distribution de possibilité associées. L’événement "la variable Ξ prend la valeur
ξ dans un ensemble universel Σ" est donnée par l’équation Ξ = ξ. Une contrainte flexible
H est imposée sur Σ limitant ainsi les valeurs affectées à Ξ. L’assertion H(ξ) peut être in-
terprétée comme le degré de compatibilité de ξ avec la contrainte décrite par H. Mais
119
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
en incluant la proposition "Ξ est H", il sera plus approprié d’interpréter H(ξ) comme le
degré de possibilité que Ξ = ξ. Cette interprétation de la possibilité d’un événement est
en générale moins expressive en comparaison avec les probabilité mais utilisant moins
d’informations [D UBOIS et collab., 2004].
Définition 4.8. Soient H un ensemble flou sur Σ et la proposition "Ξ est H", la possibilité
r H (ξ) de Ξ = ξ est numériquement égale au degré H(ξ) pour lequel ξ appartient à H pour
tout ξ ∈ Σ. La mesure de possibilité associée Pos H est définie pour tout A ∈ P (Σ) par l’équa-
tion :
Comme une discrimination quantitative claire entre les nombres flous ne peut pas
être achevée dans certains cas (tels que l’intersection des parties croissantes ou décrois-
santes des fonctions d’appartenance) utilisant uniquement les opérateurs généralisés
m ãx et m i˜n, des approches plus efficaces peuvent être développées en se basant sur les
mesures de possibilité comme indiqué par les définitions suivantes [D UBOIS et P RADE,
1988].
Définition 4.9. Soient P et Q deux quantités floues. Pour déterminer si P est supérieur à
Q, la comparaison des deux ensembles P et ]Q, +∞] par la possibilité d’un évènement flou
au sens de µP , de l’évènement flou ]Q, +∞] est faite. Dans ce contexte, on obtient l’indice
fondamental de comparaison suivant :
³ ¤´
ΠP (]Q, +∞]) = sup min µP (u) , inf 1 − µQ (v) = sup inf min µP (u) , 1 − µQ (v)
£ ¡ £ ¤¢
(4.6)
u v≥u u v≥u
Si X et Y sont les variables associées avec les domaines controlés par µP et µQ respecti-
vement, alors cet indice peut être interprété comme la possibilité que les valeurs maxi-
males
¡ que¢ X peut prendre sont supérieures aux valeurs maximales que Y peut prendre
Pos X̄ > Ȳ . Le calcul explicite de la valeur de cet indice se réduit à trouver les cor-
données des points d’intersection des parties extrèmes droites des fonctions ³ d’apparte-
´
nances µP et µQ . Pour des nombres flous du type L-R donnés par P = p, p̄, αP , βP
³ ´ ³ ´ ³ ´ L−R
z−p̄ z−q̄
et Q = q, q̄, αQ , βQ , la résolution de l’équation f (z) = 1 − βP − βQ = 0 donne
L−R
∗ βQ βP +βQ p̄+βP q̄
z = βP +βQ
.
Corollaire 4.2. Pour des nombres flous trapézoïdaux ( L (z) = R (z) = max (0, 1 − z)), en sub-
stituant la valeur de z ∗ dans µQ , on obtient l’expression suivante pour le degré de possibilité
en fonction des valeurs des déviations et modales des nombres flous :
p̄ − q̄ + βP
µ µ ¶¶
¡ ¢
Pos X̄ > Ȳ = max 0, min 1, (4.7)
βP + βQ
Sans grande difficulté, il est possible d’étendre la formule précédente de possibilité (ob-
tenue pour le cas trapézoïdal) au cas où l’allure des fonctions d’appartenance est donnée
par un polynôme de deuxième degré (allure parabolique).
¡ Pour
Corollaire 4.3.
2
¢des nombres flous plats (intervalles flous) d’allure parabolique (L (z) =
R (z) = max 0, 1 − z ), l’expression du degré de possibilité en fonction des paramètres de
120
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
déviations gauche et droite ainsi que les paramètres modaux associés aux nombres flous est
comme suit :
p̄ + βP ≤ q̄
¡¡ ¢ ¢
0 si
p̄ ≥ q̄ + βQ
¡ ¡ ¢¢
1 si
¡ ¢
Pos X̄ > Ȳ = (4.8)
1 − z1 −p̄ 2 si ¡z ∈ ¡£p̄, p̄ + β ¤ ∩ £q̄, q̄ + β ¤¢¢
³ ´
βP 1 P Q
1 − z2 −p̄ 2 si ¡z ∈ ¡£p̄, p̄ + β ¤ ∩ £q̄, q̄ + β ¤¢¢
³ ´
βP 2 P Q
avec z 1 et z 2 représentent les solutions de l’équation du seconde ordre donnée par g (z) =
z−p̄ 2 z−q̄ 2
³ ´ ³ ´
1 − βP − βQ = 0.
Démonstration.
Comme les deux parties gauche et droite des fonctions d’appartenance ont une allure
parabolique, les cordonnées des points d’intersection des fonctions d’appartenance ne
sont que les racines de l’équation du deuxième ordre :
z−p̄ 2 z−q̄ 2
³ ´ ³ ´
g (z) = 1 − βP − βQ = 0. La résolution de cette équation utilisant la méthode
classique du discriminant permet d’avoir les expressions explicites des racines z 1 et z 2
comme indiqué ci-dessous :
rn³ ´ o
2
β2Q p̄+β2P q̄−βP βQ β2Q +β2P −(p̄−q̄ )
z1 =
β2P +β2Q
rn³ ´ o
2 2 2
βQ p̄+βP q̄+βP βQ β2Q +β2P −(p̄−q̄ )
z2 =
β2P +β2Q
β
¡¡ ¢ ¢
0 si p̄ + P ≤ q̄
p̄ ≥ q̄ + βQ
¡ ¡ ¢¢
1 si
¡ ¢
Pos X̄ > Ȳ =
z 1 −p̄ 2
³ ´
β β
¡ ¡£ ¤ £ ¤¢¢
1 − β P
si z 1 ∈ p̄, p̄ + P ∩ q̄, q̄ + Q
1 − z2 −p̄ 2 si ¡z ∈ ¡£p̄, p̄ + β ¤ ∩ £q̄, q̄ + β ¤¢¢
³ ´
βP 2 P Q
121
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
l’ensemble des tâches est à exécuter sur une ressource unique. Des contraintes addition-
nelles sur l’évaluation des deux fonctions objectifs sont incluses pendant la procédure
d’optimisation. La formulation du problème est élaborée en se basant sur les hypothèses
suivantes :
Les notations suivantes sont utilisées pour décrire notre problème d’ordonnancement à
une machine avec paramètres incertains :
• n : Nombre de tâches ;
• p̃ i : Durée opératoire de tâche i (i = 1, 2, ..., n) ;
• C̃i : Date fin d’exécution de tâche i (i = 1, 2, ..., n) ;
• d˜i : Date échue de tâche i (i = 1, 2, ..., n) ;
• J : Ensemble de tâches avec Car d (J) = n ;
• ωi : Coefficient de pénalité de tâche i associé à la somme pondérée des possibilités
de retard ;
0
• ωi : Coefficient de pénalité de tâche i associé à la somme pondérée des dates de fin
d’exécution ;
• Le f f : Facteur d’apprentissage.
Comme la durée opératoire et la date échue d’une tâche i sont considérées comme
des paramètres flous, nous proposons de modéliser l’incertitude au niveau de ces para-
mètres utilisant des fonctions d’appartenance (fonctions L et R) d’allure parabolique. En
effet, les nombres flous plats ont été utilisés dans plusieurs problèmes pratiques pour la
modélisation convenable des paramètres incertains (voir par exemple [G UPTA et collab.,
2013] et [E BRAHIMNEJAD, 2016]). Par conséquent, la fonction d’appartenance générique
des durées opératoires floues est donnée par :
³ p −x ´2
i
1 − pour x ≤ p
αp̃ i
i
µp̃ i (x) = 1 pour p ≤ x ≤ p̄ i
i
(4.9)
1 − x−p̄ i 2 pour x ≥ p̄
³ ´
βp̃ i i
122
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
µ ¶2
d i −x
pour x ≤ d i
1 − αd˜
i
µd˜i (x) = 1 pour d i ≤ x ≤ d¯i (4.10)
µ ¶2
d¯i
1 − x− pour x ≥ d¯i
β˜ di
D’une façon équivalente, une notation plus compacte peut être³ obtenue comme ´ un
quadruplet (représentation L-R) pour les deux paramètres p̃ i = p , p̄ i , αp̃ i , βp̃ i et
³ ´ i L−R
d˜i = d i , d¯i , αd˜i , βd˜i . En pratique, la détermination exacte des valeurs de déviations
L−R
gauche/droite et la valeur modale nécessite l’intervention des experts [B UCKLEY, 2005].
Dans le cadre de notre problème d’ordonnancement bi-objectif, nous considérons que la
durée opératoire floue actuelle d’une tâche est affectée par la position de la tâche dans la
séquence selon le modèle d’apprentissage de Biskup donné dans le cas déterministe par
[B ISKUP, 1999] :
p iA = i Le f f × p i (4.11)
Utilisant le principe d’extension pour les durées opératoires floues nous pouvons écrire :
³ ´
p̃ iA = i Le f f ⊗ p̃ i = i Le f f × p̄ i , i Le f f × p , i Le f f × αp̃ i , i Le f f × βp̃ i (4.12)
i L−R
Avant de calculer les deux fonctions objectifs, nous avons besoin d’obtenir les expressions
des dates de fin floues pour une tâche fixe i dans l’ordonnancement. La date fin floue
i i
d’exécution est calculée par la formule C̃i = ⊕ p̃ Aj = ⊕ j Le f f ⊗ p̃ j . Dans la notation
P P
j =1 j =1
à !
i i i i
Le f f Le f f Le f f Le f f
× αp̃ j , × βp̃ j
P P P P
L-R, nous avons C̃i = j ×p , j × p̄ j , j j . En se
j =1 j j =1 j =1 j =1
L−R
basant sur la notation L-R de la date fin floue C̃i , il est possible de déduire la possibilité
de retard exprimant le degré de la réalisation de l’évènement "la tâche i est en retard"
comme suit :
123
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
ÃÃ ! !
i i
j Le f f × p̄ j + j Le f f × βp̃ j ≤ d¯i
P P
0 si
j =1 j =1
à !
i
³ ´
j Le f f × p̄ j ≥ d¯i + βd˜i
P
1 si
j =1
¢ 2
Pos C̃i > d˜i = i
¡
L
x 1 − j e f f ×p̄ j
P
j =1
x 1 ∈ h 1 Le f f , p̃, d˜ , h̄ 1 Le f f , p̃, d˜
¡ £ ¡ ¢ ¡ ¢¤¢
1 − Pi si
L
j e f f ×βp̃ j
j =1
i
2
P Le f f
x 2 − j × p̄ j
j =1 ¡ £ ¡
˜ , h̄ 1 Le f f , p̃, d˜
¢ ¡ ¢¤¢
1 − si x ∈ h L , p̃, d
i
P Le f f
2 1 e f f
j
×βp̃ j
j =1
(4.13)
avec
h 1 Le f f , p̃, d˜ , h̄ 1 L ˜ =
£ ¡ ¢ ¡ ¢¤
e
Ã" f f , p̃, d # !
i i i h i
Le f f Le f f Le f f
× βp̃ j ∩ d¯i , d¯i + βd˜i
P P P
j × p̄ j , j × p̄ j + j
j =1 j =1 j =1
à ! à !2 à ! (à à !2 ! Ãà ! !2 ) 21
i Le f f i Le f f i L i L i L
β2˜ d¯i − j e f f ×βp̃ j βd˜ β2˜ + j e f f ×βp̃ j j e f f ×p̄ j −d¯i
P P P P P
j ×p̄ j + j ×βp̃ j −
di j =1 j =1 j =1 i di j =1 j =1
x1 = Ã !2
i Le f f
+β2˜
P
j ×βp̃ j
j =1 di
à ! à !2 à ! (à à !2 ! Ãà ! !2 ) 12
i L i L i L i L i L
β2˜ j ef f j ef f d¯i + j e f f ×βp̃ j βd˜ β2˜ + j ef f j ef f −d¯i
P P P P P
×p̄ j + ×βp̃ j ×βp̃ j − ×p̄ j
di j =1 j =1 j =1 i di j =1 j =1
x2 = Ã !2
i Le f f
+β2˜
P
j ×βp̃ j
j =1 di
Donc, la première fonction objectif est exprimée par la somme pondérée des possi-
iP
=n
bilités de retard des tâches dans l’ordonnancement ( ωi × Pos C̃i > d˜i ).
¡ ¢
i =1
Concernant la deuxième fonction objectif, la somme pondérée des dates de fin floues
d’exécution des tâches est exprimée par :
à ! à !
n 0 i n 0 i
ω × j L e f f × p , ωi × j Le f f × p̄ j ,
P P P P
i =1 i j i =1
n j =1 j =1
P 0
ωi ⊗ C̃i =
i =1
à ! à !
n 0 i n 0 i
Le f f Le f f
ωi × × αp̃ j , ωi × × βp̃ j
P P P P
j j
i =1 j =1 i =1 j =1
L−R
La formule finale de la deuxième fonction objectif exprimée par la magnitude de la
iP
=n 0
µ ¶
somme pondérée des dates de fin floues (Mag ωi ⊗ C̃i ) est donnée par :
i =1
124
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
à à ! à !!
n n i n i
µ ¶
0 0 0
ωi ⊗ C̃i = 12 ωi × j Le f f × p ωi × j Le f f × p̄ j
P P P P P
Mag +
i =1 i =1 j =1 j i =1 j =1
à à ! à !!
n 0 i n 0 i
2
ωi × j Le f f × αp̃ j − ωi × j Le f f × βp̃ j
P P P P
− 15
i =1 j =1 i =1 j =1
Il est à mentionner que les coefficients de pénalité sont choisis de telle sorte que
0
ωi > ωi , ce qui permet de refléter l’hypothèse économique que le coût de retard de li-
vraison d’une unité d’un produit au client est souvent supérieure au coût par unité de
temps par unité de produit engendré lors de la prolongation du séjour de cette unité
au sein du système de production. Dans ce qui suit, nous présentons deux théorèmes
annonçant
¯ la¯complexité des problèmes ¯ d’ordonnancements
¯ mono¶ objectifs donnés par
¯iP
=n iP
=n 0
µ
1 ¯¯Le f f , p̃ i , d˜i ¯¯ ωi × Pos C̃i > d˜i et 1 ¯¯Le f f , p̃ i ¯¯Mag ωi ⊗ C̃i respectivement.
¯ ¡ ¢ ¯ ¯
i =1 i =1
¯ ¯
¯iP
=n
˜
Théorème 4.2. Le problème 1 ¯Le f f , p̃ i , d i ¯¯ ωi × Pos C̃i > d˜i est NP-difficile au sens
¯ ¡ ¢
¯
i =1
fort.
Démonstration.
En premier, nous avons besoin de reformuler notre problème d’optimisation sous forme
décisionnelle.
Instance : Un ensemble fini de tâches J = {1, ..., n}. Pour chaque tâche j ∈ J, une durée
opératoire floue, une date échue floue, un coefficient de pénalité réel et un facteur
d’apprentissage sont associés. Une valeur fixe B (borne supérieure) est donnée pour
exprimer la taille de la contrainte.
iP
=n
ωi × Pos C̃i > d˜i ≤ B ?
¡ ¢
Question : Existe t’il un ordonnancement pour J tel que
i =1
Il¯ est facile ¯ d’observer que la version décisionnelle du problème
¯iP
=n
1 ¯¯Le f f , p̃ i , d˜i ¯¯ ωi × Pos C̃i > d˜i appartient à la classe NP car un algorithme (ma-
¯ ¡ ¢
i =1
chine de Turing) non déterministe nécessite seulement de prévoir une permutation des
tâches et de tester dans un temps polynômial si la somme pondérée des possibilités de
retard ne dépasse pas la taille de la contrainte B. ¯ ¯
¯ ¯iP=n
Maintenant, nous démontrons que le problème d’ordonnancement 1 ¯¯Le f f ¯¯ Ui peut
¯ ¯ i =1
¯iP=n
être réduit polynômialement à notre problème 1 ¯¯Le f f , p̃ i , d˜i ¯¯ ωi × Pos C̃i > d˜i . Nous
¯ ¡ ¢
¯ ¯ i =1
¯ ¯iP
=n
rappelons qu’une instance de 1 ¯¯Le f f ¯¯ Ui consiste d’un ensemble de tâches J = {1, ..., n},
i =1
durée opératoire positives p i , dates échues positives d i et facteur d’apprentissage Le f f
commun à toutes les tâches i ∈ J. Le retard d’une tâche i est défini par :
1 si Ci > d i
Ui =
0 si Ci ≤ d i
125
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
¯ ¯
0
³ ´ ¯iP
=n
= n, p̃ i =1,n , d˜i =1,n , ωi =1,n , Le f f du problème 1 ¯¯Le f f , p̃ i , d˜i ¯¯ ωi × Pos C̃i > d˜i
¯ ¡ ¢
Π
i =1
comme suit :
¡ ¢
p̃ i = p i , p i , 0, 0
d˜i = (d i , d i , 0, 0)
ω =1
i
Comme dans ce cas, les durés opératoires et les dates échues ¡ sont des para-
˜
¡ ¢ ¢
mètres réels, l’assertion suivante est vraie pour chaque tâche Pos C̃i > d i = Ui ⇒
iP
=n ¢ iP =n
µ ¶
ωi × Pos C̃i > d˜i =
¡
Ui . De cette implication, nous pouvons déduire que la
i =1 ¯i =1 ¯
¯ ¯iP=n
solution optimale de 1 ¯Le f f ¯¯ Ui pour l’instance Π est la même solution optimale de
¯
¯ ¯ i =1
¯iP
=n 0 0
1 ¯¯Le f f , p̃ i , d˜i ¯¯ ωi × Pos C̃i > d˜i pour Π . De plus, il est claire que l’instance Π peut
¯ ¡ ¢
i =1
être déduite de Π dans un temps d’ordre polynômial¯ O (n). Ceci¯ signifie qu’en implé-
¯iP
=n
mentant un algorithme polynômial au problème 1 ¯¯Le f f , p̃ i , d˜i ¯¯ ωi × Pos C̃i > d˜i ,
¯ ¡ ¢
¯ ¯ i =1
¯ ¯iP=n
nous serons capable de résoudre le problème 1 ¯¯Le f f ¯¯ Ui dans un temps polynômial
¯ ¯ i =1
¯ ¯iP=n
également. Le problème 1 ¯¯Le f f ¯¯ Ui est NP-difficile au sens fort comme prouvé
i =1 ¯ ¯
¯iP=n
dans [L IN, 2007], d’où notre problème 1 ¯Le f f , p̃ i , d i ¯¯ ωi × Pos C̃i > d˜i est fortement
˜
¯ ¡ ¢
¯
i =1
NP-difficile.
¡ ¢
Théorème 4.3. Si les tâches ont ³ des poids
´ agréables flous i.e. ∀ i , j ∈ J × J :
0 0
Mag p̃ j ≥ Mag p̃ i implique ωi ≥ ω j , alors pour la minimisation du problème
¡ ¡ ¢ ¡ ¢¢
¯ ¯
iP=n 0
µ ¶
ωi ⊗ C̃i , il suffit de classer les tâches dans l’ordre croissant du rapport
¯ ¯
1 ¯Le f f , p̃ i ¯Mag
¯ ¯
i =1
Mag (p̃ k )
0 pour k = 1, n
ωk
Démonstration.
La démonstration est basée sur la linéarité de la fonction magnitude (qui est vérifiée car
les coefficients de pénalité prennent des valeurs positives) et la procédure de permutation
des tâches comme détaillé pour un cas similaire dans [B ENTRCIA et M OUSS, 2015].
Malgré que le théorème précédent déclare que le problème peut être résolu dans
un temps d’ordre polynômial, mais dans le cas général lorsque ¯ l’hypothèse
¯ µ d’agréa-
iP
=n 0
¶
ωi ⊗ C̃i
¯ ¯
bilité floue n’est pas satisfaite, la complexité du problème 1 ¯¯Le f f , p̃ i ¯¯Mag
i =1
reste ouverte comme c’est le cas pour le même problème avec donnés détermi-
nistes [M OSHIEOV, 2001]. À ce niveau de développement, il est possible de formu-
ler notre problème d’ordonnancement bi-objectif à une machine avec données incer-
taines et effet d’apprentissage basé sur la position, les deux fonctions objectifs sont
à minimiser. Donc, la notation à trois champs de notre problème est donnée par
126
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
¯ ¯µ
¯ iP
=n iP
=n 0
µ ¶¶
˜ ˜
ωi × Pos C̃i > d i , Mag ωi ⊗ C̃i . Si l’approche de la somme pon-
¯ ¡ ¢
1 ¯Le f f , p̃ i , d i ¯
¯ ¯
i =1 i =1
dérée est utilisée pour élaborer une seule fonction objectif, l’analyse de la complexité sera
une mission facile à accomplir et la complexité de calcul dépendra principalement de la
complexité du problème le plus sophistiqué. Mais, quand les deux objectifs sont mani-
pulés individuellement dans le contexte d’une stratégie de classement non dominée, le
nombre des ordonnancements non dominés du front optimal peut croître d’une façon
exponentielle en fonction de la taille du problème. Le théorème suivant est très utile car il
relie la complexité des problèmes d’optimisations mono-objectifs aux problèmes multi-
objectifs [C HEN et B ULFIN, 1993].
Sans restriction, ce théorème reste valide même avec l’introduction des contraintes du
deuxième champ dans la notation de Graham.
Corollaire
¯ 4.4.¯µ Le problème d’ordonnancement bi-objectif à une machine noté par
¯ iP
=n iP
=n 0
µ ¶¶
1 ¯¯Le f f , p̃ i , d˜i ¯¯ ωi × Pos C̃i > d˜i , Mag ωi ⊗ C̃i est NP-difficile au sens fort.
¯ ¡ ¢
i =1 i =1
Démonstration.
Ce Corollaire découle directement de l’application des Théorèmes 4.2 et 4.4.
127
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
est la recherche coucou combinée avec une procédure de recherche locale afin d’inten-
sifier la recherche autour des solutions rencontrées. Les deux approches cherchent à gé-
nérer toutes les solutions optimales dans le but de permettre aux décideurs d’établir un
compromis entre les objectifs considérés. Il est à mentionner que ces métaheuristiques
sont à base de population commençant avec des configurations initiales aléatoires ou ob-
tenues selon une heuristique et améliorent avec les itérations jusqu’à la vérification d’un
critère d’arrêt.
À ce niveau du développement, nous avons entre les mains tous les ingrédients pour
décrire l’exécution pas à pas de l’algorithme génétique multi-objectif adopté. En premier,
la population initiale est combinée avec la population des enfants de taille n pop créée
par application des opérateurs de sélection par tournoi binaire, recombinaison et muta-
tion. Dans ce cas, l’élitisme est assuré car les populations des parents et des enfants sont
supportées dans la même génération. Maintenant, la population des parents associée à
128
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
la prochaine génération est remplie des fronts non dominants dans l’ordre de leurs rang
jusqu’à dépasser la taille de la population n pop . Les éléments du front responsable de cet
excès sont sélectionnés dans l’ordre descendant de la distance d’encombrement jusqu’à
atteindre la taille exacte de la population. Donc, la prochaine population des parents est
employée pour la sélection, croisement et mutation pendant la création d’une population
des enfants de même taille. Ces étapes sont réitérées tant que le critère d’arrêt n’est pas
satisfait comme illustré sur le pseudo code suivant (Algorithme 4.1) [D EB, 2001].
129
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
une probabilité fixe pour l’obtention de deux descendants ajoutés à la population des en-
fants. La méthode de croisement utilisée dans ce travail est le croisement à deux points,
où deux positions sont générées aléatoirement et les génotypes localisés entre ces deux
points sont copiés d’un parent et la séquence est complétée par les génotypes de l’autre
parent. En inversant l’ordre de sélection des parents, il est possible d’avoir un deuxième
enfant dans le processus de croisement. Cette procédure est répétée jusqu’au remplissage
des positions dans la population des enfants. En ce qui concerne l’opérateur de mutation,
nous adoptons la mutation basée sur la permutation des tâches où deux positions dans
un ordonnancement sont choisies arbitrairement et les tâches associées sont interchan-
gées si la probabilité générée est égale ou dépasse le taux de mutation. La complexité de
l’approche NSGA II proposée en fonction du nombre de tâches n sous l’hypothèse que la
taille de la population et le nombre maximum d’itération dépend linéairement de n peut
être calculée comme suit en commençant par la phase d’initialisation :
Pour la simplification, nous concentrons dans la boucle POUR principale sur la com-
plexité des instructions pour une itération comme illustré ci-dessous.
• Exécution
¡ de la procédure
¢ de tri basé sur l’opérateur de comparaison d’encombre-
ment : O n × log n ;
• Inclusion des solutions les plus dispersées : O (n) ;
• Création de la nouvelle population des enfants : O n 3 .
¡ ¢
130
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
naturelle d’expulser les oeufs du oiseau hôte du nid en plus de simuler les sons des ois-
sillons hôtes afin d’augmenter leur part de la nourriture. Lorsque l’implémentation al-
gorithmique du comportement du coucou est appliquée à des problèmes d’optimisation
continue, l’utilisation de vol de Lévy au lieu d’un mouvement brownien pur mène à une
meilleure performance. Via l’utilisation de cette règle de transition, la diversification dans
les populations générées par la recherche coucou devient plus importante car la distribu-
tion des longeurs des pas est à queue lourde, et toute taille du pas est permise. La distance
totale de l’origine converge à une distribution stable après un grand nombre de pas. La
transition arbitraire utilisant le vol de Lévy entre deux états est décrite par l’expression
suivante [PAVLYUKEVICH, 2007] :
u
s= 1
(4.15)
|v| β
Les deux paramètres u et v sont supposés suivant une distribution de la loi normale :
u = N 0, σu
2
¡ ¢
v = N 0, σ2v
¡ ¢
131
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
ic
Pt h = (4.16)
Maxg ener at i on
L’ensemble des opérations utilisées pour générer une nouvelle solution à partir de
la meilleure solution dans la stratégie d’intensification est composée de trois modifica-
tions locales. L’opérateur d’insertion supprime une tâche de sa position originale et l’in-
sert dans une nouvelle position. L’opérateur de permutation a pour objectif d’obtenir une
nouvelle solution par l’échange des contenues de deux positions différentes. L’opérateur
de décalage décale circulairement l’ordre des tâches par un pas fixe à gauche ou à droite
selon la valeur aléatoire binaire générée. Plusieurs études ont prouvé que l’hybridation
d’une métaheuristique avec une procédure de recherche locale résulte en des avantages
tels que la convergence rapide ainsi qu’une meilleure qualité des solutions proches de
l’optimale [B LUM et collab., 2011]. Dans ce contexte, la recherche de voisinage variable est
adoptée dans l’intégration avec la recherche coucou. La recherche du voisinage variable
est une méthode de recherche locale stochastique basée sur l’alternance stochastique des
voisinages pendant la phase de recherche. Dans chaque étape, la recherche utilise cer-
tains opérateurs élémentaires pour la génération et l’exploitation du voisinage d’une so-
lution avec l’objectif de tomber sur une solution améliorée. Alors, le processus commence
avec la sélection d’un opérateur qui est abandonné et remplacé par un autre lorsque la
recherche échoue dans l’amélioration de la solution courante. La recherche s’arrête avec
l’identification d’une solution qui est localement optimale par rapport à tous les voisi-
132
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
133
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
134
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
• Classement
¡ 3¢ de la population initiale des parents en des
¡ niveaux de non dominance :
2
¢
O n pour l’évaluation des fonctions objectifs et O n pour la procédure rapide
de classement
Pour des raisons de simplification, nous concentrons, dans la principale boucle TANT
QUE, sur la complexité des instructions pour une itération comme suit :
• Initialisation de la population des enfants Qk : O n 2 ;
¡ ¢
• Exécution
¡ 2¢ de la boucle POUR : O (n) pour le tirage d’un individu arbitraire x 1r and ,
O n pour la génération d’une nouvelle solution cuck par application ¡ 2du
¢ vol de
r and
Lévy, O (n) pour le tirage d’un deuxième individu arbitraire x 2 et O n pour le
test de non dominance ;
• Tirage du troisième individu arbitraire : O (n) ;
• Initialization aléatoire d’un pourcentage de taille p a ×n de la population
¡ 2 ¢ des enfants
r and
utilisant le troisième individu arbitraire x 3 comme graine : O n ;
¡ ¢
• Application de la recherche à voisinage variable : O n × g (n) ;
• Combinaison des populations des parents et des enfants : O (n) ;
¡ 3¢
• Classement non dominé de la population combinée : O n pour l’évaluation de la
fonction objectif et O n 2 pour la procédure de classement rapide ;
¡ ¢
pour la recherche à voisinage variable est dans le pire des cas de l’ordre de n!. De ce résul-
tat, nous pouvons déduire que la complexité de l’algorithme est basée sur les sections de
recherche à voisinage variable et le tri en niveaux de non dominance. Donc, toute amé-
lioration doit être focalisée sur la réduction de la complexité de ces deux méthodes.
135
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
iP
=n 0
défini par π∗ = min f 1 (π) , f 2 (π) avec f 1 (π) = ωi (π) × Pos C̃i (π) > d˜i (π) , f 2 (π) =
¡ ¢ ¡ ¢
π∈Ω ¶ i =1
iP
=n
µ
Mag ωi (π) ⊗ C̃i (π) et Ω est l’ensemble des ordonnancements faisables π.
i =1
Définition 4.10. On dit que l’ordonnancement π1 domine l’ordonnancement π2 selon le
critère de dominance de Pareto si les inégalités suivantes sont satisfaites :
∀k ∈ {1, 2} f i (π1 ) ≤ f i (π2 )
(4.17)
∃k ∈ {1, 2} f i (π1 ) < f i (π2 )
Donc, il est recommandé d’étudier l’influence du couplage entre différents critères de do-
minance sur les performances des approches multi-objectifs. En effet, cette combinaison
peut être un outil efficace pour guider la recherche vers des régions prometteuses ou bien
d’étendre les parties extrêmes des fronts non dominés, ce qui aide à croître la diversité
des solutions.
136
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
0
iii) Les coefficients de pénalité ω j , associés avec la somme pondérée des dates de fin
d’exécution, sont obtenus en multipliant ·par 10 les¸ nombres aléatoires générés à
partir de la distribution uniforme discrète a ω0 , b ω0 ;
j j
iv) En analogie avec les modèles d’ordonnancement déterministes, la gamme des dates
échues (notée par RDD) et le facteur d’étroitesse des dates échues (noté par TF) sont
introduits pour contrôler la difficulté à générer les problèmes où une valeur élevée
de RDD indique une large plage de dates échues, tandis qu’une faible valeur indique
une plage étroite de dates échues. Des valeurs de TF proche de 1 indique que les
dates échues sont serrées et des valeurs proche de 0 indique que les dates échues
sont lâches. Les valeurs des deux paramètres sont sélectionnées de l’intervalle [0, 1] ;
v) Pour la date échue floue d˜j de la tâche j , d j et d¯j sont affectés des valeurs entières
"Ã ! Ã ! #
n n
p × 1 − TF − RDD p̄ j × 1 − TF + RDD
P ¡ ¢ P ¡ ¢
de la distribution uniforme 2 , 2 et
j =1 j j =1
" Ã ! #
n
RDD
respectivement. Par la suite, αd˜j et βd˜j sont tirés aléa-
P ¡ ¢
dj, p̄ j × 1 − TF + 2
j =1
d j +d¯j
· µ ¶¸
toirement de l’intervalle 1, 0.2 × 2 .
Une description complète de toutes les instances ainsi que les données de configu-
rations utilisées dans ce travail peut être téléchargée sur le lien :<http://lab.univ-batna2.
dz/lap/index.php/component/content/article?id=31>.
Les valeurs affectées aux bornes inférieures et supérieures nécessaires comme des entrées
pendant la procédure de génération des instances sont illustrées sur le Tableau 4.1.
TABLEAU 4.1 Valeurs des différents paramètres nécessaires à la génération des instances
Comme le front non dominé optimal est dans la plus part des cas inconnu à l’excep-
tion des problèmes de petites tailles pour lesquels le calcul par recherche exhaustive est
raisonnable, nous évaluons les performances des approches proposées à travers trois mé-
triques capables d’estimer les différents aspects des fronts approximés. Il est à noter que
ces métriques ne nécessitent pas en générale le calcul du front optimal. La première mé-
trique est le nombre d’ordonnancements (i.e. Cardinal) constituant le front produit par
un algorithme al g i et il est défini par :
f
n al g = Car d ( f r ont al g i ) (4.18)
i
La deuxième métrique proposée pour la première fois par Zitzler et ses collègues [Z ITZ -
LER et collab., 2003] est la proportion des ordonnancements trouvés par une méthode
d’optimisation al g i qui sont dominés par au moins un ordonnancement obtenu par une
autre méthode al g j . Cette métrique est indépendante de l’échelle dans le sens qu’elle
ne nécessite pas la normalisation des valeurs de la fonction objectif même si l’ordre de
137
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
grandeur des fonctions objectifs est relativement différent. La proportion des ordonnan-
cements dominés est exprimée par :
³n ¯ o´
Car d π2 ∈ f r ont al g j ¯ ∃π1 ∈ f r ont al g i : π1 ≥ π2
¯
R al g i −al g j = ³ ´ (4.19)
Car d f r ont al g j
La troisième métrique est la distance modifiée introduite initialement par Riise et éten-
due par Dugardin et ses collègues dans le but de supporter les valeurs qui partagent les
fronts comparés ( [R IISE, 2002] et [D UGARDIN et collab., 2010]). L’idée derière cette mé-
trique réside dans la mesure de la distance algébrique totale entre les solutions du front
al g i à leurs projections orthogonales sur le front de référence al g j . La normalisation est
achevée pour éviter la sensibilité à la variation du nombre de solutions. Donc, différentes
solutions sont connectées et la ligne est extrapolée pour former des demi droites conti-
nues pour permettre la projection des points localisés en dehors de l’étendu du front de
référence [L ACOMME et collab., 2006]. Cette métrique peut être formulée dans une nota-
tion normalisée comme suit :
³ ´
Car d f r ont al g j
P
dk
1 k=1
µal g i −al g j = ³ ´q
¢2 ¡ ¢2 (4.20)
Car d f r ont al g j
¡
f 1 max − f 1 min + f 2 max − f 2 min
avec d k est la distance entre un point du front généré par al g i et sa projection orthogo-
nale sur le front généré par al g j . Le reste des paramètres dans l’expression sont données
par :
n o
π
¯
f 1 min = min f 1 (π)¯ ∈ f r ont al g i ∪ f r ont al g j
n o
¯ π ∈ f r ont al g ∪ f r ont al g
¯
f = max f (π)
1 max 1
i j
n o
π
¯
f = min f (π) ∈ f r ont ∪ f r ont
2 min 2 al g i al g j
¯
n o
2 max = max f 2 (π) π ∈ f r ont al g i ∪ f r ont al g j
f ¯
¯
¡∆ ¢ : y = y 3 −y 2
(x − x 2 ) + y 2
2,3 x 3 −x 2
138
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
x 2 −x 1
¡ ⊥ ¢
∆1,2 : y = − y 2 −y 1 (x − x 1 ) + y 1
¡∆⊥ ¢ : y = − x3 −x2 (x − x ) + y
2,3 y 3 −y 2 2 2
pas être projetés sur le front de référence (front non dominé 1). Une telle situation
peut dégrader considérablement l’efficacité de la métrique de la distance modifiée dans
l’évaluation des performances des approches d’optimisation multi-objectif. Selon nos
connaissances, aucune solution n’est fournie dans la littérature pour cette limitation et
pour cela nous proposons pour la solution avec label B de calculer la distance à la plus
proche solution du front de référence au lieu de la distance de projection. En effectuant
ce changement, nous espérons que le nombre de positionnements aberrants entre les
deux fronts peut être réduit considérablement.
F IGURE 4.1 Situations possibles de projection de deux fronts non dominés obtenus par
des métaheuristiques différentes.
Il est à mentionner que les deux directions doivent être considérées dans le calcul
de la proportion des ordonnancements dominés et la distance modifiée. Ceci peut être
expliqué par le fait que les deux métriques ne sont pas symétriques ni complémen-
taires, ce qui nécessite l’évaluation des performances des algorithmes avec la permuta-
tion de l’algorithme de référence chaque fois. À cause du nombre d’instances associées
à chaque configuration (20 instance pour chaque nombre fixe de tâches), les métriques
citées sont calculées sur la base de la moyenne des résultats issus de l’ensemble des
instances pour une configuration bien déterminée. Alors, les quantités moyennes
³ sui-
´
f
vantes n̄ al g , R̄ al g i −al g j et µ̄al g i −al g j sont utilisées pour l’évaluation avec al g i , al g j ∈
i
139
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
© ª
Opt i mal , NSGA II, r echer che coucou et al g i 6= al g j . Cette notation permet de dif-
férencier entre ces approches : optimale (recherche exhaustive), recherche coucou et al-
gorithme génétique élitiste de tri non dominé sans oublier la non symétrie des métriques
considérées. Mais à cause du temps de calcul important consommé par une énumération
exhaustive, l’approche optimale n’est appliquée que pour les petites instances. À cause
de la dépendance des performances des méthodes d’optimisation du choix adéquat des
valeurs des paramètres de configurations, nous avons effectué quelques tests pour dé-
terminer une configuration appropriée en termes des performances. Cette procédure de
test est achevée uniquement pour les petites instances dû au coût de calcul lourd. Dans
le Tableau 4.2, nous résumons les principaux paramètres ainsi que les valeurs associées
aux métaheuristiques proposées. Ces valeurs sont retenues fixes à l’exception lorsque une
analyse de sensibilité est conduite. En ce qui concerne le nombre de générations, nous
fixons la valeur pour notre algorithme génétique multi-objectif à 10 × n et le temps enre-
gistré (en secondes) pour ce nombre d’itérations est alloué à l’exécution de la recherche
coucou pour que la comparaison soit légale entre ces deux approches.
/ : Non applicable
Dans les Tableaux 4.3, 4.4 et 4.5, nous résumons les résultats de simulation obte-
nus par l’algorithme génétique multi-objectif et la recherche coucou dans l’espace de
domination de Pareto. Il est à mentionner que les valeurs moyennes des cardinaux des
meilleurs fronts non dominés pour les vingt instances sont calculées par une méthode
d’énumération complète uniquement pour les configurations de petites tailles (5, 6 et 7
tâches) à cause des coûts de calcul. Nous observons que l’approche hybride (recherche
coucou/recherche à voisinage variable) est plus efficace dans l’obtention des solutions
optimales en comparaison avec l’algorithme génétique, qui donne des résultats légère-
ment inférieurs à la valeur moyenne des cardinaux optimaux. Pour un nombre de tâches
supérieure à 10, la valeur moyenne des cardinaux des fronts non dominés générés par la
recherche coucou est considérablement réduite en comparaison avec l’algorithme géné-
tique. La moyenne des proportions des ordonnancements trouvés par la recherche cou-
cou et dominés par ceux de l’algorithme génétique croît de zéro pour les petites instances
pour atteindre une valeur de l’ordre de 30% pour un nombre de tâches égale à 40. En
ce qui concerne la moyenne des distances modifiées normalisées, elle est toujours posi-
tive lorsque le front optimal est considéré comme référence car les solutions optimales
ne sont jamais dominées. Nous observons également que cette mesure n’est pas signi-
140
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
ficative lorsque elle est calculée pour la recherche coucou comparativement aux solu-
tions optimales, ce qui confirme que les fronts obtenus sont très proches l’un de l’autre.
Pour un nombre de tâches égale ou supérieur à dix, la moyenne des distances modifiées
normalisées µ̄cuck−nsg a exprimant la position relative du meilleur front obtenu par la re-
cherche coucou par rapport au meilleur front obtenu par l’algorithme génétique est né-
gative. Cette remarque indique que les fronts de la recherche coucou sont généralement
situés au dessous des fronts de l’algorithme génétique multi-objectif, ce qui confirme la
performance supérieure (d’une manière globale) de l’approche coucou hybride. Pour un
nombre de tâches inférieur à 10, nous remarquons que les deux moyennes des distances
modifiées normalisées (µ̄cuck−nsg a et µ̄nsg a−cuck ) sont positives car dans certains cas les
fronts coucou de certaines instances sont meilleures que les fronts de NSGAII et c’est
l’inverse pour les instances restantes. Sous cette situation, la moyenne des distances mo-
difiées normalisées ne reflète pas d’une façon précise la position relative des vingt ins-
tances associées à une configuration, ce qui implique la consultation de la métrique de la
moyenne des proportions des ordonnancements dominés et la valeur moyenne des car-
dinaux des meilleurs fronts pour avoir une interprétation plus réaliste.
TABLEAU 4.3 Variation des performances (la moyenne des cardinaux des fronts générés)
des approches proposées en fonction du nombre de tâches avec règle de dominance de
Pareto (Le f f = 0, TF = 0.5 et RDD = 0.5).
f f f
n n̄ opt n̄ cuck n̄ nsg a
5 3.85 3.75 3.6
6 4.7 4.55 4.25
7 5.25 4.85 4.85
8 / 7.15 6.7
9 / 7.25 6.75
10 / 9.7 9.3
15 / 15 17.85
20 / 19.5 27.4
25 / 24.15 36.4
30 / 22.7 46.15
35 / 25.7 54.7
40 / 27.45 63.85
/ : Non applicable
Le Tableau 4.6 présente les variations des performances des deux algorithmes en
fonction de la gamme et du facteur d’étroitesse gouvernant la génération des dates échues
floues pour un nombre fixe de tâches (20 tâches). Ce tableau montre que la recherche
coucou donne un nombre réduit des solutions non dominées dans la majorité des cas
à l’exception de la configuration TF = 1 et RDD = 0.2. En outre, la recherche coucou est
considérablement plus performante en terme de la moyenne des proportions des ordon-
nancements dominés qui varie entre 0% à 16% tandis qu’il varie de 20% à 52% pour la
moyenne des proportions des solutions de l’algorithme génétique dominées au moins
par une solution de la recherche coucou. Pour la métrique de la moyenne des distances
modifiées normalisées, dans la majorité des cas de µ̄cuck−nsg a , nous avons des valeurs né-
gatives indiquant que la plupart des fronts de la recherche coucou sont localisés au des-
sous ou très proches des fronts obtenus par l’algorithme génétique. Alors, nous pouvons
conclure que l’approche hybride de la recherche coucou est (globalement) plus robuste
141
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
TABLEAU 4.4 Variation des performances (la moyenne des proportions des ordonnance-
ments dominés) des approches proposées en fonction du nombre de tâches avec règle de
dominance de Pareto (Le f f = 0, TF = 0.5 et RDD = 0.5).
/ : Non applicable
TABLEAU 4.5 Variation des performances (la moyenne des distances modifiées normali-
sées) des approches proposées en fonction du nombre de tâches avec règle de dominance
de Pareto (Le f f = 0, TF = 0.5 et RDD = 0.5).
/ : Non applicable
142
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
envers les variations de la gamme et le facteur d’étroitesse des dates échues des tâches.
f f
TF RDD n̄ cuck n̄ nsg a R̄cuck−nsg a R̄nsg a−cuck µ̄cuck−nsg a µ̄nsg a−cuck
0.2 18.30 21.35 0.11 0.30 −15 × 10−4 30 × 10−4
0.2 0.6 8.80 13.70 0.14 0.24 −4 × 10−4 20 × 10−4
1 5.20 7.25 0.04 0.28 −376×10−4 408 × 10−4
0.2 20.45 24.35 0.09 0.42 −11 × 10−4 13 × 10−4
0.6 0.6 20.90 25.55 0.11 0.47 −10 × 10−4 25 × 10−4
1 17.95 25.15 0.16 0.31 56 × 10−4 12 × 10−4
0.2 4.55 3.75 0 0.20 68 × 10−4 92 × 10−4
1 0.6 14.5 15.15 0.02 0.43 57 × 10−4 26 × 10−4
1 17.75 22.6 0.07 0.52 −10 × 10−4 19 × 10−4
143
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
TABLEAU 4.7 Variation des performances des approches proposées en fonction du coeffi-
cient d’apprentissage avec règle de dominance de Pareto (n = 10, TF = 0.5 et RDD = 0.5).
f f
Le f f n̄ cuck n̄ nsg a R̄cuck−nsg a R̄nsg a−cuck µ̄cuck−nsg a µ̄nsg a−cuck
0 9.7 9.3 45 × 10−4 2495 × 10−4 −16 × 10−4 36 × 10−4
-0.01 12.8 13.5 697 × 10−4 1177 × 10−4 76 × 10−4 11 × 10−4
-0.02 12.95 13.15 483 × 10−4 2040 × 10−4 −3 × 10−6 23 × 10−4
-0.03 13.15 14.25 328 × 10−4 1767 × 10−4 13 × 10−4 57 × 10−4
-0.04 13.1 13 567 × 10−4 1914 × 10−4 8 × 10−4 14 × 10−4
-0.05 13 13.65 305 × 10−4 1565 × 10−4 109 × 10−4 17 × 10−4
-0.06 13.10 12.8 543 × 10−4 1762 × 10−4 44 × 10−4 2 × 10−4
-0.07 12.8 13.15 334 × 10−4 1945 × 10−4 11 × 10−4 21 × 10−4
-0.08 12.55 13.05 654 × 10−4 1657 × 10−4 193 × 10−4 14 × 10−4
-0.09 11.75 11.85 253 × 10−4 2075 × 10−4 276 × 10−4 16 × 10−4
-0.1 12.35 12.45 295 × 10−4 2167 × 10−4 186 × 10−4 43 × 10−4
F IGURE 4.2 Représentation des meilleurs fronts obtenus par les deux approches avec
considération simultanée des règles de dominance Pareto et Lorenz (L’instance numero
17 de la configuration n=20).
dominés dans le cas de la recherche coucou est considérablement réduite de même pour
le cas de l’algorithme génétique multi-objectif pour lequel cette mesure est légèrement
améliorée en comparaison avec l’application unique du critère de Pareto comme donné
sur les Tableaux 4.3, 4.4 et 4.5. Cette remarque confirme l’avantage de l’utilisation
conjointe de différents types de règles de dominance avec les mécanismes d’intensifi-
144
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
TABLEAU 4.8 Variation des performances (la moyenne des cardinaux des fronts générés)
des approches proposées en fonction du nombre de tâches avec considération simulta-
née des règles de dominance de Pareto et Lorenz (Le f f = 0, TF = 0.5 et RDD = 0.5).
f f f
n n̄ opt n̄ cuck n̄ nsg a
5 3.85 3.8 3.6
6 4.7 4.55 4.25
7 5.25 5 4.85
8 / 7.3 6.75
9 / 7.25 6.8
10 / 10.10 9.5
15 / 16.7 18.15
20 / 22.7 29.35
25 / 26.8 38.4
30 / 26.35 49.7
35 / 28.7 57.35
40 / 30.85 66.95
/ : Non applicable
l’algorithme génétique élitiste de¢¢ tri non dominé est le gagnant dans le cas de
µcuck−nsg µ
¡¡ ¢ ¡
¡¡ a > 0 ∧ nsg¢a−cuck < 0 et l’équivalence des deux
¢ ¡ algorithmes ¢¢ dans le
cas de µcuck−nsg a ≤ 0 ∧ µnsg a−cuck ≤ 0 ∨ µcuck−nsg a ≥ 0 ∧ µnsg a−cuck ≥ 0 . Nous
¡ ¢¢ ¡¡
n’est pas compté mais partitionné d’une façon équitable entre les deux algorithmes
considérés [F ONG et collab., 2003]. Le test des signes est adopté pour évaluer l’hypothèse
145
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
TABLEAU 4.9 Variation des performances (la moyenne des proportions des ordonnance-
ments dominés) des approches proposées en fonction du nombre de tâches avec consi-
dération simultanée des règles de dominance de Pareto et Lorenz (Le f f = 0, TF = 0.5 et
RDD = 0.5).
/ : Non applicable
TABLEAU 4.10 Variation des performances (la moyenne des distances modifiées norma-
lisées) des approches proposées en fonction du nombre de tâches avec considération si-
multanée des règles de dominance de Pareto et Lorenz (Le f f = 0, TF = 0.5 et RDD = 0.5).
/ : Non applicable
146
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
nulle que la médiane des valeurs gagnantes est égale à zéro contre l’hypothèse alternative
que la médiane des valeurs gagnantes est supérieure à zéro. Les hypothèses nulle et
alternative sont définies comme suit :
H0 : La méd i ane d e nombr e d es vi c t oi r es d e l a r echer che coucou = 0
À cause de la taille de notre échantillon (240), il est possible d’utiliser une approxi-
mation normale pour la distribution de probabilité binomiale dans la détermination
de la région du rejet du test des signes [WACKERLY et collab., 2008]. Comme les valeurs
faibles de p constituent une évidence forte contre l’hypothèse nulle, le test rejette l’hy-
pothèse nulle en faveur de l’hypothèse alternative à un niveau de signification de 1% car
la valeur-p obtenue est inférieure au niveau de signification (1.3327 × 10−9 < 1%). Donc,
il est très probable que la mesure de performance de l’approche recherche coucou en
fonction de la distance modifiée normalisée soit supérieure à la mesure de performance
de l’algorithme génétique multi-objectif.
4.6 Conclusion
147
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
4.7 Références
A BBASBANDY, S. et T. H AJJARI. 2009, «A new approach for ranking of trapezoidal fuzzy
numbers», Computers and Mathematics with Applications, vol. 57, no 3, p. 413–419. 118
A L -T URKI , U., C. F EDJKI et A. A NDIJANI. 2001, «Tabu search for a class of single-machine
scheduling problems», Computers and Operations Research, vol. 28, no 12, p. 1223–
1230. 111
AYDILEK , A., H. AYDILEK et A. A LLAHVERDI. 2017, «Algorithms for minimizing the number
of tardy jobs for reducing production cost with uncertain processing times», Applied
Mathematical Modelling, vol. 45, p. 982–996. 115
B ENTRCIA , T. et L.-H. M OUSS. 2015, Fuzzy Modeling of the Single Machine Schedu-
ling Problems including the Learning Effect,, chap. 14, in Talbi, E-G. and Yalaoui, F.
and Amodeo, L. (eds.), Metaheuristics for Production Systems, Series : Operations Re-
search/Computer Science Interfaces Series, Springer. 115, 126
B ENTRCIA , T., L.-H. M OUSS, N.-K. M OUSS, F. YALAOUI et L. B ENYOUCEF. 2015, «Evalua-
tion of optimality in the fuzzy single machine scheduling problem including discoun-
ted costs», International Journal of Advanced Manufacturing Technology, vol. 80, no 5,
p. 1369–1385. 114
148
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
B OJADZIEV, G. et M. B OJADZIEV. 1996, Fuzzy Sets, Fuzzy Logic, Applications, World Scien-
tific. 118
B UCKLEY, J. J. 2005, Fuzzy Probabilities, New Approach and Applications, Springer Press.
123
C HANAS , S. 2001, «On the interval approximation of a fuzzy number», Fuzzy Sets and Sys-
tems, vol. 122, no 2, p. 353–356. 116
D AUZÈRE -P ÉRÈS , S. 1995, «Minimizing late jobs in the general one machine scheduling
problem», European Journal of Operational Research, vol. 81, no 1, p. 134–142. 112
D ERRAC , J., S. G ARCÍA, D. M OLINA et F. H ERRERA. 2011, «A practical tutorial on the use
of nonparametric statistical tests as a methodology for comparing evolutionary and
swarm intelligence algorithms», Swarm and Evolutionary Computation, vol. 1, no 1, p.
3–18. 145
D IAMOND, P. et P. K LOEDEN. 1994, Metric Spaces of Fuzzy Sets : Theory and Applications,
World Scienific Press. 116
149
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
E BRAHIMNEJAD, A. 2016, «A new method for solving fuzzy transportation problem with lr
flat fuzzy numbers», Information Sciences, vol. 357, p. 108–124. 122
F ONG , D. Y. T., C. W. K WAN, K. F. L AM et K. S. L. L AM. 2003, «Use of the sign test for the
median in the presence of ties», The American Statistician, vol. 57, no 4, p. 237–240. 145
H ANOUN , S., D. C REIGHTON et S. N AHAVANDI. 2014, «A hybrid cuckoo search and variable
neighborhood descent for single and multiobjective scheduling problems», Internatio-
nal Journal of Advanced Manufacturing Technology, vol. 75, no 9, p. 1501–1516. 131,
133
H ANSEN , P. et N. M LADENOVI Ć. 2001, «Variable neighborhood search : Principles and ap-
plications», European Journal of Operational Research, vol. 130, no 3, p. 449–467. 133
150
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
K IM , Y. D. 1993, «A new branch and bound algorithm for minimizing mean tardiness in
two-machine flowshops», Computers and Operations Research, vol. 20, no 4, p. 391–401.
136
K LIR , G. et B. Y UAN. 1995, Fuzzy Sets and Fuzzy Logic : Theory and Applications, Prentice
Hall Press. 119
L ACOMME , P., C. P RINS et M. S EVAUX. 2006, «A genetic algorithm for a bi-objective ca-
pacitated arc routing problem», Computers and Operations Research, vol. 33, no 12, p.
3473–3493. 138
L I , J., X. Y UAN, E. S. L EE et D. X U. 2011, «Setting due dates to minimize the total weighted
possibilistic mean value of the weighted earliness-tardiness costs on a single machine»,
Computers and Mathematics with Applications, vol. 62, no 1, p. 4126–4139. 111
M ANTEGNA , R. 1994, «Fast, accurate algorithm for numerical simulation of lévy stable
stochastic processes», Physical Review E, vol. 49, no 5, p. 4677–4683. 131
M’H ALLAH , R. et R. L. B ULFIN. 2003, «Minimizing the weighted number of tardy jobs on
a single machine», European Journal of Operational Research, vol. 145, no 1, p. 45–56.
112
M’H ALLAH , R. et R. L. B ULFIN. 2007, «Minimizing the weighted number of tardy jobs on a
single machine with release dates», European Journal of Operational Research, vol. 176,
no 2, p. 727–744. 113
M OHAMAD, A. B., A. M. Z AIN et N. E. N. B AZIN. 2014, «Cuckoo search algorithm for opti-
mization problems - a literature review and its applications», Applied Artificial Intelli-
gence : An International Journal, vol. 28, no 5, p. 419–448. 131
M UNDT, A. et T. W ICH. 2007, Single Machine Scheduling with Tardiness Involved Objec-
tives : A Survey, mémoire de maîtrise, Université de Linköpings, Sweden. 113
151
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
PAVLYUKEVICH , I. 2007, «Lévy flights, non-local search and simulated annealing», Journal
of Computational Physics, vol. 226, no 1, p. 1830–1844. 131
Q IAN , J. et G. S TEINER. 2013, «Fast algorithms for scheduling with learning effects and
time-dependent processing times on a single machine», European Journal of Operatio-
nal Research, vol. 225, no 3, p. 547–551. 114
R ASTI -B ARZOKI , M. et S. R. H EJAZI. 2013, «Minimizing the weighted number of tardy jobs
with due date assignment and capacity-constrained deliveries for multiple customers
in supply chains», European Journal of Operational Research, vol. 228, no 2, p. 345–357.
113
R IISE , A. 2002, «Comparing genetic algorithms and tabu search for multi-objective op-
timization», dans International Federation of Operational Research Studies Conference
IFORS, Edinburhg, UK. 138
RUDEK , R. 2017, «The single machine total weighted completion time scheduling problem
with the sum-of-processing time based models : Strongly np-hard», Applied Mathema-
tical Modelling, vol. 50, p. 314–332. 113
S CALAS , E. et M. L ECCARDI. 2005, «Comparison of three algorithms for lèvy noise gene-
ration», dans Fifth EUROMECH Nonlinear Dynamics Conference, Eindhoven, The Ne-
therlands. 131
152
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
W ONGA , B. K. et V. S. L AI. 2011, «A survey of the application of fuzzy set theory in pro-
duction and operations management : 1998-2009», International Journal of Production
Economics, vol. 129, no 1, p. 157–168. 136
W RIGHT, T. P. 1936, «Factors affecting the cost of airplanes», Journal of the Aeronautical
Sciences, vol. 3, no 4, p. 122–128. 113
W U , C.-C. et W.-C. L EE. 2008, «Single-machine scheduling problems with a learning ef-
fect», Applied Mathematical Modelling, vol. 32, no 7, p. 1191–1197. 113
YAGER , R. R. 1981, «A procedure for ordering fuzzy subsets of the unit interval», Informa-
tion Sciences, vol. 24, no 2, p. 143–161. 118
YANG , X. S. et S. D EB. 2009, «Cuckoo search via lévy flights», dans World congress on na-
ture and biologically inspired computing, Coimbatore, India. 130
Z ADEH , L. A. 1965, «Fuzzy sets», Information and Control, vol. 8, no 3, p. 338–353. 116
Z ADEH , L. A. 1978, «Fuzzy sets as a basis for a theory of possibility», Fuzzy Sets and Sys-
tems, vol. 1, p. 3–28. 119
153
Chapitre 4. Problème d’ordonnancement bi-objectif à une machine avec effet
d’apprentissage et paramètres incertains
154
Conclusion générale
Steve Jobs
155
Conclusion générale
156
Conclusion générale
Synthèse
Au cours de cette thèse, la recherche bibliographique réalisée relativement aux pro-
blèmes d’ordonnancement à une machine a permis de déceler le gap significatif exis-
tant entre les développements théoriques et les recommandations pratiques notamment
en termes du traitement de certaines contraintes. En effet, les approches d’ordonnance-
ment étant souvent élaborées sur une base déterministe pour laquelle l’imprécision des
données due à des facteurs internes/externes est ignorée ou pas prise convenablement
en compte. Par conséquent, une solution optimale au sens classique peut s’avérer inva-
lide ou obsolète suite à la présence des sources d’incertitudes dans l’environnement. Le
contexte de la thèse s’est donc naturellement focalisé sur le support des paramètres in-
certains au sein des approches d’ordonnancement pendant les phases de modélisation
ainsi que de résolution.
Les travaux effectués dans cette thèse ont permis, du point de vue mathématique,
non seulement de revisiter quelques opérations arithmétiques définies sur l’espace des
nombres flous mais aussi d’apporter des extensions intéressantes au niveau des pro-
priétés structurelles de ces nombres. Nos contributions liées à l’ordonnancement sont
localisées au croisement de deux champs thématiques. Le premier fait le point sur la
modélisation des problèmes d’ordonnancement à une machine dans l’incertain en in-
tégrant d’autres contraintes alors que le deuxième champ concerne le developpement
d’outils d’optimisation et l’évaluation de leurs performances. Dans le premier champ,
nous avons représenté les paramètres d’ordonnancement (durées opératoires, dates
d’échéance,...etc.) par des nombres flous ayant une allure bien spécifique et nous avons
considéré la notion d’optimalité selon plusieurs interprétations : notion d’optimalité gra-
duelle pour un ordonnancement fixe, notion d’optimalité ordinaire dans le cadre d’un
problème d’optimisation combinatoire mono-objectif et notion d’optimalité ordinaire
dans le cadre d’un problème d’optimisation combinatoire multi-objectif. Les résultats is-
sus de l’analyse de complexité basée sur ces concepts d’optimalité nous ont permis de
démontrer que malgré l’obtention de quelques problèmes d’ordonnancement ayant une
complexité polynômiale, la résolution des modèles résultants sans hypothèses simplifica-
trices sur les paramètres d’ordonnancement est loin d’être un but trivial. Dans le second
champ de recherche englobant les outils d’optimisation et leurs caractéristiques, nous
avons développé suivant cet axe plusieurs approches de résolution en particulier des mé-
taheuristiques à base de trajectoire et de population, qui ont fait preuve dans le domaine
d’ordonnancement. Nous avons consolidé l’efficacité de ces algorithmes en proposant
des schémas d’intégration divers où la motivation vient du constat que l’hybridation entre
différentes approches d’optimisation peut conduire à une amélioration de la qualité des
solutions obtenues. En particulier, nous avons étudié l’utilité d’adopter un algorithme
génétique comme phase optionnelle dans la recherche par motifs. De plus, nous avons
proposé des versions multi-objectives des approches algorithme génétique et recherche
coucou destinées aux problèmes d’optimisation discrets avec analyse de l’influence de
deux critères de dominance. Finalement, nous avons approuvé ces approches de réso-
lution à travers des tests statistiques mettant en évidence une validation plus fine des
résultats en comparaison avec les déductions grossières basées sur les valeurs moyennes
des mesures de performance.
L’exploitation des modèles et des approches proposés nous a permis d’aboutir aux
remarques générales suivantes :
157
Conclusion générale
Perspectives
Après l’analyse des problèmes d’ordonnancement à une machine avec paramètres in-
certains et l’adoption de la théorie de possibilité pour la modélisation d’aspects incer-
tains, nous estimons que les résultats obtenus peuvent donner naissance à de futures
perspectives concernant les problèmes d’ordonnancement flous. Comme la présence des
périodes d’indisponibilité de la machine due par exemple à une défaillance n’est pas évo-
quée dans cette thèse, il serait très intéressant de considérer ce type de contraintes plus en
détail via l’utilisation de la théorie des probabilités floues. Une autre ouverture de ce tra-
vail peut être l’exploitation des méthodes exactes pour les problèmes d’ordonnancement
flous, ce qui nécessite la reformulation des notions associées afin de justifier l’efficacité
des approches métaheuristiques proposées. Enfin, un dernier axe de recherche concerne
la généralisation des idées implémentées pour les systèmes de production de type flow-
shop, job-shop et pourquoi pas aller même vers le cas open-shop.
158
Résumé
Les systèmes de production actuels sont soumis à une forte pression de l’environ-
nement. Cette situation peut conduire à l’altération des stratégies conventionnelles
d’ordonnancement. En effet, plusieurs paramètres et contraintes relatifs aux tâches
nécessitent une reformulation à la base d’outils adéquats. C’est dans ce contexte que
s’inscrit ce travail de thèse dans lequel nous proposons plusieurs approches intégrées
pour la modélisation du problème d’ordonnancement à une machine avec prise en
compte simultanément d’une variété de sources d’incertitude. En outre, nous analysons
la complexité des formulations résultantes et nous implémentons des règles d’optimalité
globale ainsi que des métaheuristiques pour élaborer des solutions exactes ou appro-
chées. L’évaluation des métriques de performance atteste l’efficacité des approches de
résolution proposées.
Abstract
Current production systems are subject to a strong pressure from their environ-
ments. Such situation can lead to the alteration of conventional scheduling strategies.
Indeed, several parameters and constraints relative to scheduled tasks require a re-
formulation on the basis of adequate tools. In this framework, we propose several
integrated approaches for modeling the problem of single machine scheduling with
simultaneous consideration of a variety of sources of uncertainty. In addition, we analyze
the complexity of the resulting formulations and implement global optimality rules in
addition to metaheuristics in order to obtain exact or approximate solutions. The perfor-
mance metrics evaluation validates the effeciency of the proposed resolution approaches.
Keywords : Single machine scheduling, fuzzy theory, optimality rules and optimiza-
tion methods