文献阅读笔记

文章来源

项目	内容
论文名称	《求解柔性作业车间调度的一种新邻域结构》
期刊名称	《系统工程理论与实践》
作者名字	黄学文
作者学校	大连理工大学(经济管理学院)

摘要

针对FJSP问题，提出一种新的邻域结构，这种结构能够保证任意一次邻域移动可以改进当前解，从而显著缩小了邻域规模。在禁忌搜索算法种设计了基于该邻域结构的两级搜索策略，该策略既增加了邻域搜索的有效性，又保证了最优解的连通性。最后，测试，结果证明了新邻域结构的有效性。

1 引言

求解方法	特点
数学规划为代表的精确算法	可精确求解，但计算复杂性高，故只对小规模问题有效
启发式算法	近似算法，在合理的时间内求得问题的近似最优解

禁忌搜索
禁忌搜索从一个初始解 出 发， 基于 一定 的邻域结构 ， 不断地进行移动 以 寻找更好的解， 达到 终止条件后将寻找 到 的最优解作为 问 题的 最终解． 其 中 ， 邻域结构是一种通过在 当 前解 中进行一次移动得到 另 一个解 （ 邻域解） 的机制 ， 其性能直接影 响 禁忌搜索 的求解质量和有效性． 邻域结构 的性能取决于邻域结构是否具备连通性 （ 即 从任意一个初始解 出 发， 通过有限次的 移动 可达到 问 题的最优解） 和邻域规模的大小 ． 因 此， 设计邻域结构 的关键 问 题是在保证连 通性的基础上， 通过删 除不可行和 非 改进的移动以缩小邻域规模， 从而提高搜索效率。

邻域结构分为两类
求解FJSP问 题的邻域结构可分为两类， 这两类领域结构都是基于Balas的研究结论， 即移动非关键工序不能减少关键路径的长度。

第一类邻域结构可改变工序在机器上的加工顺序

第一类邻域结构	描述
N1	将邻域移动定义为交换同一台机器上加工的两个相邻关键工序（N1具备连通性，但邻域规模大，且包含了大量非改进的移动）
N2	在Ｎ１的基础上，増加了严格的移动约束条件，提出了Ｎ；Ｎ２缩小了邻域规模， 但不具备连通性．
N3	Ｎ ３ 允许同时交换多个相邻工序，且被证明包含 了Ｎｌ ；Ｎ３虽然具备连通性，但邻域规模更加庞大．
块的概念	块是关键路径上由同一台机器加工的相邻关键 工序的最大工序序列 ，其 中 ， 块中的第一道工序称为块首工序，最后一道工序称为块尾工序， 其余的工序为块内工序 ． 基于交换块内任意工序的加工顺序不能减小关键路径长度的结论
N4	在保证邻域解可行的基础上， 将块内的工序尽可能地往块首或块尾移动
N5	在Ｎ４的基础上提出了Ｎ５，即 交换关键路径上块首或块尾两个相邻工序 ；Ｎ５显著缩小了邻域规模，但不具备连通性．
N6	即将内部工序向块首之前或块尾之后移动 ；Ｎ６ 缩小 了 邻域规模且保证了连通性． 目前，Ｎ６已成为求解 ＪＳＰ 和ＦＪＳＰ 问题最有效的邻域结 构之一．

第二类邻域结构可同时改变工序的加工机器和工序在机器上的加工顺序，其基本思想是从当前解中移除一个关键工序，再将其插入到合适的位置，以获得邻域解

第二类邻域结构
Ｄ ＆ ｆ和 Ｐ 提 出 了 求解 ＦＪＳＰ问 题的一种邻域结构 ，并保证任意邻域解对应于一个可行调度， 但其邻域规模较大
随后 ， Ｍ 和 Ｇ 通过定义工序的最佳插入 区 间 ， 提出 了 求解 ＦＪＳＰ 问题的改进邻域结构 ， 即 Ｍ＆Ｇ 邻域结构 ， 该邻域结构既具备连通性， 又显著缩小了邻域规模．

2 问题描述

2.1 问题定义

2.2 调度的析取图描述

