Neste trabalho, apresentamos um estudo sobre o problema de dimensionamento de lotes com múltiplas plantas, múltiplos itens e múltiplos períodos. As plantas têm capacidade de produção limitada e a fabricação de cada produto incorre em tempo e custo de preparação de máquina. Nosso objetivo é encontrar um plano de produção que satisfaça a demanda de todos os clientes, considerando que a soma dos custos de produção, de estoque, de transporte e de preparação de máquina seja a menor possível. Este trabalho tem duas contribuições centrais. Primeiramente, propomos a modelagem do problema de dimensionamento de lotes com múltiplas plantas utilizando o conceito de localização de facilidades. Para instâncias de pequena dimensão, os testes computacionais mostraram que a resolução do problema remodelado apresenta, como esperado, resultados melhores que o modelo original. No entanto, seu elevado número de restrições e de variáveis faz com que as instâncias de maiores magnitudes não consigam ser resolvidas. Para trabalhar com instâncias maiores, propomos um método híbrido (math-heurística), que combina o método relax-and-fix, com a restrição de local branching. Testes computacionais mostram que o método proposto apresenta soluções factíveis de boa qualidade para estas instâncias / In this work, we present a study about the multi-plant, multi-item, multi-period lot-sizing problem. The plants have limited capacity, and the production of each item implies in setup times and setup costs. Our objective is to find a production plan which satisfies the demand of every client, considering that the sum of the production, stocking, transport and setup costs is the lowest possible. This work has two main contributions. Firstly, we propose the multi-plant lot-sizing problem modeling using the facility location concept. For small dimension problems, computational tests showed that the remodeled problem resolution presents, as expected, better results than the original model. However, the great number of restrictions and variables make bigger instances to be intractable. To work with the bigger dimension instances, we propose a hybrid method (math-heuristic), which combines the relax-and-fix method and the local branching restriction. Computational tests show that the proposed math-heuristic presents good quality feasible solutions for these instances

No description available.

This thesis deals with modelling diffenrent types of production lines. Modeling is done by the mathematical programming and simulation methods. Optimization related computations are mostly implemented in program GAMS. Simulation is realized by using program Matlab/SimEvents. The results are presented by the Gantt diagrams.

[pt] Nesta dissertação será apresentado como fundos de pensão na modalidade benefícios definidos podem recorrer à programação linear inteira mista para resolver problemas de ALM. Devemos considerar que a legislação brasileira determina que participantes e patrocinadores devam pagar contribuição extraordinária em caso de déficit ou, em caso de superávit persistente, parte do excesso contributivo deve ser devolvido aos participantes. Esse aspecto legal particular requer o uso de técnicas de programação inteira. Com o objetivo de modelar a ocorrência de eventos de desequilíbrio nos fundos de pensão foi necessária a introdução de variáveis inteiras para proceder a contagem do número de ocorrências desses eventos. Um exemplo simples, porém realista, foi introduzido para mostrar como os gestores de um fundo de pensão não só determinam a menor contribuição necessária à operação do fundo de pensão, mas também devem investir os recursos garantidores a fim de assegurar essa contribuição mínima. / [en] In this dissertation we discuss how defined benefit plans can use mixed integer linear programming to solve an ALM problem. We must consider that Brazilian pension fund regulations commands that participants and sponsors alike are to pay an extra contribution in case of deficit, or, in case of a persistent superavit, part of the exceeding contribution should return to its participants. This particular legal aspect forces us to use integer programming techniques. In order to model this lack of balance, an integer variable was considered so as to count how many times it occurs. A simple but realistic example is presented to show how pension fund managers may not only plan their operation to get the minimal possible contribution but also invest money to support it.

