混合粒子群算法求解作业车间调度问题

刘凤杰，薛仁政

混合粒子群算法求解作业车间调度问题

刘凤杰，薛仁政

（齐齐哈尔大学 计算机与控制工程学院，黑龙江 齐齐哈尔 161006）

针对最小化完工时间的作业车间调度问题，提出混合的粒子群优化算法. 针对作业车间调度中随机交换2个工件邻域变换存在盲目性，采用机器空闲时间的关键工序邻域搜索算法，结合粒子群算法收敛速度快和遗传算法变异操作增加全局搜索能力的优点，将2种算法结合. 通过标准JSP问题测试库验证了算法的有效性．

粒子群算法；车间调度；关键路径；邻域搜索

智能优化算法被广泛应用于作业车间调度问题．薛玲玲[1]采用基于工序的编码方法，在编码后的个体上进行邻域构建的基于块结构邻域搜索的遗传算法，求解作业车间调度最小化最大完工时间．刘丽娜[2]等针对求解后期易陷入局部最优，利用量子计算、正余弦搜索和警戒者数量递减策略对麻雀搜索算法进行改进，优化作业车间调度问题．王玉芳[3]等提出加入自适应调整的遗传操作以及精英替换策略的改进混合遗传模拟退火算法，应用于作业车间调度问题求解．何斌[4]等提出动态交叉与变异概率的一种改进的遗传算法优化作业车间调度的最小化最大完工时间．Nouiri[5]等以最小化最大完工时间为目标，提出了一种混合离散粒子群优化算法，用于求解具有资源柔性的双资源约束作业车间调度问题．Amin[6]等研究了基于周期事件调度问题的周期作业车间调度问题，提出了一种基于粒子群优化和模拟退火算法的混合算法．吕媛媛[7]等提出一种新的改进多目标粒子群算法优化最小化最大完工时间和最小化总拖延时间．

本文结合JSP的特点，提出结合遗传算法改进的粒子群算法．该算法自适应惯性权重和学习因子，提高了搜索能力．基于工序的编码方式，采用混沌动力学模型初始化粒子，使粒子均匀分布解空间，引入关键路径邻域搜索，克服随机交换工序的盲目性．此算法在JSP基准算例上进行测试，验证了算法的有效性．

1 作业车间调度模型

JSP模型被定义为

适应值是评价一个粒子所处位置优劣程度的函数，适应值越高，粒子所在位置越优秀，适应度值越低，粒子所处位置越差，粒子的适应度值评价公式为

2 混合粒子群求解JSP

2.1 改进粒子群优化算法

2.1.1 标准粒子群算法 粒子群算法（Particle Swarm Optimization，PSO）是通过研究鸟类群体觅食活动提出的一种群智能优化算法．由于该算法形式简单，参数少，收敛速度快等优点，因此获得了国内外学者的广泛关注．

2.1.2 自适应惯性权重和学习因子 在粒子群算法中，既要考虑全局搜索能力，又要考虑局部搜索能力，全局搜索能力能够增加搜索范围，局部搜索能力能够搜索最优值．当粒子靠近最优值时增加局部搜索能力，否则增加全局搜索能力，基于此方案提出自适应惯性权重计算方法，自适应惯性权重进行更新

本文改进粒子群算法的速度和位置公式为

2.2 改进遗传算法

遗传算法（Genetic Algorithm，GA）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，有较强的局部和全局搜索能力，在很多领域得到应用．遗传算法通过建立初始种群，计算适应度，按照一定方法进行选择、交叉和变异操作进行搜索最优解．选择、交叉、变异操作是遗传算法的关键性操作.

在遗传算法中，交叉操作提高收敛速度，但其在局部寻求最优解；变异操作收敛速度慢，但能够增加全局寻求最优解．结合交叉和变异操作的优势，在初期增加全局寻优能力，在算法后期增加局部寻优能力，提出一种自适应交叉、变异的遗传算法．

2.2.1 交叉操作 交叉操作是对种群中染色体进行随机配对，对种群中选中的染色体以一定的概率交换种群的基因片段，产生新的染色体．交叉的方式包括：单点交叉、多点交叉、均匀交叉．交叉操作增加了局部搜索能力，本文的交叉操作每次交叉随机选用3种交叉方式中的一种，对染色体的工件进行交叉操作．

2.2.2 变异操作 变异操作是模拟自然界生物变异的过程，采用文献[8]自适应变异概率改变染色体的基因片段来改变基因，增加种群的多样性．变异操作采用两点交换、基因段逆序、随机插入工序、打乱互换4种操作．

2.2.3 选择操作 选择操作是将父代个体的信息传递给子代的过程，在选择操作过程中希望将适应度高的父代以较高的概率进行传递．通过选择操作，使后代个体中优秀的个体数量增加，有利于后代整体向更好的方向进化．根据适应度决定父代个体被选择的概率为

2.3 编码与解码

在作业车间调度问题中由于基于工序的编码方式简单、直观，所以本文采用基于工序的编码方式．基于工序的编码方式，采用随机初始种群会产生较多劣解和重复解，影响了算法的搜索能力．本文采用混沌动力学模型logistic[9]77生成初始种群，生成初始种群的公式为

