This dissertation consists of three independent sections: In the first part, focusing on the auto industry we look at the challenges and solution strategies of employing build-to-order (BTO) with global supply. We consider some familiar tools for managing domestic supply and exploit them for managing international supply, and propose new methods. We study frequency of supply as a way to improve performance. We study the impact of forecast accuracy, and conclude that improvements there alone may not be sufficient to obtain desired savings. Within this perspective we look at a new shipping policy, 'Ship-to-Average", which prescribes sending a fixed quantity, based on the long term average forecast, with each shipment and making adjustments only if the inventory strays outside a prescribed range. In the second part we look at a Brownian control problem. When a manufacturer places repeated orders with a supplier to meet changing production requirements, he faces the challenge of finding the right balance between holding costs and the operational costs involved in adjusting the shipment sizes. Consider a storage system whose content fluctuates as a Brownian motion in the absence of control. A linear holding cost is incurred continuously. Inventory level can be adjusted by any quantity at a fixed plus proportional cost. We show control band policies are optimal for the average cost problem and calculate the optimal policy parameters. This form of policy is described by three parameters q, Q, S. When the inventory falls to 0 (rises to S), the controller expedites (curtails) shipments to return it to q (Q). Developing techniques based on Lagrangian relaxation we show that this type of policy is optimal even with constraints on the size of adjustments and on the maximum inventory level. The Brownian Control problem can be viewed as an idealization --without delivery delays, of the problem of supplying BTO operations, and provides some theoretical explanation for the Ship-to-Average policies. In fact, Ship-to-Average policies are a practical implementation of Control Band policies in the setting with delivery delays. Finally, we explore the power and applicability of the Lagrangian approach developed in the second part.

In this dissertation, the problem of planning the motion of m Unmanned Vehicles (UVs) (or simply vehicles) through n points in a plane is considered. A motion plan for a vehicle is given by the sequence of points and the corresponding angles at which each point must be visited by the vehicle. We require that each vehicle return to the same initial location(depot) at the same heading after visiting the points. The objective of the motion planning problem is to choose at most q(≤ m) UVs and find their motion plans so that all the points are visited and the total cost of the tours of the chosen vehicles is a minimum amongst all the possible choices of vehicles and their tours. This problem is a generalization of the wellknown Traveling Salesman Problem (TSP) in many ways: (1) each UV takes the role of salesman (2) motion constraints of the UVs play an important role in determining the cost of travel between any two locations; in fact, the cost of the travel between any two locations depends on direction of travel along with the heading at the origin and destination, and (3) there is an additional combinatorial complexity stemming from the need to partition the points to be visited by each UV and the set of UVs that must be employed by the mission. In this dissertation, a sub-optimal, two-step approach to motion planning is presented to solve this problem:(1) the combinatorial problem of choosing the vehicles and their associated tours is based on Euclidean distances between points and (2) once the sequence of points to be visited is specified, the heading at each point is determined based on a Dynamic Programming scheme. The solution to the first step is based on a generalization of Held-Karp’s method. We modify the Lagrangian heuristics for finding a close sub-optimal solution. In the later chapters of the dissertation, we relax the assumption that all vehicles are homogenous. The motivation of heterogenous variant of Multi-depot, Multiple Traveling Salesmen Problem (MDMTSP) derives form applications involving Unmanned Aerial Vehicles (UAVs) or ground robots requiring multiple vehicles with different capabilities to visit a set of locations.

As air traffic congestion grows, air traffic flow management (ATFM) is becoming a great concern. ATFM deals with air traffic and the efficient utilization of the airport and airspace. Air traffic efficiency is heavily influenced by unanticipated factors, or uncertainties, which can come from several sources such as mechanical breakdown; however, weather is the main unavoidable cause of uncertainty. Because weather is unpredictable, it poses a critical challenge for ATFM in current airport and airspace operations. Convective weather results in congestion at airports as well as in airspace sectors. During times of congestion, the decision as how and when to send aircraft toward an airspace sector in the presence of weather is difficult. To approach this problem, we first propose a two-stage stochastic integer program by emphasizing a given single sector. By considering ground delay, cancellation, and cruise speed for each flight on the ground in the first stage, as well as air holding and diversion recourse actions for each flight in the air in the second stage, our model determines how aircraft are sent toward a sector under the uncertainty of weather. However, due to the large number of weather scenarios, the model is intractable in practice. To overcome the intractability, we suggest a rolling horizon method to solve the problem to near optimal. Lagrangian relaxation and subgradient method are used to justify the rolling horizon method. Since the rolling horizon method can be solved in real time, we can apply it to actual aircraft schedules to reduce the costs incurred on the ground as well as in airspace. We then extend our two-stage model to a multistage stochastic program, which increases the number of possible weather realizations and results a more efficient schedule in terms of costs. The rolling horizon method as well as Lagrangian relaxation and subgradient method are applied to this multistage model. An overall comparison among the previously described methodologies are presented.

