本文主要是介绍文献阅读《求解柔性作业车间调度问题的一种新邻域结构》，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

文献阅读笔记

文章来源

摘要

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

1 引言

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

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

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

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

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：输出最优解；

这篇关于文献阅读《求解柔性作业车间调度问题的一种新邻域结构》的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！