An approximation-based approach for fuzzy multi-period production planning problem with credibility objective

This paper develops a fuzzy multi-period production planning and sourcing problem with credibility objective, in which a manufacturer has a number of plants or subcontractors. According to the credibility service levels set by customers in advance, the manufacturer has to satisfy different product demands. In the proposed production problem, production cost, inventory cost and product demands are uncertain and characterized by fuzzy variables. The problem is to determine when and how many products are manufactured so as to maximize the credibility of the fuzzy costs not exceeding a given allowable invested capital, and this credibility can be regarded as the investment risk criteria in fuzzy decision systems. In the case when the fuzzy parameters are mutually independent gamma distributions, we can turn the service level constraints into their equivalent deterministic forms. However, in this situation the exact analytical expression for the credibility objective is unavailable, thus conventional optimization algorithms cannot be used to solve our production planning problems. To overcome this obstacle, we adopt an approximation scheme to compute the credibility objective, and deal with the convergence about the computational method. Furthermore, we develop two heuristic solution methods. The first is a combination of the approximation method and a particle swarm optimization (PSO) algorithm, and the second is a hybrid algorithm by integrating the approximation method, a neural network (NN), and the PSO algorithm. Finally, we consider one 6-product source, 6-period production planning problem, and compare the effectiveness of two algorithms via numerical experiments.     

A simulation optimization approach for a two-echelon inventory system with service level constraints

In this paper, we present a simulation optimization algorithm for solving the two-echelon constrained inventory problem. The goal is to determine the optimal setting of stocking levels to minimize the total inventory investment costs while satisfying the expected response time targets for each field depot. The proposed algorithm is more adaptive than ordinary optimization algorithms, and can be applied to any multi-item multi-echelon inventory system, where the cost structure and service level function resemble what we assume. Empirical studies are performed to compare the efficiency of the proposed algorithms with other existing simulation algorithms.     

Production planning via scenario modelling

Several Linear Programming (LP) and Mixed Integer Programming (MIP) models for the production and capacity planning problems with uncertainty in demand are proposed. In contrast to traditional mathematical programming approaches, we use scenarios to characterize the uncertainty in demand. Solutions are obtained for each scenario and then these individual scenario solutions are aggregated to yield a nonanticipative or implementable policy. Such an approach makes it possible to model nonstationarity in demand as well as a variety of recourse decision types. Two scenario-based models for formalizing implementable policies are presented. The first model is a LP model for multi-product, multi-period, single-level production planning to determine the production volume and product inventory for each period, such that the expected cost of holding inventory and lost demand is minimized. The second model is a MIP model for multi-product, multi-period, single-level production planning to help in sourcing decisions for raw materials supply. Although these formulations lead to very large scale mathematical programming problems, our computational experience with LP models for real-life instances is very encouraging.     

A production planning model for an unreliable production facility: Case of finite horizon and single demand

We study a two-level inventory system that is subject to failures and repairs. The objective is to minimize the expected total cost so as to determine the production plan for a single quantity demand. The expected total cost consists of the inventory carrying costs for finished and unfinished items, the backlog cost for not meeting the demand due-date, and the planning costs associated with the ordering schedule of unfinished items. The production plan consists of the optimal number of lot sizes, the optimal size for each lot, the optimal ordering schedule for unfinished items, and the optimal due-date to be assigned to the demand. To gain insight, we solve special cases and use their results to device an efficient solution approach for the main model. The models are solved to optimality and the solution is either obtained in closed form or through very efficient algorithms.     

Stochastic multi-site capacity planning of TFT-LCD manufacturing using expected shadow-price based decomposition

This paper presents a stochastic optimization model and efficient decomposition algorithm for multi-site capacity planning under the uncertainty of the TFT-LCD industry. The objective of the stochastic capacity planning is to determine a robust capacity allocation and expansion policy hedged against demand uncertainties because the demand forecasts faced by TFT-LCD manufacturers are usually inaccurate and vary rapidly over time. A two-stage scenario-based stochastic mixed integer programming model that extends the deterministic multi-site capacity planning model proposed by Chen et al. (2010) [1] is developed to discuss the multi-site capacity planning problem in the face of uncertain demands. In addition a three-step methodology is proposed to generate discrete demand scenarios within the stochastic optimization model by approximating the stochastic continuous demand process fitted from the historical data. An expected shadow-price based decomposition, a novel algorithm for the stage decomposition approach, is developed to obtain a near-optimal solution efficiently through iterative procedures and parallel computing. Preliminary computational study shows that the proposed decomposition algorithm successfully addresses the large-scale stochastic capacity planning model in terms of solution quality and computation time. The proposed algorithm also outperforms the plain use of the CPLEX MIP solver as the problem size becomes larger and the number of demand scenarios increases.     

