Multi-Item, Multi-Facility Supply Chain Planning: Models, Complexities, and Algorithms

We propose a planning model for products manufactured across multiple manufacturing facilities sharing similar production capabilities. The need for cross-facility capacity management is most evident in high-tech industries that have capital-intensive equipment and a short technology life cycle. We propose a multicommodity flow network model where each commodity represents a product and the network structure represents manufacturing facilities in the supply chain capable of producing the products. We analyze in depth the product-level (single-commodity, multi-facility) subproblem when the capacity constraints are relaxed. We prove that even the general-cost version of this uncapacitated subproblem is NP-complete. We show that there exists an optimization algorithm that is polynomial in the number of facilities, but exponential in the number of periods. We further show that under special cost structures the shortest-path algorithm could achieve optimality. We analyze cases when the optimal solution does not correspond to a source-to-sink path, thus the shortest path algorithm would fail. To solve the overall (multicommodity) planning problem we develop a Lagrangean decomposition scheme, which separates the planning decisions into a resource subproblem, and a number of product-level subproblems. The Lagrangean multipliers are updated iteratively using a subgradient search algorithm. Through extensive computational testing, we show that the shortest path algorithm serves as an effective heuristic for the product-level subproblem (a mixed integer program), yielding high quality solutions with only a fraction (roughly 2%) of the computer time.     

Discrete and continuous time representations and mathematical models for large production scheduling problems: A case study from the pharmaceutical industry

The underlying time framework used is one of the major differences in the basic structure of mathematical programming formulations used for production scheduling problems. The models are either based on continuous or discrete time representations. In the literature there is no general agreement on which is better or more suitable for different types of production or business environments. In this paper we study a large real-world scheduling problem from a pharmaceutical company. The problem is at least NP-hard and cannot be solved with standard solution methods. We therefore decompose the problem into two parts and compare discrete and continuous time representations for solving the individual parts. Our results show pros and cons of each model. The continuous formulation can be used to solve larger test cases and it is also more accurate for the problem under consideration.     

A multicriteria approach to the location of public facilities

We argue that practical problems involving the location of public facilities are really multicriteria problems, and ought to be modeled as much. The general criteria are those of cost and service, but there exist several distinct criteria in each of those two categories. For the first category, fixed investment cost, fixed operating cost, variable operating cost, total operating cost, and total discounted cost are all reasonable criteria to consider. In terms of service, both demand served and response time (or distance traveled) are appropriate criteria, either agglomerated or considered on the basis of the individual clients. In this paper we treat such multicriteria questions in the framework of a model for selecting a subset of M sites at which to establish public facilities in order to serve client groups located at N distinct points. We show that for some combinations of specific criteria, parametric solutions of a generalized assignment problem (GAP) will yield all efficient solution. In most other cases the efficient solutions can be found through parametric solution of a GAP with additional constraints of a type which can be incorporated into an existing algorithm for the GAP. Rather than attempting to find all efficient solutions, however, we advocate an interactive approach to the resolution of multicriteria location problems and elaborate on a specific interactive algorithm for multicriteria optimization which for the present model solves a finite sequence of GAP's or GAP-type problems. Finally, some similar aspects of private sector location problems are discussed.     

Greenhouse gas abatement — toward Pareto-optimal decisions under uncertainty

This paper examines the economic logic of integrated assessment — balancing the costs against the benefits of greenhouse gas abatement. Stylized facts are employed in a multiregion computable general equilibrium model with a public good. The percentage shares of global emissions are determined outside the model — based upon some form of international agreement — and emission rights are tradeable between regions. The analysis is confined to Pareto-optimal (cooperative) solutions. We focus on the sensitivity of initial decisions to low-probability, high-consequence scenarios associated with cumulative emissions. For simplicity, there are only two regions, two tradeable goods, two time periods, and two states-of-world. With the particular form of public good model adopted here (production rather than utility function impacts), it turns out that a Pareto-optimal hedging strategy is indepedent of the emission shares allocated to each region. Equity issues may be separated from those of economic efficiency. Similar results extend to cases in which there are additional regions, tradeable goods, time periods, and states-of-world.Presented at the Conference on the Economics of Global Environmental Change, Birmingham University, May 9–11, 1994. This research was funded by the Electric Power Research Institute (EPRI). The views presented here are solely those of the individual authors, and do not necessarily represent the views of EPRI or its members.     

