This thesis presents a hybrid decision aid approach for supply networks redesign and planning int the context of multi-site enterprises. This approach is iterative and integrates a mixed integer programming model and a simulation model being at different decisional levels : the mathematical model is a strategic/tactical model and the simulation model is a tactical/operational model. These two models are based on the same modelling of the supply network. First, we describe the elements constituting the decision aid approach. We present two generic mixed integer programming models, multi-product, multi-echelon and multi-period, which search to maximize the profit of the multi-site enterprise. We propose a heuristic approach to solve one of these programs. We describe the developed simulation model. It reproduces the behaviour of the whole supply chain and takes into account the management policies. then, we present the adopted integration methodology. For a problem based on industrial cases, we show that the two models have their role in the decision aid approach and that they contribute both in the search of a good quality network design.

The scope of this thesis is modelling and solving large-scale planning problems in the supply chain within the forest industry. Five research papers are included, the first three of which focus on the modelling, and the last two on the solution methods. All problems included are tactical multi-commodity problems expressed as mixed integer programming (MIP) models. The work has been done in collaboration with two Swedish companies within the forest industry. In Paper I, a problem concerning the supply chain of forest fuel for Sydved Energileveranser AB is modelled and solved. We study the problem of deciding when and where forest residues are to be converted into wood chips, and how the residues and chips are to be transported and stored in order to satisfy energy demand at heating plants. The company has long-term contracts with forest owners and saw mills. Decisions in the model include whether or not additional harvest areas and saw mills are to be contracted and which terminals to use. The planning horizon is one year and monthly time periods are used. Papers II--V are based on planning problems at Södra Cell AB. The planning horizon is normally one year. Papers II--III consider only one time period. In Paper II the supply chain from pulp mills to customers is modelled and the combined problem of deciding terminal locations and which ship routes to use is studied. Shipping vessels chartered on short or long term are used to transport products to terminals in Europe. From each terminal, the products are transported to customers by truck, train, or a combination of both. In addition, trains and trucks can be used for transports directly to customers from mills. In Paper III the entire supply chain, from harvest areas to customers, is considered. Decisions included are transportation of raw materials, production mix, the distribution of pulp products, and the selection of potential orders and their quantities at customers. The ship routes are considered as flow links. In Papers IV--V the problems in Papers II--III are combined into one model and several time periods are used. Lagrangian heuristics based on Lagrangian decomposition are used as solution methods in both papers. In Paper IV, the approach leads to subproblems for each time period, whereas in Paper V, another approach that results in subproblems for different parts of the supply chain is developed. All models are based on real data from the companies. The models are detailed and describe the problems accurately. The solution methods are developed such that the solution time is kept within practical limits. Results from Papers II--III have been used by Södra Cell AB to support the change of the terminal structure as well as in budget planning. / Denna avhandling presenterar matematiska modeller och lösningsmetoder för optimering av olika logistikproblem inom skogsindustrin. Vi studerar försörjningskedjor för skogsbränsle och massaproduker, och beaktar den årliga planeringen i syfte att optimera flödet. Det första problemet behandlar skogsbränsle och är ett samarbete med Sydved Energileveranser AB. Råmaterial i form av grenar och toppar från avverkningsplatser ska flisas och transporteras till värmeverk, eventuellt via terminaler. Det finns möjlighet att flisa både i skogen och på terminaler. Biprodukter från sågverk kan också användas som råmaterial. Vid behov kan utbudet av råmaterial utökas genom att fler avverkningsplatser och sågverk kontrakteras. Värmeverken har en efterfrågan, angiven i kWh per månad, som ska uppfyllas. Exempel på beslut som ska tas är var flisning ska ske, om nya avverkningsplatser ska kontrakteras, var lagring ska ske, samt hur och när skogsbränslet ska transporteras. Nästföljande problem behandlar massaprodukter och är ett samarbete med Södra Cell AB. Olika sorters massaved från skogen och biprodukter från sågverk utgör råmaterial för produktion av massaprodukter. Råmaterialet transporteras till massabruk för tillverkning enligt specificerade recept. De färdiga produkterna transporteras sedan med fartyg till terminaler i Europa. Från terminalerna transporteras produkterna vidare till pappersbruk, vilka är företagets slutkunder. Massaprodukterna transporteras i vissa fall med lastbil eller tåg direkt från massabruken till kunderna. Efterfrågan är angiven inom vissa gränser i olika order. Vissa order är fasta, vilket innebär att dess efterfrågan måste uppfyllas, medan andra order är fria. Exempel på beslut som ska tas är vilka bruk olika produkter ska produceras på, hur många och vilka terminaler som ska användas, samt hur transporterna ska utföras för att ge bästa resultat. Utifrån ovanstående beskrivningar har matematiska modeller formulerats. Ge-nom att lösa dessa kan vi få svar på logistik- och transportfrågorna och ett optimalt flöde kan hittas. För att lösa modellerna har kommersiell programvara använts. Heuristiker och mer avancerade optimeringsmetoder har också utvecklats i syfte att producera bra lösningar snabbare. / Article 4 was a manuscript entitled "Solving a multi-period supply chain problem for a pulp industry using Lagrangian heuristics based on time periods" at the time of the thesis defence.

