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 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.     

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).     

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.     

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.     

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%).     

Optimal policy for a dynamic,non-stationary,stochastic inventory problem with capacity commitment

This paper studies a single-product, dynamic, non-stationary, stochastic inventory problem with capacity commitment, in which a buyer purchases a fixed capacity from a supplier at the beginning of a planning horizon and the buyer’s total cumulative order quantity over the planning horizon is constrained with the capacity. The objective of the buyer is to choose the capacity at the beginning of the planning horizon and the order quantity in each period to minimize the expected total cost over the planning horizon. We characterize the structure of the minimum sum of the expected ordering, storage and shortage costs in a period and thereafter and the optimal ordering policy for a given capacity. Based on the structure, we identify conditions under which a myopic ordering policy is optimal and derive an equation for the optimal capacity commitment. We then use the optimal capacity and the myopic ordering policy to evaluate the effect of the various parameters on the minimum expected total cost over the planning horizon.     

节能情形下制造企业动态批量生产策略与节能方式选择

随着诸多严厉的环保政策的实行,节能管理已成为我国高耗能制造企业运营管理中的一个重要内容。通过构建自我节能、节能效益分享和节能量保证三种节能方式下制造企业的动态批量生产决策模型,首先分析了给定节能方式下制造企业的最优动态批量生产策略,其次探讨了制造企业最优节能方式选择。结果表明,最优动态批量生产策略满足“零库存生产”规则。进一步的数值实验分析结果表明:面临前两种节能方式时,当节能服务公司与制造企业的节能投资成本系数比率和采用合同能源管理的预计节能率较小时,制造企业应选择后者,反之应选择前者;面临后两种节能方式时,当采用合同能源管理的预计节能率较小时,制造企业选择两者无差异,反之应选择前者。     

The fractional-order SIS epidemic model with variable population size

In this work, we deal with the fractional-order SIS epidemic model with constant recruitment rate, mass action incidence and variable population size. The stability of equilibrium points is studied. Numerical solutions of this model are given. Numerical simulations have been used to verify the theoretical analysis.     

An inequality model for solving interval dynamic response of structures with uncertain-but-bounded parameters

In this paper, we look into the dynamic response of structures with uncertain-but-bounded parameters. A new inequality model for determining the interval dynamic response is presented. First we propose an interval dynamic response solution theorem. An inequality model which is a mathematics programming problem is suggested by the presented theorem. Using the central difference method, we substitute the differential items of the inequality model by difference items. By solving them, the interval dynamic response can be obtained. Two examples are used to illustrate the feasibility and the efficiency of the model.