在复现另一篇文献An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem的算法时，发现其中的局部搜索使用了k-insertion的邻域动作，于是找到出处：effective neighbourhood functions for the flexible job shop problem。这篇文章主要是对k-insertion的一些性质的解释与证明，我顺着原文献的思路推导了一下证明过程，顺便对这次阅读做一下记录。
文章首先介绍了FJSP的由来，然后解释了局部搜索、邻域动作的概念（这一部分这里省略，想了解请移步原文献[1]）。最后总结了这篇文章的贡献：对于工序 v v v和机器 k k k，提出了一种计算解集 F v k F_{vk} Fvk的方法， F v k F_{vk} Fvk总是包含将 v v v最优地插入 k k k的解。
文章这一部分主要介绍了用于描述FJSP问题的解的图的形式。这种图在其他文献中被称为析取图（disjunctive graph），Roy和Sussmann[2]、Balas[3]等人较早将其运用于Job-Shop调度问题。Roy和Sussmann的文章我看了其中对于析取图的解释，非常清楚明了，顺便也记录一下。
这里给出一个简单案例对如何构建一个析取图进行解释。假设在一个JSP问题之中，有3个作业，作业1和作业3有3个工序，作业2有2个工序。将每一个作业的每一个工序视为一个节点。首先，按照每一个作业的工序加工优先级构建一个有向图，图中的有向边表示作业中高优先级工序流向低优先级工序。作业1的节点是1，2，3，作业2的节点是4，5，作业3的节点是6，7，8。工序1、6具有相同的加工机器k1，工序2、5、8具有相同的机器k2，工序3、4、7具有相同的机器k3。该图中，节点0和节点9是虚拟节点，仅仅作为开始和结束用，没有实际含义。图中，任一条弧 ( i , j ) (i,j) (i,j)的权为 i i i在对应机器上的处理时间。比如弧 ( 2 , 3 ) (2,3) (2,3)的权为顶点2表示的工序在其加工机器上的处理时间（也有另一种描述，即用顶点的权表示处理时间）。
接下来，使用虚线连接具有相同加工机器的节点。这些虚线称为“析取弧（disjunctive arc）”。相同加工机器的任意两个顶点之间均有一个析取对（两条方向相反的析取弧 ( i , j ) (i,j) (i,j)或 ( j , i ) (j,i) (j,i)）。析取弧 ( i , j ) (i,j) (i,j)的权是顶点 i i i在其加工机器上的处理时间。
析取弧的方向需要被确定。析取弧的方向确定之后，这个图就变成了一个优先图（precedence graph）。任一个顶点都受到其所有前驱顶点的优先级约束。
这个析取图描述了一个调度计划：先在机器k1上按1->6进行加工，等待这两道工序加工完毕之后，在机器k2上加工2，完毕后在k3上加工3->4->7，完毕后在k2上继续加工4->7，最后所有工序加工完毕。该图中，每一个顶点的开始时间都受制于两个前驱顶点中开始时间最晚的那一个。
观察上边的访问顺序，可以发现顶点3和7之间的弧可以省略，顶点2和8之间的弧也可以省略。像这样具有“三角性”的弧，可以省去直接从头顶点连到尾顶点的弧。如此一来析取图就变成了如下所示的图：
通过取析取弧不同方向，可以构造出不同的析取图，每个析取图都表示一个调度计划。连接第一个节点和最后一个节点的路径的权值是路径上所有节点的权值之和；最大权值路径被称为关键路径（critical path），其权值等于相应调度计划的最大完工时间（makespan）。 关键路径上的顶点和弧被称作是“关键的（critical）”。
为什么关键路径（最大权值路径）的长度能够表示最大完工时间？
我自己的理解：析取图中每一个工序都受到作业紧前工序和机器紧前工序的限制（优先约束），当前工序需要判断作业紧前工序加工完成时间和机器紧前工序加工完成时间哪一个时间较晚，它才能开始加工。这实际上是一种动态规划的思想，假设任意一个顶点 v v v，它的完工时间用 c v c_v cv表示，在机器上的处理时间用 p v , k p_{v,k} pv,k表示，它的机器紧前工序是 M P [ v ] MP[v] MP[v]，作业紧前工序是 J P [ v ] JP[v] JP[v]，则顶点 v v v的完工时间为： c v = max { c M P [ v ] + p k , M P [ v ] , c J P [ v ] + p k , J P [ v ] } c_v=text{max}{c_{MP[v]}+p_{k,MP[v]},c_{JP[v]}+p_{k,JP[v]}} cv=max{cMP[v]+pk,MP[v],cJP[v]+pk,JP[v]}，这种最优子结构导致到达最后一个顶点的完工时间是析取图中最长（最大权值）的路径。
另外，析取弧的方向不能随便取，不然会出现“死锁”现象。如下图所示。析取图中不能出现环。环的出现意味着违反了优先约束，比如说一个作业中的任意两道工序 O 1 O_1 O1和 O 2 ( s O 1 < s O 2 ) O_2(s_{O_1}<s_{O_2}) O2(sO1<sO2)，假如将 O 2 O_2 O2安排到了 O 1 O_1 O1之前（或者析取图中 O 2 O_2 O2有通向 O 1 O_1 O1的路径），那么析取图中必定会出现环。
上述的析取图是对于JSP问题而言的，由于FJSP问题相比起JSP问题多出了机器选择的决策过程，反映在析取图中为一个顶点有多条析取弧可供选择。
为了方便下文的阐述，先说明一些符号：
在析取图中，工序 v v v在机器 k k k的k-insertion分为以下两个步骤：
顶点 v v v的k-insertion被称为最优k-insertion，如果：
顶点 v v v的insertion是最优的（v的最优insertion），如果 v v v的最优k-insertion比其他顶点的最优k-insertion的makespan都小。
下面说明如何得到一个k-insertion集合 F v k F_{vk} Fvk，它总是包含顶点 v v v的最优k-insertion。
对于 G − G^{-} G−中的任一个工序 x x x，头长度和尾长度分别为 s x − s_x^{-} sx−和 t x − t_x^{-} tx−，总有 s x − ≤ s x s_x^{-} le s_x sx−≤sx， t x − ≤ t x t_x^{-} le t_x tx−≤tx。
这里原文献中没有给出进一步解释，那我自己来证明吧：分三种情况考虑，第一种情况是在G中 x x x有通向 v v v的路径，那么去除 v v v的机器弧不会对 x x x的头长度产生任何影响，尾长度可能不变也可能减小，不可能增加（机器弧的断开导致计算x的尾长度时一些处理时间不再被纳入考虑，所以尾长度不可能增加）；第二种情况是在G中 v v v有通向 x x x的路径，此时尾长度不受影响，头长度有可能不变也有可能减小（与情况一同理）；第三种情况是G中 x x x和 v v v之间没有任何路径相通，那么断开机器弧之后它们之间当然也不会有路径相通， x x x的头长度和尾长度不受影响。
G − G^{-} G−中， v v v选择一个机器 k k k，用 Q k Q_k Qk表示机器 k k k上的工序序列。注意 v ∉ Q k v notin Q_k v∈/Qk。定义 R k = { x ∈ Q k ∣ s x + p x > s v − } , L k = { x ∈ Q k ∣ t x + p x > t v − } R_k={x in Q_k|s_x+p_x gt s_v^{-}},L_k={x in Q_k|t_x+p_x gt t_v^{-}} Rk={x∈Qk∣sx+px>sv−},Lk={x∈Qk∣tx+px>tv−}。则将 v v v插入 L k − R k L_k - R_k Lk−Rk之后， R k − L k R_k - L_k Rk−Lk之前都是合法的k-insertion。
证明：
首先，使用 P J [ v ] PJ[v] PJ[v]和 S J [ v ] SJ[v] SJ[v]分别表示 v v v的作业紧前工序和紧后工序，在 G − G^{-} G−中 s v − = s P J [ v ] − + p P J [ v ] s_v^{-}=s_{PJ[v]}^{-}+p_{PJ[v]} sv−=sPJ[v]−+pPJ[v]， t v − = t S J [ v ] − + p S J [ v ] t_v^{-}=t_{SJ[v]}^{-}+p_{SJ[v]} tv−=tSJ[v]−+pSJ[v]，注意， s P J [ v ] − s_{PJ[v]}^{-} sPJ[v]−与 s P J [ v ] s_{PJ[v]} sPJ[v]是相等的， t S J [ v ] − t_{SJ[v]}^{-} tSJ[v]−与 t S J [ v ] t_{SJ[v]} tSJ[v]也是相等的（这个好简单，不证了）。 x x x是 Q k Q_k Qk中的某一个工序，如果在 G − G^{-} G−中 x x x向 v v v有路径存在，那么 x x x必定有路径向 P J [ v ] PJ[v] PJ[v]，则由于优先约束的存在， v v v不能插入到 x x x之前，否则 v v v与 P J [ v ] PJ[v] PJ[v]之间有环存在，析取图非法。 同理，如果在 G − G^{-} G−中 v v v向 x x x有路径存在， v v v不能插入到 x x x之后。如果在 G − G^{-} G−中 x x x向 v v v没有路径存在， v v v可以插入到 x x x之前或之后，都不会产生环。
R k R_k Rk的定义，决定了 x ∈ R k x in R_k x∈Rk向 v v v不会有路径存在。 文献中没有进一步说明，我自己分两种情况解释：第一种情况，如果在 G − G^{-} G−中 x x x与 v v v之间有路径相通，要么 x x x通向 P J [ v ] PJ[v] PJ[v]，要么 S J [ v ] SJ[v] SJ[v]通向 x x x，由于在 R k R_k Rk中 s x + p x > s v − s_x+p_x gt s_v^{-} sx+px>sv−，即 s x + p x > s P J [ v ] − + p P J [ v ] s_x+p_x gt s_{PJ[v]}^{-}+p_{PJ[v]} sx+px>sPJ[v]−+pPJ[v]，即 s x + p x > s P J [ v ] + p P J [ v ] s_x+p_x gt s_{PJ[v]}+p_{PJ[v]} sx+px>sPJ[v]+pPJ[v]，可以看出，由于 P J [ v ] PJ[v] PJ[v]在 v v v之后，且 x x x在 P J [ v ] PJ[v] PJ[v]之后， x ∈ R k x in R_k x∈Rk向 v v v不会有路径存在；第二种情况，如果在 G − G^{-} G−中 x x x与 v v v之间没有路径相通，那么 x ∈ R k x in R_k x∈Rk向 v v v注定不会有路径存在。如果 x ∈ Q k − R k x in Q_k-R_k x∈Qk−Rk，有 s x + p x ≤ s v − s_x+p_x le s_v^{-} sx+px≤sv−，同理，可以证明出 v v v向 x ∈ Q k − R k x in Q_k-R_k x∈Qk−Rk不会有路径存在。
按照上面对 R k R_k Rk的一些性质的证明，同样可以证明出 v v v向 x ∈ L k x in L_k x∈Lk不会有路径存在， x ∈ Q k − L k x in Q_k-L_k x∈Qk−Lk向 v v v不会有路径存在。
L k − R k L_{k}-R_k Lk−Rk中的每一个工序都在 R k − L k R_k-L_k Rk−Lk之前。 很明显，由于 L k − R k L_{k}-R_k Lk−Rk中每一个工序 x x x都有 s x + p x ≤ s v − s_x+p_x le s_v^{-} sx+px≤sv−， R k − L k R_k-L_k Rk−Lk中每一个工序 x x x都有 s x + p x > s v − s_x+p_x gt s_v^{-} sx+px>sv−，所以 L k − R k L_{k}-R_k Lk−Rk中的每一个工序都在 R k − L k R_k-L_k Rk−Lk之前。
将 v v v插入 L k − R k L_k - R_k Lk−Rk之后， R k − L k R_k - L_k Rk−Lk之前得到的所有k-insertion都是合法的。即在 G − G^{-} G−中 v v v与 L k − R k L_k - R_k Lk−Rk之后， R k − L k R_k - L_k Rk−Lk之前的任何工序 x x x都不会有路径存在。 在 L k − R k L_k - R_k Lk−Rk之后， R k − L k R_k - L_k Rk−Lk之前的工序 x x x有两种情况。第一种情况，当 L k ∩ R k ≠ ∅ L_k cap R_k ne empty Lk∩Rk=∅，则对于 L k − R k L_k - R_k Lk−Rk之后， R k − L k R_k - L_k Rk−Lk之前的任一工序 x x x，有 x ∈ L k ∩ R k x in L_k cap R_k x∈Lk∩Rk，由于上边已经证明了 x ∈ R k x in R_k x∈Rk向 v v v不会有路径存在， v v v向 x ∈ L k x in L_k x∈Lk不会有路径存在，所以 x ∈ L k ∩ R k x in L_k cap R_k x∈Lk∩Rk与 v v v之间不会存在路径；第二种情况，当 L k ∩ R k = ∅ L_k cap R_k = empty Lk∩Rk=∅，对于 L k − R k L_k - R_k Lk−Rk之后， R k − L k R_k - L_k Rk−Lk之前的任一工序 x ∈ Q k − ( L k ∪ R k ) x in Q_k-(L_k cup R_k) x∈Qk−(Lk∪Rk)，有 x ∉ R k x notin R_k x∈/Rk且 x ∉ L k x notin L_k x∈/Lk，则 s x + p x ≤ s v − s_x+p_x le s_v^{-} sx+px≤sv−且 t x + p x ≤ t v − t_x+p_x le t_v^{-} tx+px≤tv−，上文证明了总有 s x − ≤ s x s_x^{-} le s_x sx−≤sx， t x − ≤ t x t_x^{-} le t_x tx−≤tx，则 s x − + p x ≤ s v − s_x^{-}+p_x le s_v^{-} sx−+px≤sv−且 t x − + p x ≤ t v − t_x^{-}+p_x le t_v^{-} tx−+px≤tv−，可以看出此时在 G − G^{-} G−中 x x x的头长度和尾长度均小于 v v v的头长度和尾长度，上文说过， G − G^{-} G−中 x x x要与 v v v之间存在路径，要么 x x x存在向 P J [ v ] PJ[v] PJ[v]的路径（此时 x x x的头长度小于v的头长度同时 x x x的尾长度大于v的尾长度），要么 S J [ v ] SJ[v] SJ[v]有向 x x x的路径（此时 x x x的头长度大于v的头长度同时 x x x的尾长度小于v的尾长度），而“ x x x的头长度和尾长度均小于 v v v的头长度和尾长度”不存在于这两种情况中，所以 L k − R k L_k - R_k Lk−Rk之后， R k − L k R_k - L_k Rk−Lk之前的任一工序 x x x与 v v v不存在任何相通的路径。
将 L k − R k L_k - R_k Lk−Rk之后， R k − L k R_k - L_k Rk−Lk之前的所有k-insertion用 F v k F_{vk} Fvk表示。有： F v k F_{vk} Fvk之外的k-insertion比起 F v k F_{vk} Fvk之中的k-insertion无法得到更小的makespan。
证明：
设 ( u , w ) (u,w) (u,w) 是 Q k Q_k Qk 中相邻两个工序， v v v 正好插入到 u 、 w u、w u、w 之间。 G − G^{-} G− 通过添加机器弧 ( u , v ) (u,v) (u,v) 和 ( v , w ) (v,w) (v,w) 并且设置顶点的权重为 p v k p_{vk} pvk 得到 G ( u , w ) G^{(u,w)} G(u,w)， G ( u , w ) G^{(u,w)} G(u,w) 的所有节点用 V V V表示，对于节点 x ∈ V x in V x∈V，头长度和尾长度分别用 s x ( u , w ) s_x^{(u,w)} sx(u,w) 和 t x ( u , w ) t_x^{(u,w)} tx(u,w) 表示，在 G ( u , w ) G^{(u,w)} G(u,w) 中， v v v所在的最长路径为： s v ( u , w ) + p v k + t v ( u , w ) s_v^{(u,w)}+p_{vk}+t_v^{(u,w)} sv(u,w)+pvk+tv(u,w)。
由于 G ( u , w ) G^{(u,w)} G(u,w) 从 G − G^{-} G− 中添加机器弧得来， G ( u , w ) G^{(u,w)} G(u,w) 的makespan要么是存在于 G − G^{-} G− 中最长路径的makespan，要么是添加的机器弧导致产生了新的更大的makespan。所以， G ( u , w ) G^{(u,w)} G(u,w) 中最大完工时间为： C max ( u , w ) = max { l − ( 0 , ∗ ) , s v ( u , w ) + p v k + t v ( u , w ) } C_{text{max}}^{(u,w)}=text{max}{l^{-}(0,*),s_v^{(u,w)}+p_{vk}+t_v^{(u,w)}} Cmax(u,w)=max{l−(0,∗),sv(u,w)+pvk+tv(u,w)}在上式中， l − ( 0 , ∗ ) l^{-}(0,*) l−(0,∗)是常量，想要最小化 C max ( u , w ) C_{text{max}}^{(u,w)} Cmax(u,w)，需要让 s v ( u , w ) + p v k + t v ( u , w ) s_v^{(u,w)}+p_{vk}+t_v^{(u,w)} sv(u,w)+pvk+tv(u,w)最小，由于 s v ( u , w ) = max { s u − + p u , s v − } , t v ( u , w ) = max { t w − + p w , t v − } s_v^{(u,w)}=text{max}{s_u^{-}+p_u,s_v^{-}},t_v^{(u,w)}=text{max}{t_w^{-}+p_w,t_v^{-}} sv(u,w)=max{su−+pu,sv−},tv(u,w)=max{tw−+pw,tv−}，可以得到： s v ( u , w ) + p v k + t v ( u , w ) = s v − + p v k + t v − + max { s u − + p u − s v − , 0 } + max { t w − + p w − t v − , 0 } s_v^{(u,w)}+p_{vk}+t_v^{(u,w)}=s^{-}_v+p_{vk}+t^{-}_v+text{max}{s_u^{-}+p_u-s_v^{-},0}+text{max}{t_w^{-}+p_w-t_v^{-},0} sv(u,w)+pvk+tv(u,w)=sv−+pvk+tv−+max{su−+pu−sv−,0}+max{tw−+pw−tv−,0}记 Δ ( u , w ) = max { s u − + p u − s v − , 0 } + max { t w − + p w − t v − , 0 } Delta(u,w)=text{max}{s_u^{-}+p_u-s_v^{-},0}+text{max}{t_w^{-}+p_w-t_v^{-},0} Δ(u,w)=max{su−+pu−sv−,0}+max{tw−+pw−tv−,0}，所以，如果 v v v插入 ( u , w ) (u,w) (u,w)让 Δ ( u , w ) Delta(u,w) Δ(u,w)最小，那么 ( u , w ) (u,w) (u,w)就是 v v v的最优k-insertion。
下面，根据以上推导来继续证明：在 L k − R k L_k-R_k Lk−Rk之后， R k − L k R_k-L_k Rk−Lk之前总存在一个 v v v的最优k-insertion，并且如果 L k ∩ R k = ∅ L_k cap R_k = empty Lk∩Rk=∅， L k − R k L_k-R_k Lk−Rk之后， R k − L k R_k-L_k Rk−Lk之前的所有v的k-insertion都会是v的最优k-insertion。
如果 L k ∩ R k ≠ ∅ L_k cap R_k ne empty Lk∩Rk=∅，分两步证明：
- 第一步：证明将 v v v插入到 L k − R k L_k-R_k Lk−Rk最后一个工序之后，不会差于将 v v v插入到 L k − R k L_k-R_k Lk−Rk任一个工序之前。在这种情况下，对于 L k − R k L_k-R_k Lk−Rk的任一个工序 u u u（其紧后工序是 w w w），总有 s u + p u − s v − ≤ 0 s_u+p_u-s_v^{-} le 0 su+pu−sv−≤0，所以 max { s u + p u − s v − , 0 } = 0 text{max}{s_u+p_u-s_v^{-},0} =0 max{su+pu−sv−,0}=0，上面已经证明 s u ≥ s u − s_u ge s_u^{-} su≥su−，所以 max { s u − + p u − s v − , 0 } = 0 text{max}{s_u^{-}+p_u-s_v^{-},0} =0 max{su−+pu−sv−,0}=0，这样一来 Δ ( u , w ) = max { t w − + p w − t v − , 0 } Delta(u,w)=text{max}{t_w^{-}+p_w-t_v^{-},0} Δ(u,w)=max{tw−+pw−tv−,0}，可以看到 t w − t_w^{-} tw−越小（ L k − R k L_k-R_k Lk−Rk越往后）， Δ ( u , w ) Delta(u,w) Δ(u,w)越小。
- 第二步，证明将 v v v插入到 R k − L k R_k-L_k Rk−Lk第一个工序之前，不会差于将 v v v插入到 R k − L k R_k-L_k Rk−Lk任一个工序之后。这种情况跟第一步中的情况是对称的，可以用第一种情况中的证明来加以证明。
如果 L k ∩ R k = ∅ L_k cap R_k = empty Lk∩Rk=∅， L k − R k = L k L_k-R_k=L_k Lk−Rk=Lk， R k − L k = R k R_k-L_k=R_k Rk−Lk=Rk。则对于任意工序 x ∈ Q − ( L k ∪ R k ) x in Q-(L_k cup R_k) x∈Q−(Lk∪Rk) ，有 s x + p x ≤ s v − , p x + t x ≤ t v − s_x+p_x le s_v^{-}, p_x+t_x le t_v^{-} sx+px≤sv−,px+tx≤tv−，则： max { s x − + p x − s v − , 0 } = 0 , max { t x − + p x − t v − , 0 } = 0 text{max}{s_x^{-}+p_x-s_v^{-},0} =0, text{max}{t_x^{-}+p_x-t_v^{-},0} =0 max{sx−+px−sv−,0}=0,max{tx−+px−tv−,0}=0，可以得知此时 Δ ( u , w ) = 0 Delta(u,w)=0 Δ(u,w)=0，完工时间的改变一致，上文已经证明 L k − R k L_k-R_k Lk−Rk即 L k L_k Lk中越往右， R k − L k R_k-L_k Rk−Lk即 R k R_k Rk中越往左 Δ ( u , w ) Delta(u,w) Δ(u,w)越小，所以 L k − R k L_k-R_k Lk−Rk之后， R k − L k R_k-L_k Rk−Lk之前的所有v的k-insertion都会是v的最优k-insertion。
事实上，到这里，就可以实现k-insertion。文献接下来的部分是对k-insertion的计算速度进行优化，因为每次k-insertion之后，都需要重新计算析取图的关键路径长度，时间复杂度是 o ( N ) o(N) o(N)。文中提出了一种方法计算关键路径的近似长度，所用时间为 o ( log N ) o(text{log}N) o(logN)。这一部分有兴趣的请移步文献[1]自行阅读。
我在另一篇文章中使用k-insertion实现了禁忌搜索：
【车间调度】基于k-insertion的禁忌搜索算法求解经典FJSP问题（Java源码）
[1] Mastrolilli, Monaldo and Luca Maria Gambardella. “Effective Neighborhood Functions for the Flexible Job Shop Problem.” Journal of Scheduling 3 (1998): 3-20.
[2] Balas E. Machine scheduling via disjunctive graphs: an implicit enumeration algorithm. Operations Research, 1969, 17: 941~957
[3] Roy B and Sussmann B. Les problèmes d’ordonnancement avec contraintes disjonctives, Note D.S. no. 9 bis, SEMA, Paris, France, Décembre, 1964
本文发布于:2024-02-01 12:56:08，感谢您对本站的认可！
本文链接：https://www.4u4v.net/it/170676336736746.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
| 留言与评论（共有 0 条评论） |
