Problèmes d’ordonnancement cyclique

Les problèmes d’ordonnancement sont parmi les problèmes d’optimisation combinatoire les plus étudiés. L’ordonnancement, comme défini dans la littérature, consiste à placer des tâches dans le temps, et plus précisément à trouver une date de début pour chaque tâche. Les tâches peuvent être soumises à différentes contraintes. Parmi celles que nous trouvons couramment dans la littérature de l’ordonnancement, il y a par exemple les contraintes de précédence. Ces contraintes expriment le fait qu’une tâche ne peut pas s’exécuter avant que l’exécution d’une autre tâche soit achevée. Il y aussi des contraintes de ressources. Par ressource, nous entendons des ressources humaines comme les opérateurs dans une ligne d’assemblage, ou techniques comme les machines ou les robots. Ces contraintes définissent la quantité d’une ou plusieurs ressources qui doivent être allouées afin d’exécuter une tâche donnée, ainsi que la capacité de ses ressources qui doit être respectée à chaque instant. Il est commun de rencontrer des contraintes de deadlines dans les problèmes d’ordonnancement. Ces contraintes imposent le fait que pour chaque tâche i, elle doit être exécutée avant une date fixée di . Notons que dans certains cas, ces deadlines ne peuvent pas être satisfaites et peuvent donc engendrer des pénalités. Notons qu’il existe bien d’autres contraintes selon les types de problèmes étudiés ainsi que les applications. À ces contraintes d’ordonnancement se rajoute en général une (ou plusieurs) fonction(s) objectif(s) permettant de mesurer la performance des solutions possibles. Parmi les fonctions objectifs les plus utilisées, nous citons la minimisation du makespan, c’est à dire la durée totale de l’ordonnancement, la minimisation de la somme pondérée des dates de fin d’exécution des tâches, la minimisation du nombre de deadlines non respectées, etc.

Dans les problèmes d’ordonnancement classique chaque tâche est exécutée une seule et unique fois. Dans cette thèse, nous nous intéressons à un autre type de problèmes d’ordonnancement où l’exécution des tâches, dites tâches génériques, doit être répétées plusieurs ou une infinité de fois. Ce cas est très récurrent, par exemple, dans les cellules robotisées [Levner 2007]. En effet, un ensemble de robots exécute les mêmes tâches d’une manière répétitive, ce qui permet d’établir un ordonnancement qui va être répété infiniment. Il est aussi récurent que l’aspect cyclique apparaisse dans les problèmes de planning. Par exemple, les passages des transports publics sont périodiques, l’emploi du temps du personnel du transport peut l’être aussi [Liebchen 2007]. Dans d’autre cas, l’introduction d’un aspect cyclique est une des manières de réduire la taille des problèmes d’ordonnancement classique. Ceci est réalisé en créant des batchs qui peuvent être exécutés d’une manière cyclique. Les objectifs considérés en ordonnancement cyclique sont différents de ceux considérés en ordonnancement classique. En ordonnancement cyclique, l’objectif le plus utilisé est la minimisation du temps de cycle. Cela revient à minimiser la différence de temps entre deux exécutions successives. Notons que minimiser le temps de cycle d’un ordonnancement est semblable à la maximisation du taux de production, ce qui permet une meilleure utilisation des ressources. Le deuxième critère le plus utilisé est la minimisation du work-in-process, qui représente le nombre maximum d’occurrences du même job qui peuvent être exécutées en même temps. Minimiser cette valeur revient à minimiser les stocks intermédiaires. Notons que minimiser le work-in-process va dans le même sens que de minimiser le makespan des premières exécutions des tâches.

Il existe de nombreux avantages quant à l’utilisation de l’ordonnancement cyclique. En effet, cela permet une meilleure utilisation des ressources. C’est-à-dire, contrairement à l’ordonnancement classique, permet d’avoir une vision à long terme quant à l’utilisation des ressources. Il permet d’avoir des stocks de produits finis plus lisses et enfin, il offre une simplicité d’implémentation puisqu’il suffit de trouver un ordonnancement pour un ensemble de tâches et de le répéter infiniment. L’ordonnancement cyclique trouve des applications dans différents domaines. Par exemple, il existe des applications dans le domaine de la robotique [Levner 2007, Dawande 2005, Kats 2002a], le pipeline logiciel [Benabid 2011a, Gasperoni Asperoni 1994, Sucha 2008, Hanzalek 2011], les systèmes de production [Hanen 1997, HITZ 1979], la logistique, etc.

Problème d’ordonnancement cyclique de base

