欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
对于订单具有紧交货期限且以最大化完工总收益为目标的占线订单排序问题，Woeginger（1994）提出了完工收益与订单长度满足C——收益函数关系的一类模型，并给出了竞争比为4的最优确定性策略。本文针对该模型设计了一个简单的随机策略，并证明其具有竞争比2。该策略明显简单于已有的各种随机策略；同时，本文结论大大改进了Seiden（1998）所给出的当前最好竞争比3．732。
英文摘要：
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 a model where the weight and length of order satisfies benevolent function, and proved an optimal 4-competitive strategy. We present a randomized strategy with competitive ratio of 2, which is much simpler than previous randomized ones and improves the previous best competitive ratio of 3. 732 by Selden （1998）.
同期刊论文项目
同项目期刊论文
期刊信息
位置：