网络并行计算中多处理机任务调度问题研究

发布时间：2018-01-17 12:38

本文关键词：网络并行计算中多处理机任务调度问题研究　出处：《计算机工程与应用》2017年10期 　论文类型：期刊论文

【摘要】：在网络并行计算系统中,具有多处理机任务需求的多步骤调度是一类常见问题,为此提出一种混合了多处理机任务调度(Multiprocessor Task Scheduling,MTS)和作业车间调度(Job-shop Scheduling Problem,JSP)的调度模型,即多处理机任务作业车间调度(Multiprocessor Task Job-shop Scheduling Problem,MTJSP)。与传统MTS不同的是MTJSP的每项任务的完成都要经历多个步骤。首先对m台处理机加工n项任务的MTJSP调度问题建立数学模型,然后设计了一种混合粒子群优化(Hybrid Particle Swarm Optimization,HPSO)算法进行求解。算法的改进工作包括:设计出针对多处理机问题的解码策略;采用新的粒子更新方式;增加记忆库功能,以保证全局最优解的多样性;加入基于模拟退火的局部搜索功能。大量的仿真实验验证HPSO的性能,结果显示HPSO不但能够有效解决MTJSP问题,在求解经典JSP问题中也表现优良。
[Abstract]:In network parallel computing systems, multistep scheduling with multiprocessor task requirements is a common problem. In this paper, a mixed multiprocessor Task Scheduling is proposed. MTS) and Job-shop Scheduling problem (JSP) scheduling model. That is, multiprocessor Task Job-shop Scheduling Problem. Different from traditional MTS, each task of MTJSP has to go through many steps. Firstly, the mathematical model of MTJSP scheduling problem of m processing n tasks is established. Then, a hybrid Particle Swarm Optimization is designed. The improvement of HPSO algorithm includes: designing decoding strategy for multiprocessor problem; Adopting a new particle renewal method; The function of memory bank is added to ensure the diversity of global optimal solution. Adding the local search function based on simulated annealing. A large number of simulation experiments verify the performance of HPSO. The results show that HPSO can not only solve the MTJSP problem effectively. It also performs well in solving classical JSP problems.
【作者单位】：北京林业大学经济管理学院;
【基金】：教育部人文社科基金(No.14YJC630030) 国家自然科学基金(No.71502015,No.71402006) 北京社会科学基金(No.16GLC059) 北京高等学校青年英才计划项目(No.YETP0776)
【分类号】：TP18;TP338.6
【正文快照】： 1引言网络并行计算是并行计算领域的研究热点,其发展满足了日益增长的大规模科学、工程和商业计算需求。但网络并行计算系统具有复杂性高、技术难度大等特点,目前还有很多问题急需解决,其中如何高效地进行处理机资源的计算任务分配已成为当前研究者的关注热点,因为计算资源协

【相似文献】