【车间调度】论文阅读复现——effective neighbourhood functions for the flexible job shop problem

这篇具有很好参考价值的文章主要介绍了【车间调度】论文阅读复现——effective neighbourhood functions for the flexible job shop problem。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

在复现另一篇文献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的一些性质的解释与证明,我顺着原文献的思路推导了一下证明过程,顺便对这次阅读做一下记录。

1.简介(INTRODUCTION)

文章首先介绍了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的解。

2.解图(THE SOLUTION GRAPH)

文章这一部分主要介绍了用于描述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问题多出了机器选择的决策过程,反映在析取图中为一个顶点有多条析取弧可供选择。

3.文献回顾(LITERATURE REVIEW)

4.移动工序(MOVING AN OPERATION)

为了方便下文的阐述,先说明一些符号:

  • l ( i , j ) l(i,j) l(i,j):从 i i i j j j的最长路径。 l ( 0 , ∗ ) l(0,*) l(0,)表示虚拟的开始顶点到虚拟的结束顶点之间的最长路径,即关键路径。
  • p v k p_{vk} pvk:工序 v v v在机器 k k k上的处理时间,有时为了简单也会写成 p v p_v pv,但是是暗含了它在 k k k上处理的含义。
  • M v M_v Mv:工序 v v v的可选机器集合
  • s v s_v sv:顶点 v v v的头长度, s v = l ( 0 , v ) s_v=l(0,v) sv=l(0,v),表示顶点的开始时间
  • t v t_v tv:顶点 v v v的尾长度, t v = l ( v , ∗ ) t_v=l(v,*) tv=l(v,),可以用 s v + p v k + t v s_v+p_{vk}+t_v sv+pvk+tv是否等于最大完工时间来判断该工序是否处在关键路径上。

在析取图中,工序 v v v在机器 k k k的k-insertion分为以下两个步骤:

  1. 移除 v v v所有机器弧, v v v从所在的机器序列中被移除(析取图中 v v v的权同时被置为0),得到一个子图 G − G^{-} G
  2. v v v分配给 k k k,并选择 v v v k k k中的插入位置,重连机器弧(假如插入位置是 ( u , w ) (u,w) (u,w),则首先断开 ( u , w ) (u,w) (u,w)之间的弧,接着依次重连 ( u , v ) (u,v) (u,v) ( v , w ) (v,w) (v,w)之间的弧并重置两个弧的权)。

顶点 v v v的k-insertion被称为最优k-insertion,如果:

  1. 它是合法的。如果k-insertion让结果的析取图产生了环,那么该k-insertion非法。
  2. 结果的makespan比其他合法k-insertion的makespan小,即该k-insertion的makespan最小。

顶点 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 sxsx t x − ≤ t x t_x^{-} \le t_x txtx

这里原文献中没有给出进一步解释,那我自己来证明吧:分三种情况考虑,第一种情况是在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={xQksx+px>sv},Lk={xQktx+px>tv}则将 v v v插入 L k − R k L_k - R_k LkRk之后, R k − L k R_k - L_k RkLk之前都是合法的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 xRk 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 xRk v v v不会有路径存在;第二种情况,如果在 G − G^{-} G x x x v v v之间没有路径相通,那么 x ∈ R k x \in R_k xRk v v v注定不会有路径存在。如果 x ∈ Q k − R k x \in Q_k-R_k xQkRk,有 s x + p x ≤ s v − s_x+p_x \le s_v^{-} sx+pxsv,同理,可以证明出 v v v x ∈ Q k − R k x \in Q_k-R_k xQkRk不会有路径存在

按照上面对 R k R_k Rk的一些性质的证明,同样可以证明出 v v v x ∈ L k x \in L_k xLk不会有路径存在 x ∈ Q k − L k x \in Q_k-L_k xQkLk v v v不会有路径存在

L k − R k L_{k}-R_k LkRk中的每一个工序都在 R k − L k R_k-L_k RkLk之前。 很明显,由于 L k − R k L_{k}-R_k LkRk中每一个工序 x x x都有 s x + p x ≤ s v − s_x+p_x \le s_v^{-} sx+pxsv R k − L k R_k-L_k RkLk中每一个工序 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 LkRk中的每一个工序都在 R k − L k R_k-L_k RkLk之前。

