The latest generation of semiconductor wafer fabs produce Integrated Circuits (ICs) on silicon wafers of 300mm diameter. In this dissertation, we address the following two types of (new) scheduling problems that are encountered in this generation of wafer fabs: multiple-lots-per-carrier scheduling problem (MLCSP) and integrated automated material handling and lot scheduling problem (IMHLSP). We consider several variations of the MLCSP depending upon the number of machines used, the prevailing processing technology of the machines, and the type of objective functions involved. For the IMHLSP, we study two instances, one with infinite number of vehicles and the other with finite number of vehicles. We begin by introducing a single-machine, multiple-lots-per-carrier with single-wafer-processing-technology scheduling problem for the objective of minimizing the total completion time (MLCSP1). The wafer carrier is a front-opening unified pod (FOUP) that can hold a limited number of wafers. The problem is easy to solve when all the lots are of the same size. For the case of different lot sizes, we first relax the carrier (FOUP) capacity and propose a dynamic programming-based algorithm, called RelaxFOUP-DP, which enables a quick determination of its optimal solution that serves as a lower bound for the problem with limited FOUP capacity. Then, a branch-and-bound algorithm, designated as MLCSP1-B&B, is developed that relies on the lower bound determined by the RelaxFOUP-DP algorithm. Numerical tests indicate that MLCSP1-B&B finds optimal solutions much faster than the direct solution of the MLCSP1 model by the AMPL CPLEX 10.1 Solver. In fact, for the medium and low density problems, the MLCSP1-B&B algorithm finds optimal solutions at the starting node (node zero) itself. Next, we consider a single-machine, multiple-lots-per-carrier with single-carrier-processing-technology scheduling problem for the objective of minimizing total completion time (MLCSP2). As for the case of MLCSP1, the optimal solution for the case in which all the lots are of the same size can be obtained easily. For the case of different lot sizes, we determine a lower bound and an upper bound for the problem and prove the worst-case ratios for them. Subsequently we analyze a two-machine flow shop, multiple-lots-per-carrier with single-wafer-processing-technology scheduling problem for the objective of minimizing the makespan (MLCSP3). We first consider a relaxed version of this problem, and transform the original problem to a two-machine flow shop lot streaming problem. Then, we propose algorithms to find the optimal capacitated sublot sizes for the case of lots with (1) the same ratio of processing times, and, (2) different ratios of processing times on the machines. Since the optimal solutions obtained from the lot streaming problem may not be feasible to the MLCSP3, we develop heuristic methods based on the heuristic procedures for the bin packing problem. We develop four heuristic procedures for lots with the same ratio of processing times, and another four procedures for lots with different ratios of processing times on the machines. Results of our numerical experimentation are presented that show that our heuristic procedures generate almost optimal solutions in a matter of a few seconds. Next, we address the integrated automated material handling and lot scheduling problem (IMHLSP) in the presence of infinite number of vehicles. We, first, propose a new strong hybrid model, which has the advantages of both segregate and direct models. In the segregate model, a job is always transferred to the stocker after its completion at a station, while in the direct model, it is transferred to the next machine in case that machine can accommodate the jobs; otherwise, the job will stay at current station. The decisions involved in the strong hybrid model are the sequence in which to process the lots and a selection between the segregate and direct models for each lot, whichever optimizes system performance. We show that, under certain conditions about the processing times of the lots, the problem can be approximated by the cases of either infinite buffer or zero-buffer at the machines. Hence, we consider all three cases of the IMHLSP in this chapter, namely, infinite buffer, zero-buffer, and limited buffer sizes. For the strong hybrid model with limited buffer size, we propose a branch-and-bound algorithm, which uses a modified Johnson's algorithm to determine a lower bound. Two upper bounds for this algorithm are also determined. Results of our numerical investigation indicate that our algorithm finds optimal solutions faster than the direct solution of the IMHLSP model by the AMPL CPLEX 10.1 Solver. Experimental results also indicate that for the same problem size, the times required to solve the IMHLSP model with interbay movements are larger than those for intrabay movements. Finally, we investigate the IMHLSP in the presence of limited number of vehicles. Due to the complex nature of the underlying problem, we analyze small-size versions of this problem and develop algorithms for their solution. For some of these problems, we can find optimal solutions in polynomial time. Also, based on our analysis on small-size systems, we have shown why some real-time dispatching (RTD) rules used in real fabs are expected to perform well while not the others. In addition, we also propose some new and promising RTD rules based on our study. / Ph. D.

