The research work presented in this dissertation relates to lot sizing and its applications in the areas of operational planning and shop floor scheduling and control. Lot sizing enables a proper loading of requisite number of jobs on the machines in order to optimize the performance of an underlying production system. We address lot sizing problems that are encountered at the order entry level as well as those that are faced at the time of distributing the jobs from one machine to another and those that arise before shipping the jobs (orders) to customers. There are different issues and performance measures involved during each of these scenarios, which make the lot sizing problems encountered in these scenarios different from one another. We present algorithms and relevant theoretical analyses for each of the lot sizing problems considered, and also, present results of numerical experimentation to depict their effectiveness We first study the lot sizing problem encountered while transferring jobs from one machine to another. A lot of the jobs is to be split into smaller lots (called sublots) such that the lot is processed on multiple machines in an overlapping manner, a process which is known in the literature as lot streaming. Two lot streaming problems, FL2/n/C and FLm/1/C, are investigated in Chapter 2. FL2/n/C involves a two-machine flow shop in which multiple lots are to be processed. The objective is to minimize the combined cost of makespan and material handling (the latter is proportional to the number of sublots). A dynamic programming-based methodology is developed to determine the optimal sublot sizes and the number of sublots for each lot while assuming a known sequence in which to process the lots. We designate this problem as LSP-DP. This methodology is, then, extended to determine an optimal sequence in which to process the lots in conjunction with the number of sublots and sublot sizes for each lot. We designate this problem as LSSP-DP. Three multidimensional heuristic search procedures (denoted as LSSP-Greedy, LSSP-Cyclic and LSSP-ZP) are proposed for this problem in order to obtain good-quality solutions in a reasonable amount of computational time. Our experimentation reveals that both lot streaming and lot sequencing generate significant benefits, if used alone. However, for the objective of minimizing total handling and makespan cost, lot streaming is more beneficial than lot sequencing. The combined use of lot streaming and sequencing, expectedly, results in the largest improvement over an initial random solution. LSP-DP is found to be very efficient, and so are the three LSSP heuristics, all of which are able to generate near-optimal solutions. On the average, LSSP-Greedy generates the best solutions among the three, and LSSP-Cyclic requires the least time. FLm/1/C deals with the streaming of a single lot over multiple machines in a flow shop. The objective is a unified cost function that comprises of contributions due to makespan, mean flow time, work-in-process, transfer time and setup time. The distinctive features of our problem pertain to the inclusion of sublot-attached setup time and the fact that idling among the sublots of a lot is permitted. A solution procedure that relies on an approximation equation to determine sublot size is developed for this problem for equal-size sublots. The approximation avoids the need for numerical computations, and enables the procedure to run in polynomial time. Our experimentation shows that this solution procedure performs quite well and frequently generates the optimal solution. Since the objective function involves multiple criteria, we further study the marginal cost ratios of various pairs of the criteria, and propose cost sensitivity indices to help in estimating the impact of marginal cost values on the number of sublots obtained. The lot sizing problem addressed in Chapter 3 is motivated by a real-life setting associated with semiconductor manufacturing. We first investigate the integration of lot sizing (at the operational planning level) and dispatching (at the scheduling and control level) in this environment. Such an integration is achieved by forming a closed-loop control system between lot sizing and dispatching. It works as follows: lot sizing module determines lot sizes (loading quota) for each processing buffer based on the current buffer status via a detailed linear programming model. The loading quotas are then used by the dispatching module as a general guideline for dispatching lots on the shop floor. A dispatching rule called "largest-remaining-quota-first" (LRQ) is designed to drive the buffer status to its desired level as prescribed by the lot sizing module. Once the buffer status is changed or a certain amount of time has passed, loading quotas are updated by the lot sizing module. Our experimentation, using the simulation of a real-life wafer fab, reveals that the proposed approach outperforms the existing practice (which is based on "first-in-first-out" (FIFO) model and an ad-hoc lot sizing method). Significant improvements are obtained in both mean values and standard deviations of the performance metrics, which include finished-goods inventory, backlog, throughput and work-in-process. The integration of lot sizing and dispatching focuses on the design of an overall production system architecture. Another lot sizing problem that we present in Chapter 3 deals with input control (or workload control) that complements this architecture. Input control policies are responsible for feeding the production system with the right amount of work and at the right time, and are usually divided into "push" or "pull" categories. We develop a two-phase input control methodology to improve system throughput and the average cycle time of the lots. In phase 1, appropriate operational lot sizes are determined with regard to weekly demand, so as to keep the lot start rate at the desired level. In phase 2, a "pull" policy, termed CONLOAD, is applied to keep the bottleneck's workload at a target level by releasing new lots into the system whenever the workload level is below the desired level. Since the operators are found to be the bottleneck of the system in our preliminary investigation, the "operator workload" is used as system workload in this study. Using throughput and cycle time as the performance metrics, it is shown that this two-phase CONLOAD methodology achieves significant improvement over the existing CONWIP-like policy. Furthermore, a reference table for the target operator workload is established with varying weekly demand and lot start rate. The last lot sizing problem that we address has to do with the integration of production and shipping operations of a make-to-order manufacturer. The objective is to minimize the total cost of shipping and inventory (from manufacturer's perspective) as well as the cost of earliness and tardiness of an order (from customer's perspective). An integer programming (IP) model is developed that captures the key features of this problem, including production and delivery lead times, multiple distinct capacitated machines and arbitrary processing route, among others. By utilizing the generalized upper bound (GUB) structure of this IP model, we are able to generate a simplified first-level RLT (Reformulation Linearization Technique) relaxation that guarantees the integrity of one set of GUB variables when it is solved as a linear programming (LP) problem. This allows us to obtain a tighter lower bound at a node of a branch-and-bound procedure. The GUB-based RLT relaxation is complemented by a GUB identification procedure to identify the set of GUB variables that, once restricted to integer values, would result in the largest increment in the objective value. The tightening procedure described above leads to the development of a RLT-based branch-and-bound algorithm. Our experimentation shows that this algorithm is able to search the branch-and-bound tree more efficiently, and hence, generates better solutions in a given amount of time. / Ph. D.

Wine companies face two important challenges in their supply chain: the international shipping temperatures and their effect on the perceived quality of the wine and the optimization of the bottling schedule. The wine maker takes special care in producing the best quality product, which is then shipped to the importer/distributor or consumer, generally in non-refrigerated containers at the mercy of the prevailing environmental conditions. The contributions of this work is that it is the first to measure, for a significant period of time, the temperatures along the international wine supply chain and to link them to the specific supply chain processes. This is also the first work that analyzes the effect of shipping temperature on the perceived quality of the product by those who make the purchase decision for importers, restaurants and supermarkets. Results indicate that the wine is very likely to have been exposed to extreme temperatures during shipping. For white wines, tasters are able to detect differences in wines which have been exposed to shipping temperatures and show a preference towards them. For red wines, they are unable to detect differences. Our contribution to the second challenge was the development of a model that produces solutions for the wine bottling lot sizing and scheduling problem with sequence dependent setup times, in an adequate time-frame, which can be implemented by large wineries. We have developed a model and algorithm that produces fast, good and robust solutions for the winery lot sizing and scheduling problem with sequence dependent setup times. We implemented an effective decomposition algorithm that uses the structure of the problem, that can be applied to other families of sequence dependent scheduling and lot sizing problem. Results indicate that the model achieves reductions of 30\% in the total plan costs.

Simultaneous lot-sizing and scheduling problem is the problem to decide what products to be produced on which machine and in which order, as well as the quantity of each product. Problems of this type are hard to solve. Therefore, they were studied for years, and a considerable number of papers is published to solve different lotsizing and scheduling problems, specifically real-case problems. This work proposes a Real-Coded Genetic Algorithm (RCGA) with a new chromosome representation to solve a non-identical parallel machine capacitated lot-sizing and scheduling problem with sequence dependent setup times and costs, machine cost and backlogging. Such a problem can be found in real world production line at furniture manufacturer in Sweden. Backlogging is an important concept in this problem, and it is often ignored in the literature. This study implements three different types of crossover; one of them has been chosen based on numerical experiments. Four mutation operators have been combined together to allow the genetic algorithm to scan the search area and maintain genetic diversity. Other steps like initializing of the population and a reinitializing process have been designed carefully to achieve the best performance and to prevent the algorithm from trapped into the local optimum. The proposed algorithm is implemented and coded in MATLAB and tested for a set of standard medium to large-size problems taken from the literature. A variety of problems were solved to measure the impact of different characteristics of problems such as the number of periods, machines, and products on the quality of the solution provided by the proposed RCGA. To evaluate the performance of the proposed algorithm, the average deviation from the lower bound and runtime for the proposed RCGA are compared with three other algorithms from the literature. The results show that, in addition to its high computational speed, the proposed RCGA outperforms the other algorithms for non-identical parallel machine problems, while it is outperformed by the other algorithms for problems with the more identical parallel machine. The results show that the different characteristics of problem instances, like increasing setup cost, and size of the problem influence the quality of the solutions provided by the proposed RCGA negatively.

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

Este trabalho trata de um problema de programação da produção em fundições de pequeno porte, que consiste em programar as ligas que devem ser produzidas em cada período do planejamento e como tais ligas devem ser usadas para a produção de itens sob encomenda, de modo que atrasos e custos operacionais sejam minimizados. Devido à certa incerteza nos dados do problema, a estratégia de horizonte rolante foi empregada. Este problema é representado por um modelo matemático de programação linear inteira mista. Neste trabalho foi desenvolvida uma heurística do tipo residual para obter uma boa solução inteira factível do problema, partindo da solução contínua encontrada pelos métodos relaxe-e-fixe e busca local / This work addresses a planning production problem that arises in small market-driven foundries, which consists of programming a number of alloys that have to be produced in each period of the planning horizon and how these alloys should be used to producing ordered items, in such way that delays and operational costs are minimized. Due to uncertainties in the problem data, the strategy of rolling horizon was used. This problem is modeled as a mixed integer linear programe. In this work we developed a residual typed heuristic in order to obtain a good feasible integer solution of the problem, which are built from the continuous solution found by relax-and-fix and local search methods. Keywords: Lot-sizing problems, mixed integer linear programming, production planning in foundries

Dans cette thèse nous nous intéressons à plusieurs problèmes de gestion de stocks, à travers des modèles de dimensionnement de lots sur plusieurs niveaux, en tenant compte de capacités de production. Nous étudions tout d’abord un problème de dimensionnement de lots à deux niveaux en série avec des capacités de production identiques et stationnaires aux deux niveaux, pour lequel proposons un algorithme dynamique exact pouvant résoudre le problème en temps polynomial sous certaines hypothèses. Dans le chapitre suivant nous étendons ce résultat dans deux directions : nous considérons le problème de gestion de stocks sur un nombre quelconque de niveaux en série, et nous considérons des livraisons par lots. Nous présentons un algorithme exact de résolution, polynomial et très efficace, basé sur une décomposition originale en composantes connexes induites. Nous considérons ensuite des versions plus générales de ce problème, en établissant des résultats de NP-complétude lorsque chaque niveau à une capacité ou une taille de lot différentes. Nous proposons pour ces problèmes une 2-approximation, basé sur l’encadrement de la fonction objectif par deux fonctions affines. Pour finir nous étudions un problème sur un seul niveau mais dans un système de production composé de machines identiques fonctionnant en parallèle. L’originalité de ce problème est de considérer une limitation de la consommation énergétique. A chaque période, on doit décider combien de machines allumer ou éteindre, et quel volume produire et stocker. Des résultats de complexité sont proposés, montrant que ce problème est NP-difficile même sous des hypothèses fortes, et un algorithme dynamique exact est présenté pour le cas de paramètres d’énergie stationnaires / In this thesis we are interested in several multi-level lot-sizing problems taking into account production capacities. We first study a 2-level in series lot-sizing problem with identical and stationary capacities at both levels, for which we propose an exact dynamic algorithm running in polynomial time under some hypothesis. Next chapter extends this result on two main lines: we consider the multi-level in series lot-sizing problem with batch deliveries and with a number of level which is part of the input. We provide a very efficient exact algorithm for this problem, which is polynomial in the number of levels and in the number of periods, based on an original decomposition into induced connected components. Then, we consider more general versions of this problem, for which we provide NP-hardness results when batch sizes or capacities are level-dependent. We propose 2-approximation algorithms for these problems, based on the sandwiching of the objective function by two affine functions. Finally, we study a single-level lot-sizing problem in a system composed of identical machines working in parallel. The originality of this study is to consider a periodic energy limitation. At each period it must be decided how many machines to switch on or off and the volume to be produced and stored. Complexity results are provided, showing that this problem is NP-hard, even under some restrictive assumptions, and an exact dynamic algorithm running in polynomial time is proposed for the case of stationary energy parameters

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.

We consider a one-warehouse multi-retailer system where the warehouse orders or receives from its supplier and replenishes multiple retailers with direct shipping or multi-stop routing over a finite time horizon. The warehouse has the knowledge of external (deterministic) demands at the retailers and manages their inventories while ensuring no stock-out. We consider two problems with direct shipping policy and two problems with routing policy. For the direct shipping policy, the problem is to determine the optimal replenishments for the warehouse and retailers such that the system-wide costs are minimized. In one problem, the warehouse decides about how much and when to ship to the retailers while in the other problem, inventory level of the retailer has to be raised up to a predetermined level whenever replenished. We propose strong mixed integer programming formulations for these problems. Computational experiments show that our formulations are better than their competitors and are very successful in solving the problems to optimality. For the routing policy, the problem is to decide on when and in what sequence to visit the retailers and how much to ship to a retailer so as to minimize system-wide costs. In one problem, the warehouse receives given amounts from its supplier while in the other the warehouse decides on its own replenishments. We propose branch-and-cut algorithms and heuristics based on strong formulations for both problems. Computational results reveal that our procedures perform better than their competitors in the literature for both problems.

Vendor Managed Inventory (VMI) policy has been widely used in various supply chains due to the benefits such as lower inventory levels and costs of retailer, and less frequent stock outs. In this study, the benefits of VMI policy in a manufacturer-retailer setting are analyzed under three different scenarios (Traditional Decision Making, VMI agreement and Centralized Decision Making). A manufacturer that produces a particular product is considered and that product is sold to a retailer operating under known demand forecasts. Under Traditional Decision Making System, each party is responsible for its own costs. Under VMI, manufacturer controls the replenishment decisions of the retailer and solves a Constrained Two-Echelon Lot Sizing Problem with Backordering. Under Centralized Decision Making, manufacturer and retailer act like merged, the problem under consideration is Two-Echelon Single Item Lot Sizing with Backordering. Through an extensive numerical study, three different scenarios&rsquo / results are compared and the conditions beneficial under VMI are identified. Under VMI, a Lagrangean Relaxation algorithm is proposed to reduce solution time. In terms of computational effort, solution times of proposed algorithm and MIP model are compared.

In this study, we consider the General Lot Sizing and Scheduling Problem in single level capacitated environments with sequence dependent item changeovers. Process industries may be regarded as suitable application areas of the problem. The focus on capacity utilization and intensively time consuming changeovers necessitate the integration of lot sizing and sequencing decisions in the production plan. We present a mathematical model which captures the essence of cases in the most generic and realistic setting of the problem. We discuss the impact and validity of some of the assumptions commonly encountered in the related literature. We also represent the problem using an alternative formulation and attempt to enhance the formulations with the use of some additional inequalities. Finally, we develop a heuristic by restricting the number of possible changeovers. Computational results are discussed.