A new dynamic programming algorithm for the single item capacitated dynamic lot size model

We develop a new dynamic programming method for the single item capacitated dynamic lot size model with non-negative demands and no backlogging. This approach builds the Optimal value function in piecewise linear segments. It works very well on the test problems, requiring less than 0.3 seconds to solve problems with 48 periods on a VAX 8600. Problems with the time horizon up to 768 periods are solved. Empirically, the computing effort increases only at a quadratic rate relative to the number of periods in the time horizon.This research was supported in part by NSF grants DDM-8814075 and DMC-8504786.     

A dynamic programming algorithm for dynamic lot size models with piecewise linear costs

We propose a new algorithm for dynamic lot size models (LSM) in which production and inventory cost functions are only assumed to be piecewise linear. In particular, there are no assumptions of convexity, concavity or monotonicity. Arbitrary capacities on both production and inventory may occur, and backlogging is allowed. Thus the algorithm addresses most variants of the LSM appearing in the literature. Computational experience shows it to be very effective on NP-hard versions of the problem. For example, 48 period capacitated problems with production costs defined by eight linear segments are solvable in less than 2.5 minutes of Vax 8600 cpu time.     

A note on “quality improvement and setup reduction in the joint economic lot size model”

In a recent paper, Affisco et al. [J.F. Affisco, M.J. Paknejad, F. Nasri, Quality improvement and setup reduction in the joint economic lot size model, European Journal of Operations Research 142 (2002) 497–508] propose a quality-adjusted joint economic lot size model that considers investments in quality improvement and setup cost reduction. In particular, they consider a single-vendor, single-buyer, deterministic demand economic lot-sizing problem, and they investigate the potential impact of economic investments in the vendor’s quality improvement and setup cost reduction efforts on the system-wide costs. However, the particular form of the investment function that they use to represent the cost of investments in quality improvement does not represent actual practice in many industries. Hence, in this note, we develop modified models for quality improvement and simultaneous quality improvement and setup cost reduction using a modified form of the investment function. Our fundamental results and conclusions are substantially different than those in Affisco et al. (2002).     

A dynamic lot sizing model with exponential machine breakdowns

This paper addresses the dynamic lot sizing model with the assumption that the equipment is subject to stochastic breakdowns. We consider two different situations. First we assume that after a machine breakdown the setup is totally lost and new setup cost is incurred. Second we consider the situation in which the cost of resuming the production run after a failure might be substantially lower than the production setup cost. We show that under the first assumption the cost penalty for ignoring machine failures will be noticeably higher than in the classical lot sizing case with static demand. For the second case, two lot sizes per period are required, an ordinary lot size and a specific second (or resumption) lot size. If during the production of a future period demand the production quantity exceeds the second lot size, the production run will be resumed after a breakdown and terminated if the amount produced is less than this lot size. Considering the results of the static lot sizing case, one would expect a different policy. To find an optimum lot sizing decision for both cases a stochastic dynamic programming model is suggested.     

Polynomial cases of the economic lot sizing problem with cost discounts

In this paper we study the economic lot sizing problem with cost discounts. In the economic lot sizing problem a facility faces known demands over a discrete finite horizon. At each period, the ordering cost function and the holding cost function are given and they can be different from period to period. There are no constraints on the quantity ordered in each period and backlogging is not allowed. The objective is to decide when and how much to order so as to minimize the total ordering and holding costs over the finite horizon without any shortages. We study two different cost discount functions. The modified all-unit discount cost function alternates increasing and flat sections, starting with a flat section that indicates a minimum charge for small quantities. While in general the economic lot sizing problem with modified all-unit discount cost function is known to be NP-hard, we assume that the cost functions do not vary from period to period and identify a polynomial case. Then we study the incremental discount cost function which is an increasing piecewise linear function with no flat sections. The efficiency of the solution algorithms follows from properties of the optimal solution. We computationally test the polynomial algorithms against the use of CPLEX.     

Production lot size problem with failure in repair and backlogging derived without derivatives

Conventional approaches for solving the production lot size problems are by using the differential calculus on the long-run average production-inventory cost function with the need to prove optimality first. This note presents a simple algebraic method to replace the use of calculus for determining the optimal lot size. This study refers to the approach used by Grubbström and Erdem [Grubbström, R.W., Erdem, A., 1999. The EOQ with backlogging derived without derivatives, International Journal of Production Economics 59, 529–530] and extends it to the model examined by Chiu and Chiu [Chiu, S.W., Chiu, Y.-S.P., 2006. Mathematical modelling for production system with backlogging and failure in repair. Journal of Scientific and Industrial Research 65(6), 499–506]. This paper demonstrates that the lot size solution and the optimal production-inventory cost of an imperfect EMQ model can be derived without derivatives. As a result, the practitioners or students with little or no knowledge of calculus may be able to manage or understand with ease the realistic production systems.     

