一、柔性作业车间调度问题
柔性作业车间调度问题(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.
二、基于非支配排序的蜣螂优化算法
基于非支配排序的蜣螂优化算法（Non-Dominated Sorting Dung beetle optimizer，NSDBO）原理介绍：
NSDBO原理
三、NSDBO求解FJSP
NSDBO求解FJSP，以最大完工时间最小、机器最大负荷最小、总机器负荷最小为目标函数。
3.1部分代码
%% 基于非支配排序的蜣螂优化算法
Result = NSDBO(MachineNum,jobNum,jobInfo,operaNumVec,candidateMachine,energy);
%% Pareto解
figure(1)
scatter3(Result.obj_matrix(:,1), Result.obj_matrix(:,2), Result.obj_matrix(:,3),150,'rp','filled')
xlabel('最大完工时间'); ylabel('机器最大负荷'); zlabel('总机器负荷', 'Rotation', 90)
legend('NSDBO')
3.2部分结果
以Mk01数据集为例：
四、完整MATLAB代码
见下方名片
标签：...,Non,机器,Dominated,beetle,ijh,jh,工件,ldots From： https://blog.csdn.net/weixin_46204734/article/details/137206857