Mots équilibrés et ordonnancement juste-à-temps périodique
1 : Laboratoire des sciences pour la conception, l'optimisation et la production
(G-SCOP)
Université Joseph Fourier - Grenoble I, Institut National Polytechnique de Grenoble - INPG, CNRS : UMR5272, Institut National Polytechnique de Grenoble (INPG)
3 : Universite de Liege
Les mots équilibrés sont étudiés en mathématiques discrètes et théorie des nombres mais aussi dans des applications comme l'ordonnancement, la maintenance, les files d'attente ou la répartition des sièges à la proportionnelle. Par exemple, dans un système de production en juste-à-temps, les différents produits d'un même type doivent être espacés afin de ne pas surcharger les postes pour lesquels ils sont longs à traiter (voir Monden 1983 pour des ateliers d'assemblage de voitures de Toyota). Si chaque type est vu comme une lettre, le mot généré par la séquence de production doit être le plus "équilibré" possible.
L'équilibre d'un mot correspond à l'intuition suivante: chaque lettre apparaît aussi uniformément que possible dans le mot. Par exemple "aaaabbc" n'est pas équilibré alors que "abacaba" l'est. Formellement, un mot est dit équilibré si le nombre d'occurrences de chaque type de lettre diffère d'au plus un quand on compare n'importe quelle paire de sous-mots de même longueur. Pour les 2 mots ci-dessus les densités de a,b,c sont respectivement 4/7, 2/7 et 1/7. Un vecteur de densité est équilibrable s'il existe un mot équilibré avec ces densités. L'objectif initial de notre recherche est de mieux cerner les vecteurs de densité équilibrables.
Les mots équilibrés ont reçu l'attention de nombreux chercheurs. Malgré cela, leurs propriétés sont encore mal comprises. Une illustration de cette affirmation est donnée par la conjecture formulée par Fraenkel, difficile malgré son apparente simplicité: "Un mot équilibré sur n lettres, ayant toutes des densités différentes a nécessairement les densités: 2^i / ((2^n)-1) pour i= 0..n-1".
L'équilibre d'un mot correspond à l'intuition suivante: chaque lettre apparaît aussi uniformément que possible dans le mot. Par exemple "aaaabbc" n'est pas équilibré alors que "abacaba" l'est. Formellement, un mot est dit équilibré si le nombre d'occurrences de chaque type de lettre diffère d'au plus un quand on compare n'importe quelle paire de sous-mots de même longueur. Pour les 2 mots ci-dessus les densités de a,b,c sont respectivement 4/7, 2/7 et 1/7. Un vecteur de densité est équilibrable s'il existe un mot équilibré avec ces densités. L'objectif initial de notre recherche est de mieux cerner les vecteurs de densité équilibrables.
Les mots équilibrés ont reçu l'attention de nombreux chercheurs. Malgré cela, leurs propriétés sont encore mal comprises. Une illustration de cette affirmation est donnée par la conjecture formulée par Fraenkel, difficile malgré son apparente simplicité: "Un mot équilibré sur n lettres, ayant toutes des densités différentes a nécessairement les densités: 2^i / ((2^n)-1) pour i= 0..n-1".
Cette conjecture reste obstinément ouverte bien que prouvée dans des cas particuliers.
Des expérimentations nous ont permis de générer tous les vecteurs de densités équilibrables jusqu'à une certaine taille. De ces résultats numériques ont été dérivées des conjectures, nouvelles à notre connaissance. L'objectif de cette présentation est de donner des pistes pour expliquer pourquoi ces conjectures nous semblent pertinentes et correctes.
| Subject : | : | typdoc_1455 |
| Language of text | : | French |
| Topics | : | Scheduling, planning and production management |
| Keywords | : | ordonnancement ; mots équilibrés |
| PDF version | : |  PDF version |
