摘要
对于订单具有紧交货期限且以最大化完工总收益为目标的占线订单排序问题,Woeginger提出了完工收益与订单长度满足D-收益函数的模型,并给出了竞争比为4的最优确定性策略。针对该模型设计了竞争比为2的一个简单随机策略,该结论改进了Epstein和Levin(2008)的竞争比2.455 4。
For the on-line order scheduling problem where each order has tight deadline and the objective aims to maximize the profit of completed orders,Woeginger（1994） put forward one model with D-benevolent function,and preented an optimal 4-competitive deterministic strategy.The paper will proposed a（2-competitive） randomized strategy.The strategy is much simpler than previous randomized ones and（improves） the previous ratio of 2.4554 by Epstein and Levin（2008）.
出处
《系统管理学报》
CSSCI
北大核心
2010年第1期93-95,共3页
Journal of Systems & Management
基金
国家杰出青年基金资助项目(70525004)
国家自然科学基金资助项目(70702030
70602031)
优秀创新群体项目(70121001)
教育部博士点新教师基金资助项目(20070698053)
关键词
订单排序
随机策略
竞争比
占线策略
order scheduling
randomized strategy
competitive ratio
on-line strategy