A spreadsheet-based optimization model for the integrated problem of producing and distributing a major weekly newsmagazine

In this paper, we address the problem of producing and distributing the Brazilian newsmagazine Época, a major weekly publication with one of the 10 largest circulations in the world. This real-world problem had been puzzling magazine publishers in Brazil and remained unsolved for many years. We propose an innovative mixed-integer-linear programming model to determine the number and location of the industrial facilities that should produce the magazines, what destinations should be assigned to each selected facility; the production sequencing and the modes of transportation (air or truck). Our model aims to minimize the total cost while adhering to production capacity and time constraints. The model was implemented in an electronic spreadsheet environment and yielded a savings of 7.1% of the total costs. Given that despite their huge popularity, little has been written on the issues of implementing full-scale optimization models in spreadsheets; thus we also provide the details of the model’s implementation in Excel.     

A multiscale time model with piecewise constant argument for a boundedly rational monopolist

We present a dynamic model for a boundedly rational monopolist who, in a partially known environment, follows a rule-of-thumb learning process. We assume that the production activity is continuously carried out and that the costly learning activity only occurs periodically at discrete time periods, so that the resulting dynamical model consists of a piecewise constant argument differential equation. Considering general demand, cost and agent’s reactivity functions, we show that the behavior of the differential model is governed by a nonlinear discrete difference equation. Differently from the classical model with smooth argument, unstable, complex dynamics can arise. The main novelty consists in showing that the occurrence of such dynamics is caused by the presence of multiple (discrete and continuous) time scales and depends on size of the time interval between two consecutive learning processes, in addition to the agent’s reactivity and the sensitivity of the marginal profit.     

Using aggregation to optimize long-term production planning at an underground mine

Motivated by an underground mining operation at Kiruna, Sweden, we formulate a mixed integer program to schedule iron ore production over multiple time periods. Our optimization model determines an operationally feasible ore extraction sequence that minimizes deviations from planned production quantities. The number of binary decision variables in our model is large enough that directly solving the full, detailed problem for a three year time horizon requires hours, or even days. We therefore design a heuristic based on solving a smaller, more tractable, model in which we aggregate time periods, and then solving the original model using information gained from the aggregated model. We compute a bound on the worst case performance of this heuristic and demonstrate empirically that this procedure produces good quality solutions while substantially reducing computation time for problem instances from the Kiruna mine.     

Minimum concave cost production system: A further generalization of multi-echelon model

We will consider a concave minimization problem associated with a series production system in which raw material is processed inm consecutive facilities. The products at some facility are either sent to the next facility or stocked in the warehouse. The amount of demand for the final products during periodi, i = 1,,n, are known in advance. Our problem is to minimize the sum of processing, holding and backlogging cost, all of which are assumed to be concave.The origin of this model is the classical economic lot size problem of Wagner and Whitin and was extensively studied by Zangwill. This model is very important from the theoretical as well as practical point of view and this is one of the very rare instances in which polynomial time algorithm has been constructed for concave minimization problems.The purpose of this paper is to extend the model further to the situation in which time lag is associated with processing at each facility. We will propose an efficient O(n ⁴ m) algorithm for this class of problems.     

The location of median paths on grid graphs

In this paper we consider the location of a path shaped facility on a grid graph. In the literature this problem was extensively studied on particular classes of graphs as trees or series-parallel graphs. We consider here the problem of finding a path which minimizes the sum of the (shortest) distances from it to the other vertices of the grid, where the path is also subject to an additional constraint that takes the form either of the length of the path or of the cardinality. We study the complexity of these problems and we find two polynomial time algorithms for two special cases, with time complexity of O(n) and O(nℓ) respectively, where n is the number of vertices of the grid and ℓ is the cardinality of the path to be located. The literature about locating dimensional facilities distinguishes between the location of extensive facilities in continuous spaces and network facility location. We will show that the problems presented here have a close connection with continuous dimensional facility problems, so that the procedures provided can also be useful for solving some open problems of dimensional facilities location in the continuous case.     

