并行处理系统的有序调度问题及其渐近最优算法

导出

摘要研究一类并行处理系统的有序调度问题.详细讨论了有序调度问题的背景及研究有序算法的意义,给出了有序算法有别于经典算法的主要特征.对目标为极大化处理器最小负载的并行有序调度问题,给出了两个近似算法族,它们是渐近最优的,并且对固定的m,最坏情况界与问题的上界非常接近,从而大大改进了已有文献中的结果.

作者谈之奕何勇

机构地区浙江大学数学系

出处《中国科学（E辑）》 CSCD 北大核心 2003年第12期1069-1076,共8页 Science in China(Series E)

基金国家自然科学基金(批准号:10271110) 高等学校优秀青年教师教学科研奖励计划中国博士后科学基金

关键词并行处理系统有序调度渐近最优算法最坏情况界操作系统

参考文献12

1[1]He Y, Tan Z. Ordinal on-line scheduling for maximizing the minimum machine completion time. Journal of Combinatorial Optimization, 2002, 6: 199～206
2[2]Friesen D, Deuermeyer B. Analysis of greedy solutions for a replacement part sequencing problem. Mathematics of Operations Research, 1981, 6: 74～87
3[3]Garey M R, Johnson D S. Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: Freeman, 1978
4[4]Graham R L. Bounds on multiprocessing finishing anomalies. SIAM Journal on Applied Mathematics, 1969, 17: 416～429
5[5]Deuermeyer B, Friesen D, Langston M. Scheduling to maximize the minimum processor finish time in a multiprocessor system. SIAM Journal on Discrete Methods, 1982, 3: 190～196
6[6]Csirik J, Kellerer H, Woeginger G. The exact LPT-bound for maximizing the minimum machine completion time. Operations Research Letters, 1992, 11: 281～287
7[7]Liu W P, Sidney J B, van Vliet A. Ordinal algorithms for parallel machine scheduling. Operations Research Letters, 1996, 18: 223～232
8[8]Tan Z, He Y. Semi online scheduling with ordinal data on two uniform machines. Operations Research Letters, 2001, 28: 221～231
9[9]Liu W P, Sidney J B. Bin packing using semi-ordinal data. Operations Research Letters, 1996, 19, 101～104
10[10]Liu W P, Sidney J B. Ordinal algorithm for packing with target center of gravity. Order, 1996, 13: 17～31

1任智格.两种分水岭分割法的比较[J].网友世界,2013(9):61-61.
2魏麒,蒋义伟.一类两阶段杂交流水作业的近似算法(英文)[J].软件学报,2012,23(5):1073-1084. 被引量：2
3TAN Zhiyi1,2 & HE Yong1 1. Department of Mathematics, Zhejiang University, Hangzhou 310027, China (email: tanzy@math.zju. edu.cn,heyong@math.zju.edu.cn),2. State Key Laboratory of CAD & CG, Zhejiang University, Hangzhou 310027, China.Ordinal scheduling problem and its asymptotically optimal algorithms on parallel machine system[J].Science in China(Series F),2004,47(2):161-169. 被引量：1
4蒋义伟,魏麒.图形处理中一类Flow-shop问题的改进算法[J].自动化学报,2011,37(11):1381-1386. 被引量：4
5刘丽娜,胡业林,郑晓亮.基于DM642的矿井视频监控系统的设计[J].煤矿机械,2012,33(11):264-265. 被引量：5
6刘韵洁,黄韬,张娇,刘江,姚海鹏,谢人超.服务定制网络[J].通信学报,2014,35(12):1-9. 被引量：11
7北京扩大城市图像监控范围逐步实现无缝覆盖[J].中国公共安全,2010,0(15):134-134.
8贾晓庆.基于B/S网络结构的嵌入式视频监控系统[J].电子设计工程,2011,19(13):159-162.
9孙西,金以慧,方崇智.死区非线性系统的全局收敛自适应控制[J].信息与控制,1992,21(6):326-331. 被引量：2
10冯亮.煤矿井下采煤设备工序虚拟化调度方法[J].计算机仿真,2015,32(4):419-423. 被引量：3

中国科学（E辑）

2003年第12期

内容加载中请稍等...