La chaine d’approvisionnement énergétique a fortement évolué aux cours des 20 dernières années. La libéralisation des marchés de l’électricité et les nouvelles technologies ont fortement influencé la manière d’envisager la production et la transmission d’électricité. Les modèles mathématiques classiques utilisés dans les problèmes lié à l’énergie ont besoin d’être revus pour intégrer les contraintes pratiques modernes.Un problème classique pour un Compagnie Génératrice (CG) est le problème de Unit Commitment (UC) qui consiste à établir un plan de production pour une demande en électricité connue. Lorsque ce problème fut considéré, le prix de l’électricité et la demande étaient relativement simple à estimer comme une seule CG nationale avait le monopole du marché. Ce problème a été étudié de manière extensive en utilisant de la Programmation Mathématique (PM). Aujourd’hui, le prix de l’électricité est relativement volatile à cause de l’introduction de marchés dérégulés et la demande du marché est répartie entre plusieurs CGs en compétition sur divers marchés. Une CG ne peut se limiter à considérer un problème de UC seul pour envisager sa production. Il y a un besoin d’intégrer les incertitudes liées au marché de l’électricité et aux quantités à produire aux modèles utilisés pour qu’une CG puisse établir un plan de production rentable.La technologie a aussi permis d’envisager de nouveaux concept tel que les Micro-Grilles (MGs). Une MG est composée d’un ensemble de consommateurs reliés à travers un réseau de transmission, possédant des générateurs d’électricité et optimisant leur consommation interne. Ce concept est possible grâce à l’utilisation croissante d’énergies renouvelables locales ainsi que l’utilisant croissante d’appareils interconnectés. Cependant, étant donné que les énergies renouvelables ont un faible rendement, sont intermittentes et que les appareils de stockage d’énergie sont encore peu efficaces, les MGs ne peuvent pas envisager d’être pleinement autonome en électricité. Il y a donc une nécessité d’avoir un fournisseur d’électricité externe pour avoir suffisamment d’électricité disponible à tout moment. Une CG jouant le rôle de fournisseur auprès d’une MG fait face énormément d’incertitude concernant la demande à cause de la gestion interne de la MG sur laquelle elle n’a pas de contrôle.Dans cette thèse, des problèmes d’optimisation intégrant de nouvelles contraintes modernes liés à l’approvisionnement énergétique sont étudiés via la PM. Plusieurs problèmes considèrant des interactions entre plusieurs acteurs sont modélisés via des formulations bi-niveau. Nous illustrons comment les difficultés liées aux contraintes modernes peuvent être exploitées pour obtenir des propriétés permettant de reformuler les problèmes étudiés en formulation linéaire en nombre entiers. Des heuristiques performantes sont obtenus à partir des formulations exactes dont certaines sont applicables à des problèmes plus généraux. Une analyse extensive de la performance des méthodes de résolution ainsi que de l’influence des contraintes modernes sont présentées dans diverses expériences numériques. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

La structure de projet se retrouve dans de nombreux contextes de l'industrie et des services. Il s'agit de réaliser un ensemble d'activités pouvant être connectées par des liens logiques de séquence (antériorité), en faisant appel à des ressources disponibles en quantité limitée. L'objectif est la minimisation d'un critère généralement lié à la durée ou au coût du projet. La plupart des problèmes d'ordonnancement de projet dans la littérature considèrent une unité de temps commune pour la détermination des dates d'exécution des activités et pour l'évaluation instantanée du respect des capacités des ressources qu'elles utilisent. Or, s'il est souvent nécessaire en pratique d'obtenir un calendrier détaillé des plages d'exécution des activités, l'utilisation des ressources peut être évaluée sur un horizon plus agrégé, comme par exemple les quarts de travail des employés. Dans cette thèse, un nouveau modèle intégrant ces deux échelles de temps est présenté afin de définir le problème d'ordonnancement de projet avec agrégation périodique des contraintes de ressources (PARCPSP). Ce problème est étudié du point de vue de la théorie de la complexité et des propriétés structurelles sont établies, mettant notamment en évidence des différences majeures avec le problème classique d'ordonnancement de projet sous contraintes de ressources (RCPSP). De ces propriétés sont dérivées des formulations exactes basées sur la programmation linéaire en nombres entiers, comparées en termes de qualité de la relaxation linéaire. Par ailleurs, plusieurs heuristiques, telles que des algorithmes de liste, ou une méthode approchée basée sur une résolution itérative qui exploite différentes échelles de temps, sont proposées. Les résultats expérimentaux montrent l'intérêt de ces différentes méthodes et illustrent la difficulté du problème. / The project structure arises in many fields of industry and services. It consists in performing a set of activities that may be linked by precedence relations, and use resources whose capacity is limited. The objective is to minimize a criterion usually linked to the duration or the cost of the project. Most of project scheduling problems in the literature assume that the same time scale should be used to determine activity start and completion dates and check resource constraints at each time. However, although it is often required in practice to build a precise schedule specifying the execution range of each activity, the resource usage can be evaluated on an aggregated basis, like worker shifts. In this thesis, a new model that enables the integration of these two time scales is presented in order to define the periodically aggregated resource-constrained project scheduling problem (PARCPSP). This problem is studied within the framework of complexity theory and several structural properties are established, highlighting major differences with the standard resource-constrained project scheduling problem (RCPSP). These properties allow deriving exact formulations based on integer linear programming, whose linear relaxations are compared. Moreover, several heuristics, such as schedule generations schemes, or an approached method based on a multi time scale iterative process, are proposed. Experimental results show the interest of these different methods and point out the intractability of the problem.

