满足多断点折扣费用函数的经济批量问题的多项式时间算法

在进货费用为全单位数量折扣函数的基础上,建立了一类有限时期内的经济批量问题.通过分析最优解的性质,设计了一个计算复杂性为O(T3+mT2)的动态规划算法,其中m为全单位数量折扣费用中的断点数,T为时期数.最后的算例进一步说明了该算法的有效性.     

具有非线性采购成本库存控制问题的研究现状与挑战

库存管理是基于运筹学而发展起来的一门学科,并成为近几十年来运筹学和管理科学重要的研究领域之一。在库存系统中,采购成本是必不可少的成本之一,主要包含产品成本、运输成本、装卸成本等。现实中,采购成本依赖于采购量,且往往是采购量的非线性函数。介绍了几类常见的采购成本函数：依赖于采购量的固定成本、增量折扣、全量折扣、车载容量折扣和凸采购成本等。基于周期盘点库存模型和连续盘点库存模型,综述了带有这些非线性采购成本函数的库存模型研究进展。虽然经过了几十年的研究,但很多带有非线性采购成本的库存模型的最优采购策略因为其复杂性至今未能被完整刻画。通过综述来简单讨论该类问题的挑战和机会。     

Optimal solutions for the economic lot-sizing problem with multiple suppliers and cost structures

This paper considers a multi-supplier economic lot-sizing problem in which the retailer replenishes his inventory from several suppliers. Each supplier is characterized by one of three types of order cost structures: incremental quantity discount cost structure, multiple set-ups cost structure and all-unit quantity discount cost structure. The problem is challenging due to the mix of different cost structures. For all cases of the problem where each supplier is characterized by one of the first two cost structures, some optimality properties are proposed and optimal algorithms based on dynamic programming are designed. For the case where all suppliers are characterized by all-unit quantity discount cost structures, it is hard to design a polynomial time algorithm by the analyzed optimal properties. However, it is proved that one of its special cases can be solved in polynomial time.     

Dynamic cost allocation for economic lot sizing games

We consider a cooperative game defined by an economic lot sizing problem with concave ordering costs over a finite time horizon, in which each player faces demand for a single product in each period and coalitions can pool orders. We show how to compute a dynamic cost allocation in the strong sequential core of this game, i.e. an allocation over time that exactly distributes costs and is stable against coalitional defections at every period of the time horizon.     

Dynamic economic lot size model with perishable inventory and capacity constraints

In this study, we consider a dynamic economic lot sizing problem for a single perishable item under production capacities. We aim to identify the production, inventory and backlogging decisions over the planning horizon, where (i) the parameters of the problem are deterministic but changing over time, and (ii) producer has a constant production capacity that limits the production amount at each period and is allowed to backorder the unmet demand later on. All cost functions are assumed to be concave. A similar problem without production capacities was studied in the literature and a polynomial time algorithm was suggested (Hsu, 2003 [1]). We assume age-dependent holding cost functions and the deterioration rates, which are more realistic for perishable items. Backordering cost functions are period-pair dependent. We prove the NP-hardness of the problem even with zero inventory holding and backlogging costs under our assumptions. We show the structural properties of the optimal solution and suggest a heuristic that finds a good production and distribution plan when the production periods are given. We discuss the performance of the heuristic. We also give a Dynamic Programing-based heuristic for the solution of the overall problem.     

多供应商多零售商下经济批量问题的多项式时间算法研究

基于多供应商和多零售商构成的经济批量问题,通过构建优化模型,分析了订购费用为全部单位数量折扣和增加数量折扣两种情形模型最优解的相关性质。将这些性质应用到动态规划算法设计中,对订购费用为全部单位数量折扣时的一种特殊情形及增加数量折扣的一般情形分别设计了求解问题最优解的多项式时间算法,并用算例说明了算法的执行过程和有效性。     

二供应商经济批量问题的多项式时间算法

为了从采购费用结构不同的供应商中找到最佳补货策略,考虑一个零售商从两个供应商补货的二供应商经济批量问题.零售商在两个供应商处的采购费用结构分别为复合安装费用和全单位数量折扣费用结构.通过对问题结构性质的分析论证,将问题的可行解转化为一个有向网络,降低问题求解的计算复杂性.综合动态规划和Dijkstra最短路算法证明了该问题是多项式时间可解的.     