在确定工序的加工顺序后，通过从左到右的顺序对工序编码安排加工，工件号第１次出现，表示该工件第１道工序被加工，工件号第２次出现，表示该工件第２道工序被加工进行解码．

2.4 关键路径邻域搜索

在作业车间调度中，由于工件加工受加工工序的限制，导致最大完工时间增加的原因是由机器空闲时间造成的．在一个可行调度中，工序之间无时间间隔的最长路径称为关键路径，关键路径上的工序为关键工序．车间调度中最大完工时间取决于关键路径的长度，关键路径由关键工序组成，调整关键工序的加工顺序将影响最大完工时间．通过搜索机器空闲时间，调整关键工件加工顺序，减少机器空闲时间，能够减小最大完工时间．

2.5 混合粒子群算法

本文采用混沌动力学模型初始化粒子，将改进的粒子群算法与遗传算法相结合，引入关键路径邻域搜索，求解作业车间调度最小化最大完工时间．该算法流程见图1．

3 实验结果与分析

本文采用JSP标准问题测试库中选取FT类：FT06，FT10，FT20，LA类：LA01，LA06，LA11，LA16共7个算例进行求解，每个算例求解20次．

实验环境为：操作系统为Windows10，编程语言为Python3.6，CPU为Intel（R）Core（TM）i7-11800H 2.30 GHz，内存为32 G，最大迭代次数为200，种群数量为200，程序独立运行20次，与标准粒子群算法和IPSO算法[9]80及文献[10]的F&F算法进行比较，结果见表1．

图1 混合粒子群算法流程

表1 算法测试结果对比

由表1可知，本文提出的混合粒子群算法共找到6个算例的最优解，且结果稳定，20次求解均可找到最优解；对于未找到最优解的FT20问题，其20次求解的最优解相比其他算法也表现良好．因此，本文所提出的算法具有良好的性能．

4 结语

本文结合粒子群算法收敛速度快和遗传算法变异操作增加全局搜索能力的优点，将2种算法结合，设计了混合粒子群优化算法．为了使初始化粒子均匀分布解空间，采用混沌动力学模型生成初始种群，采用机器空闲时间的关键工序邻域搜索算法解决了随机交换工件存在的盲目性的缺点．通过标准JSP问题测试库验证了算法的有效性，优化了作业车间调度最小化最大完工时间．未来将探索其改进算法解决FJSP．

[1] 薛玲玲．作业车间调度的块结构邻域搜索遗传算法[J]．计算机集成制造系统，2021，27（10）：2848-2857．

[2] 刘丽娜，南新元，石跃飞．改进麻雀搜索算法求解作业车间调度问题[J]．计算机应用研究，2021，38（12）： 3634-3639．

[3] 王玉芳，缪昇，马铭阳，等．改进混合遗传算法的作业车间调度研究[J]．现代制造工程，2021（5）：32-38．

[4] 何斌，张接信，张富强．一种求解作业车间调度问题的改进遗传算法[J]．制造业自动化，2018，40（8）：113-117．

[5] Nouiri M，Bekrar A，Jemai A，et al．An effective and distributed particle swarm optimization algorithm for flexible job-shop scheduling problem[J]．Journal of Intelligent Manufacturing，2018，9（3）：603-615．

[6] Amin J，Shafia M A，Moghaddam R T．A hybrid algorithm based on particle swarm optimization and simulated annealing for a periodic job shop scheduling problem[J]．The International Journal of Advanced Manufacturing Technology，2011，54（1）：309-322．

[7] 吕媛媛，樊坤，瞿华，等．多目标粒子群算法求解混合多处理机任务作业车间调度问题研究[J]．小型微型计算机系统， 2022，43（1）：218-224．

[8] Rinivas M，Patnaik L M．Adaptive probabilities of crossover and mutation in genetic algorithm[J]．IEEE Transactions on Systems， Man，and Cybernetics，1994，24（4）：656-667．

[9] 刘洪铭，曾鸿雁，周伟．基于改进粒子群算法作业车间调度问题的优化[J]．山东大学学报（工学版），2019，49（1）： 75-82．

[10] REDO C，DUARTE R．A filter-and-fan approach to the job shop scheduling problem[J]．European Journal of Operational Research，2009，194（3）：660-662．

Hybrid particle swarm optimization for solving job-shop scheduling problem

LIU Fengjie，XUE Renzheng

（School of Computer and Control Engineering，Qiqihar University，Qiqihar 161006，China）

Aiming at the job-shop scheduling problem of minimizing completion time，a hybrid particle swarm optimization algorithm is proposed．Aiming at the blindness of neighborhood transformation of randomly exchanging two workpieces in job-shop scheduling，the key process neighborhood search algorithm of machine idle time is adopted．Combined with the advantages of fast convergence speed of particle swarm optimization algorithm and mutation operation of genetic algorithm to increase the global search ability，the two algorithms are combined．The effectiveness of the algorithm is verified by the standard JSP problem test library．

particle swarm optimization algorithm；job-shop scheduling；critical path；neighbor search

TP399

A

10.3969/j.issn.1007-9831.2022.06.007

1007-9831（2022）06-0038-06

2022-03-20

黑龙江省省属高等学校基本科研业务费科研项目（135409224）

刘凤杰（1978-），女，黑龙江克山人，助理实验师，从事计算机应用研究．E-mail：liufengjie@126.com