Optimizing the economic lot size of a three-stage supply chain with backordering derived without derivatives

Multi-stage supply chain management integration provides a key to successful international business operations. This is because the integrated approach improves the global system performance and cost efficiency. The integrated production inventory models using differential calculus to solve the multi-variable problems are prevalent in operational research. This paper extends the integrated vendor–buyer inventory problem by Yang and Wee [Yang, P.C., Wee, H.M., 2002. The economic lot size of the integrated vendor–buyer system derived without derivatives. Optimal Control Applications and Methods 23, 163–169] to solve the multi-variable problems in the supply chain, and simplifies the solution procedure using a simple algebraic method. As a result, the solution procedure may be easily understood and applied so as to derive the optimal solution.     

Valid inequalities for the single-item capacitated lot sizing problem with step-wise costs

This paper presents a new class of valid inequalities for the single-item capacitated lot sizing problem with step-wise production costs (LS-SW). Constant sized batch production is carried out with a limited production capacity in order to satisfy the customer demand over a finite horizon. A new class of valid inequalities we call mixed flow cover, is derived from the existing integer flow cover inequalities by a lifting procedure. The lifting coefficients are sequence independent when the batch sizes (V) and the production capacities (P) are constant and when V divides P. When the restriction of the divisibility is removed, the lifting coefficients are shown to be sequence independent. We identify some cases where the mixed flow cover inequalities are facet defining. We propose a cutting plane algorithm for different classes of valid inequalities introduced in the paper. The exact separation algorithm proposed for the constant capacitated case runs in polynomial time. Computational results show the efficiency of the new class mixed flow cover compared to the existing methods.     

“A note on the economic lot size of the integrated vendor–buyer inventory system derived without derivatives”: A comment

Wee and Chung [Wee, H.M., Chung, C.T., 2007. A note on the economic lot size of the integrated vendor–buyer inventory system derived without derivatives. European Journal of Operational Research 177, 1289–1293] use the complete squares method to locate the optimal solution of the integrated system’s total cost TC(Q, B, n). However, their algebra method has shortcomings such that it may be invalid. The main purpose of this paper is to overcome those shortcomings and present complete proofs for Wee and Chung (2007).     

The integrality of the lot size in the basic EOQ and EPQ models: Applications to other production-inventory models

In this paper we present a method to obtain the solution of the classic economic order quantity (EOQ) and economic production quantity (EPQ) models when the lot size must be an integer quantity. This approach is operatively very simple and allows obtaining a rule to discriminate between the situation in which the optimal solution is unique and when there are two optimal solutions. Also, this method is applicable to the resolution of other production-inventory models. We expose some of them and illustrate the use of the method with numerical examples.     

A note on the economic lot size of the integrated vendor–buyer inventory system derived without derivatives

Numerous researches on the integrated production inventory models use differential calculus to solve the multi-variable problems. This study simplifies the solution procedure using a simple algebraic method to solve the multi-variable problems. As a result, students who are unfamiliar with calculus may be able to understand the solution procedure with ease. This paper refers to the approach by Grubbström and Erdem [R.W. Grubbström, A. Erdem, The EOQ with backlogging derived without derivatives, International Journal of Production Economics 59 (1999) 529–530] and extends the model by Yang and Wee [P.C. Yang, H.M. Wee, The economic lot size of the integrated vendor–buyer system derived without derivatives. Optimal Control Applications and Methods 23 (2002) 163–169] to derive an algebraic method to solve the three decision variables of the proposed model.     

Plankton growth dynamic driven by plankton body size in deterministic and stochastic environments

In this paper, we establish a new phytoplankton–zooplankton model by considering the effects of plankton body size and stochastic environmental fluctuations. Mathematical theory work mainly gives the existence of boundary and positive equilibria and shows their local as well as global stability in the deterministic model. Additionally, we explore the dynamics of V-geometric ergodicity, stochastic ultimate boundedness, stochastic permanence, persistence in the mean, stochastic extinction, and the existence of a unique ergodic stationary distribution in the corresponding stochastic version. Numerical simulation work mainly reveals that plankton body size can generate great influences on the interactions between phytoplankton and zooplankton, which in turn proves the effectiveness of mathematical theory analysis. It is worth emphasizing that for the small value of phytoplankton cell size, the increase of zooplankton body size can not change the phytoplankton density or zooplankton density; for the middle value of phytoplankton cell size, the increase of zooplankton body size can decrease zooplankton density or phytoplankton density; for the large value of phytoplankton cell size, the increase of zooplankton body size can increase zooplankton density but decrease phytoplankton density. Besides, it should be noted that the increase of zooplankton body size cannot affect the effect of random environmental disturbance, while the increase of phytoplankton cell size can weaken its effect. There results may enrich the dynamics of phytoplankton-zooplankton models.     