Optimal ordering and pricing policy with supplier quantity discounts and price-dependent stochastic demand

We study a joint ordering and pricing problem for a retailer whose supplier provides all-unit quantity discount for the product. Both generalized disjunctive programming model and mixed integer nonlinear programming model are presented to formulate the problem. Some properties of the problem are analysed, based on which a solution algorithm is developed. Two numerical examples are presented to illustrate the problem, which are solved by our solution algorithm. Managerial analysis indicates that supplier quantity discount has much influence on the ordering and pricing policy of the retailer and more profit can be obtained when the supplier provides quantity discount.     

考虑外包的单产品再制造批量决策

在已有动态批量决策问题的基础上,考虑了再制造与外包这两个因素建立了单产品的再制造批量决策模型。对考虑外包的单产品再制造批量决策问题最优解的性质进行了讨论,在此基础上利用动态规划的思想给出了时间复杂性为O(T4)的算法,并用C++实现了本算法,实验表明本算法是有效的。     

An efficient approach for solving the lot-sizing problem with time-varying storage capacities

We address the dynamic lot size problem assuming time-varying storage capacities. The planning horizon is divided into T periods and stockouts are not allowed. Moreover, for each period, we consider a setup cost, a holding unit cost and a production/ordering unit cost, which can vary through the planning horizon. Although this model can be solved using O(T³) algorithms already introduced in the specialized literature, we show that under this cost structure an optimal solution can be obtained in O(T log T) time. In addition, we show that when production/ordering unit costs are assumed to be constant (i.e., the Wagner–Whitin case), there exists an optimal plan satisfying the Zero Inventory Ordering (ZIO) property.     

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.     

基于多种运输渠道的经济批量问题的多项式时间算法

为了集中管理, 降低成本, 增强竞争优势, 供应商通常只负责生产,而把产品的配送业务外包给某个配送中心, 由配送中心按照零售商的需求决定发货运输的方式和时间.这样供应商, 配送中心和零售商就构成了二级供应链系统.本文研究的是运输方式为不同参数的全单位数量折扣结构时, 二级供应链系统的经济批量问题.分析了最优解的性质,并对此问题的一种特殊情形给出一个多项式时间算法.     

带短期价格折扣和允许两次特殊补货的库存决策模型

针对供应商提供短期价格折扣且允许零售商两次特殊补货的库存系统, 建立了以零售商库存效益最大化为目标的库存决策模型, 分析了模型的性质, 根据经济订单批量补货决策下补货时间点与折扣时段的关系, 确定了零售商在不同补货策略下的库存效益增值函数. 据此给出零售商相应的最优补货策略函数表达式, 提出了该模型的一个全局优化算法, 并通过数值算例验证了模型和算法的有效性与可行性.     

An Experimental Comparison of MRP Purchase Discount Methods

This paper addresses the managerial issue of how best to order purchased materials in MRP environments when discounts are available from vendors. The least unit cost, least period cost, McLaren's order moment, revised part-period balancing, incremental part-period balancing, traditional discount order quantity, and an optimal algorithm are experimentally investigated under a variety of simulated scenarios. Other experimental factors include the coefficient of variation in demand, forecast uncertainty beyond the current period, the average time between orders, the ratio of the discount quantity to the EOQ, the attractiveness of the discount, the length of the planning horizon, inventory holding costs, and the autocorrelation of demand. All factors tested in this comprehensive experiment significantly affected the performance of the discount ordering procedures. Furthermore, the results from this study suggest that the least unit cost, McLaren's order moment, the traditional discount order quantity, and the optimal procedures significantly out-perform the others. A further choice among these alternative methods was found to be a function of the operating environment and limitations that may exist on available computing time.     

A heuristic for single-warehouse multiretailer supply chains with all-unit transportation cost discounts

In supply chain management research, transportation costs, if explicitly considered at all, are frequently assumed to be linear. These costs often have a more complex form, such as an all-unit discount structure – this piecewise cost function adds significant complexity when included in supply chain management problems and is therefore often ignored due to solution time or tractability concerns. We present and evaluate a new heuristic procedure which provides good solutions to problems involving all-unit discount cost functions while significantly reducing solution times. The general nature of this procedure does not require assumptions about the supply chain structure or policies, and is therefore applicable in a wide range of settings.     

Multi-item single source ordering problem with transportation cost: A Lagrangian decomposition approach