In this study, we consider a logistics system, in which a single supplier delivers a product to multiple retailers over a finite time horizon. Supplier decides on the amount to order in each period and services retailers facing deterministic dynamic demand via a fleet of vehicles having limited capacity. Each retailer has specific minimum and maximum levels of inventory in an order-up-to level inventory policy setting. The problem is to simultaneously determine the quantity of product to order to the supplier, retailers to be visited, the quantity of product to be delivered to retailers and routes of vehicles in each period so as to minimize system-wide costs. We present a mathematical formulation for the problem, for which we develop several Lagrangian relaxation based solution procedures providing both upper and lower bounds to the problem. We implement these solution procedures on test instances and present the results. Computational study shows that our solution procedures generate good feasible solutions in reasonable time.

Esta tese aborda um problema de dimensionamento e sequenciamento de lotes de produção baseado em uma indústria alimentícia brasileira que opera por meio de diversas linhas de produção heterogêneas. Nesse ambiente produtivo, as linhas de produção compartilham recursos escassos, tais como, trabalhadores e máquinas e devem ser montadas (ativadas) em cada período produtivo, respeitando-se a capacidade disponível de cada recurso necessário para ativação das mesmas. Modelos de programação matemática inteira mista são propostos para representação do problema, bem como diversos métodos heurísticos de solução, compreendendo procedimentos construtivos e de melhoramento baseados na formulação matemática do problema e heurísticas lagrangianas. São propostas heurísticas do tipo relax-and-fix explorando diversas partições das variáveis binárias dos modelos e uma heurística baseada na decomposição do modelo para construção de soluções. Procedimentos do tipo fix-and-optimize e matheuristics do tipo iterative MIP-based neighbourhood search são propostas para o melhoramento das soluções iniciais obtidas pelos procedimentos construtivos. Testes computacionais são realizados com instâncias geradas aleatoriamente e mostram que os métodos propostos são capazes de oferecer melhores soluções do que o algoritmo Branch-and-Cut de um resolvedor comercial para instâncias de médio e grande porte. / This doctoral dissertation addresses the simultaneous lot sizing and scheduling problem in a real world production environment where production lines share scarce production resources. Due to the lack of resources, the production lines cannot operate all simultaneously and they need to be assembled in each period respecting the capacity constraints of the resources. This dissertation presents mixed integer programming models to deal with the problem as well as various heuristic approaches: constructive and improvement procedures based on the mathematical formulation of the problem and lagrangian heuristics. Relax-and-fix heuristics exploring some partitions of the set of binary variables of a model and a decomposition based heuristic are proposed to construct solutions. Fix-and-optimize heuristics and iterative MIP-based neighbourhood search matheuristics are proposed to improvement solutions obtained by constructive procedures. Computational tests are performed with randomly instances and show that the proposed methods can find better solutions than the Branch-and-Cut algorithm of a commercial solver for medium and large size instances.

Um importante problema de programação da produção surge em indústrias de papel integrando o problema de planejamento em múltiplas máquinas paralelas com o problema de corte. O problema de dimensionamento de lotes deve determinar a quantidade de jumbos (bobinas grandes de papel) de diferentes tipos de papel a serem produzidos em cada máquina. Estes jumbos são então cortados para atender a demanda de itens (bobinas menores de papel). O planejamento, que minimiza custos de produção e preparação, deve produzir jumbos (cada máquina produz jumbos de larguras diferentes) que diminuam a perda no processo de corte. Por outro lado, o melhor número de jumbos do ponto de vista de minimizar a perda no processo de corte pode acarretar em altos custos de preparação. Ambos são problemas de otimização combinatória não trivial, o que tem motivado extensas pesquisas nas últimas décadas, entretanto, essa combinação não é bem explorada na literatura. Neste trabalho, são propostos um modelo de otimização integrado e métodos heurísticos de solução. Foram realizados experimentos computacionais com o intuito de analisar o desempenho dos métodos propostos e os resultados apresentaram- se bastante satisfatórios, significando que tais métodos são apropriados para tratar o problema integrado. / An important production programming problem arises in paper industries coupling mul- tiple machine scheduling with cutting stock. From machine scheduling the problem of determining the quantity of jumbos (large rolls of paper) of different types of paper to be produced in each machine arises. These jumbos are then cut to meet the demand for items (smaller rolls of paper). Scheduling that minimizes setups and production costs may produce jumbos (each machine produces jumbos of a specific width) which may increase waste in the cutting process. On the other hand, the best number of jumbos in the point of view of minimizing waste in the cutting process may lead to high setup costs. Both problems are non-trivial combinatorial optimization problems, which have motivated ex- tensive research in the last decades, however their combination is not well explored in the literature. In this work, a coupled optimization modelling and heuristic solution methods are proposed. Computational experiments are devised in order to analyze the performance of the methods and the results had been presented sufficiently satisfactory, meaning that such methods are appropriate to deal with the integrated problem.

