随机需求下考虑半成品库存的多周期生产决策优化

为了更好地应对需求的不确定性,在需求实现之前,企业既可以生产成品直接满足需求,亦可生产部分半成品,在观察到实际需求之后短时间内迅速完成剩余生产环节以满足需求。未加工的半成品和未售出的成品可用于满足后续周期的需求。作为一种提高生产灵活性的手段,分阶段生产的方式会产生更高的成本。企业需要在成本和灵活性之间作出权衡,优化生产决策。模型通过动态规划的方法,研究需求不确定情况下考虑半成品库存的多周期生产决策问题,通过分析目标函数以及最优值函数的结构性质,推导出最优的多周期生产策略为修正的目标库存策略,并且分析了不同参数对最优策略的影响。     

Capacity and Production Managment in a Single Product Manufacturing System

In planning and managing production systems, manufacturers have two main strategies for responding to uncertainty: they build inventory to hedge against periods in which the production capacity is not sufficient to satisfy demand, or they temporarily increase the production capacity by “purchasing” extra capacity. We consider the problem of minimizing the long-run average cost of holding inventory and/or purchasing extra capacity for a single facility producing a single part-type and assume that the driving uncertainty is demand fluctuation. We show that the optimal production policy is of a hedging point policy type where two hedging levels are associated with each discrete state of the system: a positive hedging level (inventory target) and a negative one (backlog level below which extra capacity should be purchased). We establish some ordering of the hedging levels, derive equations satisfied by the steady-state probability distribution of the inventory/backlog, and give a more detailed analysis of the optimal control policy in a two state (high and low demand rate) model.     

考虑海外代购的品牌商定价模型研究

随着海外代购体量的日趋增大,代购带来的低价威胁对于在不同国家不同市场销售产品的公司来说已经成为一个日益严重的问题。同时,代购渠道中假货的问题也愈发严重。因此,在海外代购背景下探究产品定价模型具有必要性。以往研究普遍认为这种未经授权的销售会削减品牌方的利润,但实则不然。基于这一发现,本研究为在两个不同市场销售相同产品但面临代购低价威胁的公司制定考虑代购的市场定价模型。由公司制定两个市场的价格,消费者选择是否从包括代购在内的三个渠道购买产品。推出两个授权市场的最优价格,分析各参数变化对最优价格的影响,并校验最优价格对消费者需求和总利润的影响。模型分析表明,高价市场中有部分消费者需求转向海外代购,同时低价市场的消费者需求也受到了影响,且在一定条件下,提高高价市场的产品定价能够扩大低价市场的需求,从代购的角度解释了现实中需求曲线向上倾斜的现象。此外,两个独立市场之间的价格差距对代购市场的销售也产生了积极影响,并且在某些条件下,增大价格差距可以提高公司的收益水平。随后讨论了一种极端模型和三种扩展模型,通过模型分析表示,扩展后的定价模型也显示出与基础市场模型相似的灵敏度分析结果,同样得到两个市场的价差扩大会导致代购市场的销售额增加的结论,并且在一定条件下,公司的利润更高,增加了结论的可信度。     

A dynamic inventory model with supplier selection in a serial supply chain structure

Considering the inherent connection between supplier selection and inventory management in supply chain networks, this article presents a multi-period inventory lot-sizing model for a single product in a serial supply chain, where raw materials are purchased from multiple suppliers at the first stage and external demand occurs at the last stage. The demand is known and may change from period to period. The stages of this production–distribution serial structure correspond to inventory locations. The first two stages stand for storage areas for raw materials and finished products in a manufacturing facility, and the remaining stages symbolize distribution centers or warehouses that take the product closer to customers. The problem is modeled as a time-expanded transshipment network, which is defined by the nodes and arcs that can be reached by feasible material flows. A mixed integer nonlinear programming model is developed to determine an optimal inventory policy that coordinates the transfer of materials between consecutive stages of the supply chain from period to period while properly placing purchasing orders to selected suppliers and satisfying customer demand on time. The proposed model minimizes the total variable cost, including purchasing, production, inventory, and transportation costs. The model can be linearized for certain types of cost structures. In addition, two continuous and concave approximations of the transportation cost function are provided to simplify the model and reduce its computational time.     

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.     

大庆油田物资采购及库存优化机制设计与模型研究