Le problème d’ordonnancement cyclique de base (BCSP : Basic Cyclic Scheduling Problem) est un problème central en ordonnancement cyclique, étant donné qu’il constitue la base de résolution de la plupart des problèmes d’ordonnancement cyclique. En effet, dans plusieurs problèmes d’ordonnancement cyclique, une fois que le valeurs de certaines variables de décision sont fixées, le sous-problème qui en résulte est un BCSP, ce qui permet d’utiliser les algorithmes de résolution du BCSP afin d’évaluer des solutions de problèmes plus complexes. Soit T = {1, …, n} un ensemble de n tâches dites tâches génériques. Elles sont dites génériques parce qu’elles doivent être exécutées de manière répétitive. Chaque tâche i ∈ T a une durée d’exécution pi et doit être exécutée sans préemption. Afin de distinguer les différentes exécutions de ces tâches génériques, nous notons hi, ki la k-ème occurrence de la tâche i telle que k ∈ N, et t(i, k) ∈ R sa date de début. Un ordonnancement cyclique σ est une affectation des dates de début tσ (i, k) ∈ R pour chaque occurrence hi, ki de chaque tâche générique i ∈ T .

Modélisation du BCSP

Différents modèles ont été proposés dans la littérature pour la représentation des problèmes d’ordonnancement cyclique. Nous rappelons quelques modélisations, en nous concentrant davantage sur celles basées sur la théorie des graphes et sur la programmation linéaire.

Algèbre (max, +)
La représentation par l’algèbre (max, +) a été proposée pour le BCSP dans [Cuninghame-Green 1962]. Cette approche est une approche algébrique, créée comme une alternative à l’algèbre usuelle qui utilise des équations linéaires. En effet, il existe des problèmes d’ordonnancement, dont les problèmes d’ordonnancement cyclique, qui nécessitent l’opérateur max qui n’est pas linéaire. Cette approche ne sera pas détaillée dans ce manuscrit mais on peut mentionner [Singh 2014], [Houssin 2011] et [Barman 2018].

Réseau de Petri
Un BCSP peut être modélisé par un réseau de Petri ([Benabid-Najjar 2012] et [Song 1998a]). Plus précisément, par une classe de réseaux de Petri appelée graphe à événement temporisé (TEGs : Timed event graphs). Notons que le passage d’un graphe uniforme à un TEG et l’inverse peut se faire d’une manière aisée. Les TEGs représentent un outils de modélisation et de visualisation pour des problèmes d’ordonnancement en général et des problèmes d’ordonnancement cyclique en particulier. Concernant la résolution, le graphe TEG est mis en équations avant de résoudre le problème.

Théorie des graphes
En théorie des graphes, deux représentations possibles pour le BCSP existent. La première est une représentation étendue, c’est à dire un graphe contenant toutes les occurrences des tâches génériques et tous les arcs de précédence. Dans ce graphe, qui est un graphe infini, chaque nœud représente une occurrence hi, ki d’une tâche générique i ∈ T . Il existe un arc (i, j) entre l’occurrence hi, ki et hj, k + Hij i si et seulement si il y a une contrainte de précédence générique entre i et j ayant une hauteur Hij . Notons que cette représentation n’est utilisée que pour prouver certains résultats sur le BCSP et non pas pour sa résolution. L’autre possibilité est de représenter le BCSP par un graphe générique bi-valué G = (T ,P, L, H), appelé graphe uniforme. Chaque nœud v ∈ T représente une tâche générique dans le BCSP et chaque arc eij ∈ P représente une contrainte de précédence dans le BCSP. La fonction L : A 7→ N associe, pour chaque arc eij ∈ P, une longueur L(eij ) = pi et la fonction H : A 7→ Z, appelée fonction de hauteur, associe pour chaque arc eij ∈ P, une hauteur H(eij ) = Hij .

Table des matières

Introduction
1 Problèmes d’ordonnancement cyclique
1.1 Introduction
1.2 Problème d’ordonnancement cyclique de base
1.2.1 Modélisation du BCSP
1.2.2 Caractérisation du temps de cycle optimal
1.2.3 Résolution d’un BCSP
1.2.4 Extensions du BCSP
1.2.5 Ordonnancement K-périodique
1.3 Problème du job shop cyclique
1.3.1 Résoudre un problème de CJSP
1.4 Problèmes d’ordonnancement cyclique : extensions
1.5 Conclusion
2 Optimisation robuste et ordonnancement
2.1 Introduction
2.2 Approche statique
2.2.1 Ensembles d’incertitude
2.3 Optimisation robuste discrète
2.4 Approche multi-niveaux
2.4.1 Incertitude sur le membre de droite
2.4.2 Règles de décisions affines
2.5 Ordonnancement et robustesse
2.6 Conclusion
3 Problème d’ordonnancement cyclique de base robuste
3.1 Introduction
3.2 Définition du problème
3.3 Résultats théoriques
3.4 Approches de résolution pour le U Γ-BCSP
3.4.1 Procédure de séparation
3.4.2 Algorithme itératif
3.4.3 Recherche binaire
3.4.4 Adaptation de l’algorithme de Howard
3.5 Expérimentations numériques
3.6 Conclusion
Conclusion

Lire le rapport complet