多目标应用：四种多目标优化算法（NSOOA、NSPSO、NSDBO、NSCOA）求解柔性作业车间调度问题(FJSP），MATLAB代码

标签：NSCOA 机器 FJSP NSDBO 算法 jh ... 工件 ldots

一、柔性作业车间调度问题

柔性作业车间调度问题(Flexible Job Scheduling Problem, FJSP) 的描述如下：n个工件 { J , J 2 , . . , J n } \{J,J_2,..,J_n\} {J,J2,..,Jn}要在 m m m 台机器 { M 1 , M 2 , . . , M m } \{M_1,M_2,..,M_m\} {M1,M2,..,Mm} 上加工。每个工件包含一道或多道工序，工序顺序是预先确定的，每道工序可以在多台不同加工机器上进行加工，工序的加工时间随加工机器的不同而不同。调度目标是为每道工序选择最合适的机器、确定每台机器上各个工序的最佳加工顺序以及开工时间，使整个系统的某些性能指标达到最优。因此，柔性作业车间调度问题包含两个子问题：确定各工件的加工机器 (机器选择子问题) 和确定各个机器上的加工先后顺序 (工序排序子问题)。

此外，在加工过程中还需要满足下面的约束条件：
(1) 同一台机器同一时刻只能加工一个工件；
(2) 同一工件的同一道工序在同一时刻只能被一台机器加工；
(3) 每个工件的每道工序一旦开始加工不能中断；
(4) 不同工件之间具有相同的优先级；
(5)不同工件的工序之间没有先后约束，同一工件的工序之间有先后约束；
(6)所有工件在零时刻都可以被加工。

1.1符号描述

n : n: n:工件总数；
m : m: m: 机器总数；
i , e : i,e: i,e: 机器序号， i , e = 1 , 2 , 3 , . . . , m i,e=1,2,3,...,m i,e=1,2,3,...,m ;
j , k : j,k: j,k: 工件序号， j , k = 1 , 2 , 3 , . . . , n ; j,k=1,2,3,...,n; j,k=1,2,3,...,n; h j : h_j: hj:工件 j j j 的工序总数；
h , l : h,l: h,l: 工序序号， h = 1 , 2 , 3 , . . . , h j h=1,2,3,...,h_j h=1,2,3,...,hj ;
Ω j h : \Omega_{jh}: Ωjh:工件 j j j 的第 h h h 道工序的可选加工机器集；
m j h : m_{jh}: mjh:工件 j j j 的第 h h h 道工序的可选加工机器数；
O j h : O_{jh}: Ojh:工件 j j j 的第 h h h道工序；
M i j h : M_{ijh}: Mijh:工件 j j j 的第 h h h道工序在机器 i i i 上加工；
p i j h : p_{ijh}: pijh:工件 j j j的第 h h h道工序在机器 i i i上的加工时间；
s j h : s_{jh}: sjh:工件 j j j 的第 h h h 道工序加工开始时间；
c j h : c_{jh}: cjh:工件 j j j的第 h h h道工序加工完成时间；
d j : d_j: dj:工件 j j j 的交货期；
L L L: 一个足够大的正数；
C j C_j Cj: 每个工件的完成时间；
C max ⁡ : C_{\max}: Cmax: 最大完工时间；
T o : T o = ∑ j = 1 n h j T_o:\quad T_o=\sum_{j=1}^nh_j To:To=∑j=1nhj, 所有工件工序总数；
x i j h = { 1 , 如果工序 O j h 选择机器 i ; 0 , 否则； x_{ijh}=\begin{cases}1,\text{如果工序}O_{jh}\text{选择机器}i;\\0,\text{否则；}\end{cases} xijh={1,如果工序Ojh选择机器i;0,否则；
y i j h k l = { 1 , 如果 O i j h 先于 O i k l 加工 ; 0 , 否则 ; y_{ijhkl}=\begin{cases}1,\text{如果}O_{ijh}\text{先于}O_{ikl}\text{加工};\\0,\text{否则};\end{cases} yijhkl={1,如果Oijh先于Oikl加工;0,否则;

1.2约束条件

C 1 : s j h + x i j h × p i j h ≤ c j h C_{1}:s_{jh}+x_{ijh}\times p_{ijh}\leq c_{jh} C1:sjh+xijh×pijh≤cjh

其中： i = 1 , … , m ; j = 1 , … , n ; i=1,\ldots,m;j=1,\ldots,n; i=1,…,m;j=1,…,n; h = 1 , … , h j h=1,\ldots,h_j h=1,…,hj
C 2 : c j h ≤ s j ( h + 1 ) C_{2}:c_{jh}\leq s_{j(h+1)} C2:cjh≤sj(h+1)
其中 : j = 1 , … , n ; h = 1 , . . . , h j − 1 :j=1,\ldots,n;h=1,...,h_j-1 :j=1,…,n;h=1,...,hj−1
C 3 : c j h j ≤ C max ⁡ C_{3}:c_{jh_j}\leq C_{\max} C3:cjhj≤Cmax
其中： j = 1 , . . . , n j=1,...,n j=1,...,n
C 4 : s j h + p i j h ≤ s k l + L ( 1 − y i j h k l ) C_{4}:s_{jh}+p_{ijh}\leq s_{kl}+L(1-y_{ijhkl}) C4:sjh+pijh≤skl+L(1−yijhkl)

其中 : j = 0 , … , n ; k = 1 , … , n ; h = 1 , … , h j ; l = 1 , … , h k ; i = 1 , … , m :j=0,\ldots,n;k=1,\ldots,n;h=1,\ldots,h_j;l=1,\ldots,h_k;i=1,\ldots,m :j=0,…,n;k=1,…,n;h=1,…,hj;l=1,…,hk;i=1,…,m
C 5 : c j h ≤ s j ( h + 1 ) + L ( 1 − y i k l j ( h + 1 ) ) C_{5}:c_{jh}\leq s_{j(h+1)}+L(1-y_{iklj(h+1)}) C5:cjh≤sj(h+1)+L(1−yiklj(h+1))

其中 : j = 1 , … , n ; k = 0 , … , n ; h = 1 , … , h j − 1 ; l = 1 , … , h k ; i = 1 , … , m :j=1,\ldots,n;k=0,\ldots,n;h=1,\ldots,h_j-1;\quad l=1,\ldots,h_k;\quad i=1,\ldots,m :j=1,…,n;k=0,…,n;h=1,…,hj−1;l=1,…,hk;i=1,…,m
h 1 : ∑ i = 1 m j h x i j h = 1 h_{1}:\sum_{i=1}^{m_{jh}}x_{ijh}=1 h1:∑i=1mjhxijh=1
其中： h = 1 , . . . , h j ; j = 1 , . . . , n ; h=1,...,h_j;j=1,...,n; h=1,...,hj;j=1,...,n;

h 2 : ∑ j = 1 n ∑ h = 1 h j y i j h k l = x i k l h_{2}:\sum_{j=1}^n\sum_{h=1}^{h_j}y_{ijhkl}=x_{ikl} h2:∑j=1n∑h=1hjyijhkl=xikl

其中： i = 1 , … , m ; k = 1 , … , n ; l = 1 , … , h k i=1,\ldots,m;k=1,\ldots,n;l=1,\ldots,h_k i=1,…,m;k=1,…,n;l=1,…,hk
h 3 : ∑ i = 1 n ∑ i = 1 n k y i j h k l = x i j h h_{3}:\sum_{i=1}^n\sum_{i=1}^{n_k}y_{ijhkl}=x_{ijh} h3:∑i=1n∑i=1nkyijhkl=xijh

其中： i = 1 , … , m ; j = 1 , … , n ; h = 1 , … , h k i=1,\ldots,m;j=1,\ldots,n;\quad h=1,\ldots,h_k i=1,…,m;j=1,…,n;h=1,…,hk
C 6 : s j h ≥ 0 , c j h ≥ 0 C_{6}:s_{jh}\geq0,c_{jh}\geq0 C6:sjh≥0,cjh≥0

其中 : j = 0 , 1 , . . . , n ; h = 1 , . . . , h j :j=0,1,...,n;h=1,...,h_j :j=0,1,...,n;h=1,...,hj

C 1 C_{1} C1和 C 2 C_{2} C2表示每一个工件的工序先后顺序约束 ;
C 3 C_{3} C3表示工件的完工时间的约束,即每一个工件的完工时间不可能超过总的完工时间 ;
C 4 C_{4} C4和 C 5 C_{5} C5表示同一时刻同一台机器只能加工一道工序 ;
h 1 h_{1} h1表示机器约束,即同一时刻同一道工序只能且仅能被一台机器加工;
h 2 h_{2} h2和 h 3 h_{3} h3表示存在每一台机器上可以存在循环操作 ;
C 6 C_{6} C6表示各个参数变量必须是正数。

1.3目标函数

(1) 最大完工时间最小。

完工时间是每个工件最后一道工序完成的时间，其中最大的那个时间就是最大完工时间(makespan)。它是衡量调度方案的最根本指标，主要体现车间的生产效率，也是 FJSP 研究中应用最广泛的评价指标之一。如下式所示：

f 1 = min ⁡ ( max ⁡ l ≤ j ≤ n ( C j ) ) f_1=\min(\max_{\mathrm{l\leq}j\leq n}(C_j)) f1=min(maxl≤j≤n(Cj))

(2)机器最大负荷最小。

在 FJSP 求解中，存在选择机器的过程，各个机器的负荷随着不同的调度方案而不同。负荷最大的机器就是瓶颈设备，为提高每台机器的利用率，必须使得各台机器的负荷尽量小且平衡。如下式所示：

f 2 = min ⁡ ( max ⁡ l ≤ i ≤ m ∑ j = 1 n ∑ h = 1 h j p i j h x i j h ) f_2=\min(\max_{\mathrm{l\leq}i\leq m}\sum_{j=1}^n\sum_{h=1}^{h_j}p_{ijh}x_{ijh}) f2=min(maxl≤i≤m∑j=1n∑h=1hjpijhxijh)

(3)总机器负荷最小。

工序在不同机器上的加工时间是不同的，那么总的机器负荷随着不同的调度方案而不同。尽量使最大完工时间一样的情况下，减少所有机器的总消耗。如下式所示：

f 3 = min ⁡ ( ∑ i = 1 m ∑ j = 1 n ∑ h = 1 h j p i j h x i j h ) f_3=\min(\sum_{i=1}^m\sum_{j=1}^n\sum_{h=1}^{h_j}p_{ijh}x_{ijh}) f3=min(∑i=1m∑j=1n∑h=1hjpijhxijh)
参考文献：
[1]张国辉.柔性作业车间调度方法研究[D].华中科技大学,2009.

二、四种多目标优化算法（NSOOA、NSPSO、NSDBO、NSCOA）介绍

非支配鱼鹰优化算法 (NSOOA, Non-dominated Sorting Osprey Optimization Algorithm):
- 原理: 鱼鹰优化算法（Osprey Optimization Algorithm, OOA）是一种模拟鱼鹰捕食行为的算法。它通过模拟鱼鹰在水面上盘旋、俯冲和捕食的行为来搜索最优解。非支配排序被用于生成Pareto前沿，以确保解的多样性和优化目标的平衡。
- 特点: 算法能够快速收敛到全局最优解，并且能够保持解的多样性，适合解决多目标优化问题。
非支配粒子群优化算法 (NSPSO, Non-dominated Sorting Particle Swarm Optimization):
- 原理: 粒子群优化算法（Particle Swarm Optimization, PSO）是一种模拟鸟群或鱼群的社会行为的算法。NSPSO结合了非支配排序和粒子群优化算法，通过粒子间的信息共享和个体学习来优化多目标问题。
- 特点: 算法具有良好的全局搜索能力和快速收敛性，同时能够保持解的多样性。
非支配蜣螂优化算法 (NSDBO, Non-dominated Sorting Dung Beetle Optimization):
- 原理: 蜣螂优化算法（Dung Beetle Optimization, DBO）是一种模拟蜣螂滚球行为的算法。它通过模拟蜣螂寻找食物、滚球和避障的行为来搜索最优解。非支配排序用于生成Pareto前沿，以确保解的多样性和优化目标的平衡。
- 特点: 算法具有较强的局部搜索能力和逃逸局部最优的能力，适合解决复杂的多目标优化问题。
非支配小龙虾优化算法 (NSCOA, Non-dominated Sorting Crayfish Optimization Algorithm):
- 原理: 小龙虾优化算法（Crayfish Optimization Algorithm, COA）是一种模拟小龙虾觅食和逃避捕食者行为的算法。它通过模拟小龙虾的觅食路径和逃避策略来搜索最优解。非支配排序用于生成Pareto前沿，以确保解的多样性和优化目标的平衡。
- 特点: 算法具有良好的探索能力和适应性，能够适应不同的优化问题，并且能够保持解的多样性。

三、四种算法求解FJSP

四种算法求解FJSP，以最大完工时间最小、机器最大负荷最小、总机器负荷最小为目标函数。

3.1部分代码

%% 算法求解
%% 算法求解
R(1).Result = NSOOA(MachineNum,jobNum,jobInfo,operaNumVec,candidateMachine,energy);
R(2).Result = NSPSO(MachineNum,jobNum,jobInfo,operaNumVec,candidateMachine,energy);
R(3).Result = NSDBO(MachineNum,jobNum,jobInfo,operaNumVec,candidateMachine,energy);
R(4).Result = NSCOA(MachineNum,jobNum,jobInfo,operaNumVec,candidateMachine,energy);
%% Pareto解
Strcol={'r*','go','bs','k>'};
NameAlgorith={'NSOOA','NSPSO','NSDBO','NSCOA'};
figure(1)
for i=1:4
    scatter3(R(i).Result.obj_matrix(:,1), R(i).Result.obj_matrix(:,2), R(i).Result.obj_matrix(:,3),50,Strcol{i})
    hold on
end
xlabel('最大完工时间'); ylabel('总能耗'); zlabel('总成本', 'Rotation', 90)
legend(NameAlgorith)