Short-term liner ship fleet planning with container transshipment and uncertain container shipment demand

This paper proposes a short-term liner ship fleet planning problem by taking into account container transshipment and uncertain container shipment demand. Given a liner shipping service network comprising a number of ship routes, the problem is to determine the numbers and types of ships required in the fleet and assign each of these ships to a particular ship route to maximize the expected value of the total profit over a short-term planning horizon. These decisions have to be made prior to knowing the exact container shipment demand, which is affected by some unpredictable and uncontrollable factors. This paper thus formulates this realistic short-term planning problem as a two-stage stochastic integer programming model. A solution algorithm, integrating the sample average approximation with a dual decomposition and Lagrangian relaxation approach, is then proposed. Finally, a numerical example is used to evaluate the performance of the proposed model and solution algorithm.     

Capacitated dynamic lot sizing problems in closed-loop supply chain

In this paper, we address the capacitated dynamic lot sizing problem arising in closed-loop supply chain where returned products are collected from customers. These returned products can either be disposed or be remanufactured to be sold as new ones again; hence the market demands can be satisfied by either newly produced products or remanufactured ones. The capacities of production, disposal and remanufacturing are limited, and backlogging is not allowed. A general model of this problem is formulated, and several useful properties of the problem are characterized when cost functions are concave. Moreover, this problem is analyzed and solved to optimality using dynamic programming algorithms under different scenarios. It is shown that the problem with only disposal or remanufacturing can be converted into a traditional capacitated lot sizing problem and be solved by a polynomial algorithm if the capacities are constant. A pseudo-polynomial algorithm is proposed for the problem with both capacitated disposal and remanufacturing. The problem with capacitated production and remanufacturing and the problem with uncapacitated production and capacitated remanufacturing are also analyzed and solved. Through numerical experiments we show that the proposed algorithms perform well when solving problems of practical sizes. From the experimental results also indicates that it is worthwhile to expand the remanufacturing capacity only when returned products exist in a relatively long planning horizon, and production capacities have little effect on the remanufacturing plan when the demand is mainly satisfied by the production.     

Service level robustness in stochastic production planning under random machine breakdowns

In this paper, we consider a multi-period, multi-product production planning problem where the production rate and the customer service level are random variables due to machine breakdowns. In order to determine robust production plans, constraints are introduced in the stochastic capacitated lot-sizing problem to ensure that a pre-specified customer service level is met with high probability. The probability of meeting a service level is evaluated by using the first passage time theory of a Wiener process to a boundary. A two-step optimization approach is proposed to solve the developed model. In the first step, the mean-value deterministic model is solved. Then, a method is proposed in the second step to improve the probability of meeting service level. The resulting approach has the advantage of not being a scenario-based one. It is shown that substantial improvements in service level robustness are often possible with minimal increases in expected cost.     

应急物资预置问题的可信性优化模型

基于可信性理论,研究了多受灾点、多出救点、多物资的应急设备选址和物资预置问题.考虑到运输费用、出救点的供应量、受灾点的需求量和道路容量的不确定性,用模糊变量来刻画,建立了模糊环境下应急物资预置的可信性优化模型以最小化期望总费用.当模型中的模糊变量相互独立且服从三角分布时,推导了总费用目标及服务质量和弧容量约束的解析表达式,从而将原模型转化为等价的确定模型.鉴于等价模型是一个混合整数规划,可采用Lingo软件编程求解.最后,数值算例演示所提建模思想.实验结果说明了所建模型的有效性.     

Nonconvex piecewise linear knapsack problems

This paper considers the minimization version of a class of nonconvex knapsack problems with piecewise linear cost structure. The items to be included in the knapsack have a divisible quantity and a cost function. An item can be included partially in the given quantity range and the cost is a nonconvex piecewise linear function of quantity. Given a demand, the optimization problem is to choose an optimal quantity for each item such that the demand is satisfied and the total cost is minimized. This problem and its close variants are encountered in manufacturing planning, supply chain design, volume discount procurement auctions, and many other contemporary applications. Two separate mixed integer linear programming formulations of this problem are proposed and are compared with existing formulations. Motivated by different scenarios in which the problem is useful, the following algorithms are developed: (1) a fast polynomial time, near-optimal heuristic using convex envelopes; (2) exact pseudo-polynomial time dynamic programming algorithms; (3) a 2-approximation algorithm; and (4) a fully polynomial time approximation scheme. A comprehensive test suite is developed to generate representative problem instances with different characteristics. Extensive computational experiments show that the proposed formulations and algorithms are faster than the existing techniques.     

