期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

直线上的k-配送小车调度问题与竞争策略 被引量：1

Scheduling for On-line k Delivery-carts Problem on a Real Line and Its Competitive Strategy
下载PDF
导出
摘要 提出和研究了直线上的局内k-配送小车调度问题。应用复位策略,竞争比为k+2;设计了解决该问题的竞争算法,证明采用局部双覆盖策略LocalDoubleCoverageStrategy(LDCS)的竞争比为k.最后,简单地分析了该问题的一个特例——局内电梯调度问题,得出了比较结果。 <Abstrcat> 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.
作者 辛春林 崔文田 衣方磊 马卫民
机构地区 西安交通大学管理学院 清华大学经济管理学院
出处 《系统工程》 CSCD 北大核心 2005年第5期25-28,共4页 Systems Engineering
基金 国家自然科学基金资助项目(70471035 10371094 70401006) 国家自然科学基金会优秀创新研究群体基金资助项目(70121001)
关键词 局内问题 直线上的k-配送小车 局部双覆盖策略 竞争算法 On-line Problem k Delivery-carts on a Real Line Local Double Coverage Strategy Competitive Algorithms
分类号 TB114.1 [理学—运筹学与控制论]
  • 相关文献

参考文献13

  • 1Sleator D D,Tarjan R E. Amortized efficiency of list update and paging rules[J]. Communications of the ACM,1985,28:202～208.
  • 2Chrobak M,Karloff H,Payne T,Vishwanathan S. New results on server problem[A]. Proc.1st ACM-SIAM Symp.on Discrete Algorithms[C]. 1990:291～300.
  • 3Chrobak M,Larmore L. An optimal on-line k-server algorithm for trees[J]. SIAM Journal of Computing,1991,20:144～148.
  • 4Alon N,Karp R M,Peleg D,et al. A graph-theoretic game and its application to the k-Server problem[J]. SIAM J.Comput.,1995,24(1):78～100.
  • 5Manasse M S,McGeoch L A,Sleator D D. Competitive algorithms for server problems[J]. Journal of Algorithms,1990,11:208～230.
  • 6BenDavid S,borodin A. A new measure for the study of the on-line algorithm[J]. Algorithmca,1994,111:73～79.
  • 7Koutsoupias E,Papadimitriou C. On the k-server conjecture[J]. STOC,1994:507～511.
  • 8堵丁柱.k车服务问题与竞争算法[J].数学的实践与认识,1991,21(4):36-40. 被引量：40
  • 9徐寅峰,王刊良.局内出租车调度与竞争算法[J].西安交通大学学报,1997,31(S1):58-63. 被引量：26
  • 10徐寅峰,王刊良,丁建华.限制图上的局内出租车调度与竞争算法[J].系统工程学报,1999,14(4):361-365. 被引量：11

二级参考文献19

  • 1徐寅峰,王刊良.局内出租车调度与竞争算法[J].西安交通大学学报,1997,31(S1):58-63. 被引量：26
  • 2马卫民 王刊良 已接受.局内管理问题及其竞争策略论[J].管理科学学报,.
  • 3Graham R L. Bounds for certain multiprocessing anomalies[J]. Bell System Technical Journal, 1966,45:1563-1581.
  • 4Karlin A, Manasse M, Rudolph L, Sleator D D. Competitive snoopy caching[J]. Algorithmica, 1988,3: 79-119.
  • 5Manasse M S, McGeoch L A, Sleator D D. Competitive algorithms for server problems[J]. Journal of Algorithms, 1990, (11) :208-230.
  • 6Borodin A,Linial N,Saks M. An optimal on-line algorithm for metrical task systems[J]. Journal of the ACM,1992,39: 745-763.
  • 7New Algorithms for an Ancient Scheduling Problem[A]. Proceedings of the 24th ACM symposium on Theory of Computing[C]. Victoria ,Canada, 1992 : 54-58.
  • 8BenDavid S,borodin A. A new measure for the study of the on-line algorithm[J]. Algorithmca, 1994, (11):73.
  • 9Koutsoupias E, Papadimitriou C. On the k-servicer conjecture[J] ,STOC. , 1994:507-511.
  • 10Ma W M,XU Y F,Wang K L. On-line k-truck problem and its competitive algorithm[J]. Journal of Global Optimization, 2001,21 (1) : 15- 25.

共引文献63

同被引文献13

  • 1David S, et al. A new measure for the study of the on-line algorithm[J]. Algorithmic ,1994 ,(11) : 73-91
  • 2Koutsoupias E, Papadimitriou C. On the k-srver conjecture[A]. Proc of STOC. Montreal[C]. 1994:507-511.
  • 3Manasse M S, McGeoch L A,Sleator D D. Competitive algorithms for k-server problems [J]. Journal of Algorithms, 1990, (11) : 208-230.
  • 4Feuerstein E,Stougie L. On-line single server dial-aride problems [J]. Theoretical Computer Science,2001, (1):91-105.
  • 5Xu Y F,Wang K L,Zhu B. On the k-taxi problem[J]. Journal of Information, 1999, (2) :429-434.
  • 6Ma W M, XU Y F, Wang K L. On-line k-truck problem and its competitive algorithm[J]. Journal of Global Optimization, 2001, ( 1 ) : 15 - 25.
  • 7Yi F L,Tian L. On the online dial-a-ride problem with time windows [J]. Lecture Notes in Computer Science, 2005,3521:85-94.
  • 8Psaraftis H N. An exact algorithm for the single vehicle many-to-many dial-a-ride problem with time windows[J]. Transportation Science, 1983, 17 : 351-357.
  • 9Diana M, Dessouky M M. A new regret insertion heuristic for solving large-scale dial-a-ride problemswith time windows[J]. Transportation Research Part B,2004.38:539-557.
  • 10Irani S,Lu X,Regan A. On-line algorithms for the dynamic traveling repair problem[A]. Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms[C]. 2002:517-524.

引证文献1

二级引证文献1

系统工程
2005年 第5期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部