Dans cette thèse, nous étudions deux problèmes de planification de production motivés par des applications du monde réel. Tout d'abord, un problème de planification de production pour un projet de fabrication de vêtements est étudié et un outil d'optimisation est développé pour le résoudre. Deuxièmement, une version restreinte du problème de dimensionnement du lot de capacité avec des configurations dépendantes de la séquence est explorée. Diverses formulations mathématiques sont développées et une analyse de complexité est effectuée pour donner une première analyse du problème. / In this thesis, we study two production planning problems motivated by challenging real-world applications. First, a production planning problem for an apparel manufacturing project is studied and an optimization tool is developed to tackle it. Second, a restricted version of the capacitated lot sizing problem with sequence dependent setups is explored. Various mathematical formulations are developed and complexity analysis is performed to offer a first glance to the problem.

Quality is an important measurement within a semiconductor manufactory. Due to the fact that yield is directly affected by quality of the manufacturing process, in this paper a quality based scheduling approach will be presented which compares different methods like dispatching, MIP and CP, regarding different objectives. To test the different used methods a benchmark model of a semiconductor manufactory is build up. Here a lithography work center is used in detail where the rest of the fabrication is only build up as a delay station. With this model the repeatability for the example of a lithography step is investigated. Thereby in this investigation it is assumed, that each lithography tool has an offset which is transferred to the structure. Now the quality of a product should be best, if the offset from one layer to the next layer is minimized.

In this dissertation, we address three different combinatorial optimization problems (COPs), each of which has specific real-life applications. Owning to their specific nature, these problems are different from those discussed in the literature. For each of these problems, we present a mathematical programming formulation, analyze the problem to determine its useful, inherent structural properties, and develop an efficient methodology for its solution by exploiting these properties. The first problem that we address is the course timetabling problem encountered at Virginia Tech. The course timetabling problem for a university is a difficult problem and has been studied by many researchers over the years. As a result, a plethora of models and approaches have been reported in the literature. However, most of these studies have focused on applications pertaining to course scheduling for a single or at most few departments of a university. The sheer size of the university-wide timetabling problem that we address, involving thousands of courses to be scheduled in hundreds of classrooms in each semester, makes it a challenging problem. We employ an appropriate decomposition technique that relies on some inherent structural properties of the problem both during the modeling and algorithmic development phases. We show the superiority of the schedules generated by our methodology over those that are currently being used. Also, our methodology requires only a reasonable amount of computational time in solving this large-size problem. A facility layout problem involving arbitrary-shaped departments is the second problem that we investigate in this dissertation. We designate this problem as the arbitrary-shaped facility layout problem (ASFLP). The ASFLP deals with arranging a given set of departments (facilities, workstations, machines) within the confines of a given floor space, in order to optimize a desired metric, which invariably relates to the material handling cost. The topic of facility planning has been addressed rather extensively in the literature. However, a major limitation of most of the work reported in the literature is that they assume the shape of a department to be a rectangle (or even a square). The approach that relies on approximating an arbitrary-shaped department by a rectangle might result in an unattractive solution. The key research questions for the ASFLP are: (1) how to accurately model the arbitrary-shaped departments, and (2) how to effectively and efficiently determine the desired layout. We present a mixed-integer programming model that maintains the arbitrary shapes of the departments. We use a meta-heuristic to solve the large-size instances of the ASFLP in a reasonable amount of time. The third problem that we investigate is a supply chain scheduling problem. This problem involves two stages of a supply chain, specifically, a manufacturer and one or more customers. The key issue is to achieve an appropriate coordination between the production and distribution functions of the manufacturer so as to minimize the sum of the shipping and job tardiness costs. We, first, address a single customer problem, and then, extend our analysis to the case of multiple customers. For the single-customer problem, we present a polynomial-time algorithm to solve it to optimality. For the multiple-customer problem, we prove that this problem is NP-hard and solve it by appropriately decomposing it into subproblems, one of which is solvable in polynomial time. We propose a branch-and-bound-based methodology for this problem that exploits its structural properties. Results of an extensive computational experimentation are presented that show the following: (1) our algorithms are efficient to use and effective to implement; and (2) significant benefits accrue as a result of integrating the production and distribution functions. / Ph. D.

This thesis deals with stochastic location routing problem. Multiple stochas- tic and deterministic models are formulated and it is discussed that it is difficult to solve these problems via exact integer programming methods. It is necessary to develop heuristic methods to find a solution of these problems. Multiple ver- sions of these problems are formulated and their properties and possibilities how to solve them are discussed. Therefore, the brand new Blockchain metaheuristic is developed and later used for solving stochastic location routing problem ap- plied on a waste collection problem. As a part of Blockchain metaheuristic we develop the new application of Greedy algorihtm that is used for finding initial solution. The quality of the heuristic algorithm developed by us is presented in a numerical study. 1