2024年3月15日发(作者：英正平)
110
传感器与微系统
(Transducer
and
Microsyslem
Technologies)
2021
年第
40
卷第
6
期
DOI
：
10.
13873/J.
1000-9787(2021)06-0110-04
］
计算与测试
［
求解模糊作业车间调度问题的混沌乌鸦搜索算法
*
*
刘凯
-
黄辉先
-
赵骥
V
(1
.湘潭大学信息工程学院
，
湖南湘潭
411105
；
2.
清华大学清华大学国家
CIMS
工程技术研究中心
，
北京
100084)
摘要
：
为求解模糊作业车间调度问题
(FJSSP),
提出了一种改进的混沌乌鸦搜索算法
(
CCSA)
。
算法采
用基于工序的编码,并设计了一种修补方式以使
CCSA
有效求解町
SSP
；
为增强算法的邻域搜索能力引入
了变异算子;为提高算法的进化能力
，
提出了基于余弦相似度的多样最优个体集来引导进化
，
使在增强进
化效率的同吋保证种群多样性;为进一步提高算法在求解
FJSSP
时的搜索效率
，
提出了一种基于机器空闲
缩小的搜索方法
。
最后选取了
5
个典型实例进行了测试
，
实验结果验证了所提算法的有效性
。
关键词
：
模糊作业车间调度问题
；
混沌乌鸦搜索算法
；相似性度量；
局部最优
中图分类号
：
TP18
文献标识码
：
A
文章编号
：
1000~9787(
2021
)064)1104)4
Chaotic
crow
search
algorithm
for
fuzzy
job-shop
scheduling
LIU
Kai
1
,
HUANG
Huixian
1
,
ZHAO
Ji
1
'
2
(1
・
College
of
Information
Engineering
,
Xiangtan
University
,
Xiangtan
411105,
China
；
2
・
Tsinghua
University
,
National
Computer
Integrated
Manufacturing
Systems
Engineering
Research
Center
of
Tsinghua
University
,
Beijing
100084,
China)
Abstract
:
An
improved
chaotic
crow
search
algorithm
(
CCSA
)
is
proposed
for
solving
the
fuzzy
job-shop
scheduling
problem
(
FJSSP)
.
The
algorithm
adopts
the
process-based
coding
method
,
and
a
solution-correct
way
is
designed
to
make
CCSA
solve
FJSSP
effective!y
・
In
order
to
enhance
the
neighborhood
search
ability
of
the
algorithm,the
mutation
operator
is
introduced
・
In
order
to
improve
lhe
evolutionary
ability
of
the
algorithm,multiple
optimal
individual
set
based
on
the
Cosine
Similarity
is
proposed
to
guide
the
evolution,
which
not
only
enhanced
lhe
evolutionary
efficiency
but
also
ensures
the
diversity
of
lhe
population
・
In
order
to
further
improve
the
search
efficiency
of
CCSA
when
solving
FJSSP,
a
search
method
based
on
the
reduction
of
machine's
spare
time
is
proposed.
Finally
,
five
benchmark
problems
are
selected
for
testing,and
lhe
results
verify
the
effectiveness
of
lhe
proposed
algorithm.
Keywords
:
fuzzy
job-shop
scheduling
problem
(
FJSSP
)
；
chaotic
crow
search
algorithm
(
CCSA
)
；
similarity
measurement
;
local
optimum
0
引言
作业车间调度问题
(
JSSP)
是一个典型的
NP-hard
问
期的
FJSSP,Niu
Q
等人⑷通过将
GA
中的交叉和变异算子
结合到粒子群优化
(
PSO)
算法中对
PSO
进行改进并应用于
FJSSP
中
，
最后和
GA
进行比较验证了算法的优越性
。
Hu
Y
等人⑸用改进的差分进化算法
(
DE)
对
FJSSP
进行了求
题⑴
，
在过去的五十几年里,一直受到许多学者的关注与
研究，
其研究成果被广泛应用于生产
，
工程管理，
计算机等
领域
，
因此研究
JSSP
具有重要的学术和实际意义
。
而作为
JSSP
的扩充
，
模糊作业车间调度问题
(
fuzzy
job-shop
sche
duling
problem,FJSSP)
在
JSSP
的基础上加入不确定性条件
解
。
Bustos-Tellez
C
A
等人⑹利用线性规划
(
LP)
的方法对
FJSSP
建立了模糊
LP
模型。
然而
，
相比
JSSP,
对于
FJSSP
的研究还远远不够
,
并且多元启发式方法容易陷入局部最
优解
,
而
LP
方法又在求解大规模问题上太过复杂
,
难以计
算
，
所以仍须研究人员能够提出更多更好的解决方法来解
如模糊加工时间
，
使得问题更接近真实的生产情况
，
更具研
究价值
。
Tsujimura
Y
等人刘最先用遗传算法
(
genetic
alo-
rithm,GA)
解决带模糊加工时间的
FJSSP,Sakawa
M
等人⑶
决问题
。
乌鸦搜索算法
(
crow
search
algorithm
,
CSA
)
是
Askarza-
将
GA
进行了改进并应用于具有模糊加工时间和模糊交货
收稿日期
=2019-10-13
*
基金项目
：
东莞市引进创新科技团队计划资助项目(
2)
第
6
期
刘凯
，
等:求解模糊作业车间调度问题的混沌乌鸦搜索算法
111
deh
A®
提出的新群体智能算法
。
Sayed
G
I
等人⑻对该算
法引入了混沌机制
，
即混沌乌鸦搜索算法
(chaotic
crow
search
algorithm
,
CCSA
)
并成功应用于二进制特征选择问
题
，
最终对比发现该算法具有优秀的全局优化能力和求解
速度
。
刘雪静等人⑼将
CCSA
应用于
0-1
背包问题上同样
得出其具有良好的全局寻优能力和收敛速度
，
这些应用都
表现出
CCSA
值得在更多不同领域被研究
，
因此
，
本文提出
将
CCSA
应用于求解带模糊加工时间的
FJSSP
上
，
并且通过
对问题和算法的研究将算法做了改进
,
最后进行了对比仿
真实验
，
验证了本文所提出的改进策略的有效性以及所提
算法能够有效求解
FJSSP
。
1
FJSSP
町
SSP
的描述和数学模型可参考文献
［
4
］
。
而目标函
数选用
minCmm
=max{
C
】
,C
2
,Cj
,•••
,C
n
j
,
即最小化最大
完成时间
，
其中
q
为工件
j
的模糊完成时间
。
町
SSP
中引入模糊三角数
(
triangular
fuzzy
number
,TFN)
表示问题中的模糊加工时间⑶
,TFN
运算比较参考文献
［
3
］
。
其中考虑到
FJSSP
的实际意义,本文提出如式
(
1)
所示的取
大运算方式
C
=
max
A
,B
=(
max
j
a,
,b
x
}
,
max
j
a
2
,b
2
}
,
max
j
a
3
,b
3
|
)
(1)
图
i
为两个
tfn
的取大操作图
CSA
是受到乌鸦群藏匿食物的行为启发而来的⑺
，
而
CCSA
在
CSA
的基础上引入了混沌序列
。假设乌鸦群的数
量为为乌鸦
i在第
I
次搜索之后的位置
，
此时它所找
到的最佳藏匿食物的位置称为乌鸦的记忆位置
，
记为
其中
,i=l,2,-,/V
；
«=l,2-,t
max
,«
max
表示最大搜索次数
。
算法主要步骤如下
：
步骤
1
初始化
。
初始化产
=/•
*
。
步骤
2
搜索新位置
。
群体中每只乌鸦会随机选择另
一只乌鸦作为目标进行位置搜索
。
假设在第/次迭代中
，
乌鸦
，
进行跟随的是乌鸦
z,
则这时会出现两种情况
：
1)
乌鸦
z
没有发现自己被乌鸦
i
跟随
乌鸦
：
将靠近乌鸦
z
的记忆位置
,
通过式
(
2)
更新
乌鸦
i
的位置
=yi.i
+Ci
x/Z
-/•
)
*
(2)
式中
刃为表示搜索步长;
c,
e
(0,1),
为混沌序列的第
i
个
值,该混沌序列由
Circle
Map
何来产生
，
其映射公式为
C
l+1
=mod(C,
+
,1),
c
=0.5,(/=0.2
(3)
2)
乌鸦
z
发现自己被乌鸦i
跟随了
此时乌鸦
i
无法靠近乌鸦
z
的记忆位置,只能随机找一
个新位置来更新自己的位置
。
根据上述两种情况的描述可将乌鸦
，
的位置更新公式
总结如下
y'
,+1
={
r/-
,+1
+G
x/Z
x(M
..
2
''
-/•
)
*
［
generate
a
random
position
,
otherwise
(4)
式中
AP'
•'为乌鸦
z
在第
t
次搜索时能够发现被乌鸦
i
跟随
的概率
。
步骤
3
更新记忆位置
。
群体中的乌鸦在每次搜索更
新完自己的位置之后
，
通过一个评价函数
F
”
判断是否替换
记忆位置
，
具体更新公式为
(
严
，
化(严心化(加)
A/'-
,+1
=
(5)
,
otherwise
步骤
4
重复步骤
(2)
~步骤
(3)
搜索血次
。
步骤
5
输出优化结果。
乌鸦群中最优的记忆位置即
为算法的最终优化结果
。
3
FJSSP
的
CCSA
基于针对町
SSP
特点设计岀可应用于求解
FJSSP
的
CCSA
O
算法的编码策略采用基于工序的编码⑵
。
3.1
修补与变异
由于
CCSA
的变量是连续的
，
要想求解
FJSSP
这类离散
问题便需设计一个修补算子对位置更新公式计算出的新解
进行修补操作
,使算法能够在正确的解空间中进行搜索
。
同时
，
由于
CCSA
单单依靠式
(
4)
进行搜索过于单一
，
无法
对目标个体的邻域充分搜索
。因此引入变异算子以概率
戸认血将新解进行变异
，
以此丰富个体的邻域搜索行为
。
变
异方式采用自身交换策略
：
随机选择解中的两个编码不同
的位置进行交换
。
具体算法描述如下
：
算法
1
新解的修补与变异算法
输入:
CCSA
按式
(
4)
计算出的新解
，
人
“
2
输出
：
经过修补与变异之后的解
,y
mulate
o
1)
将儿讯向上取整得到歹罰
。
2)
分别统计人曲中范围在工件号内的各个编号出现的
次数
。
3)
将畑中小于
1
的数从小到大修正为工件号统计次
数小于工序数的最小工件号
，
同理将大于工件数的编号从
大到小修正为工件号统计次数小于工序数的最大工件号
，
得到人吆
2
4)
在人唤
“
中随机选择两个不同的工件编号进行交换
，
得到儿皿
。
112
传感器与微系统
第
40
卷
3.2
多样最优个体集
原始
CCSA
中引导更新的目标个体为随机选择
，
为提
高乌鸦的搜索效率并保证种群的多样性
，
本文提出基于相
似性度量的多样性最优选择策略来优化和丰富目标集
。
为了评估两个个体间的相似度
，
本文引入经常被用于
信息检索当中的基于余弦
(cosine)
定理E
的相似性度量方
式
。
用
X
和丫来表示两个个体,其中用笛表示
X
的第
，
个
分量了表示
y
的第
i
个分量
，
则
由于在
FJSSP
中
，
个体
X
和
y
中的每个元素都是正整
数
,
因此,任何两个个体之间的
COS
0
都在［
0,1
］
之间
，
数值
越接近
1,
则表示
X
和
y
的相似度越大
。
因此
，
基于余弦相
似度的多样最优个体集的选择算法如算法
2
。
算法
2
多样最优个体集选择算法
输入:第/代群体的记忆位置,最优的记忆位置个
数,
SP
；
多样的记忆位置个数
,
div
;
相似度阈值
，
乩
输出
：
多样最优个体目标集,
set
。
1)
随机生成一个目标集
set
。
2)
从
M
中选择评价值为前
sp
名的个体逐个对
set进
行随机替换
。
3)
从剩下的
M'
中按顺序选择一个与
M
1
中所有个体的
相似度平均值低于
R
的个体
，
然后随机替换
set
中除步
骤
(2)
选中之外的个体
。
4)
重复步骤
(3
次
，
直到
j
等于
div
或者
M'
遍历完成
。
5)
返回目标集
set
。
3.3
基于机器空闲时间缩小的搜索方法
由于
FJSSP
解空间极大且复杂
，使得
CCSA
群体的搜索
效率不高
、
收敛慢
。为了进一步提升算法的搜索效率
，
本文
提出一种基于机器空闲缩小的搜索方法以结合到
CCSA
中
。
在描述方法的具体步骤之前
，
先有如下定义
：
令
St”
和
Et
”
分别表示任务
w
的开始时间和结束时间
。
定义待优任务
、
待优工件
、
待优工序
。
假设吗和血为
机器队列中连续的两个任务
，
若有
Ei
wi
K2 , 则处称为待 优任务 ， 型所属工件称为待优工件用 2 所在工序称为待优 工序 。 该搜索方法是通过优先加工待优工序的前续工序所在 的任务 ， 使得待优任务的可开始加工时间提前来缩小机器 的空闲时间 。对于某个可行解 ， 随机选择一个机益 , 对该机 器的加工队列进行遍历(首个任务不进行调整) ， 判断每个 任务是否为待优任务， 若是则以一定的概率 P 制进行空闲时 间缩小 ， 缩小的算法如算法 3 。 算法 3 空闲时间缩小算法 输入:问题的一个可行解, S ； 机器号, m ； 待优任务号,仞 。 输出 ： 调整之后的新解 ,S newO 1) 寻找 w 所属工件和工序分别记为人和 p% 。 2) 判断人的工序卩％- 1 所在任务的可开始吋间是否 比当前开始时间小且不在自身机器队列的队首 ， 若是则该 任务为可提前任务 , 执行步骤 (3), 否则执行步骤( 6) 。 3) 将该可提前任务和所在队列中的前一个任务交换 ， 刷新调度方案 ， 若 w 之前的空闲时间为零 ， 则退出计算返回 新解 S “ ” ， 否则执行步骤 (4) 。 4) 若待缩小的空闲时间减少则执行步骤 ( 5), 否则放 弃此次交换并退出计算返回结果 s newO 5) 若 p% -1 〉 1, 则保留此次交换,然后以作为算 法 3 的输入递归执行 ， 否则保留交换,退出计算返回 S newO 6) 令 pn w =pn u . -1 , 若 pn u >1 则重新执行步骤 (2) 。 7) 返回结果 S 唤 。 为避免因为引入规律导致种群个体过于集中 ， 陷入局 部最优 ， 本文采用隔代搜索 ， 每间隔勺代从种群中选择 N x sr,(0 个体逐个进行 50 次基于贪婪策略问的搜 索 ，其中 N 为种群数量, sr 即选择比率 。 3.4 算法流程 根据上述设计 ， 改进后的算法总体流程如图 2 所示 。 图 2 算法总体流程图 4 实验与分析 为了验证算法对于 FJSSP 的有效性 ， 本文从文献 ［ 13 ］ 中选取了 Job Shop 调度中的 5 个典型的 Benchmark 并做模 糊化的处理 ， 模糊化的方式为 T = (t -rand,t,t +rarui') ， 其 中 m 加表示小于/的随机整数 ， 且当 t 越大时, m 加占/的 比重越小 。 同时为了方便比较 ， 结果比较都采用最大模糊 完成时间的中间数作为参考 。 实验环境:算法编程平台为 MATLAB R2016B, 操作系 统为 Windows7_64 位 ,CPU 为 Intel Core i7 -7500U@2. 70 GHZ, 内存为 8 GB 。 本文分别将原始的 CCSA, 加入变异算子和多样最优个 体集的 XD-CCSA ( X-diversity-chaotic crow search algorithm) , 第 6 期 刘凯 ， 等:求解模糊作业车间调度问题的混沌乌鸦搜索算法 113 本文所提算法 RST-CCSA ( reducing spare time — chaotic crow search algorithm ) 以及 GA 在 5 个实例上测试了各 10 次 。所 有测试中种群数量都设置为 N =200 ， 均进化 2 000 代 , 其余 参数 AP =0. 2 ,fl =2. 0, 变异概率 P raulale =0. 28, 目标集中最 优个体数 sp =5 , 低相似度个体数 div =20 , 相似度阈值 R = 0. 86, 基于机器空闲时间搜索方法的参数金 =50,sr =0. 4, =0.88 。 实验结果如表 1 所示 ， 表中给出了 10 次测试所得的最 优值 、 最差值 、 平均值以及所占 CPU 平均值时间 ， 表中各个实 例编号下面的加粗数据为 BKS 值 ， 即已知文献中的最优解 。 表 1 各算法的计算结果 算例算法 最优值最劣值 平均值 FT06 CCSA (42,55,75) (44,58,77) (43.6,57.1,76) 55XD-CCSA (42,55,76)(47,57,77) (43.4,55.8,76) RST-CCSA (42,55,75)(42,55,76) (42,55,75.4) GA (42,55,75) (42,55,76) (42,55,75.3) FT10 CCSA (1035,1098,1221) (1090,1156,1300) (1073.5,1138.6,1276.3) 930 XD-CCSA (944.994.1100) (979,1035,1154) (961.7,1021,1127.1) RST-CCSA (881,930,1034) (919,978,1097) (902.6,952.1,1075.6) GA (908,955,1092) (928,983,1124) (919.5,974.9,1104.1) FT20 CCSA (1181,1232,1340) (1243,1318,1429) (1197.7,1269.6,1375.7) 1165 XD-CCSA (1136,1207,1319) (1230,1297,1394) (1174.6,1248.4,1344.4) RST-CCSA (1114,1180,1287) (1123,1202,1302) (1115.9,118 & 5,1291. 6) GA (1117,1180,1300) (1132,1195,1284) (1118.3,1187.6,1293. 6> LA11 CCSA (1155,1225,1321) (1195,1270,1370)(1183,1242.9,1337.4) 1222 XD-CCSA (116 乙 1222,1319)(1158,1229,1323) (1160.8,1224.6,1320.6) RST-CCSA (1162,1222,1309) (1162,1223,1322)(1161.1,1222.3,1305) GA (1161,1222,1287) (1160,1222,1309)(1160.7,1222,1299.3) LAI 6 CCSA (955,1008,1068) (984,1035,1110) (968.2,1022.6,1092.5) 945 XD-CCSA (923,979,1047) (960,1013,1077) (947,995.7,1062.1) RST-CCSA (892,946,1002) (954,997,1064) (925.1,974.1,1038.1) GA (916,959,1023) (945,994,1068) (929.6,978.6,1047.9) 从表中数据可看岀相较于改进前的 CCSA,XD-CCSA 的寻优能力得到了加强 ， 说明本文设计的变异算子和多样 最优个体集为 CCSA 的搜索带来了更多的信息 ， 增强了种 群的多样性 ， 提高了算法的寻优能力 。 而 RST-CCSA 相较 于包括 GA 在内的其它三个 ， 其寻优能力最强 ，在 FT06, FT10 和 LA11 上达到 BKS 值 ， 且在 FT10 上只有 RST-CCSA 达到了 best know solution ( BKS) 值 ， 在 FT20 和 LA16 上虽没 有达到 BKS 值,但较于 GA 来说表现更好 ， 说明本文提出的 基于机器空闲时间缩小的搜索方法能够在进化过程中提高 种群个体的搜索能力 ， 从而整体提高算法的寻优能力。 但 不足的是需牺牲一定的算法效率。 从表 2 中数据可看出, RST-CCSA 相较于 CCSA 来说 CPU time 消耗都比较大 ， 但是 较于 GA 来说, RST-CCSA 的时间消耗还是可以接受的 ， 甚 至在 FT06 这种规模较小的问题上消耗要小于 GA O 本文还做了收敛性对比 ， 如图 3 中的进化曲线所示 ， 由 于 FT06 规模较小 ， 各算法表现都不错 ， 可比性不强， 因此只 对 FT10,FT20,LAll,LA16 进行了对比 。从图中可以看出 混沌乌鸦算法有较强的持续进化能力 ， 而 RST-CCSA 虽然 在前期的收敛速度上稍弱于 GA, 但是得益于 CCSA 的持续 进化能力 , RST-CCSA 的最终优化结果要好于 GA 。 同时也 可以看出 RST-CCSA 相较于原始 CCSA, 其收敛速度有所提 升 ， 可见本文的改进既保留了 CCSA 的持续进化能力 ， 同时 还提高了收敛速度 ， 从而使得算法整体性能有较大的提升 。 表 2 各算法 CPU 平均时间 s 算法 FT06 FT10 FT20 LA11LA16 CCSA 11.7877.12105.27 83.46 69.86 XD-CCSA 19.3389.97135.26 96.72 92.51 RST-CCSA 89.20 323.86 349.96 295.13 301.56 GA 101.82 317.54 297.20 276.32 263.24 _ ss _ 0 . FT20 -CCSA I 一 S S H 一 1 500 -• s- z — XD-CCSA RST-CCSA 1 300 职 +< 航 : « 4< I 100 迭代次数 / 次 瞩 0 500 1 000 1 500 2 000 S 4oo 3oo 迭代次数 / 次 T ' LAI I — 纟 LA16 — J 3 ••XD-CCSA CCSA S o o — H 2 — RST-CCSA GA 国 -- CCSA — XD-CCSA fe H 1oo 浪 o o 9 — RST-CCSA GA 1 职 +< «* OO « OO 5 00 O 00 5 00 2 00 O 500 1000 1500 2000 迭代次数 / 次 迭代次数 / 次 图 3 算法进化曲线 5 结束语 本文采用基于工序的编码方式并设计修补算子 ， 成功 地将 CCSA 应用于求解町 SSP 上。 并通过引入变异算子丰 富了个体的搜索行为 ， 通过设计多样最优个体集使算法在 提高搜索效率的同吋保证了种群信息的多样性 ， 通过设计 一种基于机器空闲时间缩小的新搜索方法融合进算法中进 一步提高了算法的搜索效率和求解质量 。 通过对 5 个经典 实例的测试 、 对比和分析，验证了所做出的改进有效提高了 收敛速度和寻优能力 ， 而且比 GA 具有更好的求解质量 ， 为 求解町 SSP 提供了一种新的有效解决方式以及为求解其它 类似问题提供了参考 。 本文所提算法在其收敛速度上还有 提升的空间 ， 值得进一步研究 。 参考文献 ： [ 1 ] GAREY M R,SETHI J R. The complexity of flowshop and job shop scheduling] J] ・ Mathematics of Operations Research ,1976 9 1(2) ： 117-129. [2] TSUJIMURA Y, GEN M, KUBOTA E, et al. Solving job-shop scheduling problem with fuzzy processing time using genetic algo- rithmf J ]. Journal of Japan Society for Fuzzy Theory and Systems , 1995,7(5) ： 1073 -1083. [3 ] SAKAWA M , MORI T. An efficient genetic algorithm for job-shop scheduling problems with fuzzy processing lime and fuzzy duedate[J]. Computers & Industrial Engineering, 1999,36 (2 ) ： 325 -341. (下转第 117 页) 第 6 期 孔祥阳 ， 等:基于双非凸约束的遥感图像高密度条带去除算法 117 像配准方法 [ J ] •传感器与微系统 ,2015,34(10) ： 22 -24. [2] regularization model for remote sensing image stripes removal [ J ]. Neurocomput,2017 ,267(6) ： 95 — 106. 吴赵丽 ， 梁栋 ， 赵晋陵 ， 等•基于无人机遥感影像芨芨草盖度 的图像分割方法 [J]. 传感器与微系统 ,2018,37(4) ： 51 -53. [3] [10] DOU H X,HUANG T Z,DENG L J,et al. Directional L0 sparse modeling for image stripes removal [ J ]. Remote Sensing, 2018 , 10(3) ： 361 -390. 马鹏 ， 王小鹏,张永芳 ， 等•基于多尺度自适应均衡的遥感图 像边缘检测方法 [J] •传感器与微系统 ,2018,37(1):147 - 149. f 11 CHANG Y, YAN L , WU T, et al. Remote sensing image stripe noise removal : from image decomposition perspective [ J ]. IEEE Transactions on Geoscience and Remote Sensing, 2016 ,54(12) : [4] CHEN J,LIN H , SHAO Y , et al. Oblique striping removal in remote sensing imagery based on wavelet transform [ J ]. Int 9 1 J Remote Sens, 2006,27 ： 1717 —1723. 1 一 14. [12] SHEN H F,ZHANG L P. A MAP-based algorithm for destriping and inpainting of remotely sensed images]J]. IEEE Trans Geosci [5] MUNCH B,TRTIK P,MARONE F,et al. Stripe and ring artifact removal with combined wavelet-Fourier filteringf J] . Opt Express , 2009,17:8567 -8591. Remote Sens, 2009,47 ： 1492 — 1502. [13 J YUAN G Z,GHANEM B. LOTV : A new method for image restora tion in the presence of impulse noise[ C ]// IEEE Conference on [6] CAO B,DU Y,XU D,et al. An improved histogram matching al gorithm for the removal of striping noise in optical remote sensing imagery [J] . Optik — International Journal for Light and Electron Computer Vision and Pattern Recognition ,2015 ： 5369 — 5377. Optics, 2015,126(23) ： 4723 -4730. [14] JIAO Y,J1N B,LU X. A primal dual active set with continuation algorithm for the regularized optimization problem [ J J . Applied [7 ] BOUALI M , LADJAL S. Toward optimal destriping of MODIS data using a unidirectional variational model [ J J . IEEE Trans Geosci and Computational Harmonic Analysis, 2014 ,39(3) ： 400 — 426. Remote Sens, 2011,49 ： 2924 -2935. [15] DONOHO D L. De-noising by soft-thresholding [ J ] ・ I EEE Transactions on Information Theory ,1995 ,41(3) ： 613 — 627. [8] CHANG Y,YAN L,FANG H,et al. Simultaneous destriping and denoising for remote sensing images with unidirectional total varia tion and sparse representation ]J ・ IEEE Geoscience and Remote [16] 帅慕蓉 ，廖秀英 ， 程辉 ， 等.改进阈值函数的图像去噪方法 [J] ・ 传感器与微系统 ,2019,38(8) ： 42 — 45. 作者简介 ： Sensing Letters, 2014,11 (6) ： 1051 -1055. 孔祥阳 ( 1985 -) ， 男 ， 通讯作者 ， 博士研究生 ， 讲师 ， 研究领域 [9] CHEN Y , HUANG T Z, DENG L J , et al , Group sparsity based 为数字图像处理 。 (上接第 113 页) [4] NIU Q , JIAO B , GU X, et al. Particle swami optimization com bined with genetic operators for job shop scheduling problem with fuzzy processing time [ J 」 . Applied Mathematics and Computa- tion,2008 ,205( 1) ： 148 -158. [9] 刘雪静 ， 贺毅朝,吴聪聪 ， 等•求解 0-1 背包问题的混沌二进 制乌鸦算法 [J]. 计算机工程与应用 ,2018,54(10):173 一 179. [ 10 ] YANG D , LIU Z , ZHOU J. Chaos optimization algorithms based on chaotic maps with differenl probability distribution and search speed for global optimization J J . Communications in Nonlinear [5 ] HU Y , YIN M,LI X,et al. A novel objective function for job-shop scheduling problem with fuzzy processing time and fuzzy due date Science and Numerical Simulation ,2014,19(4) ： 1229 — 1246. using differential evolution algorithm [ J ] • The International [U] 王潘潘 ， 钱谦 ， 王锋•改进加权 Slope one 协同过滤推荐算法研 Journal of Advanced Manufacturing Technology , 2011,56 ( 9 ) ： 1125-1138. 究 [J] •传感器与微系统 ,2017,36(7):138 -141. [ 12 ] 王友钊 ， 彭宇翔 ， 潘芬兰.基于贪心算法和遗传算法的仓储车 [6] BUSTOATELLEZ C A, TENJOGARCIA J S, F1GUEROAGAR ・ 辆调度算法 [J] •传感器与微系统 ,2012,31(10) ： 125 一 12& [ 13 ] JAIN A S, MEERAN S. Deterministic job-shop scheduling ： Past, CIA J C , et al. Solving job-shop scheduling problems with fuzzy processing times and fuzzy due elates [C]// International Confe rence Information Processing, 2018 ： 790 — 799. present and future [ J ] ・ European Journal of Operational Re ・ search, 1999,113(2) ： 390 -434. [7] ASKARZADEH A. A novel metaheuristic method for solving con strained engineering optimization problems : Crow search algo 作者简介 ： 刘 凯 (1994-) ， 男 ， 通讯作者 ， 硕士研究生 ， 研究方向为智能 算法 ， 生产调度优化 。 rithm [ J ].Computers & Structures ,2016,169 ： 1 — 12. 黄辉先 (1957 — ) ， 男 ， 教授 ， 主要研究领域为复杂建模与非线 [8 ] SAYED G I , HASSANIEN A E , AZAR A T. Feature selection via 性控制 ， 先进控制理论 , 优化算法及工业自动化控制 。 赵骥 (1965 -), 男 ，高级工程师 ， 主要研究领域为智能工厂 a novel chaotic crow search algorithm [ J ] ・ Neural Computing and Applications,2019,31(1) ： 171 -188. 管控技术研究与系统 。
2024年3月15日发(作者：英正平)
110
传感器与微系统
(Transducer
and
Microsyslem
Technologies)
2021
年第
40
卷第
6
期
DOI
：
10.
13873/J.
1000-9787(2021)06-0110-04
］
计算与测试
［
求解模糊作业车间调度问题的混沌乌鸦搜索算法
*
*
刘凯
-
黄辉先
-
赵骥
V
(1
.湘潭大学信息工程学院
，
湖南湘潭
411105
；
2.
清华大学清华大学国家
CIMS
工程技术研究中心
，
北京
100084)
摘要
：
为求解模糊作业车间调度问题
(FJSSP),
提出了一种改进的混沌乌鸦搜索算法
(
CCSA)
。
算法采
用基于工序的编码,并设计了一种修补方式以使
CCSA
有效求解町
SSP
；
为增强算法的邻域搜索能力引入
了变异算子;为提高算法的进化能力
，
提出了基于余弦相似度的多样最优个体集来引导进化
，
使在增强进
化效率的同吋保证种群多样性;为进一步提高算法在求解
FJSSP
时的搜索效率
，
提出了一种基于机器空闲
缩小的搜索方法
。
最后选取了
5
个典型实例进行了测试
，
实验结果验证了所提算法的有效性
。
关键词
：
模糊作业车间调度问题
；
混沌乌鸦搜索算法
；相似性度量；
局部最优
中图分类号
：
TP18
文献标识码
：
A
文章编号
：
1000~9787(
2021
)064)1104)4
Chaotic
crow
search
algorithm
for
fuzzy
job-shop
scheduling
LIU
Kai
1
,
HUANG
Huixian
1
,
ZHAO
Ji
1
'
2
(1
・
College
of
Information
Engineering
,
Xiangtan
University
,
Xiangtan
411105,
China
；
2
・
Tsinghua
University
,
National
Computer
Integrated
Manufacturing
Systems
Engineering
Research
Center
of
Tsinghua
University
,
Beijing
100084,
China)
Abstract
:
An
improved
chaotic
crow
search
algorithm
(
CCSA
)
is
proposed
for
solving
the
fuzzy
job-shop
scheduling
problem
(
FJSSP)
.
The
algorithm
adopts
the
process-based
coding
method
,
and
a
solution-correct
way
is
designed
to
make
CCSA
solve
FJSSP
effective!y
・
In
order
to
enhance
the
neighborhood
search
ability
of
the
algorithm,the
mutation
operator
is
introduced
・
In
order
to
improve
lhe
evolutionary
ability
of
the
algorithm,multiple
optimal
individual
set
based
on
the
Cosine
Similarity
is
proposed
to
guide
the
evolution,
which
not
only
enhanced
lhe
evolutionary
efficiency
but
also
ensures
the
diversity
of
lhe
population
・
In
order
to
further
improve
the
search
efficiency
of
CCSA
when
solving
FJSSP,
a
search
method
based
on
the
reduction
of
machine's
spare
time
is
proposed.
Finally
,
five
benchmark
problems
are
selected
for
testing,and
lhe
results
verify
the
effectiveness
of
lhe
proposed
algorithm.
Keywords
:
fuzzy
job-shop
scheduling
problem
(
FJSSP
)
；
chaotic
crow
search
algorithm
(
CCSA
)
；
similarity
measurement
;
local
optimum
0
引言
作业车间调度问题
(
JSSP)
是一个典型的
NP-hard
问
期的
FJSSP,Niu
Q
等人⑷通过将
GA
中的交叉和变异算子
结合到粒子群优化
(
PSO)
算法中对
PSO
进行改进并应用于
FJSSP
中
，
最后和
GA
进行比较验证了算法的优越性
。
Hu
Y
等人⑸用改进的差分进化算法
(
DE)
对
FJSSP
进行了求
题⑴
，
在过去的五十几年里,一直受到许多学者的关注与
研究，
其研究成果被广泛应用于生产
，
工程管理，
计算机等
领域
，
因此研究
JSSP
具有重要的学术和实际意义
。
而作为
JSSP
的扩充
，
模糊作业车间调度问题
(
fuzzy
job-shop
sche
duling
problem,FJSSP)
在
JSSP
的基础上加入不确定性条件
解
。
Bustos-Tellez
C
A
等人⑹利用线性规划
(
LP)
的方法对
FJSSP
建立了模糊
LP
模型。
然而
，
相比
JSSP,
对于
FJSSP
的研究还远远不够
,
并且多元启发式方法容易陷入局部最
优解
,
而
LP
方法又在求解大规模问题上太过复杂
,
难以计
算
，
所以仍须研究人员能够提出更多更好的解决方法来解
如模糊加工时间
，
使得问题更接近真实的生产情况
，
更具研
究价值
。
Tsujimura
Y
等人刘最先用遗传算法
(
genetic
alo-
rithm,GA)
解决带模糊加工时间的
FJSSP,Sakawa
M
等人⑶
决问题
。
乌鸦搜索算法
(
crow
search
algorithm
,
CSA
)
是
Askarza-
将
GA
进行了改进并应用于具有模糊加工时间和模糊交货
收稿日期
=2019-10-13
*
基金项目
：
东莞市引进创新科技团队计划资助项目(
2)
第
6
期
刘凯
，
等:求解模糊作业车间调度问题的混沌乌鸦搜索算法
111
deh
A®
提出的新群体智能算法
。
Sayed
G
I
等人⑻对该算
法引入了混沌机制
，
即混沌乌鸦搜索算法
(chaotic
crow
search
algorithm
,
CCSA
)
并成功应用于二进制特征选择问
题
，
最终对比发现该算法具有优秀的全局优化能力和求解
速度
。
刘雪静等人⑼将
CCSA
应用于
0-1
背包问题上同样
得出其具有良好的全局寻优能力和收敛速度
，
这些应用都
表现出
CCSA
值得在更多不同领域被研究
，
因此
，
本文提出
将
CCSA
应用于求解带模糊加工时间的
FJSSP
上
，
并且通过
对问题和算法的研究将算法做了改进
,
最后进行了对比仿
真实验
，
验证了本文所提出的改进策略的有效性以及所提
算法能够有效求解
FJSSP
。
1
FJSSP
町
SSP
的描述和数学模型可参考文献
［
4
］
。
而目标函
数选用
minCmm
=max{
C
】
,C
2
,Cj
,•••
,C
n
j
,
即最小化最大
完成时间
，
其中
q
为工件
j
的模糊完成时间
。
町
SSP
中引入模糊三角数
(
triangular
fuzzy
number
,TFN)
表示问题中的模糊加工时间⑶
,TFN
运算比较参考文献
［
3
］
。
其中考虑到
FJSSP
的实际意义,本文提出如式
(
1)
所示的取
大运算方式
C
=
max
A
,B
=(
max
j
a,
,b
x
}
,
max
j
a
2
,b
2
}
,
max
j
a
3
,b
3
|
)
(1)
图
i
为两个
tfn
的取大操作图
CSA
是受到乌鸦群藏匿食物的行为启发而来的⑺
，
而
CCSA
在
CSA
的基础上引入了混沌序列
。假设乌鸦群的数
量为为乌鸦
i在第
I
次搜索之后的位置
，
此时它所找
到的最佳藏匿食物的位置称为乌鸦的记忆位置
，
记为
其中
,i=l,2,-,/V
；
«=l,2-,t
max
,«
max
表示最大搜索次数
。
算法主要步骤如下
：
步骤
1
初始化
。
初始化产
=/•
*
。
步骤
2
搜索新位置
。
群体中每只乌鸦会随机选择另
一只乌鸦作为目标进行位置搜索
。
假设在第/次迭代中
，
乌鸦
，
进行跟随的是乌鸦
z,
则这时会出现两种情况
：
1)
乌鸦
z
没有发现自己被乌鸦
i
跟随
乌鸦
：
将靠近乌鸦
z
的记忆位置
,
通过式
(
2)
更新
乌鸦
i
的位置
=yi.i
+Ci
x/Z
-/•
)
*
(2)
式中
刃为表示搜索步长;
c,
e
(0,1),
为混沌序列的第
i
个
值,该混沌序列由
Circle
Map
何来产生
，
其映射公式为
C
l+1
=mod(C,
+
,1),
c
=0.5,(/=0.2
(3)
2)
乌鸦
z
发现自己被乌鸦i
跟随了
此时乌鸦
i
无法靠近乌鸦
z
的记忆位置,只能随机找一
个新位置来更新自己的位置
。
根据上述两种情况的描述可将乌鸦
，
的位置更新公式
总结如下
y'
,+1
={
r/-
,+1
+G
x/Z
x(M
..
2
''
-/•
)
*
［
generate
a
random
position
,
otherwise
(4)
式中
AP'
•'为乌鸦
z
在第
t
次搜索时能够发现被乌鸦
i
跟随
的概率
。
步骤
3
更新记忆位置
。
群体中的乌鸦在每次搜索更
新完自己的位置之后
，
通过一个评价函数
F
”
判断是否替换
记忆位置
，
具体更新公式为
(
严
，
化(严心化(加)
A/'-
,+1
=
(5)
,
otherwise
步骤
4
重复步骤
(2)
~步骤
(3)
搜索血次
。
步骤
5
输出优化结果。
乌鸦群中最优的记忆位置即
为算法的最终优化结果
。
3
FJSSP
的
CCSA
基于针对町
SSP
特点设计岀可应用于求解
FJSSP
的
CCSA
O
算法的编码策略采用基于工序的编码⑵
。
3.1
修补与变异
由于
CCSA
的变量是连续的
，
要想求解
FJSSP
这类离散
问题便需设计一个修补算子对位置更新公式计算出的新解
进行修补操作
,使算法能够在正确的解空间中进行搜索
。
同时
，
由于
CCSA
单单依靠式
(
4)
进行搜索过于单一
，
无法
对目标个体的邻域充分搜索
。因此引入变异算子以概率
戸认血将新解进行变异
，
以此丰富个体的邻域搜索行为
。
变
异方式采用自身交换策略
：
随机选择解中的两个编码不同
的位置进行交换
。
具体算法描述如下
：
算法
1
新解的修补与变异算法
输入:
CCSA
按式
(
4)
计算出的新解
，
人
“
2
输出
：
经过修补与变异之后的解
,y
mulate
o
1)
将儿讯向上取整得到歹罰
。
2)
分别统计人曲中范围在工件号内的各个编号出现的
次数
。
3)
将畑中小于
1
的数从小到大修正为工件号统计次
数小于工序数的最小工件号
，
同理将大于工件数的编号从
大到小修正为工件号统计次数小于工序数的最大工件号
，
得到人吆
2
4)
在人唤
“
中随机选择两个不同的工件编号进行交换
，
得到儿皿
。
112
传感器与微系统
第
40
卷
3.2
多样最优个体集
原始
CCSA
中引导更新的目标个体为随机选择
，
为提
高乌鸦的搜索效率并保证种群的多样性
，
本文提出基于相
似性度量的多样性最优选择策略来优化和丰富目标集
。
为了评估两个个体间的相似度
，
本文引入经常被用于
信息检索当中的基于余弦
(cosine)
定理E
的相似性度量方
式
。
用
X
和丫来表示两个个体,其中用笛表示
X
的第
，
个
分量了表示
y
的第
i
个分量
，
则
由于在
FJSSP
中
，
个体
X
和
y
中的每个元素都是正整
数
,
因此,任何两个个体之间的
COS
0
都在［
0,1
］
之间
，
数值
越接近
1,
则表示
X
和
y
的相似度越大
。
因此
，
基于余弦相
似度的多样最优个体集的选择算法如算法
2
。
算法
2
多样最优个体集选择算法
输入:第/代群体的记忆位置,最优的记忆位置个
数,
SP
；
多样的记忆位置个数
,
div
;
相似度阈值
，
乩
输出
：
多样最优个体目标集,
set
。
1)
随机生成一个目标集
set
。
2)
从
M
中选择评价值为前
sp
名的个体逐个对
set进
行随机替换
。
3)
从剩下的
M'
中按顺序选择一个与
M
1
中所有个体的
相似度平均值低于
R
的个体
，
然后随机替换
set
中除步
骤
(2)
选中之外的个体
。
4)
重复步骤
(3
次
，
直到
j
等于
div
或者
M'
遍历完成
。
5)
返回目标集
set
。
3.3
基于机器空闲时间缩小的搜索方法
由于
FJSSP
解空间极大且复杂
，使得
CCSA
群体的搜索
效率不高
、
收敛慢
。为了进一步提升算法的搜索效率
，
本文
提出一种基于机器空闲缩小的搜索方法以结合到
CCSA
中
。
在描述方法的具体步骤之前
，
先有如下定义
：
令
St”
和
Et
”
分别表示任务
w
的开始时间和结束时间
。
定义待优任务
、
待优工件
、
待优工序
。
假设吗和血为
机器队列中连续的两个任务
，
若有
Ei
wi
K2 , 则处称为待 优任务 ， 型所属工件称为待优工件用 2 所在工序称为待优 工序 。 该搜索方法是通过优先加工待优工序的前续工序所在 的任务 ， 使得待优任务的可开始加工时间提前来缩小机器 的空闲时间 。对于某个可行解 ， 随机选择一个机益 , 对该机 器的加工队列进行遍历(首个任务不进行调整) ， 判断每个 任务是否为待优任务， 若是则以一定的概率 P 制进行空闲时 间缩小 ， 缩小的算法如算法 3 。 算法 3 空闲时间缩小算法 输入:问题的一个可行解, S ； 机器号, m ； 待优任务号,仞 。 输出 ： 调整之后的新解 ,S newO 1) 寻找 w 所属工件和工序分别记为人和 p% 。 2) 判断人的工序卩％- 1 所在任务的可开始吋间是否 比当前开始时间小且不在自身机器队列的队首 ， 若是则该 任务为可提前任务 , 执行步骤 (3), 否则执行步骤( 6) 。 3) 将该可提前任务和所在队列中的前一个任务交换 ， 刷新调度方案 ， 若 w 之前的空闲时间为零 ， 则退出计算返回 新解 S “ ” ， 否则执行步骤 (4) 。 4) 若待缩小的空闲时间减少则执行步骤 ( 5), 否则放 弃此次交换并退出计算返回结果 s newO 5) 若 p% -1 〉 1, 则保留此次交换,然后以作为算 法 3 的输入递归执行 ， 否则保留交换,退出计算返回 S newO 6) 令 pn w =pn u . -1 , 若 pn u >1 则重新执行步骤 (2) 。 7) 返回结果 S 唤 。 为避免因为引入规律导致种群个体过于集中 ， 陷入局 部最优 ， 本文采用隔代搜索 ， 每间隔勺代从种群中选择 N x sr,(0 个体逐个进行 50 次基于贪婪策略问的搜 索 ，其中 N 为种群数量, sr 即选择比率 。 3.4 算法流程 根据上述设计 ， 改进后的算法总体流程如图 2 所示 。 图 2 算法总体流程图 4 实验与分析 为了验证算法对于 FJSSP 的有效性 ， 本文从文献 ［ 13 ］ 中选取了 Job Shop 调度中的 5 个典型的 Benchmark 并做模 糊化的处理 ， 模糊化的方式为 T = (t -rand,t,t +rarui') ， 其 中 m 加表示小于/的随机整数 ， 且当 t 越大时, m 加占/的 比重越小 。 同时为了方便比较 ， 结果比较都采用最大模糊 完成时间的中间数作为参考 。 实验环境:算法编程平台为 MATLAB R2016B, 操作系 统为 Windows7_64 位 ,CPU 为 Intel Core i7 -7500U@2. 70 GHZ, 内存为 8 GB 。 本文分别将原始的 CCSA, 加入变异算子和多样最优个 体集的 XD-CCSA ( X-diversity-chaotic crow search algorithm) , 第 6 期 刘凯 ， 等:求解模糊作业车间调度问题的混沌乌鸦搜索算法 113 本文所提算法 RST-CCSA ( reducing spare time — chaotic crow search algorithm ) 以及 GA 在 5 个实例上测试了各 10 次 。所 有测试中种群数量都设置为 N =200 ， 均进化 2 000 代 , 其余 参数 AP =0. 2 ,fl =2. 0, 变异概率 P raulale =0. 28, 目标集中最 优个体数 sp =5 , 低相似度个体数 div =20 , 相似度阈值 R = 0. 86, 基于机器空闲时间搜索方法的参数金 =50,sr =0. 4, =0.88 。 实验结果如表 1 所示 ， 表中给出了 10 次测试所得的最 优值 、 最差值 、 平均值以及所占 CPU 平均值时间 ， 表中各个实 例编号下面的加粗数据为 BKS 值 ， 即已知文献中的最优解 。 表 1 各算法的计算结果 算例算法 最优值最劣值 平均值 FT06 CCSA (42,55,75) (44,58,77) (43.6,57.1,76) 55XD-CCSA (42,55,76)(47,57,77) (43.4,55.8,76) RST-CCSA (42,55,75)(42,55,76) (42,55,75.4) GA (42,55,75) (42,55,76) (42,55,75.3) FT10 CCSA (1035,1098,1221) (1090,1156,1300) (1073.5,1138.6,1276.3) 930 XD-CCSA (944.994.1100) (979,1035,1154) (961.7,1021,1127.1) RST-CCSA (881,930,1034) (919,978,1097) (902.6,952.1,1075.6) GA (908,955,1092) (928,983,1124) (919.5,974.9,1104.1) FT20 CCSA (1181,1232,1340) (1243,1318,1429) (1197.7,1269.6,1375.7) 1165 XD-CCSA (1136,1207,1319) (1230,1297,1394) (1174.6,1248.4,1344.4) RST-CCSA (1114,1180,1287) (1123,1202,1302) (1115.9,118 & 5,1291. 6) GA (1117,1180,1300) (1132,1195,1284) (1118.3,1187.6,1293. 6> LA11 CCSA (1155,1225,1321) (1195,1270,1370)(1183,1242.9,1337.4) 1222 XD-CCSA (116 乙 1222,1319)(1158,1229,1323) (1160.8,1224.6,1320.6) RST-CCSA (1162,1222,1309) (1162,1223,1322)(1161.1,1222.3,1305) GA (1161,1222,1287) (1160,1222,1309)(1160.7,1222,1299.3) LAI 6 CCSA (955,1008,1068) (984,1035,1110) (968.2,1022.6,1092.5) 945 XD-CCSA (923,979,1047) (960,1013,1077) (947,995.7,1062.1) RST-CCSA (892,946,1002) (954,997,1064) (925.1,974.1,1038.1) GA (916,959,1023) (945,994,1068) (929.6,978.6,1047.9) 从表中数据可看岀相较于改进前的 CCSA,XD-CCSA 的寻优能力得到了加强 ， 说明本文设计的变异算子和多样 最优个体集为 CCSA 的搜索带来了更多的信息 ， 增强了种 群的多样性 ， 提高了算法的寻优能力 。 而 RST-CCSA 相较 于包括 GA 在内的其它三个 ， 其寻优能力最强 ，在 FT06, FT10 和 LA11 上达到 BKS 值 ， 且在 FT10 上只有 RST-CCSA 达到了 best know solution ( BKS) 值 ， 在 FT20 和 LA16 上虽没 有达到 BKS 值,但较于 GA 来说表现更好 ， 说明本文提出的 基于机器空闲时间缩小的搜索方法能够在进化过程中提高 种群个体的搜索能力 ， 从而整体提高算法的寻优能力。 但 不足的是需牺牲一定的算法效率。 从表 2 中数据可看出, RST-CCSA 相较于 CCSA 来说 CPU time 消耗都比较大 ， 但是 较于 GA 来说, RST-CCSA 的时间消耗还是可以接受的 ， 甚 至在 FT06 这种规模较小的问题上消耗要小于 GA O 本文还做了收敛性对比 ， 如图 3 中的进化曲线所示 ， 由 于 FT06 规模较小 ， 各算法表现都不错 ， 可比性不强， 因此只 对 FT10,FT20,LAll,LA16 进行了对比 。从图中可以看出 混沌乌鸦算法有较强的持续进化能力 ， 而 RST-CCSA 虽然 在前期的收敛速度上稍弱于 GA, 但是得益于 CCSA 的持续 进化能力 , RST-CCSA 的最终优化结果要好于 GA 。 同时也 可以看出 RST-CCSA 相较于原始 CCSA, 其收敛速度有所提 升 ， 可见本文的改进既保留了 CCSA 的持续进化能力 ， 同时 还提高了收敛速度 ， 从而使得算法整体性能有较大的提升 。 表 2 各算法 CPU 平均时间 s 算法 FT06 FT10 FT20 LA11LA16 CCSA 11.7877.12105.27 83.46 69.86 XD-CCSA 19.3389.97135.26 96.72 92.51 RST-CCSA 89.20 323.86 349.96 295.13 301.56 GA 101.82 317.54 297.20 276.32 263.24 _ ss _ 0 . FT20 -CCSA I 一 S S H 一 1 500 -• s- z — XD-CCSA RST-CCSA 1 300 职 +< 航 : « 4< I 100 迭代次数 / 次 瞩 0 500 1 000 1 500 2 000 S 4oo 3oo 迭代次数 / 次 T ' LAI I — 纟 LA16 — J 3 ••XD-CCSA CCSA S o o — H 2 — RST-CCSA GA 国 -- CCSA — XD-CCSA fe H 1oo 浪 o o 9 — RST-CCSA GA 1 职 +< «* OO « OO 5 00 O 00 5 00 2 00 O 500 1000 1500 2000 迭代次数 / 次 迭代次数 / 次 图 3 算法进化曲线 5 结束语 本文采用基于工序的编码方式并设计修补算子 ， 成功 地将 CCSA 应用于求解町 SSP 上。 并通过引入变异算子丰 富了个体的搜索行为 ， 通过设计多样最优个体集使算法在 提高搜索效率的同吋保证了种群信息的多样性 ， 通过设计 一种基于机器空闲时间缩小的新搜索方法融合进算法中进 一步提高了算法的搜索效率和求解质量 。 通过对 5 个经典 实例的测试 、 对比和分析，验证了所做出的改进有效提高了 收敛速度和寻优能力 ， 而且比 GA 具有更好的求解质量 ， 为 求解町 SSP 提供了一种新的有效解决方式以及为求解其它 类似问题提供了参考 。 本文所提算法在其收敛速度上还有 提升的空间 ， 值得进一步研究 。 参考文献 ： [ 1 ] GAREY M R,SETHI J R. The complexity of flowshop and job shop scheduling] J] ・ Mathematics of Operations Research ,1976 9 1(2) ： 117-129. [2] TSUJIMURA Y, GEN M, KUBOTA E, et al. Solving job-shop scheduling problem with fuzzy processing time using genetic algo- rithmf J ]. Journal of Japan Society for Fuzzy Theory and Systems , 1995,7(5) ： 1073 -1083. [3 ] SAKAWA M , MORI T. An efficient genetic algorithm for job-shop scheduling problems with fuzzy processing lime and fuzzy duedate[J]. Computers & Industrial Engineering, 1999,36 (2 ) ： 325 -341. (下转第 117 页) 第 6 期 孔祥阳 ， 等:基于双非凸约束的遥感图像高密度条带去除算法 117 像配准方法 [ J ] •传感器与微系统 ,2015,34(10) ： 22 -24. [2] regularization model for remote sensing image stripes removal [ J ]. Neurocomput,2017 ,267(6) ： 95 — 106. 吴赵丽 ， 梁栋 ， 赵晋陵 ， 等•基于无人机遥感影像芨芨草盖度 的图像分割方法 [J]. 传感器与微系统 ,2018,37(4) ： 51 -53. [3] [10] DOU H X,HUANG T Z,DENG L J,et al. Directional L0 sparse modeling for image stripes removal [ J ]. Remote Sensing, 2018 , 10(3) ： 361 -390. 马鹏 ， 王小鹏,张永芳 ， 等•基于多尺度自适应均衡的遥感图 像边缘检测方法 [J] •传感器与微系统 ,2018,37(1):147 - 149. f 11 CHANG Y, YAN L , WU T, et al. Remote sensing image stripe noise removal : from image decomposition perspective [ J ]. IEEE Transactions on Geoscience and Remote Sensing, 2016 ,54(12) : [4] CHEN J,LIN H , SHAO Y , et al. Oblique striping removal in remote sensing imagery based on wavelet transform [ J ]. Int 9 1 J Remote Sens, 2006,27 ： 1717 —1723. 1 一 14. [12] SHEN H F,ZHANG L P. A MAP-based algorithm for destriping and inpainting of remotely sensed images]J]. IEEE Trans Geosci [5] MUNCH B,TRTIK P,MARONE F,et al. Stripe and ring artifact removal with combined wavelet-Fourier filteringf J] . Opt Express , 2009,17:8567 -8591. Remote Sens, 2009,47 ： 1492 — 1502. [13 J YUAN G Z,GHANEM B. LOTV : A new method for image restora tion in the presence of impulse noise[ C ]// IEEE Conference on [6] CAO B,DU Y,XU D,et al. An improved histogram matching al gorithm for the removal of striping noise in optical remote sensing imagery [J] . Optik — International Journal for Light and Electron Computer Vision and Pattern Recognition ,2015 ： 5369 — 5377. Optics, 2015,126(23) ： 4723 -4730. [14] JIAO Y,J1N B,LU X. A primal dual active set with continuation algorithm for the regularized optimization problem [ J J . Applied [7 ] BOUALI M , LADJAL S. Toward optimal destriping of MODIS data using a unidirectional variational model [ J J . IEEE Trans Geosci and Computational Harmonic Analysis, 2014 ,39(3) ： 400 — 426. Remote Sens, 2011,49 ： 2924 -2935. [15] DONOHO D L. De-noising by soft-thresholding [ J ] ・ I EEE Transactions on Information Theory ,1995 ,41(3) ： 613 — 627. [8] CHANG Y,YAN L,FANG H,et al. Simultaneous destriping and denoising for remote sensing images with unidirectional total varia tion and sparse representation ]J ・ IEEE Geoscience and Remote [16] 帅慕蓉 ，廖秀英 ， 程辉 ， 等.改进阈值函数的图像去噪方法 [J] ・ 传感器与微系统 ,2019,38(8) ： 42 — 45. 作者简介 ： Sensing Letters, 2014,11 (6) ： 1051 -1055. 孔祥阳 ( 1985 -) ， 男 ， 通讯作者 ， 博士研究生 ， 讲师 ， 研究领域 [9] CHEN Y , HUANG T Z, DENG L J , et al , Group sparsity based 为数字图像处理 。 (上接第 113 页) [4] NIU Q , JIAO B , GU X, et al. Particle swami optimization com bined with genetic operators for job shop scheduling problem with fuzzy processing time [ J 」 . Applied Mathematics and Computa- tion,2008 ,205( 1) ： 148 -158. [9] 刘雪静 ， 贺毅朝,吴聪聪 ， 等•求解 0-1 背包问题的混沌二进 制乌鸦算法 [J]. 计算机工程与应用 ,2018,54(10):173 一 179. [ 10 ] YANG D , LIU Z , ZHOU J. Chaos optimization algorithms based on chaotic maps with differenl probability distribution and search speed for global optimization J J . Communications in Nonlinear [5 ] HU Y , YIN M,LI X,et al. A novel objective function for job-shop scheduling problem with fuzzy processing time and fuzzy due date Science and Numerical Simulation ,2014,19(4) ： 1229 — 1246. using differential evolution algorithm [ J ] • The International [U] 王潘潘 ， 钱谦 ， 王锋•改进加权 Slope one 协同过滤推荐算法研 Journal of Advanced Manufacturing Technology , 2011,56 ( 9 ) ： 1125-1138. 究 [J] •传感器与微系统 ,2017,36(7):138 -141. [ 12 ] 王友钊 ， 彭宇翔 ， 潘芬兰.基于贪心算法和遗传算法的仓储车 [6] BUSTOATELLEZ C A, TENJOGARCIA J S, F1GUEROAGAR ・ 辆调度算法 [J] •传感器与微系统 ,2012,31(10) ： 125 一 12& [ 13 ] JAIN A S, MEERAN S. Deterministic job-shop scheduling ： Past, CIA J C , et al. Solving job-shop scheduling problems with fuzzy processing times and fuzzy due elates [C]// International Confe rence Information Processing, 2018 ： 790 — 799. present and future [ J ] ・ European Journal of Operational Re ・ search, 1999,113(2) ： 390 -434. [7] ASKARZADEH A. A novel metaheuristic method for solving con strained engineering optimization problems : Crow search algo 作者简介 ： 刘 凯 (1994-) ， 男 ， 通讯作者 ， 硕士研究生 ， 研究方向为智能 算法 ， 生产调度优化 。 rithm [ J ].Computers & Structures ,2016,169 ： 1 — 12. 黄辉先 (1957 — ) ， 男 ， 教授 ， 主要研究领域为复杂建模与非线 [8 ] SAYED G I , HASSANIEN A E , AZAR A T. Feature selection via 性控制 ， 先进控制理论 , 优化算法及工业自动化控制 。 赵骥 (1965 -), 男 ，高级工程师 ， 主要研究领域为智能工厂 a novel chaotic crow search algorithm [ J ] ・ Neural Computing and Applications,2019,31(1) ： 171 -188. 管控技术研究与系统 。