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

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

来源：运筹与管理, 2009, (06): 75-79.

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

对于订单具有紧交货期限且以最大化完工总收益为目标的占线订单排序问题,Woeginger(1994)提出了完工收益与订单长度满足C——收益函数关系的一类模型,并给出了竞争比为4的最优确定性策略。本文针对该模型设计了一个简单的随机策略,并证明其具有竞争比2。该策略明显简单于已有的各种随机策略;同时,本文结论大大改进了Seiden(1998)所给出的当前最好竞争比3.732。

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