论文研究-网络并行计算中多处理机任务调度问题研究.pdf

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