Location of paths on trees with minimal eccentricity and superior section

Network location theory has traditionally been concerned with the optimal location of a single-point facility at either a vertex or along an arc in the network. Recently, some authors have departed from this traditional problem and have considered the location of extensive facilities, such as paths, trees or cycles. In this paper, we consider the optimal location of paths on trees with regard to two objective functions: the eccentricity and the superior section. We first present methods to find paths with minimal eccentricity and minimal superior section on trees with arbitrary positive lengths. Then, we analyse the biobjective optimization problem and propose an algorithm, based on a progressive reduction of the initial tree, to obtain all efficient paths. Modifications of the proposed algorithm to solve the problem when a general objective function is used instead of the eccentricity function are also given. This work has been supported by Fundación Séneca under grant PB/11/FS/97     

An Efficient Procedure for Dynamic Lot-sizing Model with Demand Time Windows

We consider a dynamic lot-sizing model with demand time windows where n demands need to be scheduled in T production periods. For the case of backlogging allowed, an O(T ³) algorithm exists under the non-speculative cost structure. For the same model with somewhat general cost structure, we propose an efficient algorithm with O(max {T ², nT}) time complexity.     

A Model for Advanced Reservations for Intercity Visual Conferencing Services

In this paper we describe a model for systems in which the customers usually reserve the required facilities in advance. The model has been developed for a communication network which provides visual conferencing services. We concentrate upon a network with a single pair of cities. Each customer calls the reservation office and specifies the desired day, starting time and holding time for his conference. A scheduler either satisfies the customer's request or offers him up to two alternatives which he may or may not accept. Various performance indices of the system, such as the proportion of lost customers, the proportion of rescheduled customers and the facilities' occupancy rate, are derived. Numerical examples and applications are discussed.     

Facility location for market capture when users rank facilities by shorter travel and waiting times

A firm wants to locate several multi-server facilities in a region where there is already a competitor operating. We propose a model for locating these facilities in such a way as to maximize market capture by the entering firm, when customers choose the facilities they patronize, by the travel time to the facility and the waiting time at the facility. Each customer can obtain the service or goods from several (rather than only one) facilities, according to a probabilistic distribution. We show that in these conditions, there is demand equilibrium, and we design an ad hoc heuristic to solve the problem, since finding the solution to the model involves finding the demand equilibrium given by a nonlinear equation. We show that by using our heuristic, the locations are better than those obtained by utilizing several other methods, including MAXCAP, p-median and location on the nodes with the largest demand.     

Multicriteria Semi-Obnoxious Network Location Problems (MSNLP) with Sum and Center Objectives

Locating a facility is often modeled as either the maxisum or the minisum problem, reflecting whether the facility is undesirable (obnoxious) or desirable. But many facilities are both desirable and undesirable at the same time, e.g., an airport. This can be modeled as a multicriteria network location problem, where some of the sum-objectives are maximized (push effect) and some of the sum-objectives are minimized (pull effect).We present a polynomial time algorithm for this model along with some basic theoretical results, and generalize the results also to incorporate maximin and minimax objectives. In fact, the method works for any piecewise linear objective functions. Finally, we present some computational results.     

A sliding time window heuristic for open pit mine block sequencing

The open pit mine block sequencing problem (OPBS) seeks a discretetime production schedule that maximizes the net present value of the orebody extracted from an open-pit mine. This integer program (IP) discretizes the mine’s volume into blocks, imposes precedence constraints between blocks, and limits resource consumption in each time period. We develop a “sliding time window heuristic” to solve this IP approximately. The heuristic recursively defines, solves and partially fixes an approximating model having: (i) fixed variables in early time periods, (ii) an exact submodel defined over a “window” of middle time periods, and (iii) a relaxed submodel in later time periods. The heuristic produces near-optimal solutions (typically within 2% of optimality) for model instances that standard optimization software fails to solve. Furthermore, it produces these solutions quickly, even though our OPBS model enforces standard upper-bounding constraints on resource consumption along with less standard, but important, lower-bounding constraints.     

