J4 ›› 2016, Vol. 43 ›› Issue (1): 47-53.doi: 10.3969/j.issn.1001-2400.2016.01.009

• 研究论文 • 上一篇    下一篇

考虑处理机释放时间的可分任务调度优化模型

王晓丽;王宇平;孟坤   

  1. (西安电子科技大学 计算机学院,陕西 西安  710071)
  • 收稿日期:2014-08-11 出版日期:2016-02-20 发布日期:2016-04-06
  • 通讯作者: 王晓丽
  • 作者简介:王晓丽(1987-),女,讲师,博士,E-mail: wangxiaoli@mail.xidian.edu.cn.
  • 基金资助:

    国家自然科学基金资助项目(61402350,61472297,61272119);中央高校基本科研业务费专项资金资助项目(JB150307)

Release time aware divisible-load scheduling optimization model

WANG Xiaoli;WANG Yuping;MENG Kun   

  1. (School of Computer Science and Technology, Xidian Univ., Xi'an  710071, China)
  • Received:2014-08-11 Online:2016-02-20 Published:2016-04-06
  • Contact: WANG Xiaoli

摘要:

可分任务调度是近年来信息技术领域研究的热点课题.已有的可分任务调度模型大多假设所有处理机在任务分配之初全部处于空闲状态,而实际上,当新的任务到来时很多处理机可能尚处于忙碌状态.每台处理机从忙碌状态转到空闲状态的时间不同,即处理机可能具有不同的释放时间.在充分考虑处理机释放时间不同的基础上,建立了一种新的混合时序约束的可分任务调度模型,并设计了高效的全局优化遗传算法求解该模型.实验结果表明了模型的合理性和算法的有效性.

关键词: 可分任务调度, 释放时间, 混合时序约束, 遗传算法

Abstract:

Divisible-load scheduling has become an increasingly hot subject in the research on information technologies in recent years. Most existing divisible-load scheduling models assume that all processors are idle at the beginning of workload assignment. In fact, many processors may still in the busy state when a new workload arrives. Processors may have different waiting times from the busy state to the idle, that is, processors have different release times. This paper proposes a new release time aware divisible-load scheduling model with hybrid time constraints and designs an effective global optimization genetic algorithm to solve it. Finally, experimental results show the effectiveness of the proposed model and the efficiency of the proposed algorithm.

Key words: divisible-load scheduling, release time, hybrid time constraints, genetic algorithm