Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

La lithographie et la loi de Moore ont permis des avancées extraordinaires dans la fabrication des circuits intégrés. De nos jours, plusieurs systèmes très complexes peuvent être embarqués sur la même puce électronique. Les contraintes de développement de ces systèmes sont tellement grandes qu’une bonne planification dès le début de leur cycle de développement est incontournable. Ainsi, la planification de la gestion énergétique au début du cycle de développement est devenue une phase importante dans la conception de ces systèmes. Pendant plusieurs années, l’idée était de réduire la consommation énergétique en ajoutant un mécanisme physique une fois le circuit créé, comme par exemple un dissipateur de chaleur. La stratégie actuelle est d’intégrer les contraintes énergétiques dès les premières phases de la conception des circuits. Il est donc essentiel de bien connaître la dissipation d’énergie avant l’intégration des composantes dans une architecture d’un système multiprocesseurs de façon à ce que chaque composante puisse fonctionner efficacement dans les limites de ses contraintes thermiques. Lorsqu’une composante fonctionne, elle consomme de l’énergie électrique qui est transformée en dégagement de chaleur. Le but de ce mémoire est de trouver une affectation efficace des composantes dans une architecture de multiprocesseurs en trois dimensions en tenant compte des limites des facteurs thermiques de ce système. / Lithography and Moore’s law have led to extraordinary advances in integrated circuits manufacturing. Nowadays, many complex systems can be embedded on the same chip. Development constraints of these systems are so significant that a good planning from the beginning of the development stage is essential. Thus, the planning of energy management at the beginning of the development cycle has become important in the design of these systems. For several years, the idea was to reduce energy consumption by adding a cooling system once the circuit is created, a heat sink for example. The current strategy is to integrate energy constraints in the early stages of circuits design. It is therefore important to know the energy dissipation before the integration of the components in the architecture of a multiprocessor system so that each component can work within the limits of its thermal stresses. When a component is running, it consumes electric energy which is converted into heat. The aim of this thesis is to find an efficient assignment of components in a multiprocessor system architecture in three dimensions, taking into account the limits of its thermal factors.

Les travaux de ce mémoire traitent du problème d’ordonnancement et d’optimisation de la production dans un environnement de plusieurs machines en présence de contraintes sur les ressources matérielles dans une usine d’extrusion plastique. La minimisation de la somme pondérée des retards est le critère économique autour duquel s’articule cette étude car il représente un critère très important pour le respect des délais. Dans ce mémoire, nous proposons une approche exacte via une formulation mathématique capable des donner des solutions optimales et une approche heuristique qui repose sur deux méthodes de construction de solution sérielle et parallèle et un ensemble de méthodes de recherche dans le voisinage (recuit-simulé, recherche avec tabous, GRASP et algorithme génétique) avec cinq variantes de voisinages. Pour être en totale conformité avec la réalité de l’industrie du plastique, nous avons pris en considération certaines caractéristiques très fréquentes telles que les temps de changement d’outils sur les machines lorsqu’un ordre de fabrication succède à un autre sur une machine donnée. La disponibilité des extrudeuses et des matrices d’extrusion représente le goulot d’étranglement dans ce problème d’ordonnancement. Des séries d’expérimentations basées sur des problèmes tests ont été effectuées pour évaluer la qualité de la solution obtenue avec les différents algorithmes proposés. L’analyse des résultats a démontré que les méthodes de construction de solution ne sont pas suffisantes pour assurer de bons résultats et que les méthodes de recherche dans le voisinage donnent des solutions de très bonne qualité. Le choix du voisinage est important pour raffiner la qualité de la solution obtenue. Mots-clés : ordonnancement, optimisation, extrusion, formulation mathématique, heuristique, recuit-simulé, recherche avec tabous, GRASP, algorithme génétique / The thesis deals with the optimization of the production on a number of machines subject to limited availability of the resources in an extrusion facility. Because of its importance to meet deadlines, the objective is to minimize the sum of weighted tardiness. This work presents a linear formulation of the problem and a number of heuristic solution methods. The proposed heuristic solution methods can be divided into two main groups: construction methods and neighborhood search methods. Also solution construction methods are divided in two sub-groups: parallel construction heuristics and serial construction heuristics. Adaptations of the simulated annealing algorithm (SA), the genetic algorithm (GA), the Tabu search (TS) method and the Greedy randomized adaptive search procedure (GRASP) are developed. Five neighborhood structures are used within the four tested neighborhood search algorithms. In our problem, setup times are sequence dependent. Also, extruders and dies are the bottleneck piece of equipment in this industrial setting. Several problem instances were generated for the evaluation of heuristic scheduling algorithms. The experimental study shows that the construction heuristics are not sufficient to ensure good results, however the proposed neighborhood search methods perform very well. Also, the structure of neighborhoods plays an important role to guarantee better results. Keywords: scheduling, optimization, extrusion, mathematical formulation, heuristic, simulated-annealing, tabu-search, GRASP, genetic algorithm