FJSP：粒子群优化算法PSO求解柔性作业车间调度问题（FJSP），提供MATLAB代码

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

柔性作业车间调度问题（Flexible Job Shop Scheduling Problem，FJSP），是一种经典的组合优化问题。在FJSP问题中，有多个作业需要在多个机器上进行加工，每个作业由一系列工序组成，每个工序需要在特定的机器上完成。同时，每个机器一次只能处理一个工序，且每个工序的处理时间可能不同。FJSP问题的目标是找到一个最优的作业调度方案，使得所有作业的完成时间最小化。这个问题的难点在于需要考虑到多个作业、多个机器和多个工序之间的复杂关系，并且需要在有限的时间内找到最优解。
柔性作业车间调度问题( FJSP) 的描述如下：n个工件 ${J,J_2,..,J_n\}$ 要在 $m$ 台机器 ${M_1,M_2,..,M_m\}$ 上加工。每个工件包含一道或多道工序，工序顺序是预先确定的，每道工序可以在多台不同加工机器上进行加工，工序的加工时间随加工机器的不同而不同。调度目标是为每道工序选择最合适的机器、确定每台机器上各个工序的最佳加工顺序以及开工时间，使整个系统的某些性能指标达到最优。因此，柔性作业车间调度问题包含两个子问题：确定各工件的加工机器 (机器选择子问题) 和确定各个机器上的加工先后顺序 (工序排序子问题)。

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

1.1符号描述

$n :$ 工件总数；
$m :$ 机器总数；
$i, e :$ 机器序号， $i, e = 1, 2, 3, ..., m$ ;
$j, k :$ 工件序号， $j, k = 1, 2, 3, ..., n;$ $h_j:$ 工件 $j$ 的工序总数；
$h, l :$ 工序序号， $h=1,2,3,...,h_j$ ;
$\Omega_{jh}:$ 工件 $j$ 的第 $h$ 道工序的可选加工机器集；
$m_{jh}:$ 工件 $j$ 的第 $h$ 道工序的可选加工机器数；
$O_{jh}:$ 工件 $j$ 的第 $h$ 道工序；
$M_{ijh}:$ 工件 $j$ 的第 $h$ 道工序在机器 $i$ 上加工；
$p_{ijh}:$ 工件 $j$ 的第 $h$ 道工序在机器 $i$ 上的加工时间；
$s_{jh}:$ 工件 $j$ 的第 $h$ 道工序加工开始时间；
$c_{jh}:$ 工件 $j$ 的第 $h$ 道工序加工完成时间；
$d_j:$ 工件 $j$ 的交货期；
$L$ : 一个足够大的正数；
$C_j$ : 每个工件的完成时间；
$C_{\max}:$ 最大完工时间；
$T_o:\quad T_o=\sum_{j=1}^nh_j$ , 所有工件工序总数；
$x_{ijh}=\begin{cases}1,\text{如果工序}O_{jh}\text{选择机器}i;\\0,\text{否则；}\end{cases}$
$y_{ijhkl}=\begin{cases}1,\text{如果}O_{ijh}\text{先于}O_{ikl}\text{加工};\\0,\text{否则};\end{cases}$

1.2约束条件

$C_{1}:s_{jh}+x_{ijh}\times p_{ijh}\leq c_{jh}$

其中： $i=1,\ldots,m;j=1,\ldots,n;$ $h=1,\ldots,h_j$
$C_{2}:c_{jh}\leq s_{j(h+1)}$
其中 $:j=1,\ldots,n;h=1,...,h_j-1$
$C_{3}:c_{jh_j}\leq C_{\max}$
其中： $j = 1, ..., n$
$C_{4}:s_{jh}+p_{ijh}\leq s_{kl}+L(1-y_{ijhkl})$

其中 $:j=0,\ldots,n;k=1,\ldots,n;h=1,\ldots,h_j;l=1,\ldots,h_k;i=1,\ldots,m$
$C_{5}:c_{jh}\leq s_{j(h+1)}+L(1-y_{iklj(h+1)})$

其中 $: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$
$h_{1}:\sum_{i=1}^{m_{jh}}x_{ijh}=1$
其中： $h=1,...,h_j;j=1,...,n;$

$h_{2}:\sum_{j=1}^n\sum_{h=1}^{h_j}y_{ijhkl}=x_{ikl}$

其中： $i=1,\ldots,m;k=1,\ldots,n;l=1,\ldots,h_k$
$h_{3}:\sum_{i=1}^n\sum_{i=1}^{n_k}y_{ijhkl}=x_{ijh}$

其中： $i=1,\ldots,m;j=1,\ldots,n;\quad h=1,\ldots,h_k$
$C_{6}:s_{jh}\geq0,c_{jh}\geq0$

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

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

1.3目标函数

FJSP的目标函数是最大完工时间最小。完工时间是每个工件最后一道工序完成的时间，其中最大的那个时间就是最大完工时间(makespan)。它是衡量调度方案的最根本指标，主要体现车间的生产效率，如下式所示：

$f=\min(\max_{\mathrm{l\leq}j\leq n}(C_j))$

参考文献：
[1]张国辉.柔性作业车间调度方法研究[D].华中科技大学,2009.

二、算法简介

粒子群优化算法是一种基于群体智能的优化算法，它模拟了鸟群捕食时的行为，利用群体中的个体通过信息共享和合作来寻找最优解。该算法具有全局搜索能力、高效性和易于实现等优点。

算法流程如下：

初始化：随机生成一定数量的粒子，并给每个粒子随机赋予一个初始速度和位置。
适应度计算：对于每个粒子，计算其适应度值。
更新个体最优解：将每个粒子当前的位置与其历史最优位置进行比较，更新个体最优解。
更新群体最优解：将所有粒子的历史最优位置进行比较，更新群体最优解。
更新速度和位置：通过当前位置、历史最优位置以及群体最优位置来更新粒子的速度和位置。
终止条件检测：当满足预设的终止条件时，算法停止，否则回到第2步。

三、算法求解FJSP

3.1部分代码

dim=2*sum(operaNumVec);
LB = -jobNum * ones(1, dim);
UB = jobNum * ones(1, dim);
Max_iteration = 100;
SearchAgents_no = 100;
fobj=@(x)fitness(x, MachineNum,jobNum,jobInfo,operaNumVec,candidateMachine);

%% 优化算法求解FJSP
[fMin , bestX, Convergence_curve ] = pso(SearchAgents_no,Max_iteration,LB,UB,dim,fobj);
machineTable=GetMachineTable(bestX, MachineNum,jobNum,jobInfo,operaNumVec,candidateMachine);

%% 画收敛曲线图
figure
plot(Convergence_curve,'r-','linewidth',2)
xlabel('迭代次数')
ylabel('最大完工时间')
legend('pso')
saveas(gca,'1.jpg');