We consider a single-part, two-echelon supply chain problem for spare parts. The network consists of a single manufacturing plant, a set of service centers (SCs) and a set of customers. Both echelons keep spare parts using the base-stock replenishment policy. The plant behaves as an M/M/1 queueing system and has limited production and storage capacity. Demand faced by each SC follows an independent Poisson process. The problem is to determine optimal location-allocation and optimal base-stock levels at both echelons while satisfying the target service levels and customer preferences of SCs. We develop a mixed integer non-linear programming model and use cutting-plane method to optimize the inventory-location decisions. We present an exact solution procedure for the inventory stocking problem and demonstrate the limitations of using traditional inventory models like METRIC-like and Approximate in case of high utilization rates. We show the effectiveness of our proposed cutting-plane algorithm and provide important managerial insights for spare parts management.

Fractional aircraft ownership programs offer companies and individuals all the benefits of owning private jet, such as safety, consistency, and guaranteed availability, at a fraction of the cost of owning an aircraft. In the fractional ownership model, the partial owners of an aircraft are entitled to certain number of hours per year, and the management company is responsible for all the operational considerations and making sure an aircraft is available to the owners at the requested time and location. This thesis research proposes advance optimization techniques to help the management company to optimally operate its available resources and provides tools for strategic decision making. The contributions of this thesis are: (i) The development of optimization methodologies to assign and schedule aircraft and crews so that all flight requests are covered at the lowest possible cost. First, a simple model is developed to solve the crew pairing and aircraft routing problem with column generation assuming that a crew stays with one specific aircraft during its duty period. Secondly, this assumption is partially relaxed to improve resource utilization by revising the simple model to allow a crew to use another aircraft when its original aircraft goes under long maintenance. Thirdly, a new comprehensive model utilizing Benders decomposition technique and a fleet-station time line is proposed to completely relax the assumption that crew stays with one specific aircraft. It combines the fleet assignment, aircraft routing, and crew pairing problems. In the proposed methodologies, real world details are taken into consideration, such as crew transportation and overtime costs, scheduled and unscheduled maintenance effects, crew rules, and the presence of non-crew-compatible fleets. Scheduling with time windows is also discussed. (ii) The analysis of operational strategies to provide decision making support. Scenario analyses are performed to provide insights on improving business profitability and aircraft availability, such as impact of aircraft maintenance, crew swapping, effect of increasing demand by Jet-card and geographical business expansion, size of company owned aircraft, and strategies to deal with the stochastic feature of unscheduled maintenance and demand.

In semiconductor manufacturing, wafers are grouped into lots and sent to a separate facility for assembly and test (AT) before being shipped to the customer. Up to a dozen operations are required during AT. The facility in which these operations are performed is a reentrant flow shop consisting of several dozen to several hundred machines and up to a thousand specialized tools. Each lot follows a specific route through the facility, perhaps returning to the same machine multiple times. Each step in the route is referred to as a "pass." Lots in work in process (WIP) that have more than a single step remaining in their route are referred to as multi-pass lots. The multi-pass scheduling problem is to determine machine setups, lot assignments and lot sequences to achieve optimal output, as measured by four objectives related to key device shortages, throughput, machine utilization, and makespan, prioritized in this order. The two primary goals of this research are to develop a new formulation for the multipass problem and to design a variety of solution algorithms that can be used for both planning and real-time control. To begin, the basic AT model considering only single-pass scheduling and the previously developed greedy randomized adaptive search procedure (GRASP) along with its extensions are introduced. Then two alternative schemes are proposed to solve the multipass scheduling problem. In the final phase of this research, an efficient procedure is presented for prioritizing machine changeovers in an AT facility on a periodic basis that provides real-time support. In daily planning, target machine-tooling combinations are derived based on work in process, due dates, and backlogs. As machines finish their current lots, they need to be reconfigured to match their targets. The proposed algorithm is designed to run in real time. / text