本文结合大庆油田物资采购中的实际问题, 考虑物资市场、需求、库存三方之间的不确定性和复杂性,分别讨论了物资采购价格时变、物资需求时变、以及不同仓储容量限制下的库存优化模型的研究进展。进一步,设计了针对大庆油田物资的采购及库存优化机制,并选取大庆油田实际采购中的4种A类物资,基于时间序列方法和0-1混合整数规划,分别对机制中的价格预测部分和策略优化部分进行了数值试算,结果表明,基于准确度较高的预测价格,运用混合0-1整数规划模型制定的多品种物资的最优联合采购策略,可以实现采购成本的节省,相比于4种物资2009年的实际采购成本,节约比率高达7.66%,同时价格预测的精度也得到了用户的认可。该机制为油田物资采购和库存优化管理项目中的辅助决策支持系统原型设计提供了参照。但考虑到大庆油田实际采购中的各种复杂因素的影响,还需进一步完善该优化机制,并对相关模型进行改进。     

Speculative production and anticipative reservation of reactive capacity by a multi-product newsvendor

In this paper the optimal sourcing decisions of a multi-product newsvendor prior to the selling season of the products are studied. To satisfy the uncertain demands, the newsvendor can either utilize speculative production, or anticipatively reserve capacity. During the selling season when demand has become known, the newsvendor can utilize its reserved capacity and reactively satisfy demand uncovered by its speculative production. For the case where capacity for speculative production may be limited, but potential reservation of reactive capacity is unlimited two capacity reservation settings are analyzed and compared. In the first one capacity for each product has to be reserved separately, while in the second setting one joint capacity reservation for all products is permitted which can then be allocated to the different products optimally during the selling season. For the case of separate individual reservations the optimal strategies are analytically derived and structural insights concerning their existence are presented. As the model allowing for joint reservation can not be tackled analytically in general an approximation based on an LP formulation is used. Through a numerical example insights on the value of the increased flexibility induced by joint reservation, the cost-premium acceptable for joint reservation and the relative levels of capacity reservation in the two settings are given.     

仓库容量有限条件下的随机存贮管理模型

以商场的商品销售与存贮为研究对象,建立了一类在仓库容量有限条件下的存贮管理决策模型,并给出了最优存贮策略.针对某个大型超市的三种商品的真实销售数据,我们运用该模型分析求解得出了三种商品的最优订货点L*分别为35、39和40.结合销售存贮管理中的实际情况,我们针对商场同时订购多种商品时的情况对模型进行了初步推广,并依据此推广模型得出了在同时订购三种商品时的最优订货点L*为7.2.最后我们进一步讨论了在商品销售率随存贮时间发生变化及存贮变质性商品时的存贮管理决策模型,以便满足不同商家的订货和存贮策略.     

Integrated revenue management approaches for capacity control with planned upgrades

In many service industries, firms offer a portfolio of similar products based on different types of resources. Mismatches between demand and capacity can therefore often be managed by using product upgrades. Clearly, it is desirable to consider this possibility in the revenue management systems that are used to decide on the acceptance of requests. To incorporate upgrades, we build upon different dynamic programming formulations from the literature and gain several new structural insights that facilitate the control process under certain conditions. We then propose two dynamic programming decomposition approaches that extend the traditional decomposition for capacity control by simultaneously considering upgrades as well as capacity control decisions. While the first approach is specifically suited for the multi-day capacity control problem faced, for example, by hotels and car rental companies, the second one is more general and can be applied in arbitrary network revenue management settings that allow upgrading. Both approaches are formally derived and analytically related to each other. It is shown that they give tighter upper bounds on the optimal solution of the original dynamic program than the well-known deterministic linear program. Using data from a major car rental company, we perform computational experiments that show that the proposed approaches are tractable for real-world problem sizes and outperform those disaggregated, successive planning approaches that are used in revenue management practice today.     

The distance constrained multiple vehicle traveling purchaser problem

In the Distance Constrained Multiple Vehicle Traveling Purchaser Problem (DC-MVTPP) a fleet of vehicles is available to visit suppliers offering products at different prices and with different quantity availabilities. The DC-MVTPP consists in selecting a subset of suppliers so to satisfy products demand at the minimum traveling and purchasing costs, while ensuring that the distance traveled by each vehicle does not exceed a predefined upper bound. The problem generalizes the classical Traveling Purchaser Problem (TPP) and adds new realistic features to the decision problem. In this paper we present different mathematical programming formulations for the problem. A branch-and-price algorithm is also proposed to solve a set partitioning formulation where columns represent feasible routes for the vehicles. At each node of the branch-and-bound tree, the linear relaxation of the set partitioning formulation, augmented by the branching constraints, is solved through column generation. The pricing problem is solved using dynamic programming. A set of instances has been derived from benchmark instances for the asymmetric TPP. Instances with up to 100 suppliers and 200 products have been solved to optimality.     

