首页 > 专利信息

求解柔性作业车间调度问题的两段式狼算法

柔性作业车间调度问题由Bucker和Schlie提出[1]，相比于经典的作业车间调度问题，它的每一道工序可以在多台机器上加工，不同机器上的加工时间亦不相同，且已被证明是NP难问题[2]；其调度目标是以某个加工性能指标为目标函数确定各机器上各个工件工序的加工次序，通常以总流经时间、最迟完工时间、最小化最大完工时间等为目标函数。

赵博选等[3]提出对策略融合的Pareto人工蜂算法求解柔性作业车间调度问题；Azzouz等[4]用遗传算法求解柔性作业车间调度问题；Xu等[5]提出改进混合免疫算法求解柔性作业车间调度问题；姜天华[6]提出一种混合灰狼算法求解柔性作业车间问题；徐华等[7]提出混合遗传蝙蝠算法求解单目标柔性作业车间调度问题；石小秋等[8]提出了一种自适应变级遗传算法求解以最小化最大完工时间为目标的柔性作业车间调度问题；王春等[9]提出了一种多目标进化算法，以优化区间柔性作业车间调度问题；Nouiri等[10]提出分布粒子算法求解柔性作业车间调度问题；尽管各种元启发式算法在FJSP问题中已得到广泛的研究，但目前仍没有任何一种算法能够获得所有问题的最优解，因此学者们仍在不断积极探索，以获得更丰富且更有效的方法。

狼算法（Wolf Pack Algorithm，WPA）是近年来提出的一种模拟自然界中狼分工协作捕猎的体智能优化算法[11]。针对WPA的相关研究表明，该算法具有较强的全局搜索能力和计算鲁棒性。目前，WPA已在复杂连续优化函数问题上得到了研究与应用[11]。在离散问题方面，狼算法已在无人机航线规划问题[12]、多配送中心车辆路径[13]、TSP[14]、矩形件排样[15]等问题中获

求解柔性作业车间调度问题的两段式狼算法

谢锐强，张惠珍

上海理工大学管理学院，上海200093

摘要：针对以最小化最大完工时间为目标函数的柔性作业车间调度问题，建立其数学模型并提出了一种两段式狼算法加以求解。采用两段式（two-vector code）的编码方式，设计初始化种的方式，保证初始解的质量及多样性；通过对原始狼算法中游走行为、召唤行为、围攻行为的重新设计，解决了原始狼算法易陷入局部最优的问题；舍弃原始狼算法中的距离判定因子，来降低算法的复杂度。对车间两个实例进行仿真测试和算法比较，验证了所提算法求解该问题的有效性，为其解决柔性作业车间调度问题提供了一种更加有效的方法。

关键词：两段式狼算法；柔性作业车间调度；最大完工时间

文献标志码：A中图分类号：TP301.6doi：10.3778/j.issn.1002-8331.2001-0160

Two-Vector Wolf Pack Algorithm for Flexible Job Shop Scheduling Problem

XIE Ruiqiang,ZHANG Huizhen

Business School,University of Shanghai for Science and Technology,Shanghai200093,China

Abstract：Aiming at the flexible job shop scheduling problem with the objective function of minimizing the maximum completion time,a two-stage wolf swarm algorithm is proposed.In order to ensure the quality of the initial solution,the two-vector code coding method is used to design the initialization population.By redesigning the walk behavior,call

behavior and siege behavior in the original wolf swarm algorithm,the problem that the original wolf swarm algorithm is easy to fall into local optimum is solved.Then the distance decision factor in the original wolf swarm algorithm is aban-doned to reduce the complexity of the algorithm.Finally,the simulation test and algorithm comparison of two examples in the workshop show the effectiveness of the proposed algorithm to solve the problem,and provide a more effective method for solving the flexible job shop scheduling problem.

Key words：two-vector wolf pack algorithm;flexible job shop scheduling;makespan

基金项目：国家自然科学基金（71401106）；教育部人文社会科学基金（16YJA630037）。

作者简介：谢锐强（1995—），男，硕士研究生，主要研究方向为生产调度、智能优化；张惠珍（1979—），通信作者，女，副教授，硕士生导师，主要研究方向为运筹学、智能优化，E-mail：。

收稿日期：2020-01-09修回日期：2020-04-29文章编号：1002-8331（2021）07-0251-06

得运用并取得了相对不错的效果。

