| 直线上的k-配送小车调度问题与竞争策略 |
| |
| 引用本文： | 辛春林,崔文田,衣方磊,马卫民.直线上的k-配送小车调度问题与竞争策略[J].系统工程,2005,23(5):25-28. |
| |
| 作者姓名： | 辛春林 崔文田 衣方磊 马卫民 |
| |
| 作者单位： | 1. 西安交通大学,管理学院,陕西,西安,710049
2. 清华大学,经济管理学院,北京,100084 |
| |
| 基金项目： | 国家自然科学基金资助项目(70471035，10371094，70401006)，国家自然科学基金会优秀创新研究群体基金资助项目(70121001) |
| |
| 摘 要： | 提出和研究了直线上的局内k-配送小车调度问题。应用复位策略，竞争比为k 2；设计了解决该问题的竞争算法，证明采用局部双覆盖策略Local Double Coverage Strategy(LDCS)的竞争比为k.最后，简单地分析了该问题的一个特例——局内电梯调度问题，得出了比较结果。
|
| 关 键 词： | 局内问题 直线上的k-配送小车 局部双覆盖策略 竞争算法 |
| 文章编号： | 1001-4098(2005)05-0025-04 |
Scheduling for On-line k Delivery-carts Problem on a Real Line and Its Competitive Strategy |
| |
| XIN Chun-lin,CUI Wen-tian,YI Fang-lei,MA Wei-min.Scheduling for On-line k Delivery-carts Problem on a Real Line and Its Competitive Strategy[J].Systems Engineering,2005,23(5):25-28. |
| |
| Authors: | XIN Chun-lin CUI Wen-tian YI Fang-lei MA Wei-min |
| |
| Institution: | XIN Chun-lin~1,CUI Wen-tian~1,YI Fang-lei~1,MA Wei-min~2 |
| |
| Abstract: | The on-line problem of k delivery-carts on a real line is studied in this paper, which is a generalization of the (well-known) k-server problem. How k delivery-carts serve a sequence of requests must be determined in an online manner. With the help of Position Maintaining Strategy (PMS for short), a competitive algorithm in a ratio of k+2 has been (obtained.) Furthermore, another deterministic on-line strategy is proposed, namely, the Local Double Coverage Strategy (LDCS for short),a competitive algorithm with competitive ratio k is achieved. Finally,a particular case concerning elevator is analyzed and some results have been obtained. |
| |
| Keywords: | On-line Problem k Delivery-carts on a Real Line Local Double Coverage Strategy Competitive Algorithms |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
