La production avec machines parallèles

Comme nous l’avons vu dans le chapitre précédent, l’un des décisions au niveau opérationnel qui a probablement des impacts sur les performances du laboratoire d’analyses physico-chimiques est la gestion opérationnelle des échantillons. Ces décisions deviennent plus complexes lorsque dans certaines étapes de l’analyse disposent d’un ensemble de machines identiques disposées parallèlement [24], [81], [67]. Cela implique dans un premier temps définir l’affectation des tâches aux machines, et ensuite, définir leur ordre de traitement. A cela, les conditions du cas étudié imposent des dates de disponibilité des tâches (ri) différentes et une fonction objectif mesurant le retard causé (minPTi). A notre connaissance, la seule publication qui résout le problème Pm/ri/ PTi est l’article de Yalaoui [140]. Dans cet article, plusieurs méthodes heuristiques ont été testées afin de résoudre le problème décrit. Une méthode appelée ABHG est signalée comme dominant dans la minimisation du retard, avec des temps de calcul acceptables. Également, dans cet article la génération d’instances est un sujet étudié. Les conclusions issues de cette étude sont reprisées dans le chapitre 3. Malgré le nombre réduit de publications concernant le problème Pm/ri/ PTi , la suite de cette section présente des références traitant des problèmes proches, où des conclusions ou des méthodes intéressantes sont proposées. Le problème où une seule machine est disponible est souvent étudié : Du et Leung [43] établissent que le problème est NP-difficile avec l’objectif de la minimisation du retard total. Une étude bibliographique à propos du problème avec une seule machine disponible a été présentée en 2009 par Koulamas [67]. Récemment, Gafarov et al. [49] ont développé un algorithme pseudo-polynomiale pour la minimisation du retard total, avec l’utilisation d’une seule machine. En 2013 Zhou et Liu [143] ont conclu que pour des problèmes structurés tels que l’ordonnancement de tâches avec la minimisation du retard total sur une seule machine, les méthodes à décomposition ont des performances comparables à celles des métaheuristiques souvent utilisées dans la résolution de ce type de problème combinatoire, en termes La production avec machines parallèles de l’utilisation de mémoire et temps de calcul. Le problème avec deux ou plusieurs machines en parallèle est traité dans certaines références comme un problème intéressant d’ordonnancement. Koulamas en 1994 [65] a réalisé une étude à propos du problème général de la minimisation de critères liés aux retards des tâches. Grâce aux conclusions avancées par l’auteur, on peut établir que le problème Pm/ri/ PTi est NP-difficile, car le problème sans les dates d’arrivée a été prouvé NP-difficile. Dans ce même article, l’auteur présente l’heuristique KPM pour le problème de machines parallèles mais avec des tâches disponibles dès l’instant 0 (les dates d’arrivée sont égales à 0). D’autres développements sont présentés par Jouglet et Savourey [61] pour la résolution du problème avec machines parallèles, et la minimisation du retard total pondéré. Le problème de minimisation du makespan (PCi) est souvent traité dans la littérature. Persma et Dijk [102] traitent le problème d’ordonnancement de l’atelier avec des machines indépendantes et minimisation du makespan. En 2011, Lin et al. [83] traitent un problème similaire, avec deux fonctions objectifs alternatives. En 2012, Dell’Amico et al. [6] comparent plusieurs méthodes de la littérature sur des instances connues du problème avec plusieurs machines en parallèle, et minimisation du makespan. Parmi les problèmes d’ordonnancement à machines parallèles, certains ont été montrés comme ayant des méthodes de résolution exactes nécessitant de temps de calcul d’ordre polynomial par rapport à la taille des instances. Ainsi, certains de ces problèmes sont : le problème d’assignation (Q/pi = p; ri/Cmax) [68], le problème à machines uniformes et minimisation de la somme des dates de fin (Qm/pi = p; ri/ PCi) [39], le problème avec machines indépendantes et minimisation de la somme des dates de fin (R/PCi) [28] [57], le problème avec fenêtres de temps et machines identiques (P/pi = p; ri/ PwiCi), entre autres. Certains cas où toutes les tâches ont des temps de traitement identiques ont été montrés comme ayant des temps de résolution polynomial par rapport à la taille de l’instance [50], [129]. Dans les cas traités dans ce mémoire, même si certaines tâches sont similaires, elles sont caractérisées par des temps de traitement différents, compris dans une plage de valeurs définie par le domaine d’activité. Pour les développements théoriques associés au chapitres 3, une plage de valeurs est pris dans la littérature (voir sections des résultats expérimentaux chapitres 3 et 4). 

 La production par lots dans les ateliers à cheminement unique

Dans le chapitre 1 nous avons vu le laboratoire d’analyses physico-chimiques comme étant une structure de recherche avec un fonctionnement similaire à un atelier de production composé de plusieurs opérations. Chacune des opérations est réalisée par un ou plusieurs équipements exclusivement dédiés à l’opération. La composition des lots de traitement est autorisée et souhaitable. Nous adressons ce problème comme F Hm, 

Les méthodes de résolution exactes

Les méthodes exactes sont proposées pour résoudre de manière optimale les problèmes combinatoires. L’efficacité de ces méthodes dépend, entre autres facteurs, de la structure du problème. Nous incluons dans cette section la programmation linéaire et les méthodes par séparation et évaluation («Branch-and-Bound»).

Programmation linéaire

Un programme linéaire est un problème d’optimisation qui inclut les éléments suivants : les variables de décision, la fonction objectif et les contraintes. Las variables de décision sont typiquement représentés par un vecteur symbolisé par X. Une combinaison linéaire de ces variables associées à des coûts (ou profits) représente la fonction objectif. Cette fonction est accompagnée d’un sens d’optimisation (minimisation, maximisation). Les contraintes sont aussi des combinaisons linéaires des variables de décision, qui imposent des limites et représentent la structure du problème traité. Une solution réalisable est, par conséquent, toute solution, qui respecte les conditions exprimées par les contraintes et qui a un coût (ou profit) calculé avec la fonction objectif. Le type de variable de décision utilisé définit la programmation linéaire à employer. Ainsi, différents types de modèles de programmation linéaire peuvent surgir : des modèles de programmation linéaire binaire (variables binaires), de programmation linéaire en nombres entiers (variables entières) ou de programmation linéaire mixte (variables entières et réelles) ou MIP («Mixed Integer Problem»), entre autres. La méthode de résolution la plus populaire pour résoudre programmes linéaires est l’algorithme simplex, lequel a été utilisé depuis sa création dans nombreux domaines [36]. Cette méthode et des améliorations sont utilisées dans des solveurs spécialisés tel que CPLEX, XPRESS, GAMS entre autres.