本文针对柔性作业车间调度问题解空间巨大及现有求解方法在寻优精度上的不足，提出了一种两段式狼算法（Two-vector Wolf Pack Algorithm，TWPA），该算法重新设计了狼的游走机制、召唤机制、围攻机制及狼更新机制，在优化过程中，提高了算法的优化性能并通过求解实际算例检验了算法的有效性。文章首先对柔性作业车间调度问题进行详细描述并建立数学模型；其次着重阐述了两段式狼算法求解FJSP问题时的编码方式以及算法具体的智能行为机制；最后，实验仿真部分通过求解两个具体算例验证了算法的有效性。

1问题描述

柔性作业车间与经典作业车间的区别就是工序可在多台机器上加工。柔性作业车间调度问题描述为：n个不同工件，在m台机器上进行加工。每个工件有各自的固定加工工艺路线，每个工艺有不同的可供

选择的加工机器子集。不同的加工工序所选择的机器具有差异性，相同工序加工机器选择的不同，对应加工时间也会有差异。调度的目标是为每个工件的工序合理地分配加工机器，并合理的安排各个机器上分配的工序加工顺序，从而使最大完工时间最小。

对于柔性作业车间调度问题，工件在加工过程中满足如下约束：

（1）同一时刻一台机器只能加工一道工序，某道工序在同一时刻只能在同一台机器上加工（资源约束）。

（2）工件的某道工序一旦开始加工便不能随意中断，直到该工序加工完成。

（3）所有工件具有相同的优先加工级，它们被加工的概率相同。

（4）不同工件的各工序之间没有加工顺序约束，同一工件的各工序之间有预先确定的加工顺序约束（顺序约束）。

（5）所有工件在零时刻都可以被加工。

（6）不考虑机器加工中断。

表1给出了3个工件、5个机器（3×5）的FJSP调度例子，表中的数据表示工序在对应的机器上的加工时间，其中“—”表示工件不能在该机器上加工。

采用最大完工时间作为优化目标，建立数学模型。

F m=min i(max l(F il))（1）

F il-F i(l-1)-P ilk×X ilk≥0（2）

∑

k∈S il

X ilk=1∧F il-B ilk=P ilk∀i,l（3）

F i'l'k≤B ilk∨P ilk≤B i'l'k∀i',l'≠i,l（4）

X ilk∈{0,1}（5）其中，目标函数F m表示所有工件中的最大完工时间最小，F il表示O il的完工时间；式（2）为工艺约束，F i(l-1)表示O il前一道工序的完工时间，P ilk表示O il在M k上的加工时间，X ilk=1表示O il在M k上加工，X ilk=0表示O il不在M k上加工；式（3）表示一道工序只能在一台机器上

加工且不能中断，B ilk和F ilk分别表示工序O il 在机器M k上的加工开始时间、加工完成时间，"∧"表示逻辑与，“∀”表示任意。式（4）表示同一时刻同一机器只能加工一道工序，B i'l'k、F i'l'k分别表示O i'l'在M k 上的开始完工时间，“∨”表示逻辑或；式（5）表示变量约束。

2狼算法（WPA）

狼算法是一种基于狼捕食行为而提出的体智能优化算法。它与蜂算法有着异曲同工之处，将整个狼分为头狼、探狼、猛狼3种角[11]，通过模拟狼的整个捕猎过程，WPA从中抽象出探狼游走、头狼召唤、猛狼围攻3种智能行为以及“胜者为王”头狼产生规则和“强者生存”的狼更新机制。

WPA的算法流程如下：

步骤1初始化狼中人工狼位置，将最优目标函数值的人工狼设为头狼。

步骤2探狼游走。探狼执行游走行为，直至某探狼侦察到的猎物气味浓度值大于头狼所感知的猎物气味浓度值或达到最大游走次数，更新头狼并发起召唤行为。

步骤3猛狼向猎物奔袭，若途中猛狼感知的猎物气味浓度大于头狼，则人工猛狼继续奔袭直到进入围攻范围。

步骤4当靠近猎物时，猛狼联合探狼捕获猎物（视头狼位置为猎物位置），执行围攻行为。

步骤5若围攻之后发现有优于头狼目标函数值的人工狼，则更新头狼，并将解空间中目标函数值最差的人工狼进行淘汰，随机生成新的人工狼，实现种的更新。

