1.1 引言
本章主要研究了以最大化完工时间和能耗指标为目标的作业车间低碳调度 模型的求解方法。首先，建立了多目标作业车间低碳调度模型；然后基于 Pareto 支配理论，设计了一种高效的 MODWSA 算法获得满意的 Pareto 非支配解；最 后，设计了一套测试算例， 将 MODWSA 算法与其它经典多目标算法进行比较分 析，验证了 MODWSA 算法的优越性。 在本研究中，作者完成了两项工作： 首先， 构建了一个新的多目标作业车间低碳数学模型；其次，设计了一种高效的 MODWSA算法获得满意的Pareto非支配解。
1.2 作业车间低碳调度模型
本章研究的作业车间低碳调度问题可描述如下： 对给定的 n 个工件及 k 台机 器，一个工件的加工需要经过 m 道工序，每道工序允许在特定的机器上加工， 任意一台机器在任意一个时刻仅能加工某一工件的某一道工序， 并且一个工件只 能在其上道工序完成后下一道工序才能开始加工 ［插入文献 ］。
考虑机器的准备时间，准备时间与同一机器上相邻两工件的加工顺序相关， 并且机器的启动和工件的加工是相连的。 对应于不同工序， 机器具有不同的速率 档位进行加工，并且可以进行调节。 从能耗的角度来看，机器有四种不同的状态： 加工状态 （机器在加工工件 ） ，启动状态（机器在准备加工一个新的工件） ，待机 状态（机器处于空转中） ，以及关机状态（机器被关机） 。通常情况下，当机器在 较高速率运作时， 工件的加工时间会被缩短， 但是相应的能耗会增加。 因此本问 题以最大化完工时间和能耗指标为目标， 由于本章所研究问题的特点， 该问题要 比传统的作业车间调度问题要复杂的多。在该问题中，其它设定如下： 工件在车间里被连续加工。也就是说，加工过程不能被中断。 机器允许有空闲时间，并且各阶段间具有容量无限的缓冲区。
当有第一个工件在机器上加工时，机器开机；当在该机器上加工的所有工件 加工完毕后，机器关机。
机器速度在工件加工过程中不能进行调整。
1.2.1 混合整数规划模型 为了提出问题的数学模型，根据上面对问题的描述，我们首先定义了下面的相 关数学符号。 符号定义：
I :工件集合,I =｛1”..i,...,n｝。
J :工序集合，J =｛1”.., j,...,m｝。
M :机器集合,M 二｛1,...,k,...,l｝。
M j :工件i
的第j道工序所在的加工机器。
:机器k上所有工件及其对应工序的集合，即 i=｛（i,j）|Mij=k｝。
pkj,v :工件i
的第j道工序在机器k上以速度v加工所需的时间。
上，工件i加工完成后紧接着工件i加工所需准备时间。当r =o, ski =0 表明
ski :在机器k
了当工件i是分配到相关机器的第一个工件，且准备时间为 0。
PPk,v :机器ksp‘i :机器kiPk :机器k
在速度v下运行所消耗的功率。
由工件i转到工件i所消耗的启动功率。 保持空转所消耗的功率。
决策变量：
b,j :工件ie,j :工件i
的第j道工序的开始加工时间。 的第j道工序的结束加工时间。
i的第j道工序在机器k上以速率v加工时，值为1 ； 否
xkj,v :二维决策变量，当工件
则值为0。
yki :二维决策变量，当工件
i紧接在工件i后在机器k上加工时，值为1;否则 值为
0。
Tonk:辅助决策变量，表明了机器Toffk:辅助决策变量，表明了机器
k的开机时间。 k的关机时间。
基于这些定义的数学符号，下面给出了流水车间低碳调度问题的混合整数规 划模型。 目标函数：
Min
Cmax=maXe,m
(1)
Min TEC =E〔 +E2 +E3
E
1
⑵
=送送 X Xpp
召議
i ,j,v
i € j
v
k ,v i,j,v
p
⑶
k k k
E
2
=乙 Z yi'i sp「i 命 怎i怎
ff
⑷
k
、 k
si 'i —L L L
曲l i'社i迂 i € j S v包 丿 目标（1）表明了最大完工时间最小。目标（2）表明了总能耗最小，其中El表
k
E3=2：—茁 yki
k
Xi,j ,v ' pi,j, v
k
ipk
(5)
示机器处于加工状态时的总能耗， E2表示机器处于启动状态时的总能耗， E3表
示了机器处于待机状态时的总能耗。他们分别对应了公式（ 约束：
k
3） - （5）.
Z Xi,j,v =1,勺曰，j €J,k =Mij
v Nk
k i,j,v
k
⑹
-i ■ I, j ■ J ,k
=M ij
e
i, j
=bi,j
- '
Pi,j,v X,
v ,V：
⑺
(8)
bi,j
_目」丄_0, -i • I, j 理2,...,m[
yii' _1, 一i,i'三 I ,k 三 M
yi'i
k
(9)
L — Z
(10)
on
e’j y： —E s： y：兰0, wj匕^=叫
i'」
T
k =(m酬
off
(11)
T k =
(maxe,j
(12)
Xkj,v ｛0,1｝； I, j J,v Vk
(13)
y」｛0,1｝； —i,iT
(14)
e,j >0,
b,j -0, —i l,j J
（15）
其中，约束（6）保证每个工件遍历所有工序，并且对应于特定工序，每个工件 被分配到一台机器上，并以一种速度级别进行加工。约束（
7）表示在加工过程
8）确
中不允许中断，工件必须在一台机器上以一种速度级别加工完毕。约束（ 保只有在工件的前一道工序完成之后下一道工序才能开始。约束（
9）和（10）
保证机器容量限制，即只有在完成了前一个工件的加工之后， 才能开始下一个工 件的加工。约束（11）表示辅助变量的计算，它等于分配给相应机器的工件的起 始时间的最小值。约束（12）表示辅助变量的计算，它等于分配给相应机器的工 件的结束时间的最大值。约束（13） — （ 15）分别定义了决策变量的可行范围。 1.2.2举例说明
举例进行说明问题（带甘特图的那种）
1.3 MODWSA算法求解作业车间低碳调度问题
从上一章 WSA算法的简述中可以看出，作为一个求解连续性问题的算法， WSA算法同样不能直接用于求解离散的作业车间调度问题，因此需要设定合理 的编码和解码方式、距离计算公式和移动策略。在这一节中，提出了一种多目标 离散鲸鱼群算法（MODWSA），以解决作业车间低碳调度冋题， 算法框架流程如 图1所示：
图1 MODWSA求解作业车间低碳调度流程图
MODWSA算法包含了模拟鲸鱼群觅食的行为， MODWSA主要包含了以下 四个步骤：初始化、工序向量更新操作，速度选择寻找“较优且最近”的鲸鱼Y、 应用速度更新操作算子对速度向量进行更新操作，具体步骤如下所示：
Step 1:初始化。首先给出参数设置，如种群大小等，然后随机初始化鲸鱼 群，对鲸鱼群中的每个个体进行适应度评价。
Step 2： 工序更新操作。采用二元锦标赛方法选择父代个体，随机选择母代
个体，对父代与母代的工件序列执行交叉变异等基本操作， 得到子代的工件序列。
Step 3:寻找离父代个体“较优且最近”的鲸鱼。针对速度向量部分，计算 与父代个体最近的较优个体，设定为鲸鱼 丫。
Step 4：速度更新操作。父代个体的速度向量向鲸鱼 丫的速度向量进行迁移 操作生成子代个体的速度向量，使子代个体的速度向量向鲸鱼 丫的速度向量方 向移动。
Step 5:精英保留策略［插入文献］。合并种群大小为N的副本种群和相同大 小的子代种群，这样得到一个大小为 2N的混合种群，评价改混合种群根据非支 配排序和拥挤距离技术选择出前 N个较好的个体作为下一次迭代更新的父本， 并淘汰余下的N个个体。具体操作过程如下图2所示。
:：_一 ：： - - - P+1
G
PG
OG
图2基于非支配排序和拥挤策略的更新操作
1.3.1编码与解码策略
编码方式是MODWSA算法求解调度问题的首要和关键任务。传统的 较多的是基于工序的编码，它具有任意置换染色体后总能得到可行调度、 间表征的完全性能和解码成主动调度等优点
JSP问题中应用
避免死锁、对解空
［插入文献］。对于传统调度问题，加工时间是固
定不变的，但本章所研究的低碳作业车间调度问题的加工时间是可以根据加工机器的速度改 变进行选择的，所以需要处理工件排序和每个工件对应的速度选择两个子任务。 提出了双层编码机制以适应问题的特征， 表示工件的加工顺序，记作
因此，本章
该编码机制包含了两层信息。 第一层基于工序编码，
二，其中每个工件的工序都用相应的工件序号表示，从左到右
扫描序列，工件序号第k次出现，表示加工该工件的第 k道工序；第二层表示每个工件每道 工序的加工速度，记作 N。为了说明这个编码机制，本章给出一个规模为 实例，如下所示：
兀=1,2,1,1,2,2 】
2工件3工序的
N = 1,3,2,3,2,2 1
在这个编码中，-：表示工件每道工序的加工顺序，其中 工件1的第1道工序和工件2的第1道工序之后加工。
二3表示工件1的第2道工序在
N表示工件每道工序的加工速度, 其中N3
表示工件2的第1道工序在对应机器 M21上以速度3进行加工。举例进行说明， 列出加工时间以
及功率消耗。
解码是将编码转化为调度解的过程。
为了将一个解决方案解码成一个可行的时间表， 需
另一个问题是确定每道工序对应机器的 加工速
要解决2个问题。一个问题是安排工件的加工顺序，
度。设u为编码任意一个工件i的第j道工序0门，加工时间为PU，且工序u的开始 加工时间为BTu，则完工时间为 BTu Pu;设工序的工件紧前工序和机器紧前工序分别为
JPu和MFU （如果存在），那么工序u的开始加工时间由它的工件紧前工序和机器紧前工序 中完工时间的最
大值决定。 的计算公式为：
所有工件从0时刻开始加工，在解码过程中工序 u开始加工时间
BTu = max（BTjp FJP >
u
U
ST
MPU
PMP）
U
如果是工件i的第一道工序，则没有紧前工序，则工件 i的第一道工序的开始时间 BTu 计算公式为：
BTu
=
ST
MPU
FMP
U
可以看出转化编码为工序及其速度选择向量后， 可依据上面2公式进行解码，得到该编
码的半主动调度解。此外，本章将一种插入式贪婪解码算法引入到低碳作业车间调度问题， 使编码解码后产生主动调度。该插入式贪婪解码算法解码方法如下：
首先将编码看作工序的有序序列， 根据工序在该序列上的顺序进行解码， 将每道工序按 选择的加工速度插入到该工序加工机器上的最佳可行加工时刻进行加工， 上所有工序都安排在其最佳可行的地方。
（可以举图例进行说明）
按此方式知道序列
1.3.2种群初始化
基于以上的双层编码机制， 一个工序向量和一个速度向量构成。
对种群进行初始化。 基于本章的描述，种群的每一个个体由
其中工序向量由工件和其对应工序决定，
随机生成；速
度向量则根据对应工序的加工机器可选速度，随机生成。
1.3.3工序向量更新操作
对应于编码的2个不同部分一一工序向量和机器加工速度向量， 略来更新编码的2个不同部分。
对应于工序向量部分，采用传统的交叉和变异算子进行操作。交叉算子可以探索解空 间的未知区域。对于解的第一层（即
兀），采用优先操作交叉算子（
本文采用不同的进化策
Precede nee Operation
Crossover， POX）［插入文献］来更新工序向量部分，具体的交叉步骤如下：
Step 1:把所有工件随机分成 2个集合J1和J2，
Step 2：复制父代R包含在J1中的工件到子代 C （保留顺序），
Step 3：复制父代P，包含在J2中的工件到子代 C （保留顺序），得到子代C。
交叉操作示意图如下所示:
Ji={1} ； J2={2,3}
序交叉操作
在变异阶段，从工序向量中选择两个不同工件的任意一道工序，交换其在序列中的位 置。给出变异操作的具体过程实例：
初始的工序向量为
n= (1,2, 1,3, 2, 3)，选择工件1的第
1道工序和工件2的第2道工序(即第1和第5位置点)位置互换，交换后的工序向量变为 n= (2, 2, 1,3, 1,3)。具体的图例如图 4所示：
变异前 1 2 1 3 2 3 ----- — —— 1 3 1 3 变异后
2 2 图4工序变异操作 1.3.4速度向量更新操作
针对速度向量，本研究选择使用 WSA算法中的移动算子来更新速度向量， 算。汉明距离最早在
使种群中每
条鲸鱼的速度向量向离自己“较优且最近”的个体移动。其中选择离的最近的个体需要运用 汉明距离进行计
1950年由Richard W. Hamming ［插入论文］提出来，目
统计数据位发生翻转的错误位数，
因此，其
在编码部分采用
具体计算
的是为了在以定长二进制数进行通信的过程中，
也被叫作信号距离。汉明距离的主要思想是计算两条信息中不同位的个数。 所示：
离散个体编码方案中， 个体之间的距离通过计算速度向量之间的汉明距离来表示, 方法如下图
V1
1 1 2 2 2 3 V2
1 2 2 图5汉明距离计算图例
1 2 4 图中的例子显示，有 3个对应位置速度不同，故此部分的汉明距离
dV是3。
选择“较优且最近” 的个体，即是寻找适应度值较好，且离该鲸鱼汉明距离值最小的个 体Y，原鲸鱼的速度向量向鲸鱼 Y的速度向量方向移动。当不存在“较优且最近”的个体 时候，则通过速度向量自我变异的方式进行移动。
2种移动方式如下所示：
当较优且最近的存在：原鲸鱼的速度向量与鲸鱼
Y的速度向量进行交叉操作。随机选
择2个交叉点，将鲸鱼 Y的速度向量中2个交叉点之间的部分复制到原鲸鱼的速度向 量中，具体交叉操作如图 6所示:
父代 鲸鱼
2 2 1 3 1 1 2 3 厂 鲸鱼Y
1 1 3 2 3 4 子代 鲸鱼
图6速度向量交叉操作
当种群中不存在较优且最近的个体时，
按照变异的方式移动。首先从速度向量中随机选
;然后选择
择一道工序改变其速度值为另一可行的速度值（对应于加工该工序的机器） 使用相同加工机器的 2道工序互换它们的加工速度。具体变异操作如图
7所示:
变异前
2 2 3 1 2 3 r 亠 X — 变异后
2 4 3 3 2 1 图7速度向量变异操作
1.4实验仿真与分析
因篇幅问题不能全部显示，请点此查看更多更全内容