摘要
对于带时间窗的局内车辆调度问题,以往文献的研究都是关于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.
出处
《系统工程》
CSCD
北大核心
2006年第4期93-96,共4页
Systems Engineering
基金
国家自然科学基金资助项目(70471035)
国家自然科学基金委员会优秀创新群体资助项目(70121001)
关键词
局内问题
竞争策略
竞争比
车辆调度
On-line Problem
Competitive Strategy
Competitive Ratio
Truck ,Scheduling