步骤6判断是否达到最大迭代次数，若达到则输出头狼的位置，即所求问题的最优解；否则转步骤2。

3求解FJSP的两段式狼算法

针对FJSP采用基于机器和工序的两段式编码方式

表13×5调度实例

J1 J2 J3O11

O12

O13

O21

O22

O31

O32

O33

—

来表征狼中的人工狼位置X i 。应用其设计的初始化种方式初始化种，对狼的智能行为进行重新设计；则基于两段式狼算法的柔性作业车间调度问题的具体操作如下所示。

3.1一些定义

设在N ×2∑i =1k

n i m j 的解空间中，N 为狼规模，

电子蚊香

2∑i =1

n i m j 为所有工件的总工序数之和，n 表示工件数

量，人工狼i 的位置定义为X i ={x i 1,x i 2,…,x in }人工狼i 所嗅到的猎物气味浓度为Y i =f (X i )；当待加工的工件总数为n ，工件n i 的加工工序工为m j 时，则个体表示为长度为2∑i =1k

n i m j 的整数串。

X i 对应柔性作业车间调度问题中的一种可行工件

工序排序编码，Y i 对应于该排序的最大完工时间，其中x ij 为第i 条可行工件排序编码的第j 个编码位置的工

件；另有X ip ≠X iq ，p ≠q 且p,q,j ∈{1,2,…,n }。

3.2编码方式

在TWPA 中，狼个体编码采用工序编码和机器编

码两段式的编码方式，其中两段的长度相等，分别对应工序分配方案和机器排序方案。当待加工的工件总数为n ，工件n i 的加工工序为m j 时，则个体表示为长度为2∑i =1k

n i m j 的整数串。下面按照表1中给出的实例数据进

行说明。

工序编码：编码长度为总工序数，基因位上的数表示工件号，若工件序号为2的工件有2道工序，那么数字2在编码中恰好出现2次，如表1实例的其中一个工序编码为[1，2，1，2，1，3，3，3]，基因位置

3上的数字1表示此时加工O12。机器编码：编码长度为总工序数，基因位上的数字表示前半段对应工序可以选择的机器集合中的第几台机器，如表1实例的一个机器编码为[2，3，4，4，2，3，4，1]，基因位3的数4表示O12选择第4台可以选择的机器，即M5，而非M4。整个数串[1，2，1，2，1，3，3，3，2，3，4，4，2，3，4，1]为一个个体。

3.3种初始化

智能算法中，多样性好的初始解可以覆盖更大的

解空间，使得搜索范围广，可以更大概率到全局最优解。同样，初始解的质量影响着整个算法的收敛速度。因此，两者显得都很重要，为了保证种的质量和多样性，采用如下两种方式初始化种。

（1）随机生成法：随机生成每道工序，按照每道工序可以选择的加工机器，任意选择一台机器。

（2）最小时间选择法：按照工序在可选机器上的加工时间选择加工时间最短的机器。当在不同机器上的

加工时间相同时，则随机选择其中一台机器进行加工。

在初始化种时，根据方法（1）生成的初始解能够很好的保证初始解的多样性，而采用方法（2）生成的初始解具有较高的质量，因此50%的初始解采用方法（1）生成，另外50%采用（2）生成。

3.4适应度函数

本文求解柔性作业车间调度时以最小化最大完工

时间为目标函数，主要思想是机器加工本工序的开始时间大于前面一道工序的完成时间时，则取机器本工序的开始时间。最大完工时间愈小，表示个体适应度值越好，即fitness =min{C max (P )}。

3.5智能行为设计

本文求解柔性作业车间调度是以适应度函数最小

化为目标函数来确定工序排序以及机器选择方案。结合柔性作业车间的具体特征，可将狼算法中的智能行为：头狼选择、探狼游走、头狼召唤、猛狼围攻和狼更新机制定义如下：

（1）头狼选择机制。根据数学模型中目标函数计算各人工狼的适应度函数，记录第i 匹人工狼的适应度函数为Y i 。则头狼Y leader =min(Y i ),i =1,2,…,n ，若同时存在多匹人工狼的适应度值相等且最小，则在其中随机选取一匹充当头狼）。记与头狼相对应的解和适应度值分别X leader 和Y leader 。

