一条路上的在线货车调度及其竞争分析

作者：辛春林; 崔文田; 徐寅峰

来源：系统工程学报, 2006, (05): 470-475.

• 在线问题
• 一条路上的货车调度
• 竞争算法
• 竞争比 on-line problem
• truck scheduling on a road
• competitive algorithms
• competitive ratio

一条路上的货车调度问题是线上的在线服务器问题的推广.决策者必须以在线方式做出决策,即已知现在和过去的信息而对未来一无所知情况下决策如何调度货车完成服务需求.优化目标是使竞争比最小.本文分空载和实载两种情行进行了讨论,对每种情形分别提出两种不同的竞争策略,得到了相应的竞争比;最后,对本文中给出的问题P3的两种竞争算法作了比较并得出了结果.

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