The traveling purchaser problem with stochastic prices: Exact and approximate algorithms

The paper formulates an extension of the traveling purchaser problem where multiple types of commodities are sold at spatially distributed locations with stochastic prices (each following a known probability distribution). A purchaser’s goal is to find the optimal routing and purchasing strategies that minimize the expected total travel and purchasing costs needed to purchase one unit of each commodity. The purchaser reveals the actual commodity price at a seller upon arrival, and then either purchases the commodity at the offered price, or rejects the price and visits a next seller. In this paper, we propose an exact solution algorithm based on dynamic programming, an iterative approximate algorithm that yields bounds for the minimum total expected cost, and a greedy heuristic for fast solutions to large-scale applications. We analyze the characteristics of the problem and test the computational performance of the proposed algorithms. The numerical results show that the approximate and heuristic algorithms yield near-optimum strategies and very good estimates of the minimum total cost.     

Combining guaranteed and spot markets in display advertising: Selling guaranteed page views with stochastic demand

While page views are often sold instantly through real-time auctions when users visit websites, they can also be sold in advance via guaranteed contracts. In this paper, we present a dynamic programming model to study how an online publisher should optimally allocate and price page views between guaranteed and spot markets. The problem is challenging because the allocation and pricing of guaranteed contracts affect how advertisers split their purchases between the two markets, and the terminal value of the model is endogenously determined by the updated dual force of supply and demand in auctions. We take the advertisers’ purchasing behaviour into consideration, i.e., risk aversion and stochastic demand arrivals, and present a scalable and efficient algorithm for the optimal solution. The model is also empirically validated with a commercial dataset. The experimental results show that selling page views via both channels can increase the publisher’s expected total revenue, and the optimal pricing and allocation strategies are robust to different market and advertiser types.     

基于贝叶斯信息更新的风险规避库存策略研究

在贝叶斯库存控制研究中一个著名的结论是：当缺货需求不能被观测到时,最优贝叶斯库存水平总会高于短视策略库存水平,原因是决策者需要通过多订货来获取对需求分布的认识. 这是基于风险中性的研究,然后现实中决策者都期望规避风险. 基于贝叶斯信息更新研究了风险规避背景下需求部分可观测的多周期报童问题,决策者的周期内效用函数满足独立可加性公理. 通过引入非正规化概率,研究发现,对风险规避的决策者,当其效用函数具有不变绝对风险规避特征时,最优贝叶斯库存水平也会高于短视策略库存水平. 非正规化概率简化了动态规划方程与结果的证明.     

Dynamic Pricing via Dynamic Programming<Superscript>1</Superscript>

This article specifies an efficient numerical scheme for computing optimal dynamic prices in a setting where the demand in a given period depends on the price in that period, cumulative sales up to the current period, and remaining market potential. The problem is studied in a deterministic and monopolistic context with a general form of the demand function. While traditional approaches produce closed-form equations that are difficult to solve due to the boundary conditions, we specify a computationally tractable numerical procedure by converting the problem to an initial-value problem based on a dynamic programming formulation. We find also that the optimal price dynamics preserves certain properties over the planning horizon: the unit revenue is linearly proportional to the demand elasticity of price; the unit revenue is constant over time when the demand elasticity is constant; and the sales rate is constant over time when the demand elasticity is linear in the price. ¹We acknowledge professor robert e. kalaba for initiating this work and suggesting solution methods.     

A variable neighborhood search for the network design problem with relays

Given a set of commodities to be routed over a network, the network design problem with relays involves selecting a route for each commodity and determining the location of relays where the commodities must be reprocessed at certain distance intervals. We propose a hybrid approach based on variable neighborhood search. The variable neighborhood algorithm searches for the route for each commodity and the optimal relay locations for a given set of routes are determined by an implicit enumeration algorithm. We show that dynamic programming can be used to determine the optimal relay locations for a single commodity. Dynamic programming is embedded into the implicit enumeration algorithm to solve the relay location problem optimally for multiple commodities. The special structure of the problem is leveraged for computational efficiency. In the variable neighborhood search algorithm, the routes of the current solution are perturbed and reconstructed to generate neighbor solutions using random and greedy construction heuristics. Computational experiments on three sets of problems (80 instances) show that the variable neighborhood search algorithm with optimal relay allocations outperforms all existing algorithms in the literature.     

Strategic commitment versus postponement in a two-tier supply chain

