摘要
一条路上的货车调度问题是线上的在线服务器问题的推广.决策者必须以在线方式做出决策,即已知现在和过去的信息而对未来一无所知情况下决策如何调度货车完成服务需求.优化目标是使竞争比最小.本文分空载和实载两种情行进行了讨论,对每种情形分别提出两种不同的竞争策略,得到了相应的竞争比;最后,对本文中给出的问题P3的两种竞争算法作了比较并得出了结果.
On-line truck scheduling problem on a road is a generalization of the on-line server problem on a real line. The player decides how to schedule trucks to satisfy serve requests one by one without future information; in other words, he must make decision in an online manner. The aim is to minimize the competitive ratio. In this paper, this problem is discussed according to two cases, that is, load factor and no-load factor are considered. We propose two different competitive strategies for each case respectively and obtain corresponding competitive ratios. Finally, two alternative competitive strategies for the problem P3 given in this paper are compared and some results are obtained.
出处
《系统工程学报》
CSCD
北大核心
2006年第5期470-475,共6页
Journal of Systems Engineering
基金
国家自然科学基金资助项目(705710627047103570401006)
关键词
在线问题
一条路上的货车调度
竞争算法
竞争比
on-line problem
truck scheduling on a road
competitive algorithms
competitive ratio