Um importante problema de programação da produção surge em indústrias de papel integrando o problema de planejamento em múltiplas máquinas paralelas com o problema de corte. O problema de dimensionamento de lotes deve determinar a quantidade de jumbos (bobinas grandes de papel) de diferentes tipos de papel a serem produzidos em cada máquina. Estes jumbos são então cortados para atender a demanda de itens (bobinas menores de papel). O planejamento, que minimiza custos de produção e preparação, deve produzir jumbos (cada máquina produz jumbos de larguras diferentes) que diminuam a perda no processo de corte. Por outro lado, o melhor número de jumbos do ponto de vista de minimizar a perda no processo de corte pode acarretar em altos custos de preparação. Ambos são problemas de otimização combinatória não trivial, o que tem motivado extensas pesquisas nas últimas décadas, entretanto, essa combinação não é bem explorada na literatura. Neste trabalho, são propostos um modelo de otimização integrado e métodos heurísticos de solução. Foram realizados experimentos computacionais com o intuito de analisar o desempenho dos métodos propostos e os resultados apresentaram- se bastante satisfatórios, significando que tais métodos são apropriados para tratar o problema integrado. / An important production programming problem arises in paper industries coupling mul- tiple machine scheduling with cutting stock. From machine scheduling the problem of determining the quantity of jumbos (large rolls of paper) of different types of paper to be produced in each machine arises. These jumbos are then cut to meet the demand for items (smaller rolls of paper). Scheduling that minimizes setups and production costs may produce jumbos (each machine produces jumbos of a specific width) which may increase waste in the cutting process. On the other hand, the best number of jumbos in the point of view of minimizing waste in the cutting process may lead to high setup costs. Both problems are non-trivial combinatorial optimization problems, which have motivated ex- tensive research in the last decades, however their combination is not well explored in the literature. In this work, a coupled optimization modelling and heuristic solution methods are proposed. Computational experiments are devised in order to analyze the performance of the methods and the results had been presented sufficiently satisfactory, meaning that such methods are appropriate to deal with the integrated problem.

[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. / [CAT] 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 no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/134017 / TESIS

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.

La programmation linéaire en nombres entiers est une approche robuste qui permet de résoudre rapidement de grandes instances de problèmes d'optimisation discrète. Toutefois, les problèmes gagnent constamment en complexité et imposent parfois de fortes limites sur le temps de calcul. Il devient alors nécessaire de développer des méthodes spécialisées afin de résoudre approximativement ces problèmes, tout en calculant des bornes sur leurs valeurs optimales afin de prouver la qualité des solutions obtenues. Nous proposons d'explorer une approche de reformulation en nombres entiers guidée par la relaxation lagrangienne. Après l'identification d'une forte relaxation lagrangienne, un processus systématique permet d'obtenir une seconde formulation en nombres entiers. Cette reformulation, plus compacte que celle de Dantzig et Wolfe, comporte exactement les mêmes solutions entières que la formulation initiale, mais en améliore la borne linéaire: elle devient égale à la borne lagrangienne. L'approche de reformulation permet d'unifier et de généraliser des formulations et des méthodes de borne connues. De plus, elle offre une manière simple d'obtenir des reformulations de moins grandes tailles en contrepartie de bornes plus faibles. Ces reformulations demeurent de grandes tailles. C'est pourquoi nous décrivons aussi des méthodes spécialisées pour en résoudre les relaxations linéaires. Finalement, nous appliquons l'approche de reformulation à deux problèmes de localisation. Cela nous mène à de nouvelles formulations pour ces problèmes; certaines sont de très grandes tailles, mais nos méthodes de résolution spécialisées les rendent pratiques. / Integer linear programming is a robust and efficient approach to solve large-scale instances of combinatorial problems. However, problems constantly gain in complexity and sometimes impose strong constraints on computation times. We must then develop specialised methods to compute heuristic primal solutions to the problem and derive lower bounds on the optimal value, and thus prove the quality of our primal solutions. We propose to guide a reformulation approach for mixed integer programs with Lagrangian relaxations. After the identification of a strong relaxation, a mechanical process leads to a second integer formulation. This reformulation is equivalent to the initial one, but its linear relaxation is equivalent to the strong Lagrangian dual. We will show that the reformulation approach unifies and generalises prior formulations and lower bounding approaches, and that it exposes a simple mechanism to reduce the size of reformulations in return for weaker bounds. Nevertheless, our reformulations are large. We address this issue by solving their linear relaxations with specialised methods. Finally, we apply the reformulation approach to two location problems. This yields novel formulations for both problems; some are very large but, thanks to the aforementioned specialised methods, still practical.