In this paper the trade-off between strategic commitment and operational flexibility is examined as it arises in a supply chain when a supplier offers competing buyers opportunities to make early purchase commitments for a product with a short life cycle. Traditionally, the use of incentives for early purchase commitments for short life-cycle products has been justified on the basis of a supplier's production lead times or capacity constraints. An alternative explanation has been proposed by offering early purchasing opportunities, a supplier can influence the form of competition in the downstream market. Using a single period model, it has been shown that, below a threshold level of demand uncertainty, the supplier can benefit from providing adequate pricing incentives to entice downstream buyers to commit to purchase quantities before demand information is revealed. Moreover, such early purchasing opportunities can benefit the supplier as well as the buyers even in the absence of production lead times or capacity constraints.     

Dual sourcing using capacity reservation and spot market: Optimal procurement policy and heuristic parameter determination

This contribution focuses on the cost-effective management of the combined use of two procurement options: the short-term option is given by a spot market with random price, whereas the long-term alternative is characterized by a multi period capacity reservation contract with fixed purchase price and reservation level. A reservation cost, proportional with the reservation level, has to be paid for the option of receiving any amount per period up to the reservation level. A long-term decision has to be made regarding the reserved capacity level, and then it has to be decided – period by period – which quantities to procure from the two sources. Considering the multi-period problem with stochastic demand and spot price, the structure of the optimal combined purchasing policy is derived using stochastic dynamic programming. Exploiting these structural properties, an advanced heuristic is developed to determine the respective policy parameters. This heuristic is compared with two rolling-horizon approaches which use the one-period and two-period optimal solution. A comprehensive numerical study reveals that the approaches based on one-period and two-period solutions have considerable drawbacks, while the advanced heuristic performs very well compared to the optimal solution. Finally, by exploiting our numerical results we give some insights into the system’s behavior under problem parameter variations.     

Personnel Recruitment Policies and Long-Term Production Planning

Any organization or industry operating in a market where there is unmet demand will be under considerable pressure to meet the demand as quickly as possible. This short-term objective can be met by rapidly expanding productive capacity in terms of both plant or other equipment and also manpower. If the commodity in demand is durable—e.g. housing, cars, computers—then when the initial requirement is met, further output is for replacement purposes. Production during the expansion phase, planned to eliminate the backlog of demand may be much greater than that needed for the next phase, meeting recurrent replacement demand. If capacity is allowed to run down, a later increase in demand will possibly find the organization with too little capacity. There follows a potentially continuing cycle of under- and over-production. Since manpower comprises a significant part of the capacity, this creates a possible cycle of under- and over-employment.Mathematical models of manpower systems can be adapted to investigate the consequences of controlling recruitment policies over fairly long periods of time. If costs can be ascribed to both under- and over-production it is possible to combine the manpower models with mathematical programming techniques to produce optimal longterm recruitment policies.The possible development of the telephone network in the Republic of Ireland is used as an illustrative example. Here it has already been established by government operational research scientists that meeting the original target number of installations for the early 1980's would require impossibly large levels of recruitment immediately. Our model shows that, if the target were achieved, an intolerably large proportion of the workforce would be redundant in a few years time. We use a linear programming model to illustrate viable policies trading off present delays in satisfying demand against future overmanning.     

时变单车路径优化模型及动态规划算法

车辆路径问题由于其广泛的应用领域及经济价值而成为学术研究热点。然而,在已有的研究文献中,车辆的速度时变与服务多任务特性很少被关注。本文讨论了具有这两个特性的单车路径优化问题。建立了以送货完成时间最早为优化目标的时变单车送货路径优化模型。由于很难获得该模型的精确解,本文提出了一种贪婪补货策略压缩原问题解空间,设计动态规划算法给出了车辆行驶时间满足FIFO规则的送货顺序近似最优解。数值算例验证了该算法所得到的解仅是原问题的近似最优解这一结论。算例同时表明优化配送时间随着车辆装载能力的增大而缩短,并在车辆装载能力超过所有客户配送总需求时实现最短配送时间,即,使用较大装载能力车辆能节约更多配送时间。     

PARTIAL VERSUS GENERAL STORAGE POLICY: COMMODITIES AND RESOURCES

This paper examines joint storage considerations when both commodities and resources can be stored, e.g., grain and water for irrigation. Results suggest that when separate agencies control public resource and commodity storage, suboptimal storage rules occur unless (i) each agency is sensitive to the policies of the other, (ii) commodity inventories are adjusted in response to prices, and (iii) resource inventories are adjusted in response to both commodity demand and resource supply conditions. For example, the common case where water storage depends on weather and reservoir conditions alone is not sufficiently general. The results imply that water management agencies that tend to be dominated by engineers and hydrological considerations need to incorporate economic considerations into decision processes.