| 带时间窗的局内开放式车调度问题的竞争分析 |
| |
| 引用本文： | 戴敏,徐寅峰,董玉成,杜源江.带时间窗的局内开放式车调度问题的竞争分析[J].系统工程,2006,24(4):93-96. |
| |
| 作者姓名： | 戴敏 徐寅峰 董玉成 杜源江 |
| |
| 作者单位： | 1. 西安交通大学,管理学院,陕西,西安,710049
2. 西安交通大学,管理学院,陕西,西安,710049;机械制造系统工程国家重点实验室,陕西,西安,710049 |
| |
| 基金项目： | 国家自然科学基金;国家自然科学基金 |
| |
| 摘 要： | 对于带时间窗的局内车辆调度问题，以往文献的研究都是关于k=1的单车调度，其开放式情形下最好的竞争比为4。针对该问题本文进行了开放式情形下多辆丰（k≥2）调度的研究分析，设计了解决试问题的竞争算法，并证明了其竞争比为3．5。同时本文分析了该问题的一种特殊情形——单车调度问题，可证明其竞争比为3．优于已有结果。
|
| 关 键 词： | 局内问题 竞争策略 竞争比 车辆调度 |
| 文章编号： | 1001-4098（2006）04-0093-04 |
| 收稿时间： | 2005-12-19 |
| 修稿时间： | 2005-12-19 |
A Competitive Analysis for the Open On-line k Trucks Scheduling Problem with Time Window |
| |
| DAI Min,XU Yin-feng,DONG Yu-cheng,DU Yuan-jiang.A Competitive Analysis for the Open On-line k Trucks Scheduling Problem with Time Window[J].Systems Engineering,2006,24(4):93-96. |
| |
| Authors: | DAI Min XU Yin-feng DONG Yu-cheng DU Yuan-jiang |
| |
| Abstract: | Most literatures about the on-line k-truck scheduling problem are mainly focused on a single one and the best competitive ratio is 4 in the open on-line scheduling problem. In this paper, the problem is extended to k trucks and a new reschedule strategy is proposed which has a competitive ratio of 3. 5. In a special case of this strategy - single truck scheduling, the competitive ratio of 3 is obtained. The result is better than the former outcomes. |
| |
| Keywords: | On-line Problem Competitive Strategy Competitive Ratio Truck Scheduling |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
