L’ordonnancement sur machines parallèles avec dates de début au plus tôt

Modélisation mathématique : Modèle avec variables mixtes

Le modèle présenté dans cette section reprend des caractéristiques utilisées par [23] et [140]. Étant donné que notre modèle contient deux types de variables, il est considéré du type MIP (Mixed Integer Problem). Des variables binaires xi,j sont utilisées pour les décisions d’affectation afin de définir si une tâche j est ordonnancée immédiatement après une tâche i sur la même machine. Ces variables de décision sont définies comme suit : xi,j =    1 Si la tâche i précède immédiatement la tâche j sur la même machine 0 Sinon Où i, j ∈ N . Les machines, étant identiques, les décisions d’affectations concernent l’identification des tâches successives et non la machine sur laquelle elles seront réalisées. Le deuxième type de variables sont les variables relatives aux temps. Ainsi, des variables entières sont utilisées pour représenter les dates de fin (Ci) et les retards (Ti). Nous utilisons des variables entières car toutes les caractéristiques sont supposées exprimées par des entiers positifs. Afin de réduire le nombre de variables générées, nous utilisons deux variables supplémentaires pour simuler le début et la fin du planning d’une machine donnée. De cette manière, le début du planning pour une machine quelconque est signalé par une tâche 0. La fin est identifié par une tâche N + 1. Le nombre de tâches supplémentaires est contrôlé avec les contraintes considérées dans le modèle. 

Classification des tâches : Les trois classes de tâches

La résolution des problèmes d’ordonnancement comme celui décrit dans ce chapitre s’effectue souvent par des méthodes approchées principalement à cause de sa complexité. En effet, le temps nécessaire pour trouver une solution optimale augmente de manière nonpolynomiale par rapport à la taille de l’instance à résoudre. Cela augmente le nombre de variables utilisées ainsi que la mémoire requise et les calculs nécessaires [59]. Les caractéristiques d’une instance du problème d’ordonnancement traité dans ce chapitre permettent d’obtenir des estimations de la difficulté à trouver des solutions de qualité suffisante. Certains auteurs ont cherché à caractériser les instances par leur réseaux d’activité associé [37], [105], [38]. Afin d’établir une classification des instances par rapport aux caractéristiques des tâches et machines et ainsi établir un lien avec la politique des retards, nous proposons d’utiliser 3 classes pour identifier les tâches. Nous appelons politique des retards (ou de difficulté globale) la distribution constatée dans les données qui définissent si en moyenne les tâches d’une instance quelconque seront ou non en retard. La composition des classes est en relation avec cette politique de risque parce qu’elles sont définies par rapport à la valeur probable du retard. ……..

La classification proposée dans cette section est dynamique

les tâches sont assignées aux classes en fonction d’un ordre établi Φ. Cette classification a été utilisée pour créer les méthodes heuristiques dans la section 3.5.2.2. Ainsi, en utilisant des thèses ou propositions développées pour problèmes avec différents fonctions objectives, nous cherchons à obtenir le meilleur comportement à l’intérieur de chaque classe. Une classification similaire a été proposée par Baptiste et al. [12] pour le problème avec une seule machine disponible. Pour définir cette classification, nous identifions avec m∗ la machine qui est disponible en premier, après avoir ordonnancé un ensemble Θ qui ne contient pas la totalité de tâches de l’ensemble N . On note t le premier instant où la machine m∗ est disponible. Pour les tâches restantes Γ, (Γ ∈/ Θ), elles seront assignées dans les trois classes suivantes : – γt≤rI : Ensemble de tâches non affectées avec ri > t – γt≤dI−pI : Ensemble de tâches non affectées où t + pi ≤ di – γt>dI−pI : Ensemble de tâches non affectées où t + pi > di La première classe γt≤rI est composée des tâches de l’ensemble Γ dont la date de disponibilité est plus grande que t. Cette classe contient (pour un ordre Φ) des tâches qui seront traitées et finies avant la date de fin souhaitée, ou exactement à cette date. Par conséquent, aucun retard n’est considéré pour les tâches dans cette classe. D’autre part, si une tâche i ∈ γt≤rI est affectée à la machine m∗ à l’instant t, le temps d’inactivité sur cette machine peut être augmenté. La classe γt≤dI−pI contient les tâches qui ont des dates de disponibilité inférieures à la disponibilité de la machine m∗ (ri < t), mais qui ne seront pas en retard (t + pi ≤ di). Pour cette classe, ainsi que pour la classe γt≤rI , nous pouvons déduire une caractéristique pour toute tâche i affectée à la machine m∗ à l’instant t. Le temps d’attente : δi = t − ri . La dernière classe γt>dI−pI correspond aux tâches qui seront très probablement en retard à condition d’être ordonnancées d’après Φ. Nous utilisons les classes γ dans la section 3.5.2.2 pour expliquer la construction des solutions en utilisant un ensemble de règles de priorité. La section suivante présente l’ensemble de méthodes de résolution testées dans ce chapitre. 