Group scheduling problems with simultaneous considerations of learning and deterioration effects on a single-machine

Group technology is important to manufacturing as it helps increase the efficiency of production and decrease the requirement of facilities. In this paper we investigate group scheduling problems with simultaneous considerations of learning and deterioration effects on a single-machine setting. The learning phenomenon is implemented to model the setup time of groups. Three models of deteriorating for the job processing time within a group are examined. We show that all the problems studied are polynomially solvable with or without the presence of certain conditions where the objective is to find an optimal schedule for minimizing the makespan. We also investigate the minimization of the total completion time. We proved that one of the deterioration models examined in this study can also be solved in a polynomial time algorithm under certain conditions.     

Dynamic evolution of economically preferred facilities

In a sustained development scenario, it is often the case that an investment is to be made over time in facilities that generate benefits. The benefits result from joint synergies between the facilities expressed as positive utilities specific to some subsets of facilities. As incremental budgets to finance fixed facility costs become available over time, additional facilities can be opened. The question is which facilities should be opened in order to guarantee that the overall benefit return over time is on the highest possible trajectory. This problem is common in situations such as ramping up a communication or transportation network where the facilities are hubs or service stations, or when introducing new technologies such as alternative fuels for cars and the facilities are fueling stations, or when expanding the production capacity with new machines, or when facilities are functions in a developing organization that is forced to make choices of where to invest limited funding.     

Existence of Equilibria in Economies with Externalities and Nonconvexities

We consider a general equilibrium model of an economy in which the production possibilities, the consumption sets and the preferences of the consumers are represented by set-valued mappings which depend on the environment to take into account the possibility of external effect. In order to encompass all kinds of nonconvexities, we do not put any convexity assumption either on the graph of the set-valued mapping which describes the technological possibilities or on the production set for a given environment. The firms are instructed to set their prices according to general pricing rules which may depend on the production plans of other producers and on consumption plans.We report an existence result of general equilibria. As in the model without external effects, the key hypotheses are bounded loss and survival assumptions. Nevertheless, we also assume that the set-valued mappings which describe the fundamentals of the economy are lower semi-continuous and have a closed graph.Our framework is sufficiently large to generalize previous works on the existence of competitive equilibria with externalities when the firms have convex production sets and on the existence of equilibria with general pricing rule without externality.     

A new lot sizing and scheduling heuristic for multi-site biopharmaceutical production

Biopharmaceutical manufacturing requires high investments and long-term production planning. For large biopharmaceutical companies, planning typically involves multiple products and several production facilities. Production is usually done in batches with a substantial set-up cost and time for switching between products. The goal is to satisfy demand while minimising manufacturing, set-up and inventory costs. The resulting production planning problem is thus a variant of the capacitated lot-sizing and scheduling problem, and a complex combinatorial optimisation problem. Inspired by genetic algorithm approaches to job shop scheduling, this paper proposes a tailored construction heuristic that schedules demands of multiple products sequentially across several facilities to build a multi-year production plan (solution). The sequence in which the construction heuristic schedules the different demands is optimised by a genetic algorithm. We demonstrate the effectiveness of the approach on a biopharmaceutical lot sizing problem and compare it with a mathematical programming model from the literature. We show that the genetic algorithm can outperform the mathematical programming model for certain scenarios because the discretisation of time in mathematical programming artificially restricts the solution space.     

Sequential location-allocation problems on chains and trees with probabilistic link demands

In this paper, we consider multiperiod minisum location problems on networks in which demands can occur continuously on links according to a uniform probability density function. In addition, demands may change dynamically over time periods and at most one facility can be located per time period. Two types of networks are considered in conjunction with three behavioral strategies. The first type of network discussed is a chain graph. A myopic strategy and long-range strategy for locatingp-facilities are considered, as is a discounted present worth strategy for locating two facilities. Although these problems are generally nonconvex, effective methods are developed to readily identify all local and global minima. This analysis forms the basis for similar problems on tree graphs. In particular, we construct algorithms for the 3-facility myopic problem and the 2-facility long-range and discounted cost problems on a tree graph. Extensions and suggestions for further research on problems involving more general networks are provided.