As a part of supply chain management literature and practice, it has been recognized that there can be significant gains in integrating inventory and transportation decisions. The problem we tackle here is a common one both in retail and production sectors where several items have to be ordered from a single supplier. We assume that there is a finite planning horizon to make the ordering decisions for the items, and in this finite horizon the retailer or the producer knows the demand of each item in each period. In addition to the inventory holding cost, an item-base fixed cost associated with each item included in the order, and a piecewise linear transportation cost are incurred. We suggest a Lagrangean decomposition based solution procedure for the problem and carry out numerical experiments to analyze the value of integrating inventory and transportation decisions under different scenarios.     

Optimal order lot sizing and pricing with free shipping

Companies, especially those in e-business, are increasingly offering free shipping to buyers whose order sizes exceed the free shipping quantity. In this paper, given that the supplier offers free shipping, we determine the retailer’s optimal order lot size and the optimal retail price. We explicitly incorporate the supplier’s quantity discount, and transportation cost into the model. We analytically and numerically examine the impacts of free shipping, quantity discount and transportation cost on the retailer’s optimal lot sizing and pricing decisions. We find that free shipping can benefit the supplier, the retailer, and the end customers, and can effectively encourage the retailer to order more of the good, to the extent of ordering a few times of the optimal order lot size without free shipping. The order lot size will increase and the retail price will decrease if the supplier offers proper free shipping.     

随机需求下的价格折扣策略研究

供需关系贯穿供应链的整个过程。因此，供需双方订货批量研究是供应链管理的一个最重要也最基本的内容之一。本以订单方式为背景，讨论了供应链环境下一个供应商和一个订货商在非合作情况下的订货模型，并在此基础上引进了一个价格折扣策略，该策略同时考虑了增量折扣和减量折扣两个情况，并给出了供需双方订货的Stackelberg博弈模型和考虑完全合作的Pareto优化模型。最后以算例加以说明。     

Hybrid heuristics for the capacitated lot sizing and loading problem with setup times and overtime decisions

The capacitated lot sizing and loading problem (CLSLP) deals with the issue of determining the lot sizes of product families/end items and loading them on parallel facilities to satisfy dynamic demand over a given planning horizon. The capacity restrictions in the CLSLP are imposed by constraints specific to the production environment considered. When a lot size is positive in a specific period, it is loaded on a facility without exceeding the sum of the regular and overtime capacity limits. Each family may have a different process time on each facility and furthermore, it may be technologically feasible to load a family only on a subset of existing facilities. So, in the most general case, the loading problem may involve unrelated parallel facilities of different classes. Once loaded on a facility, a family may consume capacity during setup time. Inventory holding and overtime costs are minimized in the objective function. Setup costs can be included if setups incur costs other than lost production capacity. The CLSLP is relevant in many industrial applications and may be generalized to multi-stage production planning and loading models. The CLSLP is a synthesis of three different planning and loading problems, i.e., the capacitated lot sizing problem (CLSP) with overtime decisions and setup times, minimizing total tardiness on unrelated parallel processors, and, the class scheduling problem, each of which is NP in the feasibility and optimality problems. Consequently, we develop hybrid heuristics involving powerful search techniques such as simulated annealing (SA), tabu search (TS) and genetic algorithms (GA) to deal with the CLSLP. Results are compared with optimal solutions for 108 randomly generated small test problems. The procedures developed here are also compared against each other in 36 larger size problems.     

Sensitivity of constrained Markov decision processes

We consider the optimization of finite-state, finite-action Markov decision processes under constraints. Costs and constraints are of the discounted or average type, and possibly finite-horizon. We investigate the sensitivity of the optimal cost and optimal policy to changes in various parameters. We relate several optimization problems to a generic linear program, through which we investigate sensitivity issues. We establish conditions for the continuity of the optimal value in the discount factor. In particular, the optimal value and optimal policy for the expected average cost are obtained as limits of the dicounted case, as the discount factor goes to one. This generalizes a well-known result for the unconstrained case. We also establish the continuity in the discount factor for certain non-stationary policies. We then discuss the sensitivity of optimal policies and optimal values to small changes in the transition matrix and in the instantaneous cost functions. The importance of the last two results is related to the performance of adaptive policies for constrained MDP under various cost criteria [3,5]. Finally, we establish the convergence of the optimal value for the discounted constrained finite horizon problem to the optimal value of the corresponding infinite horizon problem.