Program > By author > Houssin Laurent

Les problèmes de Job-Shop peuvent souvent être simplifiés en les considérant comme des problèmes cycliques. L'ordonnancement des tâches devient ainsi cyclique et son objectif
est d'organiser les activités de production en répétant un cycle de base que l'on a optimisé. De nombreux paramètres entrent en jeu dans l'optimisation du cycle de base tels que la
période du cycle choisie, l'ordre des opérations élémentaires pour réaliser un travail, la durée de ces opérations, le nombre de produits à réaliser par cycle, etc.
Plusieurs approches ont été utilisées pour résoudre ce problème. Parmi elles, nous
pouvons citer l'approche par réseaux de Petri et plus particulièrement par graphes d'événements
temporisés, l'approche par les graphes, l'approche par la programmation linéaire
et l'approche par la théorie des tas.

Concernant l'approche par la théorie des tas, le sous-problème de l'évaluation d'une
solution peut être résolu aisément avec l'aide de la théorie des tas. En effet, en traduisant
le problème dans une structure mathématique adaptée, l'évaluation du taux de production
du cycle revient au calcul d'une valeur propre d'un produit de matrices dans lequel chacune
des matrices représente une opération élémentaire. Cette propriété s'avère particulièrement
intéressante dans le cas de l'évaluation successive d'un grand nombre d'ordonnancement.

En outre, la théorie des tas permet une représentation très intuitive d'un ordonnancement,
puisque celui-ci s'illustre comme un empilement de plusieurs briques (en fait, un « tas »
de briques) dont le contour supérieur correspond aux dates de fin des dernières opérations
des machines.

Dans ce papier nous présentons les derniers résultats concerant l'application de cette théorie à l'ordonnancement cyclique.

Plus particulièrement, nous montrons que le problème du nombre d' "en cours" à l'intérieur du motif peut être résolu au prix d'une extension du tas.