Simple dynamic location problem with uncertainty: a primal-dual heuristic approach

Abstract

In this paper, the simple dynamic facility location problem is extended to uncertain realizations of the potential locations for facilities and the existence of customers as well as fixed and variable costs. With limited knowledge about the future, a finite and discrete set of scenarios is considered. The decisions to be made are where and when to locate the facilities, and how to assign the existing customers over the whole planning horizon and under each scenario, in order to minimize the expected total costs. Whilst assignment decisions can be scenario dependent, location decisions have to take into account all possible scenarios and cannot be changed according to each scenario in particular. We first propose a mixed linear programming formulation for this problem and then we present a primal-dual heuristic approach to solve it. The heuristic was tested over a set of randomly generated test problems. The computational results are provided.     

The multi-item capacitated lot-sizing problem with setup times and shortage costs

We address a multi-item capacitated lot-sizing problem with setup times and shortage costs that arises in real-world production planning problems. Demand cannot be backlogged, but can be totally or partially lost. The problem is NP-hard. A mixed integer mathematical formulation is presented. Our approach in this paper is to propose some classes of valid inequalities based on a generalization of Miller et al. [A.J. Miller, G.L. Nemhauser, M.W.P. Savelsbergh, On the polyhedral structure of a multi-item production planning model with setup times, Mathematical Programming 94 (2003) 375–405] and Marchand and Wolsey [H. Marchand, L.A. Wolsey, The 0–1 knapsack problem with a single continuous variable, Mathematical Programming 85 (1999) 15–33] results. We also describe fast combinatorial separation algorithms for these new inequalities. We use them in a branch-and-cut framework to solve the problem. Some experimental results showing the effectiveness of the approach are reported.     

An O(T) algorithm for the capacitated lot sizing problem with minimum order quantities

This paper explores a single-item capacitated lot sizing problem with minimum order quantity, which plays the role of minor set-up cost. We work out the necessary and sufficient solvability conditions and apply the general dynamic programming technique to develop an O(T³) exact algorithm that is based on the concept of minimal sub-problems. An investigation of the properties of the optimal solution structure allows us to construct explicit solutions to the obtained sub-problems and prove their optimality. In this way, we reduce the complexity of the algorithm considerably and confirm its efficiency in an extensive computational study.     

The multi-product newsboy problem with supplier quantity discounts and a budget constraint

This paper considers the multi-product newsboy problem with both supplier quantity discounts and a budget constraint, while each feature has been addressed separately in the literature. Different from most previous nonlinear optimization models on the topic, the problem is formulated as a mixed integer nonlinear programming model due to price discounts. A Lagrangian relaxation approach is presented to solve the problem. Computational results on both small and large-scale test instances indicate that the proposed algorithm is extremely effective for the problem. An extension to multiple constraints and preliminary computational results are also reported.     

An approximate dynamic programming approach for the vehicle routing problem with stochastic demands

This paper examines approximate dynamic programming algorithms for the single-vehicle routing problem with stochastic demands from a dynamic or reoptimization perspective. The methods extend the rollout algorithm by implementing different base sequences (i.e. a priori solutions), look-ahead policies, and pruning schemes. The paper also considers computing the cost-to-go with Monte Carlo simulation in addition to direct approaches. The best new method found is a two-step lookahead rollout started with a stochastic base sequence. The routing cost is about 4.8% less than the one-step rollout algorithm started with a deterministic sequence. Results also show that Monte Carlo cost-to-go estimation reduces computation time 65% in large instances with little or no loss in solution quality. Moreover, the paper compares results to the perfect information case from solving exact a posteriori solutions for sampled vehicle routing problems. The confidence interval for the overall mean difference is (3.56%, 4.11%).     

以商圈为中心的O2O动态外卖配送路径优化模型与算法

针对线上到线下(Online to Offline,O2O) 外卖路径优化问题,综合考虑其动态配送需求、货物区分等特点以及时间窗、载货量等约束条件,将商圈看作配送中心,将快递员数量与快递员总行驶时间作为最小化目标,提出了以商圈为中心的O2O动态外卖配送路径优化模型。采用周期性处理新订单的方法将相应的快递员路径的动态调整问题转化为一系列静态TSP子问题,设计了一种分阶段启发式实时配送路径优化算法框架,并给出了一个具体算法和一个数值计算实例。在VRP通用算例的基础上,以商圈为中心生成测试算例,对本文算法进行仿真实验,并与其他算法比较。结果表明：本文算法能充分利用新订单附近的快递员进行配送,并优化其配送路径,有效减少了快递员数量与快递员总行驶时间。