|本期目录/Table of Contents|

[1]赖俊凡,王宇平,王晓丽.考虑处理机时间窗口的可分任务调度优化模型[J].西安交通大学学报,2017,51(09):118-124.[doi:10.7652/xjtuxb201709017]
 LAI Junfan,WANG Yuping,WANG Xiaoli.An Optimization Model for DivisibleLoad Scheduling Considering Processor TimeWindow[J].Journal of Xi'an Jiaotong University,2017,51(09):118-124.[doi:10.7652/xjtuxb201709017]
点击复制

考虑处理机时间窗口的可分任务调度优化模型(PDF)

《西安交通大学学报》[ISSN:0253-987X/CN:61-1069/T]

卷:
51
期数:
2017年第09期
页码:
118-124
栏目:
出版日期:
2017-09-10

文章信息/Info

Title:
An Optimization Model for DivisibleLoad Scheduling
Considering Processor TimeWindow
作者:
赖俊凡王宇平王晓丽
西安电子科技大学计算机学院,710071,西安
Author(s):
LAI JunfanWANG YupingWANG Xiaoli
School of Computer Science and Technology, Xidian University, Xi’an 710071, China
关键词:
处理机可分任务调度时间窗口遗传算法
Keywords:
processor divisibleload scheduling timewindow genetic algorithm
分类号:
TP18
DOI:
10.7652/xjtuxb201709017
摘要:
针对异构分布式系统下处理机具有时间窗口约束的可分任务调度问题,通过寻找最优的任务分配方案和最优的处理机调度顺序,可以使得任务的完成时间最短。首先,在已有模型上引入处理机时间窗口的概念,使得所建模型更加贴切实际;然后,建立了一个新的考虑处理机时间窗口可分任务调度的非阻塞优化模型,同时设计了一种基于全局优化的遗传算法来求解模型;最后,为了快速、高效地求解模型,所提算法同时对处理任务量和调度顺序进行编码,利用不同的交叉算子来优化调度顺序和任务分配量,设计了合理的修正算子来修正不满足处理机时间窗口的任务分配方案,并且设计了高效的局部搜索算子来加快算法的收敛速度。仿真实验结果表明,在处理机时间窗口约束下,与已有算法相比,所提算法至少提升了20%以上的性能,从而证明了所提算法的正确性和有效性。
Abstract:
A divisibleload scheduling problem under the constraint of processor timewindow for heterogeneous distributed systems is presented, and the makespan is minimized by finding the optimal load partition strategy and the optimal distribution sequence of processors. On the basis of existing research, the concept of timewindow is introduced first, which makes the model more practical. Then a novel divisibleload scheduling nonblocking model is proposed considering the timewindow. Meanwhile, a genetic algorithm is designed for the proposed model. In order to solve the model quickly and efficiently, the load partition and the distribution sequence of processors are encoded at the same time. Different crossover operators are designed to optimize the load partition and the distribution sequence of processors, and a modification operator is designed to modify the load partition scheme which does not satisfy the constraint of processors’ timewindow. Moreover, An efficient local search operator to is also designed speed up the convergence rate of the algorithm. Finally, simulation experiments are carried out, and the results show that under the constraint of the processor timewindow, the proposed algorithm can improve the performance of the existing algorithms by at least 20%, which proves the correctness and effectiveness of the proposed algorithm.

参考文献/References:

[1]ROBERTAZZI T G. Ten reasons to use divisible load theory [J]. Computer, 2003, 36(5): 6368.
[2]SURESH S, MANI V, OMKAR S N, et al. Parallel video processing using divisible load scheduling paradigm [J]. Journal of Broadcast Engineering, 2005, 10(1): 83102.
[3]KO K, ROBERTAZZI T G. Signature search time evaluation in flat file databases [J]. IEEE Transactions on Aerospace & Electronic Systems, 2008, 44(2): 493502.
[4]MIN W H, VEERAVALLI B. Aligning biological sequences on distributed bus networks: a divisible load scheduling approach. [J]. IEEE Transactions on Information Technology in Biomedicine, 2005, 9(4): 489501.
[5]LIU D, YANG X, CHENG Z. An energyaware scheduling algorithm for divisible loads in a bus network [J]. Concurrency and Computation Practice and Experience, 2016, 28(5): 16121628.
[6]BRANDO J S, NORONHA T F, MAURICIO G. C, et al. A biased randomkey genetic algorithm for singleround divisible load scheduling [J]. International Transactions in Operational Research, 2015, 22(5): 823839.
[7]ZHANG Z, ROBERTAZZI T G. Scheduling divisible loads in Gaussian, mesh and torus network of processors [J]. IEEE Transactions on Computers, 2015, 64(11): 32493264.
[8]CHEN C Y, CHU C P. Novel methods for divisible load distribution with startup costs on a complete bary tree [J]. IEEE Transactions on Parallel & Distributed Systems, 2015, 26(10): 28362848.
[9]SURESH S, HUANG H, KIM H J. Scheduling in compute cloud with multiple data banks using divisible load paradigm [J]. IEEE Transactions on Aerospace & Electronic Systems, 2015, 51(2): 12881297.
[10]VEERAVALLI B, GHOSE D, MANI V. Optimal sequencing and arrangement in distributed singlelevel tree networks with communication delays [J]. IEEE Transactions on Parallel & Distributed Systems, 1994, 5(9): 968976.
[11]VEERAVALLI B, BARLAS G. Scheduling divisible loads with processor release times and finite size buffer capacity constraints in bus networks [J]. Cluster Computing, 2003, 6(1): 6374.
[12]HU M, VEERAVALLI B. Requirementaware strategies with arbitrary processor release times for scheduling multiple divisible loads [J]. IEEE Transactions on Parallel & Distributed Systems, 2011, 22(10): 16971704.
[13]王晓萍, 孟坤. 异构分布式系统的可分任务调度算法 [J]. 小型微型计算机系统, 2015, 36(4): 797800.
WANG Xiaoping, MENG Kun. New genetic algorithm for divisible load scheduling in heterogenous distributed systems [J]. Journal of Chinese Computer Systems, 2015, 36(4): 797800.
[14]王晓丽, 王宇平, 孟坤. 考虑处理机释放时间的可分任务调度优化模型 [J]. 西安电子科技大学学报, 2016, 43(1): 5560.
WANG Xiaoli, WANG Yuping, MENG Kun. Release time aware divisibleload scheduling optimization model [J]. Journal of Xidian University, 2016, 43(1): 5560.
[15]王晓丽, 王宇平, 蔡坤. 考虑释放时间和调度顺序的可分任务调度模型 [J]. 华中科技大学学报(自然科学版), 2015, 43(12): 106111.
WANG Xiaoli, WANG Yuping, CAI Kun. Release time and startup overhead aware divisibleload scheduling model [J]. Journal of Huazhong University of Science and Technology (Natural Science Edition), 2015, 43(12): 106111.
[16]CHOI K, ROBERTAZZI T G. An exhaustive approach to release time aware divisible load scheduling [J]. International Journal on Internet & Distributed Computing Systems, 2011, 1(2): 145151.

备注/Memo

备注/Memo:
国家自然科学基金资助项目(61472297,U1404622)
更新日期/Last Update: