Release time and distribution sequence aware divisible-load scheduling model

被引：0
作者：
Wang, Xiaoli [1 ]
Wang, Yuping [1 ]
Cai, Kun [1 ]
机构：
[1] School of Computer Science and Technology, Xidian University, Xi'an
来源：
Huazhong Keji Daxue Xuebao (Ziran Kexue Ban)/Journal of Huazhong University of Science and Technology (Natural Science Edition) | 2015年 / 43卷 / 12期
关键词：
Distribution sequence; Divisible-load scheduling; Genetic algorithm; Heterogeneous distributed systems; Release time;
D O I：
10.13245/j.hust.151222
中图分类号：
学科分类号：
摘要：
For heterogeneous parallel and distributed systems with arbitrary processor release times, the make-span was minimized by finding the optimal distribution sequence of processors and the optimal load partition. First, the influence of processor release times on the make-span was analyzed with a given distribution sequence of processors, and the function of load partition with respect to the distribution sequence and time constraints was derived. Second, a new divisible-load scheduling model was proposed with the distribution sequence and time constraints as variables and the minimum make-span as the objective. Third, an effective global optimization genetic algorithm was designed to solve this model. Finally, experimental results show that the proposed algorithm outperforms the existing algorithms in finding the minimum make-span. © 2015, Editorial Board of Journal of Huazhong University of Science and Technology. All right reserved.
引用
收藏
页码：106 / 111and132
相关论文
共 11 条
  • [1] Mani V., Ghose D., Distributed computation in linear networks: closed-form solutions, IEEE Transactions on Aerospace and Electronic Systems, 30, 2, pp. 471-483, (1994)
  • [2] Ghose D., Mani V., Distributed computation with communication delays: asymptotic performance analysis, Journal of Parallel and Distributed Computing, 23, 3, pp. 293-305, (1994)
  • [3] Bharadwaj V., Ghose D., Mani V., Optimal sequencing and arrangement in distributed single-level networks with communication delays, IEEE Trans on Parallel and Distributed Systems, 5, 9, pp. 968-976, (1994)
  • [4] Kim H.J., Jee G.L., Lee J.G., Optimal load distribution for tree network processors, IEEE Transactions on Aerospace and Electronic Systems, 32, 2, pp. 607-612, (1996)
  • [5] Veeravalli B., Li X., Ko C.C., On the influence of start-up costs in scheduling divisible loads on bus networks, IEEE Transactions on Parallel and Distributed Systems, 11, 12, pp. 1288-1305, (2000)
  • [6] Shang M.S., Optimal algorithm for scheduling large divisible workload on heterogeneous system, Applied Mathematical Modeling, 32, pp. 1682-1695, (2008)
  • [7] Murugesan G., Chellappan C., Multi-source task scheduling in grid computing environment using linear programming, International Journal of Computer Science and Engineering, 9, 1, pp. 80-85, (2014)
  • [8] Iyer G.N., Veeravalli B., Krishnamoorthy S.G., On handling large-scale polynomial multiplication in compute cloud environments using divisible load paradigm, IEEE Transactions on Aerospace and Electronic Systems, 48, 1, pp. 820-831, (2012)
  • [9] Shi H., Wang W., Kwok N.M., Et al., Adaptive indexed divisible load theory for wireless sensor network workload allocation, International Journal of Distributed Sensor Networks, 1, pp. 8-10, (2013)
  • [10] Hu M., Veeravalli B., Dynamic scheduling of hybrid real-time tasks on clusters, IEEE Transactions on Computers, 63, 12, pp. 2988-2997, (2014)
12