In this work, we address a variety of problems with applications to `ethanol production from biomass', `agile manufacturing' and `mass customization' domains. Our motivation stems from the potential use of biomass as an alternative to non-renewable fuels, the prevalence of `flexible manufacturing systems', and the popularity of `mass customization' in today's highly competitive markets. Production scheduling and design and optimization of logistics network mark the underlying topics of our work. In particular, we address three problems, Biomass Logistics Problem, Hybrid Flow Shop Scheduling Problem, and Stochastic Demand Assembly Job Scheduling Problem. The Biomass Logistics Problem is a strategic cost analysis for setup and operation of a biomass supply chain network that is aimed at the production of ethanol from switchgrass. We discuss the structural components and operations for such a network. We incorporate real-life GIS data of a geographical region in a model that captures this problem. Consequently, we develop and demonstrate the effectiveness of a `Nested Benders' based algorithm for an efficient solution to this problem. The Hybrid Flow Shop Scheduling Problem concerns with production scheduling of a lot over a two-stage hybrid flow shop configuration of machines, and is often encountered in `flexible manufacturing systems'. We incorporate the use of `lot-streaming' in order to minimize the makespan value. Although a general case of this problem is NP-hard, we develop a pseudo-polynomial time algorithm for a special case of this problem when the sublot sizes are treated to be continuous. The case of discrete sublot sizes is also discussed for which we develop a branch-and-bound-based method and experimentally demonstrate its effectiveness in obtaining a near-optimal solution. The Stochastic Demand Assembly Job Scheduling Problem deals with the scheduling of a set of products in a production setting where manufacturers seek to fulfill multiple objectives such as `economy of scale' together with achieving the flexibility to produce a variety of products for their customers while minimizing delivery lead times. We design a novel methodology that is geared towards these objectives and propose a Lagrangian relaxation-based algorithm for efficient computation. / Doctor of Philosophy / In this work, we organize our research efforts in three broad areas - Biomass Supply Chain, Hybrid Flow Shop, and Assembly Job Shop, which are separate in terms of their application but connected by scheduling and logistics as the underlying functions. For each of them, we formulate the problem statement and identify the challenges and opportunities from the viewpoint of mathematical decision making. We use some of the well known results from the theory of optimization and linear algebra to design effective algorithms in solving these specific problems within a reasonable time limit. Even though the emphasis is on conducting an algorithmic analysis of the proposed solution methods and in solving the problems analytically, we strive to capture all the relevant and practical features of the problems during formulation of each of the problem statement, thereby maintaining their applicability. The Biomass Supply Chain pertains to the production of fuel grade ethanol from naturally occurring biomass in the form of switchgrass. Such a system requires establishment of a supply chain and logistics network that connects the production fields at its source, the intermediate points for temporary storage of the biomass, and bio-energy plant and refinery at its end for conversion of the cellulosic content in the biomass to crude oil and ethanol, respectively. We define the components and operations necessary for functioning of such a supply chain. The Biomass Logistics Problem that we address is a strategic cost analysis for setup and operation of such a biomass supply chain network. We focus our attention to a region in South Central Virginia and use the detailed geographic map data to obtain land use pattern in the region. We conduct survey of existing literature to obtain various transportation related cost factors and costs associated with the use of equipment. Our ultimate aim here is to understand the feasibility of running a biomass supply chain in the region of interest from an economic standpoint. As such, we represent the Biomass Logistics Problem with a cost-based optimization model and solve it in a series of smaller problems. A Hybrid Flow Shop (HFS) is a configuration of machines that is often encountered in the flexible manufacturing systems, wherein a particular station of machines can execute processing of jobs/tasks simultaneously. In our work, we approach a specific type of HFS, with a single machine at the first stage and multiple identical machines at the second stage. A batch or lot of jobs/items is considered for scheduling over such an HFS. Depending upon the area of application, such a batch is either allowed to be split into continuous sections or restricted to be split in discrete sizes only. The objective is to minimize the completion time of the last job on its assigned machine at the second stage. We call this problem, Hybrid Flow Shop Scheduling Problem, which is known to be a hard problem in literature. We aim to derive the results which will reduce the complexity of this problem, and develop both exact as well as heuristic methods in order to obtain near-optimal solution to this problem. An Assembly Job Shop is a variant of the classical Job Shop which considers scheduling a set of assembly operations over a set of assembly machines. Each operation can only be started once all the other operations in its precedence relationship are completed. Assembly Job Shop are at the core of some of the highly competitive manufacturing facilities that are principled on the philosophy of Mass Customization. Assuming an inherent nature of demand uncertainty, this philosophy aims to achieve ‘economy of scale’ together with flexibility to produce a variety of products for the customers while minimizing the delivery lead times simultaneously. We incorporate some of these challenges in a concise framework of production scheduling and call this problem as Stochastic Demand Assembly Job Scheduling Problem. We design a novel methodology that is geared towards achieving the set objectives and propose an effective algorithm for efficient computation.

[ES] Con la globalización de los mercados y el aumento de la competitividad, la coordinación se ha convertido en un punto estratégico en la gestión de la cadena de suministro. De hecho, cada actor de la cadena de suministro ya no debe tomar decisiones sin considerar todos los eslabones, sean proveedores, proveedores de proveedores o clientes y estos internos o externos a la organización. Las cadenas de suministro son cada vez más complejas y distribuidas, compuestas por múltiples organizaciones con diferentes objetivos y políticas. La coordinación se puede lograr utilizando uno de estos dos enfoques para la toma de decisiones coordinadas: centralizada o descentralizada con un mecanismo de coordinación. Pero, las empresas son reacias a compartir información, ya sea por la confidencialidad de los datos o porque los modelos centralizados resultantes son de gran complejidad que dificultan su manejo y actualización. Además, aquellas empresas que buscan tomar decisiones en tiempo real requieren de modelos ligeros y ágiles, que, con toda la información local y coordinada con el resto, permitan tomar decisiones rápidas. Las empresas interesadas en la coordinación descentralizada con un mecanismo de coordinación esperan obtener mejores resultados con respecto a la no coordinación, aunque deberían asumir tener peores resultados que con la coordinación centralizada. Para ello en esta tesis, se han estudiado los distintos mecanismos de coordinación para la toma de decisiones descentralizada, dentro de un entorno del procedimiento de horizontes rodantes y con herramienta de planificación y programación de las operaciones basada en el concepto de stroke, que extiende el concepto de lista de materiales más allá de las estructuras tradicionales. Estos permiten desarrollar la formulación de la programación matemática y los mecanismos de coordinación necesarios para resolver los problemas de planificación de operaciones. Esta tesis se presenta como una secuencia de capítulos, con el objeto de analizar y presentar la propuesta de mecanismo de coordinación distribuido con unos recursos compartidos. Los distintos capítulos han servido de base para la preparación de artículos científicos. Estos artículos han sido presentados en congresos de la materia y remitidos a revistas científicas. / [CA] Amb la globalització dels mercats i l'augment de la competitivitat, la coordinació s'ha convertit en un punt estratègic en la gestió de la cadena de subministrament. De fet, cada actor de la cadena de subministrament ja no ha de prendre decisions sense considerar totes les baules, siguen proveïdors, sub-proveïdors o clients i aquests interns o externs a l'organització. Les cadenes de subministrament són cada vegada més complexes i distribuïdes, compostes per múltiples organitzacions amb diferents objectius i polítiques. La coordinació es pot aconseguir utilitzant un d'aquests dos enfocaments per a la presa de decisions coordinades: centralitzat o descentralitzat amb un mecanisme de coordinació. Però, les empreses són poc inclinades a compartir informació, ja siga per la confidencialitat de les dades o perquè els models centralitzats resultants són de gran complexitat que dificulten el seu maneig i actualització. A més, aquelles empresa que busquen prendre decisions en temps real requereixen de models lleugers i àgils, que, amb tota la informació local i coordinada amb la resta, permeten prendre decisions ràpides. Les empreses interessades en la coordinació descentralitzada amb un mecanisme de coordinació esperen obtindre millors resultats respecte de la no coordinació encara que haurien d'assumir tindre pitjors resultats que amb la coordinació centralitzada. Per a això en aquesta tesi, s'han estudiat els diferents mecanismes de coordinació per a la presa de decisions descentralitzada, dins d'un entorn d'horitzons rodant i amb eines de planificació i programació de les operacions basada en el concepte de stroke, que estén el concepte de llista de materials més enllà de les estructures tradicionals. Aquests permeten desenvolupar la formulació de la programació matemàtica i els mecanismes de coordinació necessaris per a resoldre els problemes de planificació d'operacions. Aquesta tesi es presenta com una seqüència de capítols, a fi d'analitzar i presentar la proposta de mecanisme de coordinació distribuït amb uns recursos compartits. Els diferents capítols han servit de base per a la preparació d'articles científics. Aquests articles han sigut presentats en congressos de la matèria i remesos a revistes científiques. / [EN] With the globalization of markets and the increase of competitiveness, coordination has become a strategic point in the management of the supply chain. In fact, each actor in the supply chain must no longer make decisions without considering all the links, whether suppliers, sub-suppliers or customers and those internal or external to the organization. Supply chains are increasingly complex and distributed, composed of multiple organizations with different objectives and policies. Coordination can be achieved using one of these two approaches to coordinate decision making: centralized or decentralized with a coordination mechanism. However, companies are reluctant to share information, either because of the confidentiality of the data or because the resulting centralized models are of great complexity that make their management and update them. In addition, those companies that seek to make decisions in real time require lightweight and agile models, which, with all the local information and coordinated with the rest, allow quick decisions. Companies interested in decentralized coordination with a coordination mechanism expect to obtain better results regarding non-coordination although they should assume to have worse results than with centralized coordination. To this end, in this thesis, the different coordination mechanisms for decentralized decision making have been studied, within an environment of rolling horizons and with tools for planning and scheduling operations based on the concept of stroke, which extends the concept of list of materials beyond traditional structures. These allow to develop the formulation of the mathematical programming and the coordination mechanisms necessary to solve the operations planning problems. This thesis is presented as a sequence of chapters, in order to analyse and present the proposal of distributed coordination mechanism with shared resources. The different chapters have served as the basis for the preparation of scientific articles. These articles have been presented at congresses of the subject and submitted to scientific journals. / Rius Sorolla, GV. (2019). Modelos y Algoritmos de Coordinación para la Planificación de Operaciones basadas en el concepto Stroke en Redes de Suministro distribuidas y con alternativas [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/134017

Les opérations d'aménagement dans le domaine de l'énergie (les réseaux de transport d'électricité et les éoliennes) font face, à partir des années 1990, à la multiplication des revendications esthétiques vis-à-vis desquelles les aménageurs répondent de plus en plus en termes de projet de paysage. Ces deux tendances témoignent de l'affirmation d'une préoccupation contemporaine pour le milieu. Cette thèse examine en quoi la question esthétique, loin de se résumer à une forme de protestation commode, pourrait être un terrain favorable pour la prise en compte du milieu par l'aménagement. Dans une première partie, en nous appuyant sur Kant et Jacques Rancière, nous proposons que les stratégies esthétiques modifient les modes d'appréhension du milieu et favorisent sa prise en compte en aménagement. Plutôt que la notion de controverse, la cohérence de cette approche est mise en valeur à travers la notion de mésentente, proposée par Jacques Rancière. Il apparaît, à travers la contestation du projet THT en Quercy Blanc, que les stratégies esthétiques contribuent à la reconnaissance des qualités du milieu par l'aménagement mais qu'elles se heurtent au contenu normatif de sa méthodologie de projet. Sommes-nous prisonnier d'un écart insurmontable entre la lecture esthétique du milieu et l'univers normatif de l'action ? Dans une seconde partie, nous avançons que l'aménagement peut tirer parti du milieu à condition de trouver une méthode prospective qui le conjecture comme un potentiel. À travers l'intérêt de Gilles Deleuze pour la symptomatologie, nous parvenons à approcher l'aménagement, non plus par sa capacité normative et anticipatrice à arrêter le sens des choses, mais comme l'art d'expérimenter de nouvelles possibilités d'existence. En étudiant deux exemples de planification éolienne, en Aveyron et dans l'Aude, il apparaît que si l'aménagement considère le milieu comme le lieu de validation d'une rationalité pratique, sa maîtrise du développement éolien est faible. Inversement, nous avons mis à jour qu'une prospective du milieu, fondée sur une approche multi-scalaire et une sémiologie cartographique non-déterminante, permettait d'asseoir une planification éolienne plus efficace.

Les travaux de recherche effectués dans le cadre de cette thèse concernent un problème delotissement et de séquencement pour une ligne de production imparfaite. Deux types d'aléas sont prisen compte : le rendement aléatoire (à cause des rebuts) et le temps d'exécution aléatoire (à cause despannes machines). Les temps de changement de série dépendant de la séquence des produits sontégalement pris en compte.Le problème est issu de d'une fabrication automatisée (usine-automate) des circuits impriméset il a été posé lors de la conception du système de gestion de production de l'atelier fabriquant lespartons conducteurs de plusieurs types. Étant donné que l'usine était complètement automatisée,l'atelier (comme le reste de l'usine) travaillait la plupart de la journée sans personnel autre que celui demaintenance, alors il fallait construire un planning de production pour les 24 heures suivantes. Ceplanning devait être répété chaque jour. Le problème consistait à définir les quantités optimales deproduits à traiter (tailles de lots) et l'ordre de passage des lots dans une ligne de production afind'optimiser un critère.Le problème traité appartient à trois domaines de recherche: 1) lotissement optimale pour lessystèmes de production imparfaits (ou lotissement sous incertitudes); 2) ordonnancement etlotissement déterministe; 3) ordonnancement avec des temps ou (et) coût de changement de série (setup).Dans la littérature scientifique nous trouvons beaucoup d’exemples de problèmes appartenant auun ou à l’intersection de deux de ces domaines. Par contre, nous n’avons pas trouvé les travaux quitraites de problèmes identiques au notre.Etant donné que le problème est trop compliqué tel qu’il est, nous avons cherché des façonsde son modélisation qui nous permettrons le résoudre. Nous avons trouvé trois cas où le problèmeinitial peut être décomposé en plusieurs parties, chacune entre lesquelles peut être transformé dans unproblème connu de la Recherche Opérationnelle. Ensuite nous avons travaillé que sur la partielotissement du problème décomposé tout en montrant comment les autres partis peuvent être résolus.Les problèmes de ce type sont très importants pour l’optimisation d’une chaine logistique.Ces résolutions aident d’organiser la production à la manière efficace, que permet aux entreprises defaire des gains financiers importants. / This thesis contains the research study of a multi-product lot-sizing and sequencing problemfor an imperfect production line. Two types of uncertainties were taken into account: the random yield(because of defective items) and random lead time (due to machine breakdowns). The sequencedependent set-up time between different products was also taken into account.This problem came from the electronics industry, more precisely from the automatedmanufacturing of several types of Printed Circuit Board. Since the plant was completely automated,the considered production line (like the rest of the plant) worked most of the day without any otherstaff but maintenance one, so it was necessary to consider a production schedule for the next 24 hours.This schedule was repeated every day. The problem was to define the optimal quantities of productsto be manufactured (lot sizes) and the sequence of these lots to optimize a given factor. The problemaddressed belongs to three research domains: 1) optimal lot-sizing for the imperfect productionsystems (or lot-sizing under uncertainty), 2) deterministic lot-sizing and scheduling, 3) schedulingwith set-up times or (and) costs. In the literature we can find many examples of problems belonging toone or the intersection of two of these areas. But we did not find any work that deals with similarproblem to ours.Since the problem is too complicated as it is, we looked for ways of modeling it, which wouldhave allowed us to solve it. We found three cases where the original problem could be decomposedinto several parts, each of which could be converted to a known problem of Operations Research.Then we worked on the lot-sizing part of the decomposed problem. Meanwhile, we showed how otherparties could be resolved.These kinds of problems are very important for a supply chain optimizing. Their solutionshelp to organize an efficient production, which in turn allows to make significant financial gains tocompany.

The Planning and Building Act regulates how municipalities plan the use of land and water. When deciding on the detailed development plan, the respective municipality is responsible for the parking standard in the space that will be allocated for parking and which is made in connection with land construction. The decision is followed up in the building permit process. One of the requirements for building permits being granted is that the parking solution is approved. A public parking lot lease is a solution that is approved by law regarding parking in another area beyond one's own property. The municipality can be a party in the agreement for leasing public parking lots in the role of land access provider and may be responsible for preparing the parking lot. In order to be valid, the lease shall guarantee a measure of permanence over time. The rights that accompany the parking lot agreement need to be monitored by authority decisions that cause a change in land use. The municipalities' responsibility to meet the policy's stated objective to increase housing may result in already built-up areas becoming denser. Surfaces such as parking lots may be used for this purpose. Increased density in municipalities requires new detailed development planning. Thirty of the country's municipalities with the highest number of completed buildings, specifically multi-family housing, were examined for the time period 2005-2016. The basis for the analysis was experiencing increased density where the land area has been affected in relation to objects for public parking leases. Current legislation is interpreted to find support for the validity of leasing public parking lots in cases of changes in land use. This study's research question relates to how the municipality should handle their role in decisions on changed land use, as a party to the civil parking lease agreement and as a public authority. The results highlight the validity of agreements to lease public parking lots despite civil authorities' decisions that change the use of land within the area in question. It is suggested that the municipality, as a civil party to the agreement, must monitor legal right by entering into the agreement. As an authority, the municipality has the responsibility to monitor and follow up the underlying decisions of the regulating authority and building permission decisions, the assessment of which may depend on the approval of the suggested solution for parking. Thus, the new decision regarding land use should not be in conflict with the underlying decisions which also continue to be valid. It is recommended that municipal administrations and companies cooperate closely in the early stages of the detailed development planning process. This is necessary to ensure that the legal right resulting from agreements to lease public parking lots is taken into consideration. The working documents in the form of geographical information may include demarcated areas which include leased public parking lots. / Plan- och bygglagen styr hur kommunerna planerar användningen av mark och vatten. Vid beslut om detaljplan ligger respektive kommuns normtal för parkering till grund för det utrymme som ska avsättas för parkering i samband med byggande av marken. Beslutet följs upp i bygglovsprocessen. Godkänd lösning för parkering är ett myndighetskrav för erhållet bygglov. Parkeringsköp är en lösning som godkänns av lagen som parkeringslösning utanför den egna fastigheten. Kommunen kan vara part i parkeringsköpsavtalet med rollen som markupplåtare och ansvarig för att iordningsställa parkeringen. Upplåtelsen ska för sin giltighet garantera viss stabilitet i tid. Rättigheten som följer med parkeringsavtalet behöver bevakas vid myndighetsbeslut som ändrar markanvändningen. Kommunernas ansvar för att möta politikiska mål om ökat bostadsbyggande kan få till följd att redan bebyggda områden förtätas. Ytor som exempelvis parkering kan tas i anspråk för syftet. Förtätning ställer krav på ny detaljplan. Trettio av landets kommuner med högst antal färdigställda bostäder i flerfamiljshus inom tidsintervallet 2005 – 2016 analyseras utifrån erfarenhet av förtätning, där markområde påverkas som är objekt för parkeringsköp. Tolkning av gällande lagstiftning görs för att hitta stöd för parkeringsköpets giltighet vid ändrad markanvändning. Studiens frågeställning gäller hur kommunen bör hantera sin roll vid beslut om ändrad markanvändning dels som part i det civilrättsliga parkeringsköpsavtalet, dels som myndighet. Resultatet framhåller parkeringsköpsavtalets giltighet trots myndighetsbeslut som ändrar markanvändningen inom aktuellt område. Kommunen som civilrättslig part i avtalet ska bevaka rättigheten förslagsvis genom inskrivning av avtalet. Som myndighet har kommunen ansvar för att bevaka och följa upp bakomliggande myndighetsbeslut, bygglovsbeslutet, vars bedömning kan vila på godkänd lösning för parkering. Det nya beslutet om annan markanvändning ska således inte stå i strid med bakomliggande beslut som fortsatt har giltighet. Tätt samarbete mellan kommunens förvaltningar och bolag i tidiga skeden av detaljplaneprocessen bör vara ett mönster som följs. Detta för att rättigheten som följer på parkeringsköpsavtalet ska uppmärksammas. Arbetsunderlaget i form av geografisk information kan innehålla markering av områden som omfattas av parkeringsköp.

O problema de dimensionamento de lotes com restrições de capacidade (CLSP) consiste em determinar um plano de produção que satisfaça a demanda requerida, respeitando as limitações de capacidade, com o menor custo possível, ou seja, minimizando os custos de produção, estocagem e preparação de máquina. Encontrar uma solução factível para o CLSP, considerando tempo de preparação de máquina, é NP-completo. Nesta dissertação, para a resolução do CLSP, utiliza-se a decomposição de Dantzig-Wolfe e o procedimento de geração de colunas, encontrando bons limitantes inferiores. Duas diferentes estratégias de decomposição são exploradas, decomposição por itens e períodos. Para a obtenção de uma solução inteira para o problema (limitante superior) foram exploradas heurísticas lagrangianas, onde a solução inicial para as heurísticas provém da geração de colunas. Os limitantes obtidos podem ser utilizados em métodos exatos, como por exemplo, em algoritmos do tipo branch-and-price. Experimentos computacionais, baseados em exemplares gerados aleatoriamente, foram realizados e os resultados analisados, as variações dos parâmetros das instâncias foram sugeridas na literatura / The Capacitated Lot Sizing Problem (CLSP) consists in determining a production plan such that all demands are met and the total costs of production, inventory and setup are minimized. Since the problem to find a feasible solution to the CLSP with setup times is NP-complete, large problem instances have been solved by heuristic methods. In this dissertation, we are particularly concerned in using the methodology of Dantzig-Wolfe decomposition and column generation to generate good bounds to the CLSP with setup times and costs. Here, we analyse two types of decomposition which are based on items and time periods (lower bound) and some lagrangian-based heuristics (upper bound). Numerical results based on randomly generated intances suggest that highquality lower bounds are obtained by column generation algorithms, such as well as upper bounds by heuristics. These bounds are useful in exact solution methods, such as branch-and-price algorithms

O planejamento da produção em indústrias moveleiras de pequeno porte é comumente constituído por decisões referentes ao volume de produção e à política de estoque, com o objetivo de minimizar o desperdício de material, os atrasos e as horas-extras utilizadas ao longo do horizonte de planejamento. Administrar tais decisões de uma maneira tratável e eficiente é, em geral, um desafio, especialmente considerando a natureza incerta dos dados. Nessa tese, são desenvolvidos modelos de otimização para apoiar tais decisões no contexto do problema combinado de dimensionamento de lotes e corte de estoque sob incertezas que surge em indústrias moveleiras. Para lidar com as incertezas dos dados, são investigadas duas metodologias: programação estocástica e otimização robusta. Dessa maneira, são propostos modelos de programação estocástica de dois estágios com recurso, assim como modelos estocásticos robustos que incorporam aversão ao risco. A motivação em também desenvolver modelos baseados em otimização robusta é considerar casos práticos em que não há uma descrição probabilística explícita dos dados de entrada, assim como evitar trabalhar com numerosos cenários, o que pode tornar o modelo estocástico computacionalmente intratável. Os experimentos numéricos baseados em exemplares reais de uma empresa moveleira de pequeno porte mostram que as soluções obtidas pelos modelos de programação estocástica fornecem planos de produção robustos e que o (a) decisor (a) pode designar suas preferências em relação ao risco aos modelos, assim como controlar o tradeoff entre o custo total esperado e a robustez da solução. Em relação aos resultados dos modelos de otimização robusta, são obtidos alguns insights entre os chamados budgets de incerteza, as taxas de atendimento da demanda e os valores ótimos. Além disso, evidências numéricas indicam que budgets de incerteza menos conservadores resultam em níveis de serviço razoáveis com baixos custos globais, enquanto a abordagem de pior caso gera, relativamente, boas taxas de atendimento da demanda, mas com custos globais elevados / Production planning procedures in small-size furniture companies commonly consist of decisions with respect to production level and inventory policy, while attempting to minimize trim-loss, backlogging and overtime usage throughout the planning horizon. Managing these decisions in a tractable and efficient way is often a challenge, especially when the uncertainty of data is taken into account. In this thesis, we develop optimization models to support these decisions in the context of the combined lot-sizing and cutting-stock problem that arises in furniture companies. To deal with data uncertainty, we investigate two methodologies: stochastic programming and robust optimization. In the former case, we propose two-stage stochastic programming models with recourse, as well as robust stochastic models to incorporate risk-aversion. In the latter case, our motivation to investigate robust optimization models is the lack of an explicit probabilistic description of the input data. Furthermore, we want to avoid dealing with a large number of scenarios, which typically lead to computationally intractable stochastic programming models. Numerical experiments based on real data from a small-size furniture plant show that the solutions of the stochastic programming models provide robust production plans so that the decision-maker can assign his or her risk preferences to the model and control the tradeoff between the expected total cost and solution robustness. Regarding the results from the robust optimization models, we provide some insights into the relationship among budgets of uncertainty, fill rates and optimal values. Moreover, numerical evidence indicate that less conservative budgets of uncertainty result in reasonable service levels with cheaper global costs, while worst case deterministic approaches lead to relatively good fill rates, but with prohibitive global costs

As decisões operacionais de produção em uma indústria de fiação são planejadas na prática determinando soluções dos sub-problemas de dimensionamento e sequenciamento de lotes e da mistura de fardos de algodão. As tarefas são: definir o tamanho, a sequência, o tempo e alocação de cada lote de produção e quais fardos de algodão devem ser utilizados na produção. Por si só, os sub-problemas representam grandes desafios no planejamento da produção. Entretanto, para melhor representar o ambiente produtivo e alcançar custos de produção mais baixos, indústrias de processo, como as de fiação, procuram integrar mais e mais seus sub-problemas de planejamento. O objetivo dessa tese é apresentar modelos matemáticos e métodos de solução para auxiliar a tomada de decisão no nível operacional do planejamento da produção. Três formulações matemáticas para o dimensionamento e sequenciamento de lotes em um sistema de dois estágios com produção sincronizada são propostas. Um novo método baseado em programação matemática e metaheurísticas e também desenvolvida para a solucão desse sub-problema. Além disso, a integração das decisões relativas a matéria-prima (fardos de algodão) ao dimensionamento e sequenciamento de lotes é analisada. As novas formulações propostas representam de forma mais realista o problema de dimensionamento e sequenciamento de lotes da indústria de fiação e de indústrias de processo com ambiente produtivo similares. O método de solução encontra boas soluções para o problema e supera outros méodos similares presentes em softwares comerciais. Além disso, o método é geral o suficiente para a solução de outros problemas de otimização. O problema integrado de dimensionamento e sequenciamento de lotes e mistura comprovou que restrições relativas à qualidade dos fios influenciam os custos e viabilidade do planejamento da produção. O planejamento integrado dessas óperações trata o sistema considerando restrições que se relacionam, definindo planos de produção mais realistas / In the practice of a spinning industry, the operational decisions of the production planning are determined by the hierarchical solution of the lot-sizing and scheduling problem and the blending problem of the cotton bales. The tasks are: to define the size, sequence, timing and allocation of each production lot and to select which cotton bales are used for production. Each of these problems represents a large challenge in planning the production. However, in order to better represent the production environment and to reach lower production costs, process industries (as the spinning industry) are integrating more and more of the production sub-problems into the planning. The aim of this thesis is to propose novel mathematical models and solution methods to assist the decision maker to plan the production at the operational level. Three formulations for the synchronized two-stage lot sizing and scheduling are proposed. A new method based on mathematical programming and metaheuristics is also developed to solve this sub-problem. In addition, the integration of the lot sizing and scheduling with decisions related to the raw materials (cotton bales) is analyzed. The novel models represent a more realistic lot sizing and scheduling for the spinning industry and process industries of similar production environment. The solution method finds good solutions to the mentioned problem and outperforms other state-of-the-art methods incorporated in commercial softwares. Moreover, the method is general enough to solve other optimization problems. The integrated lot-sizing, scheduling and blending prove that constraints related to the yarn quality influence the costs and the feasibility of the production planning. The integrated planning of these operations approaches the system considering the constraint relationship and defines more realistic production plans

Em diversas indústrias de manufatura (por exemplo, papeleira, moveleira, metalúrgica, têxtil) as decisões do dimensionamento de lotes interagem com outras decisões do planejamento e programação da produção, tais como, a distribuição, o processo de corte, entre outros. Porém, usualmente, essas decisões são tratadas de forma isolada, reduzindo o espaço de soluções e a interdependência entre as decisões, elevando assim os custos totais. Nesta tese, estudamos o processo produtivo de indústrias de móveis de pequeno porte, que consiste em cortar placas grandes disponíveis em estoque para obter diversos tipos de peças que são processadas posteriormente em outros estágios e equipamentos com capacidades limitadas para, finalmente, comporem os produtos demandados. Os problemas de dimensionamento de lotes e corte de estoque são acoplados em um modelo de otimização linear inteiro cujo objetivo é minimizar os custos de produção, estoque de produtos, preparação de máquinas e perda de matéria-prima. Esse modelo mostra o compromisso existente entre antecipar ou não a fabricação de certos produtos aumentando os custos de estoque, mas reduzindo a perda de matéria-prima ao obter melhores combinações entre as peças. O impacto da incerteza da demanda (composta pela carteira de pedidos e mais uma quantidade extra estimada) foi amortizado pela estratégia de horizonte de planejamento rolante e por variáveis de decisão que representam uma produção extra para a demanda esperada no melhor momento, visando a minimização dos custos totais. Dois métodos heurísticos são desenvolvidos para resolver uma simplificação do modelo matemático proposto, o qual possui um alto grau de complexidade. Os experimentos computacionais realizados com exemplares gerados a partir de dados reais coletados em uma indústria de móveis de pequeno porte, uma análise dos resultados, as conclusões e perspectivas para este trabalho são apresentados / In the many manufacturing industries (e.g., paper industry, furniture, steel, textile), lot-sizing decisions generally arise together with other decisions of planning production, such as distribution, cutting, scheduling and others. However, usually, these decisions are dealt with separately, which reduce the solution space and break dependence on decisions, increasing the total costs. In this thesis, we study the production process that arises in small scale furniture industries, which consists basically of cutting large plates available in stock into several thicknesses to obtain different types of pieces required to manufacture lots of ordered products. The cutting and drilling machines are possibly bottlenecks and their capacities have to be taken into account. The lot-sizing and cutting stock problems are coupled with each other in a large scale linear integer optimization model, whose objective function consists in minimizing different costs simultaneously, production, inventory, raw material waste and setup costs. The proposed model captures the tradeoff between making inventory and reducing losses. The impact of the uncertainty of the demand, which is composed with ordered and forecasting products) was smoothed down by a rolling horizon strategy and by new decision variables that represent extra production to meet forecasting demands at the best moment, aiming at total cost minimization. Two heuristic methods are proposed to solve relaxation of the mathematical model. Randomly generated instances based on real world life data were used for the computational experiments for empirical analyses of the model and the proposed solution methods