基于订单采购模式的销售商在线采购策略

摘要

In the mode of purchase to order, purchase cost and delay cost are interactive.Vendors need to choose appropriate purchase strategy to balance the two items in order to minimize the total cost.The paper first analyzes the offline case where the total information on order demands is known beforehand, and gives an optimal offline strategy with time complexity.It then discusses the online purchasing strategy for the online case where order demands are unpredictable.A 2-comptitive online strategy is proposed, and a lower bound of competitive ratio for the online case is proved as well.%对于按订单采购的销售商而言,采购成本和延误成本是影响总成本的主要因素,销售商需要采取适当的采购策略,权衡二者,以使总成本尽量小.文章首先给出了订单需求完全已知情况下的离线最优策略,并指出策略的计算复杂性为O(n2).其次,针对订单需求难以预测的情形,设计了相应的在线采购策略,证明了该策略的竞争比为2;同时,证明了该问题的竞争比下界为((√5)+1)/2＞1.618.