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

doi:10.3778/j.issn.1002-8331.1610-0303

计算机工程与应用 ›› 2017, Vol. 53 ›› Issue (10): 264-270.DOI: 10.3778/j.issn.1002-8331.1610-0303

• 工程与应用 • 上一篇

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

王蒙，樊坤，翟亚飞，李心宁

北京林业大学经济管理学院，北京 100083

出版日期:2017-05-15 发布日期:2017-05-31

Study of multiprocessor task scheduling problem in network parallel computing system

WANG Meng, FAN Kun, ZHAI Yafei, LI Xinning

Department of Economy and Management, Beijing Forestry University, Beijing 100083, China

Online:2017-05-15 Published:2017-05-31

摘要/Abstract

摘要： 在网络并行计算系统中，具有多处理机任务需求的多步骤调度是一类常见问题，为此提出一种混合了多处理机任务调度（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 the network parallel computing system, the problem which aims to schedule tasks with multiprocessor and multistage is common. Hence, this paper proposes the model of Multiprocessor Task Job-shop Scheduling Problem, i.e. MTJSP, a combination of Multiprocessor Task Scheduling（MTS） and Job-shop Scheduling Problem（JSP）. MTJSP in which every task needs more than one stage to complete is different from the classical MTS in which there is only one stage for each task. The mathematic formulation of MTJSP is constructed and a Hybrid Particle Warm Optimization（HPSO） is designed for solving it which includes the decoding schemes, new ways for particle updating, memories for better solutions and function of local searching. Plenty of instances are used to measure the performance of HPSO and numerical results show that HPSO behaves very well on instances of both JSP and MTJSP.

Key words: multiprocessor task, Job-shop Scheduling Problem（JSP）, Particle Swarm Optimization（PSO）, local search

王蒙，樊坤，翟亚飞，李心宁. 网络并行计算中多处理机任务调度问题研究[J]. 计算机工程与应用, 2017, 53(10): 264-270.

WANG Meng, FAN Kun, ZHAI Yafei, LI Xinning. Study of multiprocessor task scheduling problem in network parallel computing system[J]. Computer Engineering and Applications, 2017, 53(10): 264-270.

[1]	孙泽宇，徐琛，苏艳超，李传锋，聂雅琳. 雾计算中跨层感知分簇路由协议[J]. 计算机工程与应用, 2021, 57(9): 109-117.
[2]	谢锐强，张惠珍. 求解柔性作业车间调度问题的两段式狼群算法[J]. 计算机工程与应用, 2021, 57(7): 251-256.
[3]	徐辰华，骆珠光，吴冠宏，刘斌. 基于正弦因子和量子局部搜索的灰狼优化算法[J]. 计算机工程与应用, 2021, 57(24): 83-89.
[4]	李宝帅，叶春明. 深度强化学习算法求解作业车间调度问题[J]. 计算机工程与应用, 2021, 57(23): 248-254.
[5]	陈万芬，王宇嘉，林炜星. 异构集成代理辅助多目标粒子群优化算法[J]. 计算机工程与应用, 2021, 57(23): 71-80.
[6]	石宇强，田永政，张雨琦，石小秋. 运用含复杂网络结构的多种群遗传算法求解FJSP[J]. 计算机工程与应用, 2021, 57(2): 257-266.
[7]	郝翔，贺毅朝，朱晓斌，翟庆雷. 基于离散混合多宇宙算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2021, 57(18): 103-113.
[8]	郭佳丽，王秋萍，王晓峰. 融合学习策略和邻域搜索的飞蛾火焰算法[J]. 计算机工程与应用, 2021, 57(12): 170-179.
[9]	廖玮霖，程杉，尚冬冬，魏昭彬. 多策略融合的粒子群优化算法[J]. 计算机工程与应用, 2021, 57(1): 69-76.
[10]	吴树景，游有鹏，罗福源. 变邻域保优遗传算法求解柔性车间调度问题[J]. 计算机工程与应用, 2020, 56(22): 236-243.
[11]	闫苗苗，刘三阳. 多班级交互式教学优化算法[J]. 计算机工程与应用, 2019, 55(9): 10-16.
[12]	张鑫1，邹德旋1，肖鹏1，喻秋2. 自适应简化粒子群优化算法及其应用[J]. 计算机工程与应用, 2019, 55(8): 250-263.
[13]	闫旭，叶春明. 混合蝗虫优化算法求解作业车间调度问题[J]. 计算机工程与应用, 2019, 55(6): 257-264.
[14]	郑朝鑫1，2，董晨1，3，贺国荣1，3，陈荣忠1，3，熊子奇1，3. 基于改进粒子群算法的动态3D实时建模技术[J]. 计算机工程与应用, 2019, 55(5): 65-71.
[15]	罗雄，钱谦，伏云发. 遗传算法解柔性作业车间调度问题应用综述[J]. 计算机工程与应用, 2019, 55(23): 15-21.

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

Study of multiprocessor task scheduling problem in network parallel computing system

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics