一种改进的多处理机约束混合车间调度算法
时间：2020-11-09 04:00:35 来源：达达文档网 本文已影响 人 
杨思娜 瞿华
[摘 要] 具有多处理机任务要求的多步调度问题在网络并行计算系统中十分普遍。这样的问题可以使用“具有多处理机任务约束的混合作业车间调度”（Hybrid Job-shop Scheduling with Multiprocessor Tasks，HJSMT）模型来表示，并使用“混合粒子群的优化算法”（Hybrid Particle Swarm Optimization，HPSO）求解。改进的算法在HPSO算法的基础上进行改进：原HPSO算法在求一个任务的最早开始时间时使用穷举法，每次从时间0开始向后，逐个单位时间尝试;改进后的算法运用动态规划法求解。实验结果表明，相比原始算法的改进算法，运行速度有明显的提升，原算法进行一次迭代的时间，新算法已经完成了一次实验（一次实验包含多次迭代），在保证HJSMT问题有效解决的同时提升了算法的时间效率。
[关键词] 多处理机任务;作业车间调度;混合粒子群优化算法;动态规划
doi ：
10 . 3969 / j . issn . 1673 - 0194 . 2020. 17. 051
[中图分类号] F270.7;TP315 [文献标识码] A [文章编号] 1673 - 0194（2020）17- 0113- 03
1 引 言
在并行计算领域中，网络并行计算作为关键的发展方向，涉及各个领域，如集群计算、可扩展计算、元计算、异构计算、网格计算等。然而，由于网络并行计算系统的复杂性，其涉及的领域较多，实现起来比较困难，因此还需要解决许多问题，如资源调度[1]。在网络并行计算机系统中，为了完成具有多种资源需求的任务之间的协调调度，达到预期效果，需要在时间和空间上考虑资源的合理搭配组合。
传统的资源调度问题可以分为并行系统中多处理机的任务调度（Multiprocessor Task Scheduling，MTS）和作业车间调度问题（Job-shop Scheduling Problem，JSP）两大类。其中，MST问题每项任务需要多项资源，必须充分合理地利用一切可用资源，按某种顺序安排所有待处理的多处理器任务，使加工处理总执行时间尽可能小[2];JSP问题则对于给定的一组待加工工件与机器集合，每个工件都包含多道工序，且有特定的加工顺序，每个工序中工件的加工只能由一台机器进行处理。同时JSP问题也是难解的NP-hard问题，开发有效的算法求解此类调度问题一直是资源调度和优化领域的重要课题。然而，在一般化的网络并行计算中，一项计算任务通常需要多个步骤来完成，并且每个步骤需要多个资源参与，相当于MTS和JSP的混合，即“具有多处理机任务约束的混合作业车间调度”（Hybrid Job-shop Scheduling with Multiprocessor Tasks，HJSMT）模型。
例如文献[3]给出的一个例子：有三个应用（任务）A、B和C在各自的步骤中对资源a、b、c、d、e和f的需求如表1所示。
HJSMT问题是生产调度中一个典型的问题，不仅具有重要的理论价值，同时它在社会生产中具有重要的实际意义。首先随着世界贸易竞争越来越激烈，更优的生产调度意味着更低的生产成本和更高的生产效率，采用高效的优化技术，可以对生产过程中的突发事件做出快速、科学的反应，改善生产性能指标，有效提高生产效率。其次生产调度复杂的生产流程可以通过理论被应用到实际生产中，使得密集型的生产需求得以在生产系统中实现。本文使用动态规划法对HJSMT问题的HPSO求解算法进行改进，提升了原算法的解码效率，可以更加高效地求解网络并行计算中的HJSMT问题。
2 问题描述
3 改进的求解HJSMT的混合粒子群优化算法
3.1 混合粒子群优化算法HPSO
文獻[5]提出的混合粒子群优化算法，是结合群智能算法和本地搜索算法的优点，在粒子群算法的基础上，增加了一种基于模拟退火的局部搜索算法，用来求解网络并行计算中的HJSMT问题。
粒子群优化算法（PSO）的基本思想源自鸟群捕食行为，从鸟群飞向食物的行为特点得到启发。在该算法中，称种群为“粒子群”，称种群中的每个个体为“粒子”，对应于每个优化问题的一个候选解。首先进行种群初始化，并随机生成一群粒子，每个粒子都是优化问题（目标函数）的一个解。每次迭代，在解空间中飞行的所有粒子，通过追寻个体最优Pbest和群体最优Gbest这两个极值来更新自身的速度和位置。个体最优Pbest是某个粒子在一次迭代中找到的个体最优解，Gbest是所有个体在一次迭代中找到的种群最优解。通过不断地迭代使粒子不断更新自己的速度和位置，从而产生新的个体最优和种群最优，通过比较得出目标函数的最优解。针对HJSMT问题的特点，HPSO在此基础上采用新的位置更新方式和基于模拟退火的局部搜索方式，保证了算法性能。HPSO流程如图1所示。
3.2 粒子编码和解码策略
为了产生满足约束条件（2）和（3）的粒子，采用基于步骤的编码方式：将一个粒子表示成一个长度为■|Ji|的向量V，向量V的每个元素代表对应的工件，工件i出现|Ji|次，出现的顺序代表该工件对应的加工工序。通过解码可以将粒子还原成对应的调度方案，根据文献[5]给出一种HJSMT的主动调度解码算法进行解码：
输入：粒子向量
输出：粒子的最大完工时间
解码策略产生的调度满足约束条件（3）。编码和解码策略的结合使用，使粒子能够在可行域内找到最优解。
4 解码策略的改进
4.1 算法改进思想
上述HPSO的主动调度解码算法使用穷举法，每次搜索可行的加工步骤从时间0向后开始，逐个尝试单位时间，寻找符合当前加工任务中下一待加工步骤的处理机器，若找到符合加工步骤的剩余机器则开始加工;若该时刻没有剩余机器，则等待，重复上述搜索步骤;若工件完成所有加工步骤，则输出加工时间，未完成所有加工步骤则继续加工。由于该解码方式每搜索完成一次待加工步骤的最早开始时间就将时间初始化为0，下次搜索从时间0开始，若多次迭代测试，计算机处理时间较长，效率较低。
动态规划法是解决多阶段决策最优化问题一种常用的方法，从整体来看算法的实现是按照递推关系式进行递推，在搜索时能体现高时效性。相比于其他算法，动态规划法不仅减少了大量的计算量，而且得到当前状态对目标状态的最优值的同时还得到了中间状态的最优值，丰富了计算结果。它所解决的问题需要满足最优性原理和马尔可夫性（无后效性）。
最优性原理简单地说就是各个子问题的最优解构成原问题的最优解;马尔可夫性则是指现在时刻的随机变量的状态和过去某一时刻的随机变量状态有关， 但和过去的所有随机变量的状态无关，即n时刻的状态只与n-1时刻相关，且能被前一次状态推算出来。
HPSO算法的粒子解码问题（求最大完工时间）满足最优性和无后效性的证明如下：
令Cij为步骤Oij的最早结束时间，pij为其处理时间（见问题描述）。Aij为步骤Oij的前一道步骤，C（Aij）为其最早结束时间，p（Aij）为其处理时间。Bij为步骤Oij中用到的所有处理机集合，m为Bij中的任一处理机，C（m）为其最早结束时间，p（m）为其处理时间。则必有
因此，步骤Oij的最早结束时间Cij只与C（Aij）和C（m），m∈Bij有关，即HPSO算法的粒子解码问题同时满足最优性条件和无后效性条件，可以用动态规划法求解。
4.2 算法改进步骤
根据动态规划法，对解码策略的具体改进为：直接找待加工步骤所依赖的前序步骤中结束时间中最晚的一个，作为待加工步骤的开始加工时间。实施步骤如下：
输入：粒子向量
输出：粒子的最大完工时间
改进后的解码算法如图2所示。
4.3 实验结果
为验证改进后算法的性能，使用Java 8语言实现了原算法和改进的算法，并进行性能测试。硬件环境为：
CPU 2.50GHz、内存4.00GB;软件环境为：Windows 10操作系统，Java 8。
生成一批规模不同的HJSMT算例：
（1）任务数量n=5。
（2）步骤数量q=5。
（3）每个步骤占用的处理机数量|mij|～[1，5]。
（4）步骤的加工时间pij～[1，99]。
（5）种群数量PopSize=40。
两种算法程序运行时间如表2所示。
从表2中可见，改进的解码策略在测试时速度有明显提升，当处理机数量为25、迭代次数为100时，速度提高为原来的111.4倍。这意味着新的算法可以在更短的时间内处理更复杂的问题，或者在相同的时间内用不同的初始种群进行更多次实验，以得到更优的结果。
5 结 论
本文从具有多处理机任务约束的混合作业车间调度HJSMT问题出发，在已提出的HPSO算法的基础上，利用动态规划法对解码策略进行改进。实验证明，改进的算法极大地提高了计算效率，能够在相同的时间内进行更多次随机计算，从而获得更优的结果。在未来的研究中，可以对资源调度问题涉及的其他算法进行研究，例如粒子的搜索、粒子最优解的选取等，进一步优化算法、提升效率，提升调度的效果，使其更具时效性。
主要参考文献
[1]黄金贵，陈松乔，陈建二.网络并行计算系统中基于多处理机任务的资源调度模型[J].计算机工程与应用，2003，39（29）：54-58.
[2]黄金贵.任意处理时间的多处理機任务调度近似算法[J].计算机工程与应用，2008（33）：7-9.
[3]都志辉，陈渝，刘鹏.网格计算[M].北京：清华大学出版社，2002.
[4]Drozdowski M.Scheduling Multiprocessor Tasks- An Overview[J].European Journal of Operational Research，1996， 94（2）：215-230.
[5]王蒙，樊坤，翟亚飞，等.网络并行计算中多处理机任务调度问题研究[J].计算机工程与应用，2017，53（10）：264-270.