析取图定义为：
G = ( N , A , E ) G=(N,A,E) G=(N,A,E)
N是所有工序节点和两个虚拟节点（0和#）的集合
N = { O i j ∣ i = 1 , 2 , ⋅ ⋅ ⋅ ⋅ ⋅ n ; 1 ≤ j ≤ n i } ∪ { 0 , # } N=\{O_{ij}|i=1,2,·····n;1 \leq j\leq n_i \} \cup \{ 0, {\\\#} \} N={Oij​∣i=1,2,⋅⋅⋅⋅⋅n;1≤j≤ni​}∪{0,#}
A表示同一工件的两道连续工序之间的合取弧的集合，反映了任意工件的工序之间的顺序约束关系
A = { O i j , O i , j + 1 ∣ i = 1 , 2 , ⋅ ⋅ ⋅ ⋅ , n ; 1 ≤ j ≤ n i − 1 } ∪ { ( 0 , O i 1 ) , ( O i n i , # ) ∣ i = 1 , 2 , ⋅ ⋅ ⋅ ⋅ , n } A=\{O_{ij},O_{i,j+1}|i=1,2,····,n;1\leq j\leq n_i-1 \}\cup \{(0,O_{i1}) ,(O_{in_i},{\\\#})|i=1,2,····,n\} A={Oij​,Oi,j+1​∣i=1,2,⋅⋅⋅⋅,n;1≤j≤ni​−1}∪{(0,Oi1​),(Oini​​,#)∣i=1,2,⋅⋅⋅⋅,n}
E表示同一台机器上加工的相邻两道工序之间析取弧的集合，反映了每台机器上的工序加工顺序和加工序列；
对于任意一道工序 ω \omega ω,将它所在机器 M k M_k Mk​上的加工时间 p ω k p_{\omega k} pωk​标记在该节点的下方，视为节点的权重（ p ω k > 0 ; p 0 = p # = 0 p_{\omega k} \gt0;p_0=p_{\\\\\#}=0 pωk​>0;p0​=p#​=0）,当工序 ω \omega ω的加工机器是确定的， p ω k p_{\omega k} pωk​可简写为 p ω p_{\omega } pω​.
当且仅当析取图G中不存在任何回路时，图G对应于一个可行的调度。
在析取图中，路径（ ω 1 \omega_1 ω1​, ω 2 \omega_2 ω2​, ω 3 \omega_3 ω3​,···· ω q \omega_q ωq​）的长度等于工序 ω 1 \omega_1 ω1​到工序 ω q \omega_q ωq​之间所有工序加工时间（相应节点的权重）的总和，即 ∑ i = 2 q − 1 p ω i \sum_{i=2}^{q-1}p_{\omega i} ∑i=2q−1​pωi​.
L ( i , j ) L(i,j) L(i,j)表示工序i到工序j之间最长路径的长度， L ( 0 , ω ) L(0,\omega) L(0,ω)和 L ( ω , # ) L({\omega},{\\\#}) L(ω,#)分别表示工序 ω \omega ω的头时间 ( r ω ) (r_{\omega}) (rω​)和尾时间 ( t ω ) (t_{\omega}) (tω​).
析取图G中从开始节点到结束节点的最长路径成为关键路径，在关键路径上出现的工序称为关键工序，用 L ( 0 , # ) L(0,{\\\#}) L(0,#)表示析取图G中关键路径的长度。

显然：
图G所对应的调度的最大完工时间 C m a x ( G ) = L ( 0 , # ) C_{max}(G) = L(0,{\\\#}) Cmax​(G)=L(0,#)
对于任意的一道工序 ω \omega ω,有 C m a x ( G ) = r ω + p ω k + t w C_{max}(G)=r_{\omega}+p_{\omega k}+t_w Cmax​(G)=rω​+pωk​+tw​
上图中，关键路径的长度为5，即最大完工时间 C m a x ( G ) = 5 C_{max}(G) = 5 Cmax​(G)=5,且存在两条关键路径，分别是 0 ⇒ O 21 ⇒ O 22 ⇒ O 23 ⇒ # 0\Rightarrow{O_{21}}\Rightarrow{O_{22}}\Rightarrow{O_{23}}\Rightarrow{\\\#} 0⇒O21​⇒O22​⇒O23​⇒#， 0 ⇒ O 31 ⇒ O 23 ⇒ # 0\Rightarrow{O_{31}}\Rightarrow{O_{23}}\Rightarrow{\\\#} 0⇒O31​⇒O23​⇒#，工序 O 21 , O 22 , O 23 和 O 31 O_{21},O_{22},O_{23}和O_{31} O21​,O22​,O23​和O31​是关键工序。
工序 ω \omega ω的工件前继工序 J P [ ω ] JP[\omega] JP[ω](工件后继工序 J S [ ω ] JS[\omega] JS[ω])
工序 ω \omega ω的机器前继工序 M P [ ω ] MP[\omega] MP[ω](机器后继工序 M S [ ω ] MS[\omega] MS[ω])
在析取图G中，对于任意工序 ω ( ω ∈ N − { 0 , # } ) \omega \bigl({\omega}\in {N-\{0,\\\#\}}\bigr) ω(ω∈N−{0,#}),有：
r w = m a x { r J P [ ω ] + p J P [ ω ] , r M P [ ω ] + p M P [ ω ] } r_w=max\{r_{JP[\\\omega]} + p_{JP[\\\omega]},r_{MP[\\\omega]} + p_{MP[\\\omega]} \} rw​=max{rJP[ω]​+pJP[ω]​,rMP[ω]​+pMP[ω]​}
t w = m a x { t J S [ ω ] + p J S [ ω ] , t M S [ ω ] + p M S [ ω ] } t_w=max\{t_{JS[\\\omega]} + p_{JS[\\\omega]},t_{MS[\\\omega]} + p_{MS[\\\omega]} \} tw​=max{tJS[ω]​+pJS[ω]​,tMS[ω]​+pMS[ω]​}
E S ( ω ) ES({\\\omega}) ES(ω)表示工序 ω \omega ω在图 G G G中的最早开始时间：
E S ( ω ) = r w ES({\\\omega}) = r_w ES(ω)=rw​
L S ( ω ) LS({\\\omega}) LS(ω)表示工序 ω \omega ω在图 G G G中的最晚开始时间：
L S ( ω ) = C m a x ( G ) − ( t w + p w k ) LS({\\\omega}) = C_{max}(G)-(t_w+p_{wk}) LS(ω)=Cmax​(G)−(tw​+pwk​)
E C ( ω ) EC({\\\omega}) EC(ω)表示工序 ω \omega ω在图 G G G中的最早结束时间：
E C ( ω ) = r w + p ω k EC({\\\omega}) = r_w+p_{\\\omega k} EC(ω)=rw​+pωk​
L C ( ω ) LC({\\\omega}) LC(ω)表示工序 ω \omega ω在图 G G G中的最晚结束时间：
L C ( ω ) = C m a x ( G ) − t w LC({\\\omega}) = C_{max}(G)-t_w LC(ω)=Cmax​(G)−tw​
当且仅当 E S ( ω ) ES({\\\omega}) ES(ω) = L S ( ω ) LS({\\\omega}) LS(ω)成立时，工序 ω {\\\omega} ω时图 G G G上的关键工序

3 一种新的邻域结构

本节提出的邻域结构属于求解FJSP问题的第二类邻域结构，其所寻找的邻域解总能改变当前解。

3.1 移动一道工序

求解FJSP问题的第二类邻域结构是通过移动调度对应的析取图中的某道关键工序实现的，移动一道关键工序 ω \omega ω的步骤如下：
step1：移除与节点 ω \omega ω相关的所有析取弧，即：将工序 ω {\omega} ω从当前机器的加工序列中移除，并将 ω {\omega} ω权重设为0；
step2：假设将工序 ω {\omega} ω分配给某可选机器 M k ′ M_{k_{'}} Mk′​​,并插入到 M k ′ M_{k_{'}} Mk′​​上的析取弧 ( i , j ) (i,j) (i,j)之间 ( i , j ∈ N ) (i,j\in{N}) (i,j∈N),即：将 M k ′ M_{k_{'}} Mk′​​上的析取弧 ( i , j ) (i,j) (i,j)更改为析取弧 ( i , ω ) (i,\omega) (i,ω)和 ( ω , j ) (\omega,j) (ω,j),并将节点 ω \omega ω的权重设置为 p ω k ′ p_{{\omega}{k_{'}}} pωk′​​.

3.2 有效插入区间（弧）的识别

对于任意一个调度 S S S(对应析取图为 G G G),若通过一个移动得到一个改进解 S ′ S{'} S′(对应析取图为 G ′ G{'} G′,则需满足以下任意一个条件：
( 1 ) (1) (1)图 G ′ G{'} G′ 中的关键路径小于图 G G G中的关键路径的长度，即 C m a x ( G ′ ) < C m a x ( G ) C_{max}(G'){\lt}C_{max}(G) Cmax​(G′)<Cmax​(G);
( 2 ) (2) (2) C m a x ( G ′ ) = C m a x ( G ) C_{max}(G')=C_{max}(G) Cmax​(G′)=Cmax​(G),且图 G ′ G' G′中的关键路径数量小于图 G G G中的关键路径的数量.

定理1：对于一个可行解 S S S(对应析取图为 G G G),弧 ( i , j ) (i,j) (i,j)是关键工序 ω {\omega} ω在某可选机器 M k ′ ( M k ′ ∈ M ) M_{k'}(M_{k'}{\in}M) Mk′​(Mk′​∈M)上的某析取弧，若同时满足以下两个条件，则将工序 ω {\omega} ω移动到工序 i i i和工序 j j j之间所得到的邻域解 S ′ S' S′为可行解：
( 1 ） r i < r J S [ ω ] + p J S [ ω ] (1）r_i{\lt}r_{JS[{\omega}]}+p_{JS[{\omega}]} (1）ri​<rJS[ω]​+pJS[ω]​
( 2 ） r j + p j > r J P [ ω ] (2）r_j+p_j{\gt}r_{JP[{\omega}]} (2）rj​+pj​>rJP[ω]​
定理2：对于一个可行解 S S S(对应析取图为 G G G),弧 ( i , j ) (i,j) (i,j)是关键工序 ω {\omega} ω在某可选机器 M k ′ ( M k ′ ∈ M ) M_{k'}(M_{k'}{\in}M) Mk′​(Mk′​∈M)上的某析取弧，若同时满足以下两个条件，则将工序 ω {\omega} ω移动到工序 i i i和工序 j j j之间所得到的邻域解 S ′ S' S′（对应析取图为 G ′ G' G′）不增加图 G G G的最大完工时间 C m a x ( G ) C_{max}(G) Cmax​(G)：
( 1 ) 邻 域 解 S ′ 是 一 个 可 行 解 ； (1)邻域解S'是一个可行解； (1)邻域解S′是一个可行解；
( 2 ) m a x { r i − + p i k ′ , r ω − } + p ω k ′ + m a x { t j − + p j k ′ , t ω − } ≤ C m a x ( G ) (2)max\{r^-_i + p_{ik'},r^-_{\omega} \}+p_{\omega k'} + max\{t^-_j + p_{jk'},t^-_{\omega} \} \le C_{max}(G) (2)max{ri−​+pik′​,rω−​}+pωk′​+max{tj−​+pjk′​,tω−​}≤Cmax​(G)
定理3：若定理2中的条件（2）取严格不等式，即 m a x { r i − + p i k ′ , r ω − } + p ω k ′ + m a x { t j − + p j k ′ , t ω − } < C m a x ( G ) max\{r^-_i + p_{ik'},r^-_{\omega} \}+p_{\omega k'} + max\{t^-_j + p_{jk'},t^-_{\omega} \} {\lt} C_{max}(G) max{ri−​+pik′​,rω−​}+pωk′​+max{tj−​+pjk′​,tω−​}<Cmax​(G),则邻域解 S ′ S' S′是当前解的 S S S的改进解.
推论1：对于一个可行解 S S S(对应析取图为 G G G），弧 ( i , j ) (i,j) (i,j)是关键工序 ω {\omega} ω在某可选机器 M K ′ ( M K ′ ∈ M ) M_{K'}(M_{K'} \in M) MK′​(MK′​∈M)上的某析取弧，若同时满足以下两个条件，则将关键工序 ω {\omega} ω移动到工序 i i i和工序 j j j之间所得到的邻域解 S ′ S' S′(对应析取图为 G ′ G' G′）可以改进当前解 S S S:
( 1 ) 邻 域 解 S ′ 是 一 个 可 行 解 ； (1)邻域解S'是一个可行解； (1)邻域解S′是一个可行解；
( 2 ) { E C ( i ) − , E L S ( j ) − } ∩ { E C ( J P [ ω ] ) − , E L S ( J S [ ω ] ) − } > p ω k ′ (2)\{EC(i)^-,ELS(j)^-\}\cap\{EC(JP[{\omega}])^-,ELS(JS[{\omega}])^-\}\gt p_{\omega k'} (2){EC(i)−,ELS(j)−}∩{EC(JP[ω])−,ELS(JS[ω])−}>pωk′​
定理4：对于一个可行解 S S S(对应析取图为 G G G），弧 ( i , j ) (i,j) (i,j)是关键工序 ω {\omega} ω在某可选机器 M K ′ ( M K ′ ∈ M ) M_{K'}(M_{K'} \in M) MK′​(MK′​∈M)上的某析取弧，若同时满足以下两个条件，则将关键工序 ω {\omega} ω移动到工序 i i i和工序 j j j之间所得到的邻域解 S ′ S' S′(对应析取图为 G ′ G' G′）可以改进当前解 S S S:
( 1 ) 邻 域 解 S ′ 是 一 个 可 行 解 ； (1)邻域解S'是一个可行解； (1)邻域解S′是一个可行解；
( 2 ) { E C ( i ) , E L S ( j ) } ∩ { E C ( J P [ ω ] ) , E L S ( J S [ ω ] ) } > p ω k ′ (2)\{EC(i),ELS(j)\}\cap\{EC(JP[{\omega}]),ELS(JS[{\omega}])\}\gt p_{\omega k'} (2){EC(i),ELS(j)}∩{EC(JP[ω]),ELS(JS[ω])}>pωk′​

基于定理3（或推论1）和定理4，文章设计了如下的求解 F J S P FJSP FJSP问题的一种新邻域结构，它包括：
(1)邻域结构 N X 1 NX1 NX1:对每一道关键工序，在其任意可选机器上若寻找到满足定理4条件的插入区间，则将该关键工序插入该区间；
(2)邻域结构 N X 2 NX2 NX2:对每一道关键工序，在其任意可选机器上若寻找到满足定理3或推论1条件的插入区间，则将该关键工序插入该区间.
从定理4可知： N X 1 ⊆ N X 2 NX1 \subseteq{NX2} NX1⊆NX2,且 N X 1 NX1 NX1邻域结构的计算代价远低于 N X 2 NX2 NX2.

4 禁忌搜素算法

禁忌搜索算法包括初始解，邻域结构，禁忌列表，特赦准则和终止准则等基本要素。其中，邻域结构是决定禁忌搜索算法性能的主要因素，文章基于新的邻域结构,设计了两级邻域搜索策略.

4.1 两级邻域搜索策略

第一阶段，优先使用 N X 1 NX1 NX1邻域结构进行搜索，当 N X 1 NX1 NX1无法找到有效插入区间时，使用 N X 2 NX2 NX2邻域结构进行搜索，当 N X 2 NX2 NX2无法找到有效插入区间时，邻域搜索进入第二阶段，即采用 M & G M\&G M&G邻域结构进行邻域搜索，每接受一个邻域解后，邻域搜索重新进入第一阶段。

4.2 搜索流程

禁忌搜索算法的具体步骤如下：
S t e p 1 Step1 Step1：产生一个初始解，将该初始解赋给当前当前解和最优解，构建一个初始的禁忌列表；
S t e p 2 Step2 Step2：是否达到终止条件，若达到终止条件，进入 S t e p 6 Step6 Step6，否则进入 S t e p 3 Step3 Step3；
S t e p 3 Step3 Step3：按两级邻域搜索策略构建当前解的邻域解集合，并采用近似评价策略对邻域解集合中的每个邻域解进行评价。
S t e p 4 Step4 Step4：如果邻域解集合中的最佳邻域解优于当前最优解（满足特赦准则），则用该邻域解更新当前解和最优解，否则，在邻域解集合中选择选择未被禁忌的最佳解更新当前解；
S t e p 5 Step5 Step5：更新禁忌列表，返回 S t e p 2 Step2 Step2；
S t e p 6 Step6 Step6：输出最优解；