Batching deteriorating items with applications in computer communication and reverse logistics

We study two deterministic scheduling problems that combine batching and deterioration features. In both problems, there is a certain demand for identical good quality items to be produced in batches. In the first problem, each batch is assigned an individual machine that requires a cost and a time to be activated. All the machines are identical, work in parallel, and always produce good quality items. All the items are available at time zero and they deteriorate while waiting for production. Deterioration results in a linear increase of time and cost of production. In the second problem, there is a single machine that produces good quality as well as defective items in batches. Each batch is preceded by a setup time and requires a setup cost. Defective items have to be reworked on the same machine. They deteriorate while waiting for rework. At a time to be decided, the machine switches from production to rework defective items of the current batch. After rework, every defective item has the required good quality. In both problems, the objective is to find batch partitioning such that a linear combination of the production cost and production completion time is minimized. The two problems are observed at computer service providers and also reverse logistics. In computer service providers, machines and items correspond to communication service channels and information transfer tasks, respectively. We reduce both problems to minimizing a function of one variable representing the number of batches. In an optimal solution of either problem, there are at most two different batch sizes. Linear time algorithms are proposed for both problems.     

Multi-source facility location–allocation and inventory problem

We consider a joint facility location–allocation and inventory problem that incorporates multiple sources of warehouses. The problem is motivated by a real situation faced by a multinational applied chemistry company. In this problem, multiple products are produced in several plants. Warehouse can be replenished by several plants together because of capabilities and capacities of plants. Each customer in this problem has stochastic demand and certain amount of safety stock must be maintained in warehouses so as to achieve certain customer service level. The problem is to determine number and locations of warehouses, allocation of customers demand and inventory levels of warehouses. The objective is to minimize the expected total cost with the satisfaction of desired demand weighted average customer lead time and desired cycle service level. The problem is formulated as a mixed integer nonlinear programming model. Utilizing approximation and transformation techniques, we develop an iterative heuristic method for the problem. An experiment study shows that the proposed procedure performs well in comparison with a lower bound.     

A Multi-Objective Production Inventory Model with Backorder for Fuzzy Random Demand Under Flexibility and Reliability

In this paper, an Economic Production Quantity (EPQ) model is developed with flexibility and reliability consideration of production process in an imprecise and uncertain mixed environment. The model has incorporated fuzzy random demand, an imprecise production preparation time and shortage. Here, the setup cost and the reliability of the production process along with the backorder replenishment time and production run period are the decision variables. Due to fuzzy-randomness of the demand, expected average demand is a fuzzy quantity and also imprecise preparation time is represented by fuzzy number. Therefore, both are first transformed to a corresponding interval number and then using the interval arithmetic, the single objective function for expected profit over the time cycle is changed to respective multi-objective functions. Due to highly nonlinearity of the expected profit functions it is optimized using a multi-objective genetic algorithm (MOGA). The associated profit maximization problem is illustrated by numerical examples and also its sensitivity analysis is carried out.     

A discrete bilevel brain storm algorithm for solving a sales territory design problem: a case study

A sales territory design problem faced by a manufacturing company that supplies products to a group of customers located in a service region is addressed in this paper. The planning process of designing the territories has the objective to minimizing the total dispersion of the customers without exceeding a limited budget assigned to each territory. Once territories have been determined, a salesperson has to define the day-by-day routes to satisfy the demand of customers. Currently, the company has established a service level policy that aims to minimize total waiting times during the distribution process. Also, each territory is served by a single salesperson. A novel discrete bilevel optimization model for the sales territory design problem is proposed. This problem can be seen as a bilevel problem with a single leader and multiple independent followers, in which the leader’s problem corresponds to the design of territories (manager of the company), and the routing decision for each territory corresponds to each follower. The hierarchical nature of the current company’s decision-making process triggers some particular characteristics of the bilevel model. A brain storm algorithm that exploits these characteristics is proposed to solve the discrete bilevel problem. The main features of the proposed algorithm are that the workload is used to verify the feasibility and to cluster the leader’s solutions. In addition, four discrete mechanisms are used to generate new solutions, and an elite set of solutions is considered to reduce computational cost. This algorithm is used to solve a real case study, and the results are compared against the current solution given by the company. Results show a reduction of more than 20% in the current costs with the solution obtained by the proposed algorithm. Furthermore, a sensitivity analysis is performed, providing interesting managerial insights to improve the current operations of the company.     

3.1. OR in banking

