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

Study of multiprocessor task scheduling problem in network parallel computing system

作　　者：王蒙[1] 樊坤[1] 翟亚飞 李心宁[1] WANG Meng;FAN Kun;ZHAI Yafei;LI Xinning(Department of Economy and Management, Beijing Forestry University, Beijing 100083, China)

机构地区：[1]北京林业大学经济管理学院,北京100083

出　　处：《计算机工程与应用》2017年第10期264-270,共7页Computer Engineering and Applications

基　　金：教育部人文社科基金(No.14YJC630030);国家自然科学基金(No.71502015;No.71402006);北京社会科学基金(No.16GLC059);北京高等学校青年英才计划项目(No.YETP0776)

摘　　要：在网络并行计算系统中,具有多处理机任务需求的多步骤调度是一类常见问题,为此提出一种混合了多处理机任务调度(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问题中也表现优良。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.

关 键 词：多处理机任务 作业车间调度 粒子群优化算法 局部搜索 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]