Méthodes de résolution

Dans cette section, nous présentons les algorithmes adaptés à la résolution du problème d’ordonnancement de machines parallèles avec des dates de disponibilité de tâches différents. D’abord, nous présentons la méthode exacte utilisée : la résolution du problème linéaire. 3.5 Méthodes de résolution 61 Nous présentons ensuite un ensemble de méthodes approchées, à commencer par la généralisation des algorithmes de liste classiques. Ensuite, des méthodes de solution dynamiques construites sur la base de la classification de la section 3.4 sont décrites. Ces méthodes, grâce à des temps d’exécution réduits, sont utilisées comme points de départ pour les méthodes métaheuristiques présentées à la fin de cette section. Ces méthodes sont évaluées dans une section ultérieure. 

Méthode exacte

Dans cette sous-section, une méthode de résolution exacte est présentée. Il s’agit de la résolution du modèle mathématique présenté dans une section précédente. La résolution par des méthodes exactes permet de trouver des solutions optimales du problème étudié. Par comparaison, et sur certaines conditions (voir section 3.7), elles permettent aussi d’estimer la performance des méthodes approchées sur des instances de petites tailles. Le modèle mathématique proposé dans la section 3.3 a été conçu avec des variables entières et réelles. Ce type de modèle est basé sur la programmation linéaire à variables mixtes (MIP Mixed Integer Problem). Des expérimentations peuvent être effectuées sur des solveurs commerciaux tels que CPLEX de ILOG-IBM. Nous avons testé ce modèle. Les résultats sont résumés dans la section 3.6. La résolution du problème Pm/ri/ PTi , nécessite de construire un total de M séquences de tâches, et d’en déduire les structures de données pour les valeurs Ci et Ti . Les méthodes exactes permettent de déterminer les solutions exactes des problèmes qui nous intéressent dans une durée d’exécution longue. Les bonnes performances obtenues sur des instances théoriques ne permettent pas la résolution efficace des problèmes réels. La résolution des instances testées dans le logiciel CPLEX a été limitée à 1800 secondes. Comme tout autre logiciel pour la résolution de problèmes combinatoires, garantir l’optimalité de certaines instances n’est pas réalisable dans des temps raisonnables pour les problèmes classifiés comme NP-difficiles. Malgré cela, ces logiciels sont capables de fournir des solutions de très bonne performance, sans pour autant garantir que la solution optimale ait été trouvée. Ces modèles ont été validées par des instances résolues avec des algorithmes d’énumération complète afin de vérifier l’optimalité des solutions fournies par le logiciel CPLEX.

Les méthodes heuristiques

Autre que proposer des solutions répondant à l’objectif de minimiser la somme des retards, les méthodes heuristiques sont capables de suivre le comportement dynamique des problématiques industrielles : la taille des problèmes est souvent trop grande, et les données varient facilement. Ceci nécessite d’une résolution plus rapide des problèmes. C’est pourquoi nous nous sommes tournés vers les méthodes approchées. Le cas industriel décrit dans le chapitre 1 est composé de phases qui ne sont pas complètement standardisées (voir chapitre A pour des problématiques dans la standardisation de procédés). Les durées de certaines analyses physico-chimiques peuvent changer à cause de conditions environnementales non suivies. Sachant que pour l’instant l’information disponible ne permet pas de proposer des modèles stochastiques pour la gestion opérationnelle des équipements, trouver des méthodes de résolution rapides est la priorité. Les méthodes de résolution proposées dans cette section ont été sélectionnées afin d’explorer l’espace de solutions par section, en commençant par des solutions uniques créées par des méthodes à liste, suivi par des explorations des voisinages proches. Afin de considérer des méthodes permettant d’échapper des optimaux locaux, des métaheuristiques ont été construites autour des recherches locales. Des métaheuristiques classiques sont aussi testées. 

Algorithmes de liste classiques

Les méthodes de liste adaptées au problème Pm/ri/ PTi sont pour la plupart présentées dans [140]. Nous appelons algorithmes de liste, les algorithmes qui générèrent un ordre de priorité unique parmi les tâches à ordonnancer. Ainsi, ces méthodes permettent de construire des programmes pour la gestion des machines avec des listes de priorité qui établissent la séquence de passage des tâches. Afin d’utiliser ce type de méthodes dans la résolution du problèmes avec machines parallèles, les listes de priorité sont accompagnées d’une règle d’affectation : – Au défaut d’autre mention, toute liste établissant l’ordre de passage des tâches est suivi, en affectant chaque tâche à la première machine disponible Les méthodes couramment utilisées sont présentées ci-après : – SP T (Shortest Processing Time) : Toute liste de priorité construite en SP T priorise les tâches avec les temps de traitement le plus court. Entre deux jobs (i, j) non ordonnancées, i précède j si pi < pj Cette méthode trouve des solutions optimales pour le problème de minimisation de la somme des dates de fin effectives PCi .