占线订单排序D-收益函数下改进的随机策略

作者：郑斐峰; 徐寅峰; 张娥

来源：系统管理学报, 2010, (01): 93-95.

• 订单排序
• 随机策略
• 竞争比
• 占线策略 order scheduling
• randomized strategy
• competitive ratio
• on-line strategy

对于订单具有紧交货期限且以最大化完工总收益为目标的占线订单排序问题,Woeginger提出了完工收益与订单长度满足D-收益函数的模型,并给出了竞争比为4的最优确定性策略。针对该模型设计了竞争比为2的一个简单随机策略,该结论改进了Epstein和Levin(2008)的竞争比2.455 4。

• 单位
  西安交通大学; 西安交通大学机械制造系统工程国家重点实验室; 上海财经大学