v v v插入 L k − R k L_k - R_k LkRk之后, R k − L k R_k - L_k RkLk之前得到的所有k-insertion都是合法的。即在 G − G^{-} G v v v L k − R k L_k - R_k LkRk之后, R k − L k R_k - L_k RkLk之前的任何工序 x x x都不会有路径存在。 L k − R k L_k - R_k LkRk之后, R k − L k R_k - L_k RkLk之前的工序 x x x有两种情况。第一种情况,当 L k ∩ R k ≠ ∅ L_k \cap R_k \ne \empty LkRk=,则对于 L k − R k L_k - R_k LkRk之后, R k − L k R_k - L_k RkLk之前的任一工序 x x x,有 x ∈ L k ∩ R k x \in L_k \cap R_k xLkRk,由于上边已经证明了 x ∈ R k x \in R_k xRk v v v不会有路径存在, v v v x ∈ L k x \in L_k xLk不会有路径存在,所以 x ∈ L k ∩ R k x \in L_k \cap R_k xLkRk v v v之间不会存在路径;第二种情况,当 L k ∩ R k = ∅ L_k \cap R_k = \empty LkRk=,对于 L k − R k L_k - R_k LkRk之后, R k − L k R_k - L_k RkLk之前的任一工序 x ∈ Q k − ( L k ∪ R k ) x \in Q_k-(L_k \cup R_k) xQk(LkRk),有 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+pxsv t x + p x ≤ t v − t_x+p_x \le t_v^{-} tx+pxtv,上文证明了总有 s x − ≤ s x s_x^{-} \le s_x sxsx t x − ≤ t x t_x^{-} \le t_x txtx,则 s x − + p x ≤ s v − s_x^{-}+p_x \le s_v^{-} sx+pxsv t x − + p x ≤ t v − t_x^{-}+p_x \le t_v^{-} tx+pxtv,可以看出此时在 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 LkRk之后, R k − L k R_k - L_k RkLk之前的任一工序 x x x v v v不存在任何相通的路径。

L k − R k L_k - R_k LkRk之后, R k − L k R_k - L_k RkLk之前的所有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 uw 之间。 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 xV,头长度和尾长度分别用 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+pusv,0}+max{tw+pwtv,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+pusv,0}+max{tw+pwtv,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 LkRk之后, R k − L k R_k-L_k RkLk之前总存在一个 v v v的最优k-insertion,并且如果 L k ∩ R k = ∅ L_k \cap R_k = \empty LkRk= L k − R k L_k-R_k LkRk之后, R k − L k R_k-L_k RkLk之前的所有v的k-insertion都会是v的最优k-insertion。

如果 L k ∩ R k ≠ ∅ L_k \cap R_k \ne \empty LkRk=,分两步证明:

  • 第一步:证明 v v v插入到 L k − R k L_k-R_k LkRk最后一个工序之后,不会差于将 v v v插入到 L k − R k L_k-R_k LkRk任一个工序之前。在这种情况下,对于 L k − R k L_k-R_k LkRk的任一个工序 u u u(其紧后工序是 w w w),总有 s u + p u − s v − ≤ 0 s_u+p_u-s_v^{-} \le 0 su+pusv0,所以 max { s u + p u − s v − , 0 } = 0 \text{max}\{s_u+p_u-s_v^{-},0\} =0 max{su+pusv,0}=0,上面已经证明 s u ≥ s u − s_u \ge s_u^{-} susu,所以 max { s u − + p u − s v − , 0 } = 0 \text{max}\{s_u^{-}+p_u-s_v^{-},0\} =0 max{su+pusv,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+pwtv,0},可以看到 t w − t_w^{-} tw越小( L k − R k L_k-R_k LkRk越往后), Δ ( u , w ) \Delta(u,w) Δ(u,w)越小。
  • 第二步,证明 v v v插入到 R k − L k R_k-L_k RkLk第一个工序之前,不会差于将 v v v插入到 R k − L k R_k-L_k RkLk任一个工序之后。这种情况跟第一步中的情况是对称的,可以用第一种情况中的证明来加以证明。


如果 L k ∩ R k = ∅ L_k \cap R_k = \empty LkRk= L k − R k = L k L_k-R_k=L_k LkRk=Lk R k − L k = R k R_k-L_k=R_k RkLk=Rk。则对于任意工序 x ∈ Q − ( L k ∪ R k ) x \in Q-(L_k \cup R_k) xQ(LkRk) ,有 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+pxsv,px+txtv,则: 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+pxsv,0}=0,max{tx+pxtv,0}=0,可以得知此时 Δ ( u , w ) = 0 \Delta(u,w)=0 Δ(u,w)=0,完工时间的改变一致,上文已经证明 L k − R k L_k-R_k LkRk L k L_k Lk中越往右, R k − L k R_k-L_k RkLk R k R_k Rk中越往左 Δ ( u , w ) \Delta(u,w) Δ(u,w)越小,所以 L k − R k L_k-R_k LkRk之后, R k − L k R_k-L_k RkLk之前的所有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文章来源地址https://www.toymoban.com/news/detail-770941.html

