摘要
提出了有限预知信息的集装箱搬卸占线问题,即每一个服务请求到达时预先知道后续一部分请求信息的占线问题。建立并分析相应的数学模型,针对模型中预知信息的特征提出了贪婪移位策略。运用最坏情形分析方法研究了贪婪移位策略的竞争性能,证明其具有竞争比:(b+w-2)/w。
The paper puts forward the online container shipment problem with limited prevision information, in which an online algorithm gets to know several requests in future when each request arrives. The relevant mathematic model is set up and analyzed. The Greedy hift strategy is brought forward accoding to the trait of the model. With the analysis method of worst case performance, it is proved that the Greedy shift strategy has a competitive ratio of (b+w-2)w.
出处
《系统工程理论方法应用》
2004年第5期390-394,共5页
Systems Engineering Theory·Methodology·Applications
基金
国家自然科学基金会优秀创新群体基金支持(70121001)
关键词
占线问题
贪婪移位策略
竞争比
online problem
Greedy shift strategy
competitive ratio
