Dans une usine de production de textile, il y a des métiers à tisser. Ces métiers à tisser peuvent être configurés de différentes façons. Des tâches doivent être exécutées sur ces métiers à tisser et le temps d’exécution d’une tâche est fonction du métier sur lequel elle est effectuée. De plus, chaque tâche est seulement compatible avec les métiers à tisser étant configurés de certaines façons. Un temps de mise en course peut permettre de configurer ou préparer un métier à tisser pour l’exécution d’une tâche. Le temps de mise en course est dépendant de la tâche qui précède et de celle qui suit. Nous souhaitons alors créer un horaire pour minimiser les temps de fabrication et les retards. Toutefois, certaines contraintes doivent être respectées. Lorsque des préparations surviennent sur des métiers différents en même temps, le nombre d’employés doit être suffisant. Un métier ne peut faire qu’une seule action à la fois. L’ordonnancement d’une seule machine est un problème NP-Difficile. Dans ce projet, il faut ordonnancer environ 800 tâches sur 90 machines dans un horizon de deux semaines, tout en respectant les contraintes de personnel. Des évènements stochastiques doivent être pris en compte pour obtenir un meilleur horaire. Le bris d’un fil n’étant pas un évènement rare, l’occurrence des bris est donnée sous la forme d’une loi de Poisson. Nous proposons alors une approche de résolution utilisant une heuristique de branchement basée sur le problème du commis voyageur. Cette approche permet d’obtenir de bonnes solutions pour le problème d’ordonnancement exploré. Les solutions trouvées sont 5 à 30% meilleures en termes de fonction objectif qu’une heuristique semblable à celle utilisée par l’équipe de planification de notre partenaire industriel. Nous présentons aussi un algorithme pour garantir la robustesse d’un horaire. Notre algorithme permet de générer des horaires plus réalistes et qui résistent bien aux évènements imprévus. La combinaison de ces deux pratiques mène à l’intégration et l’utilisation du produit final par notre partenaire industriel. / In a textile factory, there are looms. Workers can configure the looms to weave different pieces of textiles. A loom can only weave a piece of textiles if the piece of textiles is compatible with its loom configuration. To change its configuration, a loom requires a setup. The setups are performed manually by workers. There are also sequence-dependent setups to prepare a loom for the upcoming piece of textiles. We wish to minimize the setups duration and the lateness. A solution must satisfy some constraints. The problem is subject to cumulative resources. The quantity of workers simultaneously configuring machines can’t exceed the total number of employees. A loom can only weave a piece of textiles at a time. Scheduling tasks on a single loom is an NP-Hard problem. In this project, we must schedule tasks an average of 800 tasks on 90 looms with a two-week horizon. Stochastic events might occur and must be accounted for. We must design an algorithm to create robust schedules under uncertainty. As a thread breaking during the weaving process isn’t a rare occurrence, a better schedule could greatly impact the performances of a company when applying the schedule to a real situation. We formulate that the number of breaks per task follows a Poisson distribution. First, we propose a branching heuristic based on the traveling salesperson problem in order to leverage computation times. The solutions found are 5 to 30% better according to their objective function than the ones of a greedy heuristic similar to what our industrial partner uses. We also present a filtering algorithm to guarantee robustness of solutions in respect to a confidence level. This algorithm improves robustness and creates more realist schedules. The algorithm is also efficient in computation time by achieving bound consistency in linear time. Combining both these techniques leads to the integration of our research in the decision system of our industrial partner.