到了这里,关于【车间调度】论文阅读复现——effective neighbourhood functions for the flexible job shop problem的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 车间调度问题及模型分类

    作业车间调度问题是许多实际生产调度问题的抽象模型,是典型的NP-hard问题,其研究具有重要的理论意义和研究价值。车间调度问题具有 求解难度高的特点, 目前最先进算法仍很难求解小规模问题的最优解。   K个机器并行机加工调度问题 每个工件只有一个工序,可以在任

    2023年04月17日
    浏览(30)
  • 车间调度问题综述

             在单机调度问题(Single machine scheduling problem,SMP)中,加工系统 只有一台机床 ,待加工的工件 有且仅有一道工序 ,所有工件都在该机床上进行加工。         在车间调度中,单机调度是指对车间内的某个特定的机器(也称为单机)进行调度,以使其在完成

    2024年02月05日
    浏览(54)
  • FixMatch+DST论文阅读笔记(待复现)

    论文标题:FixMatch: Simplifying Semi-Supervised Learning with Consistency and Confidence 论文作者:Kihyuk Sohn, David Berthelot, Chun-Liang Li, Zizhao Zhang, Nicholas Carlini, Ekin D. Cubuk, Alex Kurakin, Han Zhang, Colin Raffel 论文来源:NeurIPS 2020 代码来源:Code 半监督学习有效的利用没有标注的数据,从而提高模型的

    2024年02月08日
    浏览(41)
  • 基于遗传算法解决流水车间调度问题

    问题描述 n 个工件要在 m 台机器上加工,每个工件需要经过 m 道工序,每道工序要求不同的机器,n 个工件在 m 台机器上的加工顺序相同。工件在机器上的加工时间是给定的,设为 t i j ( i = 1.... , n ; j = 1 , . . . , m ) t_{ij}(i = 1....,n; j = 1,...,m) t ij ​ ( i = 1.... , n ; j = 1 , ... , m ) 问

    2024年02月07日
    浏览(38)
  • 论文阅读和复现:去除PPG运动伪影的IEEE论文

    论文阅读和代码复现: 《Combining Nonlinear Adaptive Filtering and Signal Decomposition for Motion Artifact Removal in Wearable Photoplethysmography》 基本介绍: 由于手腕运动造成的噪声:运动伪影,使得PPG方法的心率监测不准,去除运动伪影噪声在智能手表中是一个难点。 论文中使用的开源数据:

    2024年02月12日
    浏览(31)
  • C类期刊论文复现:基于共享储能电站的工业用户日前优化经济调度程序代码!

    适用平台: Matlab+Yalmip+Cplex/Gurobi; 程序在用户群间引入共享储能电站,建立以用户群日运行成本最优为目标的优化调度模型,分析用户群接入共享储能电站后的充放电行为和经济效益,并对共享储能电站的投资回收年限等经济性指标与服务费定价关系做进一步的研究。程序中

    2024年01月17日
    浏览(44)
  • 三维生成:Score Jacobian Chaining论文阅读/复现

    项目地址:Score Jacobian Chaining (ttic.edu) 论文地址:[2212.00774] Score Jacobian Chaining: Lifting Pretrained 2D Diffusion Models for 3D Generation (arxiv.org) 源码地址:GitHub - pals-ttic/sjc: Score Jacobian Chaining: Lifting Pretrained 2D Diffusion Models for 3D Generation (CVPR 2023)         (有Dreamfusion,DreamFields等相关基础

    2024年04月10日
    浏览(50)
  • GraphDTA论文阅读小白笔记(附代码注释和复现流程)

    具体代码复现以及代码注释可以查看https://github.com/zhaolongNCU/Demo-GraphDTA- 1.发展前景: 新药设计需要花费2.6billion,17years 药物再利用已被用于现实的疾病中 为了有效地重新调整药物的用途,了解哪些蛋白质是哪些药物的靶标是有用的 高通量筛选方法高消耗,并且彻底地完成搜

    2024年02月15日
    浏览(43)
  • 遗传算法GA解决混合流水车间调度问题HFSP

    混合流水车间调度问题(HFSP)是传统流水车间调度问题(FSP)的拓展,本文针对HFSP问题进行描述、建模和求解。 通常模型做如下假设: HFSP符号描述: 决策变量: 主要约束: 优化目标: 本节使用带精英保留的遗传算法GA对HFSP问题进行求解。求解结果如下: 自定义算例如下:

    2024年02月11日
    浏览(46)
  • 高创新!EI论文复现+改进:聚合温度调控策略的综合能源系统/微电网/虚拟电厂多目标优化调度程序代码!

    程序考虑供热的热惯性,并根据室内供热效果进行柔性供热,发挥热温度负荷的“储能”能力;针对普适性参数的室内空调进行集群研究,深入剖析温度设定值调整导致负荷波动的机理,并提出一种新的温度调整方法,平抑负荷波动;利用P2G装置实现电-气网络间能源双向协调

    2024年02月01日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包