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

柔性作业车间调度问题（Flexible Job Shop Scheduling Problem，FJSP），是一种经典的组合优化问题。在FJSP问题中，有多个作业需要在多个机器上进行加工，每个作业由一系列工序组成，每个工序需要在特定的机器上完成。同时，每个机器一次只能处理一个工序，且每个工序的处理时间可能不同。FJSP问题的目标是找到一个最优的作业调度方案，使得所有作业的完成时间最小化。这个问题的难点在于需要考虑到多个作业、多个机器和多个工序之间的复杂关系，并且需要在有限的时间内找到最优解。
柔性作业车间调度问题( FJSP) 的描述如下：n个工件 { J , J 2 , . . , J n } \{J,J_2,..,J_n\} {J,J2​,..,Jn​}要在$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:$工件总数；
$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:T_o={\sum }_{j=1}^n{h}_j$, 所有工件工序总数；
$x_{ijh}=\{\begin{array}{l}1,\text{如果工序}{O}_{jh}\text{选择机器}i;\\ 0,\text{否则；}\end{array}$
$y_{ijhkl}=\{\begin{array}{l}1,\text{如果}{O}_{ijh}\text{先于}{O}_{ikl}\text{加工};\\ 0,\text{否则};\end{array}$

1.2约束条件

$C_1:s_{jh}+x_{ijh}\times p_{ijh}\le c_{jh}$

其中：$i=1,\dots ,m;j=1,\dots ,n;$ $h=1,\dots ,h_j$
$C_2:c_{jh}\le s_{j(h+1)}$
其中$:j=$