Cette thèse présente trois approches pour aider les entreprises dans la planification dans un contexte dynamique. Chaque approche aide à différents niveaux de la planification (décisions stratégiques à long terme, tactique à moyen terme, décision opérationnelle à court terme ou même au moment de l'exécution). Après la génération d'un plan, il est possible que des événements rendent le plan inutilisable. L'entreprise doit alors générer un autre plan suivant ces nouvelles informations. Il est donc important pour une entreprise de pouvoir s'adapter rapidement aux changements et d'être plus agile. Les entreprises peuvent utiliser des systèmes d'aide à la décision permettant de les aider à prendre de meilleures décisions pour leur planification. Ces outils, bien qu'ils soient performants pour résoudre un problème, sont souvent non adaptés au contexte dynamique des entreprises. Cette thèse présente trois approches permettant d'adapter les plans rapidement suivant l'évolution des problèmes. La première approche est pour le niveau tactique de la planification. Le plan tactique considère un certain horizon de planification (ex. : 52 semaines). La solution trouvée pour cet horizon devient obsolète après un certain temps, car plusieurs éléments du problème ont changé. Il serait avantageux pour une entreprise de toujours tenir à jour le plan chaque fois qu'il y a une nouvelle information. Par contre, générer un nouveau plan demande beaucoup de temps. L'approche que nous proposons est de tenir à jour le plan, mais en s'aidant des décisions prises précédemment. Nous avons testé cette approche sur le problème d'optimiser la position des outils pour les machines à commande numérique avec tourelles. Nous avons conçu un programme à nombres entiers pour résoudre le problème. Après avoir trouvé la position optimale des outils pour chaque produit usiné, il est possible qu'un nouveau produit s'ajoute à la liste des produits à usiner. Il y a un grand coût en temps de production à devoir modifier la position des outils. Nous devons donc trouver la position des outils pour le nouveau produit sans changer la position des outils pour les autres produits pour éviter de perdre trop de temps. Le modèle conçu pour résoudre le problème comporte une fonction objectif permettant d'être réutilisé lors de l'ajout d'un nouveau produit. Il est alors possible de voir l'évolution de la solution chaque fois qu'on ajoute un nouveau produit. À chaque ajout d'un nouveau produit, nous pouvons évaluer s'il est avantageux de changer la position des outils pour tous les produits. La deuxième approche est pour le niveau opérationnel de la planification. Le planificateur peut s'aider d'un programme d'optimisation pour trouver un plan réalisable et optimal à son problème. Cependant, au niveau opérationnel, il peut arriver divers imprévus rendant le plan désuet. Par exemple, une commande de matériel peut arriver en retard ce qui crée un délai avant de pouvoir fabriquer un certain produit. Il faut donc trouver une alternative au plan initiale pour pallier cet imprévu. Il peut être difficile et même impossible pour un humain de changer le plan tout en respectant les contraintes du problème et l'optimalité du plan initial. Le planificateur peut exécuter une nouvelle fois le programme d'optimisation pour prendre en considération cet imprévu, mais cela demande un certain temps dont le planificateur n'a pas pour prendre la décision. L'approche proposée est d'utiliser un système à initiative partagée. Ce système permet de changer une solution retournée par un programme mixte à nombres entiers tout en conservant l'optimalité de la solution. Le système génère plusieurs solutions pour pouvoir rapidement retourner une solution suivant une modification à la solution par le planificateur. Pour générer les solutions rapidement, le système repose sur une technique personnalisée basée sur le noyau de la matrice de contraintes. La troisième approche est pour le niveau stratégique de la planification. Les décisions au niveau stratégique sont pour le long terme. Par exemple, une entreprise manufacturière doit décider quelles ressources achetées pour améliorer sa productivité. L'approche proposée est de suggérer des choix au planificateur lors de la génération des plans au niveau opérationnel ou tactique. L'entreprise peut alors prendre des choix plus rapidement sans devoir mettre beaucoup d'efforts d'analyse. Cette approche est testée sur un problème d'ordonnancement qui se fait au niveau de la planification opérationnelle. Suivant la génération du plan à l'aide de la programmation par contraintes, il est possible de suggérer des ressources à acheter pour améliorer la solution. Cette approche utilise l'apprentissage automatique pour prédire l'impact sur la solution d'apporter certains changements comme par exemple d'acheter une nouvelle ressource. L'idée est de s'entraîner sur les instances du problème passées pour faire des suggestions sur l'instance du problème courant. / This thesis presents three approaches to help companies pla in a dynamic context. Each approach helps at different levels of planning: strategic decisions for long-term, tactics decisions for medium-term, operational decisions for short-term or even at the time of execution. After the generation of a plan, it is possible that the plan becomes unusable following an unforeseen event. The company must then generate another plan based on this new information. It is therefore important for a company to be able to adapt quickly to changes and to be more agile. Companies can use decision support systems to help them make better decisions for their planning. These tools are effective in solving a problem, but are often not adapted to the dynamic context of companies. This thesis presents three approaches to make it possible to adapt the plans quickly following the evolution of the problems. The first approach is for the tactical level of planning. The tactical plan considers a certain planning horizon (ex.: 52 weeks). The solution found for this horizon becomes obsolete after some time, because several elements of the problem have changed. It would be advantageous for a business to always keep the plan up to date whenever there is new information. However, it would take a lot of time. Our approach is to keep the plan up to date, but with the help of decisions made previously. We tested this approach on the problem of optimizing the position of the tools for CNC machines with turrets. We designed an integer program to solve the problem. After finding the optimal tool position for each product to be machined, a new product may be added to the list of products to be machined. There is a great time cost in having to change the position of the tools. We must therefore find the position of the tools for the new product without changing the position of the tools for the other products. The template designed to solve the problem has an objective function that can be reused when adding a new product. It is then possible to see the evolution of the solution when a new product is added. The second approach is for the operational level of planning. The planner can use an optimization program to find a feasible and optimal plan for his/her problem. However, there can be various unforeseen events that make the plan obsolete. For example, a material order may arrive late which creates a delay before being able to manufacture a product. We must therefore find an alternative to the initial plan to overcome this unforeseen event. It can be difficult and even impossible for a human to change the plan while respecting the constraints of the problem as well as the optimality of the plan. The planner may run the optimization program again to take this unforeseen into consideration, but it may take too long. The proposed approach is to use a mixed initiative system making it possible to change a solution returned by an integer program while maintaining the optimality of the solution. The system generates several solutions to be able to quickly return a solution following a modification by the planner. The system is based on a custom technique based on the kernel of the constraint matrix. The third approach is for the strategic level of planning. Decisions at the strategic level are for the long term. For example, a manufacturing company must decide which tools to purchase to improve their productivity. The proposed approach is to suggest choices to the planner when generating plans at the operational level. The business can make choices faster without having to put in a lot of analytical effort. This approach is tested on a scheduling problem located at the operational planning level. This approach uses machine learning to predict the impact on the solution of making certain changes such as purchasing a new resource. The idea is to practice on past problem instances to make suggestions on the current problem instance.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Cette thèse traite de l'ordonnancement dans les systèmes distribués. L'objectif est d'étudier l'impact de l'incertitude sur les ordonnancements et de proposer des techniques pour en réduire les effets sur les critères à optimiser. Nous distinguons plusieurs aspects de l'incertitude en considérant celle liée aux limites des méthodes employées (e.g., modèle imparfait) et celle concernant la variabilité aléatoire qui est inhérente aux phénomènes physiques (e.g., panne matérielle). Nous considérons aussi les incertitudes qui se rapportent à l'ignorance portée sur les mécanismes en jeu dans un système donné (e.g., soumission de tâches en ligne dans une machine parallèle). En toute généralité, l'ordonnancement est l'étape qui réalise une association ordonnée entre des requêtes (dans notre cas, des tâches) et des ressources (dans notre cas, des processeurs). L'objectif est de réaliser cette association de manière à optimiser des critères d'efficacité (e.g., temps total consacré à l'exécution d'un application) tout en respectant les contraintes définies. Examiner l'effet de l'incertitude sur les ordonnancements nous amène à considérer les aspects probabilistes et multicritères qui sont traités dans la première partie. La seconde partie repose sur l'analyse de problèmes représentatifs de différentes modalités en terme d'ordonnancement et d'incertitude (comme l'étude de la robustesse ou de la fiabilité des ordonnancements) / This thesis consists in revisiting traditional scheduling problematics in computational environments, and considering the adjunction of uncertainty in the models. We adopt here a wide definition of uncertainty that encompasses the intrinsic stochastic nature of some phenomena (e.g., processor failures that follow a Poissonian distribution) and the imperfection of model characteristics (e.g., inaccuracy of the costs in a model due to a bias in measurements). We also consider uncertainties that stem from indeterminations such as the user behaviors that are uncontrolled although being deterministic. Scheduling, in its general form, is the operation that assigns requests to resources in some specific way. In distributed environments, we are concerned by a workload (i.e., a set of tasks) that needs to be executed onto a computational platform (i.e., a set of processors). Therefore, our objective is to specify how tasks are mapped onto processors. Produced schedules can be evaluated through many different metrics (e.g., processing time of the workload, resource usage, etc) and finding an optimal schedule relatively to some metric constitutes a challenging issue. Probabilistic tools and multi-objectives optimization techniques are first proposed for tackling new metrics that arise from the uncertainty. In a second part, we study several uncertainty-related criteria such as the robustness (stability in presence of input variations) or the reliability (probability of success) of a schedule

Reproduction de : Thèse de doctorat : Psychologie. Psychologie ergonomique : Paris 8 : 2006. / Titre provenant de l'écran-titre. Bibliogr. f. 273-282.

Thèse doctorat : Informatique : Villeurbanne, INSA : 2007. / Titre provenant de l'écran-titre. Bibliographie, 16 p. Glossaire.

Reproduction de : Thèse de doctorat : Automatique (Recherche opérationnelle) : Metz : 2002. / Titre provenant de l'écran-titre. Notes bibliographiques.

Le cloud computing a émergé au cours de la dernière décennie pour être largement adopté aujourd’hui dans plusieurs domaines de l’informatique. Il consiste à proposer des ressources axées, ou non, sur le marché sous forme de services qui peuvent être consommés de manière souple et transparente. Dans cette thèse, nous traitons le problème d’ordonnancement, un des enjeux majeurs du cloud. Selon la configuration de cloud ciblée, nous avons identifié trois niveaux d’ordonnancement : niveau service, niveau tâche et niveau machine virtuelle. Nous revisitons la modélisation du problème, la conception et l’implémentation des métaheuristiques multiobjectives pour chaque niveau d’ordonnancement du cloud. Les ordonnanceurs à base de métaheuristiques que nous proposons portent sur différents critères notamment la consommation d’énergie, les émissions de gaz à effet de serre, le profit et la qualité du service (coût et temps de réponse). Nous prouvons leur capacité d’adaptation aux contraintes du cloud en les intégrant au sein du gestionnaire de cloud OpenNebula. De plus, nos ordonnanceurs ont été largement expérimentés utilisant des configurations réalistes de cloud sur Grid’5000, en tant qu’infrastructure en tant que service (IAAS), et des scénarios concrets basés sur les instances et les tarifications d’Amazon EC2. Les résultats présentés montrent que les méthodes que nous proposons surpassent les approches d’ordonnancement existantes sur tous les critères cités précédemment. / Cloud computing has emerged during the last decade to be widely adopted nowadays in several IT areas. It consists to propose market or not market-oriented resources as services that can be consumed in a ubiquitous, flexible and transparent way. In this PhD thesis, we deal with scheduling, one of the major cloud computing issue. According to the targeted cloud configuration, we have identified three levels of scheduling: service-level, task-level and Virtual Machine-level. We revisit the problem modeling, the design and the implementation of multi-objective metaheuristics for each scheduling level of the cloud. The proposed metaheuristics-based schedulers address different criteria including energy consumption, greenhouse gas emissions, profit and QoS (cost and response time). We prove their adaptability to the cloud constraints by integrating them as a part of the OpenNebula cloud manager. Moreover, our schedulers have been extensively experimented using realistic cloud configurations on Grid'5000, considered as an infrastructure as a service (IAAS), and concrete scenarios based on Amazon EC2 instances and prices. The reported results show that our proposed methods outperform existing scheduling approaches in terms of all previously cited criteria.

Thèse ou mémoire avec insertion d'articles / Les problèmes d'ordonnancement, où il faut planifier des tâches sur une ligne du temps en respectant différentes contraintes, sont présents dans une grande variété d'industries. Cela va de la conception d'horaire pour un hôpital jusqu'à la planification de la production en usine. Malheureusement, la plupart de ces problèmes sont NP-difficiles. La programmation par contraintes s'est montrée très efficace pour résoudre ces problèmes. Dans cette thèse, nous présenterons des algorithmes de vérification et de filtrage pour trois contraintes d'ordonnancement. La première, la contrainte $\textup{Cumulative}$ limite l'utilisation d'une ressource à une capacité maximale. Pour cette contrainte, nous améliorons la complexité d'algorithmes de vérification et de filtrage existants. La deuxième contrainte, la $\textup{SoftCumulative}$, est une variation de la $\textup{Cumulative}$ où il est possible de dépasser la capacité maximale, moyennant une pénalité. La troisième, la contrainte $\textup{MinCumulative}$, force une utilisation minimale, plutôt que maximale, de la ressource. Pour ces deux dernières contraintes, nous introduisons de nouveaux algorithmes qui sont inspirés par les algorithmes classiques de la contrainte $\textup{Cumulative}$. / Scheduling problems occur in various industries. Examples of these problems include, among others, nurse rostering, production planning in a factory, and airline crew scheduling. In such problems, one needs to schedule tasks on a time line while satisfying several constraints. Unfortunately, most of these problems are NP-Hard. Constraint programming has been shown to be an effective technique to solve NP-hard scheduling problems. In this thesis, we introduce checker and filtering algorithms for three scheduling constraints. $\textup{The Cumulative}$ constraint limits the resource consumption to a maximal capacity. For that constraint, we present faster checker and filtering algorithms. $\textup{The SoftCumulative}$ constraint is a variant of the $\textup{Cumulative}$ where it is possible to exceed the capacity, but doing so incurs a penalty. The $\textup{MinCumulative}$ constraint enforces a minimum resource usage, rather than limiting it. For those two constraints, we introduce new filtering algorithms that are inspired by classical algorithms for the $\textup{Cumulative} constraint.

Les travaux de recherche proposés dans cette thèse portent sur les problèmes d'ordonnancement rencontrés dans les systèmes de production automatisés en prenant en compte des contraintes telles que l'absence d'espace de stockage entre les machines et la flexibilité des ressources. Plus particulièrement, nous avons étudié les problèmes d'ordonnancement de job-shops classiques et hybrides soumis à des contraintes de blocage particulières avec comme objectif la minimisation du temps total d'opération. Dans un premier temps, nous avons modélisé les problèmes d'ordonnancement de type job-shop (classique et flexible) avec la contrainte de blocage particulière afin d'obtenir une solution exacte. Pour les problèmes de taille plus importante, il n'était pas possible d'obtenir une solution exacte à ce problème en un temps raisonnable. Par conséquent, nous avons développé des bornes inférieures complémentaires. Dans le cas du job shop classique, une méta-heuristique basée sur l'algorithme de recuit simulé pour résoudre le problème étudié a été proposée. Pour développer un voisinage efficace, nous avons donné une méthode qui permet de détecter les conflits qui peuvent survenir après la modification des séquences. Des résultats d'expérimentations réalisés sur des instances de petites et moyennes tailles montrent l'efficacité de bornes inférieures ainsi que l'heuristique développée / The research in this thesis ; focus on the scheduling problems encountered in automated production systems and takes into account new constraints, such as buffer stocks of limited capacity, flexibility of resources, etc.. Two main objectives are set, namely the proposal of new models of scheduling, development of approaches and lower bounds for scheduling systems studied (classical job shop and hybrid job shop with blocking Rcb). The lower bounds are developed for the problems of job-shop classic and hybrid with Rcb blocking constraint. Heuristics based on simulated annealing have been developed for the job-shop problems subject to the Rcb blocking constraint. Results of experiments conducted on instances of small and medium sizes show the effectiveness of lower bounds and heuristics developed