（2）探狼游走。将解空间中除头狼之外的所有人工狼视为探狼。记探狼i 向第l (l =1,2,…,h )个方向游走前后的适应度函数值分别为Y i 和Y il ，当Y il <Y i 时，将其探狼位置更新为游走行为后的新位置；

当Y il >Y i 时，探狼的位置不发生变化。重复以上的游走行为，直到Y i <Y leader 或者游走次数T 达到最大游走次数T max 结

束游走。

探狼i 向第l (l =1,2,…,h )个方向的游走行为定义为：对与其相对应的个体编码序列的前半段工序编码保持不变，对后半段机器编码用赌算法进行重新选择。将上述游走操作执行h 次。如图1所示，在X i 中[1，2，1，2，1，3，3，3，2，3，4，4，2，3，2，3]，对该探狼工序编码段不进行任何操作，对其机器编码段进行上述方法在可选机器集里重新选择，直至得到向某个方向游走一次后探狼i 的编码为[1，2，1，2，1，3，3，3，1，2，1，3，1，3，2，1]。

图1游走机制

（3）召唤机制。将除头狼外所有人工狼视为猛狼，头狼通过嚎叫发起召唤行为，召集周围的猛狼向猎物的方向走动。将其召唤行为定义为：首先，针对人工狼个体编码的前半段工序编码段进行交叉操作，用交叉后的人工狼个体中多余的工序基因替换缺失的工序基因；然后，根据交叉前人工狼个体后半段机器编码调整交叉操作后的加工机器。具体地：如图2所示，选取头狼位置编码序列X leader中位置6的前面片段与猛狼位置X i编

码序列中的相同片段进行交叉操作，得到猛狼X i编码为[3，1，1，2，1，3，3，3，2，3，4，4，2，3，2，3]，至此，用猛狼个体X i的工序基因与头狼工序基因进行一一比对，则发现工件3的工序多余，工件2的工序缺失，因此用猛狼个体位置8上多余的工序3替换缺失的工序2，得到猛狼个体X i为[3，1，1，2，1，3，3，3，3，2，3，4，2，3，2，3]，最后，根据头狼个体中X leader的对应的操作机器来调整交叉后猛狼所对应的操作机器，得到猛狼个体X i为[3，1，1，2，1，2，3，3，3，3，4，2，3，2，2，3]。

该召唤操作保留了头狼的部分优秀基因，使得在整个寻优过程向最优解的方向移动。

若猛狼i的适应度函数值Y i<Y leader，则Y i=Y leader，该猛狼转化为头狼并发起召唤行为；否则，该猛狼结束奔袭，即等待转入围攻行为。

（4）围攻机制。将除头狼外所有人工狼视为猛狼，经过奔袭后，头狼已离猎物较近，因此可将头狼的位置X leader视为猎物所在的位置（最优解）。围攻行为定义为：猛狼编码序列X i保留与头狼位置编码序列X leader 相同的位置的相同工件片段，对不同的工序编码进行随机排序，最后，根据头狼个体中X leader的对应的操作机器来调整交叉后猛狼所对应的操作机器，得到猛狼个体X i为[3，2，1，2，1，1，3，3，3，2，3，2，4，3，4，1]。

举例如图3所示。

若存在Y i<Y leader，则用人工狼i替换头狼并结束围攻行为。围攻机制中前者的对比保留与头狼相同排列位置的工件操作体现了狼的信息传递与优秀个体（头狼）的经验共享机制；后者的随机排序操作可理解为围攻时人工狼之间在小范围内调整以达到最佳攻击位置，体现了算法在优秀解域附近对最优解的精细搜索，同时这种带有随机性的位置调整也有利于减小算法陷入局部极值的概率。

（5）狼“优胜劣汰”更新机制。狼中依据“优胜劣汰”的规则使得更有竞争力的狼得以生存，较弱的狼被淘汰。求解FJSP时，在解空间中按照初始化种的方式生成R匹人工狼，使得狼的规模扩大为R+N，此时对所有人工狼依次计算出适应度函数值，选出适应度值最大的R匹人工狼予以剔除，使狼的规模大小不发生变化，进而实现对整个狼实时更新。

3.6算法步骤

根据上述头狼选择机制、探狼游走机制、头狼召唤机制、猛狼围攻机制和狼更新机制，可将求解FJSP问题的狼算法描述为如下求解步骤：

步骤1初始化算法参数，设定狼规模大小N，最大迭代次数max_iters，最大游走次数T max，游走搜索方向h。

