带时间窗的局内开放式车调度问题的竞争分析  

A Competitive Analysis for the Open On-line k Trucks Scheduling Problem with Time Window

作　　者：戴敏[1] 徐寅峰[1] 董玉成[1] 杜源江[1] 

机构地区：[1]西安交通大学管理学院,陕西西安710049

出　　处：《系统工程》2006年第4期93-96,共4页Systems Engineering

基　　金：国家自然科学基金资助项目(70471035);国家自然科学基金委员会优秀创新群体资助项目(70121001)

摘　　要：对于带时间窗的局内车辆调度问题,以往文献的研究都是关于k=1的单车调度,其开放式情形下最好的竞争比为4。针对该问题本文进行了开放式情形下多辆车(k≥2)调度的研究分析,设计了解决该问题的竞争算法,并证明了其竞争比为3.5。同时本文分析了该问题的一种特殊情形——单车调度问题,可证明其竞争比为3,优于已有结果。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.

关 键 词：局内问题 竞争策略 竞争比 车辆调度 

分 类 号：U492[交通运输工程—交通运输规划与管理]