Increasing global competition in the business world and heightened expectations of customers have forced companies to consider not only the pricing or product quality, but reliability and timeliness of the deliveries as well. In manufacturing-centric industries such as automotive and electronics, distribution and inventory costs constitute the second and third largest cost components following the production costs. Therefore, industrial and logistics companies need to continuously search for ways to lower the inventory level and distribution cost. This trend has created a closer interaction between the different stages of a supply chain, and increased the practical usefulness of the integrated models.This thesis considers two categories of integrated scheduling problems. One is Integrated Scheduling of Production-Distribution-Inventory problems (ISPDI problems) and the other is Integrated Scheduling of Production-Inventory-Distribution-Inventory problems (ISPIDI problems). Jobs are first processed on a single machine in the production stage, and then delivered to a pre-specified customer by a capacitated transporter. Each job has a distinct due date, and must be delivered to customer before this due date. Each production batch requires a setup cost and a setup time before the first job of this batch is processed. Each round trip between the factory and customer requires a delivery cost as well as a delivery time. Moreover, it is assumed that a job which is completed before its departure date or delivered to the customer before its due date will incur a corresponding inventory cost. Our objective is to minimize the total cost involving setup, inventory and delivery costs while guaranteeing a certain customer service level.For ISPDI problems, we firstly provide a mixed integer programming model for the case of multi-product, single-stage situation, and develop an improved Genetic algorithm (GA) for solving it. Then, we extend this model to a single-product, multi-stage model, and provide two methods, dominance-related greedy algorithm and GA, for solving it. For ISPIDI problems, we establish a general non-linear model for the case of single-product situation and devise a special case from the general model. Then we provide an optimality property between the production and delivery schedules for the special case. Finally, a heuristic approach is developed for solving it. For each problem under study, in order to evaluate the performance of the proposed algorithms, some interesting lower bounds on the corresponding objective functions are established according to different methods such as Lagrangian relaxation method, classical bin-packing based method. Computational results show the efficiency of the proposed models and algorithms in terms of solution quality and running time.

We consider a single-part, two-echelon supply chain problem for spare parts. The network consists of a single manufacturing plant, a set of service centers (SCs) and a set of customers. Both echelons keep spare parts using the base-stock replenishment policy. The plant behaves as an M/M/1 queueing system and has limited production and storage capacity. Demand faced by each SC follows an independent Poisson process. The problem is to determine optimal location-allocation and optimal base-stock levels at both echelons while satisfying the target service levels and customer preferences of SCs. We develop a mixed integer non-linear programming model and use cutting-plane method to optimize the inventory-location decisions. We present an exact solution procedure for the inventory stocking problem and demonstrate the limitations of using traditional inventory models like METRIC-like and Approximate in case of high utilization rates. We show the effectiveness of our proposed cutting-plane algorithm and provide important managerial insights for spare parts management.

A hierarchical control system is proposed for automated flexible manufacturing cells (FMC) that operate in a job shop flow setting. The control system is made up of a higher level scheduler/reactive scheduler, which optimizes the production flow within the cell, and a lower level supervisor that implements the decisions of the scheduler on the shop floor. Previous studies have regularly considered the production scheduling and the supervisory control as two separate problems. This has led to: i) deadlock-prone optimized schedules that cannot be implemented in an automated setting, ii) deadlock-free optimized schedules that lack the means to be transformed into shop floor supervisors, or iii) supervisors that can safely drive the system with no consideration for production performance. The proposed control system combines mathematical models and an insertion heuristic to solve the deadlock-free scheduling problem in job shops, a deadlock-free reactive scheduling heuristic that can revise the schedules upon the occurrence of a wide variety of disruptions, and a systematic procedure that can transform schedules into readily implementable Petri net (PN) supervisors. The integration of these modules into one control hierarchy guarantees a correct, optimized and agile behavior of the controlled system. The performances of the mathematical models, the scheduling and the reactive scheduling heuristics were evaluated by comparison to performances of previous approaches. Experimental results showed that the proposed modules performed consistently better than the other corresponding approaches. The supervisor realization procedure and the overall control architecture were validated by simulation and implementation in an experimental robotic FMC. The control system developed was capable of driving the experimental cell to satisfactorily complete the processing of different product mixes that featured complex processing routes through the cell.

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.

A hierarchical control system is proposed for automated flexible manufacturing cells (FMC) that operate in a job shop flow setting. The control system is made up of a higher level scheduler/reactive scheduler, which optimizes the production flow within the cell, and a lower level supervisor that implements the decisions of the scheduler on the shop floor. Previous studies have regularly considered the production scheduling and the supervisory control as two separate problems. This has led to: i) deadlock-prone optimized schedules that cannot be implemented in an automated setting, ii) deadlock-free optimized schedules that lack the means to be transformed into shop floor supervisors, or iii) supervisors that can safely drive the system with no consideration for production performance. The proposed control system combines mathematical models and an insertion heuristic to solve the deadlock-free scheduling problem in job shops, a deadlock-free reactive scheduling heuristic that can revise the schedules upon the occurrence of a wide variety of disruptions, and a systematic procedure that can transform schedules into readily implementable Petri net (PN) supervisors. The integration of these modules into one control hierarchy guarantees a correct, optimized and agile behavior of the controlled system. The performances of the mathematical models, the scheduling and the reactive scheduling heuristics were evaluated by comparison to performances of previous approaches. Experimental results showed that the proposed modules performed consistently better than the other corresponding approaches. The supervisor realization procedure and the overall control architecture were validated by simulation and implementation in an experimental robotic FMC. The control system developed was capable of driving the experimental cell to satisfactorily complete the processing of different product mixes that featured complex processing routes through the cell.