步骤2初始化各人工狼的位置，计算各人工狼对应的目标函数值Y i。

步骤3根据头狼选择机制选择头狼并记录其位置X s与对应的适应度函数值Y leader。

步骤4依据探狼游走机制执行游走行为，直到探狼i游走之后Y i<Y leader或者游走次数T达到最大游走次数T max。

步骤5按照召唤机制执行召唤行为，若Y i<Y leader，则Y leader=Y i，猛狼i替代头狼并重新发起召唤行为。

步骤6猛狼执行围攻过程，按照围攻机制位置更新规则进行位置更新，同时进行头狼的更新并进入下一次迭代iters=iters+1。

步骤7判断是否算法到达最大迭代次数max_iters，若达到，则输出头狼的位置（当前最优解），算法结束，输出最优解；否则转到步骤4。

3.7计算复杂度分析

设算法中狼个体为N，算例中总工序为W，探狼朝某个方向游走一次的复杂度为O(n2)，DWPA中N-1个探狼采用游走机制朝h个方向游走，因此总计算复杂度为O((N-1)×W×h×T max)。

根据召唤行为，每头探狼与头狼交叉编码片段更新

图2

召唤机制

图3围攻机制

自身位置，总计算复杂度为O((N-1)×n2)。

根据围攻行为，每头猛狼与头狼交叉编码片段更新自身位置，总计算复杂度为O((N-1)×n2)。

综合算法游走行为、召唤行为、围攻行为3种搜索操作的计算复杂度可见，TWPA在求解FJSP时复杂度并不算高。

4实验仿真及分析

为了测试本文算法TWPA的有效性，采用柔性作业车间调度问题的两个实际算例进行数值实验。实验仿真环境为操作系统Windows10、处理器Inter®Core™*****************GHz，内存4.0GB，编程语言Matlab

R2016a。

4.1参数设置

6×6实例中，文献[7]设置参数为：初始种规模pop_size=100，总迭代次数t max=250，邻域搜索总迭代次数ct max=10，频率的最大最小值分别为f max=2，

f min=0，权重的最大最小值分别为w max=0.9，w min=

0.42；TWPA设置相同参数值初始种规模为N=100，最大迭代次数max_iters=250；6×8实例中，文献[17]设置参数为粒子数60，最大迭代次数5000，学习因子c1=c2=1.5；TWPA设置相同参数值初始种规模为N=60，最大迭代次数max_iters=5000；最大游走次数T max=15，游走方向h=10，更新种个数R=20。

4.2数值实验与算法比较

实例1是6×6实例，实验数据如表2所示，来源于文献[16]，利用本文的两段式狼算法求解该实例可得到的全局最优解为10，该全局最优解对应的调度甘特图如图4所示。

实例2是6×8实例，实验数据来源于文献[17]，见表3，利用本文的两段式狼算法求解该实例可得到的全局最优解为55，该全局最优解对应的调度甘特图如图5所示。

为了验证TWPA求解柔性作业车间调度问题的性能，将上面两个实例算法运行10次的实验结果如表4所示。表4中，为了与其他文献在相同指标下比较算法性能，且能直接引用其他文献的数据，故也使用了平均值和最优值，其中AVG（Average）表示算法执行n=10次后得到结果的平均值。

AVG=1n∑

i=1

C i（6）

工件1

6工序

O11

O12

O21

O22

O23

O31

O32

O41

O42

O43

O51

O52

O61

O62

O63

—

铜编织线4

—

软母排

表26个工件在6台机器上加工的FJSP实例

图46×6最优解甘特图

601

12345678910 0

402602

403

102

203

202

401

201

101

501

301302502603

表36个工件在8台机器上加工的FJSP实例

工件

工序

O11

O12

O13

O14

O15

O21

O22

O23

O31

O32

O33

O34

O35数字振镜

O41

O42

O43

O44

O51

O52

O53

O61

O62

O63

O64

O65

O66

—

17折角塞门

—

蜗轮副—

—

本文发布于:2024-09-22 12:28:17，感谢您对本站的认可！

本文链接：https://www.17tex.com/tex/2/327399.html

上一篇：浅谈智能变电站技术及其对继电保护的影响

下一篇：我要猜谜语合小冰猜谜语

标签：算法狼群工序机器加工问题作业

留言与评论（共有 0 条评论）