In this paper, we describe a deterministic multiperiod capacity expansion model in which a single facility serves the demand for many products. Potential applications for the model can be found in the capacity expansion planning of communication systems as well as in the production planning of heavy process industries. The model assumes that each capacity unit simultaneously serves a prespecified (though not necessarily integer) number of demand units of each product. Costs considered include capacity expansion costs, idle capacity holding costs, and capacity shortage costs. All cost functions are assumed to be nondecreasing and concave. Given the demand for each product over the planning horizon, the objective is to find the capacity expansion policy that minimizes the total cost incurred. We develop a dynamic programming algorithm that finds optimal policies. The required computational effort is a polynomial function of the number of products and the number of time periods. When the number of products equals one, the algorithm reduces to the well-known algorithm for the classical dynamic lot size problem.     

An efficient heuristic algorithm for the capacitated p-\! median problem

The capacitated $p$ -median problem (CPMP) is one of the well-known facility-location problems. The objective of the problem is to minimize total cost of locating a set of capacitated service points and allocating a set of demand points to the located service points, while the total allocated demand for each service point is not be greater than its capacity limit. This paper presents an efficient heuristic algorithm based on the local branching and relaxation induced neighborhood search methods for the CPMP. The proposed algorithm is a heuristic technique that utilizes a general mixed integer programming solver to explore neighborhoods. The parameters of the proposed algorithm are tuned by design of experiments. The proposed method is tested on a large set of benchmark instances. The results show that the method outperforms the best method found in the literature.     

The optimal control of just-in-time-based production and distribution systems and performance comparisons with optimized pull systems

In just-in-time (JIT) production systems, there is both input stock in the form of parts and output stock in the form of product at each stage. These activities are controlled by production-ordering and withdrawal kanbans. This paper discusses a discrete-time optimal control problem in a multistage JIT-based production and distribution system with stochastic demand and capacity, developed to minimize the expected total cost per unit of time. The problem can be formulated as an undiscounted Markov decision process (UMDP); however, the curse of dimensionality makes it very difficult to find an exact solution. The author proposes a new neuro-dynamic programming (NDP) algorithm, the simulation-based modified policy iteration method (SBMPIM), to solve the optimal control problem. The existing NDP algorithms and SBMPIM are numerically compared with a traditional UMDP algorithm for a single-stage JIT production system. It is shown that all NDP algorithms except the SBMPIM fail to converge to an optimal control.Additionally, a new algorithm for finding the optimal parameters of pull systems is proposed. Numerical comparisons between near-optimal controls computed using the SBMPIM and optimized pull systems are conducted for three-stage JIT-based production and distribution systems. UMDPs with 42 million states are solved using the SBMPIM. The pull systems discussed are the kanban, base stock, CONWIP, hybrid and extended kanban.     

Siting and Sizing of Facilities under Probabilistic Demands

In this paper a discrete location model for non-essential service facilities planning is described, which seeks the number, location, and size of facilities, that maximizes the total expected demand attracted by the facilities. It is assumed that the demand for service is sensitive to the distance from facilities and to their size. It is also assumed that facilities must satisfy a threshold level of demand (facilities are not economically viable below that level). A Mixed-Integer Nonlinear Programming (MINLP) model is proposed for this problem. A branch-and-bound algorithm is designed for solving this MINLP and its convergence to a global minimum is established. A finite procedure is also introduced to find a feasible solution for the MINLP that reduces the overall search in the binary tree generated by the branch-and-bound algorithm. Some numerical results using a GAMS/MINOS implementation of the algorithm are reported to illustrate its efficacy and efficiency in practice.     

A multi-class multi-level capacitated lot sizing model

When demand loading is higher than available capacity, it takes a great deal of effort for a traditional MRP system to obtain a capacity-feasible production plan. Also, the separation of lot sizing decisions and capacity requirement planning makes the setup decisions more difficult. In a practical application, a production planning system should prioritize demands when allocating manufacturing resources. This study proposes a planning model that integrates all MRP computation modules. The model not only includes multi-level capacitated lot sizing problems but also considers multiple demand classes. Each demand class corresponds to a mixed integer programming (MIP) problem. By sequentially solving the MIP problems according to their demand class priorities, this proposed approach allocates finite manufacturing resources and generates feasible production plans. In this paper we experiment with three heuristic search algorithms: (1) tabu search; (2) simulated annealing, and (3) genetic algorithm, to solve the MIP problems. Experimental designs and statistical methods are used to evaluate and analyse the performance of these three algorithms. The results show that tabu search and simulated annealing perform best in the confirmed order demand class and forecast demand class, respectively.