高级检索

  • ISSN 1006-3080
  • CN 31-1691/TQ
引用本文:
Citation:

平行三阶段流水作业问题的近似算法

    作者简介: 曹移林(1990-),男,硕士生,主要研究方向为排序与组合优化。E-mail:Caoyilin0908@163.com;
    通讯作者: 余炜, yuwei@ecust.edu.cn
  • 中图分类号: O223

An Approximation Algorithm for The Parallel Three-Stage Flowshop Scheduling

    Corresponding author: Wei YU, yuwei@ecust.edu.cn
  • CLC number: O223

图(3)
计量
  • 文章访问数:  4930
  • HTML全文浏览量:  1556
  • PDF下载量:  2
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-02-03
  • 网络出版日期:  2019-09-27

平行三阶段流水作业问题的近似算法

    作者简介:曹移林(1990-),男,硕士生,主要研究方向为排序与组合优化。E-mail:Caoyilin0908@163.com
    通讯作者: 余炜, yuwei@ecust.edu.cn
  • 华东理工大学理学院数学系,上海 200237

摘要: 在这篇文章中,研究了n个三阶段工件在m个流水车间进行加工的排序问题,目标为最小化最大完工时间。当m是定值时,该问题是NP困难;当m>2时,则问题是强NP困难。对于该问题,将问题分解成三种情况,对于情形一,给出了(7/3-1/3m)的近似比;对于情形二,给出了一个3的近似比;对于情形三,这是一个近似比为(23/6-1/3m);结合三种情形,最终本文给出了性能比为(23/6-1/3m)的算法。

English Abstract

  • 排序问题是组合最优化中的一类重要问题,在计算机系统控制,硬件设计,机器加工制造业,产计划调度管理等方面有着广泛的应用背景,理论上它又与算法设计和计算复杂性密切相关,此引起了国内外的广泛关注。(m, k)-PFS问题有许多的实际应用背景,包括在玻璃工厂中的应用[1],以及基于数据中心和云计算的相关应用[2]等等。对于问题(m, k)-PFS,目前已有相关的研究成果。当m=1时,问题(m, k)-PFS就变成了经典的k阶段流水作业排序问题,当k=1时,问题(m, k)-PFS就会变成经典的平行机排序问题[3]并可以用著名的列表排序[4]算法进行求解,其中m是任意数。列表排序算法是由Graham[5]提出来的,并且证明了该算法达到(2-1/m)的近似比。后来他对算法进行了一定的改进,并且将近似比改到了(4/3-1/3m),这结果的出现是由于他在利用列表排序之前将工件按一定的规则进行了排序的。当m是定值时,对于问题(m, 1)-PFS,Sahni[6]提出了一个精确的拟多项式时间算法以及完全多项式时间近似方案(FPTAS)。当m是任意数时,Hochbaum等[7]利用对偶近似算法给出了一个拟多项式算法,从而得出了多项式时间近似方案(PTAS)。

    对于一般的平行流水作业问题,直到近些年来才开始集中研究。He等[1]首先开始研究问题(m, 2)-PFS,并且提出了一些启发式算法。随后,Vairaktarakis等[8]给出了问题(2, 2)-PFS的拟多项式算法。Zhang等[9]研究了问题(2, 2)-PFS并给出了3/2-近似比,同时还对问题(3, 2)-PFS并给出了12/7-近似算法,这些都是利用Johnoson's算法将工件分成几类。另外,对于问题(m, 2)-PFS (m是定值),Dong等[10]利用动态规划原理解决了(m, 2)-PFS,提出了拟多项式精确算法,并且给出了完全多项式时间近似方案(FPTAS);对于(m, k)-PFS这类问题,当mk都是定值时,Lin等[11]给出了多项式时间近似方案(PTAS)。最近对于(m, 2)-PFS这类问题 (m是任意数),Wu等[12]给出了一个近似比为17/6的近似算法。

    本文主要研究(m, 3)-PFS,其中m是任意数;关于n个三阶段工件在m个三阶段流水车间进行加工的问题,本文给出了一个(23/6-1/3m)的近似结果,其时间复杂度为O(nlogn+mn)。

    • 对于n个工件G={J1, …, Jn}在m个流水车间F={F1, …, Fm}进行加工,作如下假设:

      1. 每个工件Ji(1 ≤ in)由三道工序O1, i, O2, i, O3 ,i构成;

      2. 每个流水车间Fl(1 ≤ lm)由三台机器Ml, 1, Ml, 2, Ml, 3组成;

      3. 任何时刻每个工件至多只能被一台机器加工且每台机器至多只能加工一个工件;

      4 每个工件都必须指派给某个流水车间进行加工,从而每个工件的三道工序都在相同的流水车间加工。如果工件Ji被指派给流水车间Fl的工序O1, iMl, 1加工;工序O2, i只有在O1, i完工之后才能由Ml, 2开始加工;同理,工序O3, i只有在O2, i完工之后才能由Ml, 3开始加工;工序O3, i的完工时间就称为工件Ji的完工时间;

      5 对于加工的工件没有优先级,而且工件一旦开始加工就不允许中断。

      基于以上假设,可以用Ji=(p1, i, p2, i, p3, i)来表示工件Ji,其中pj, i是第j道工序的加工时间。一个(可行)时间表S一方面要将每个工件都指派给某个流水车间,另一方面还需要确定指派给同一个流水车间的工件各道工序的加工次序,即求解一个经典的三阶段流水作业问题F3||Cmax。众所周知,问题F3||Cmax一定存在最优解。因此,本文只考虑排列时间表,记Cmax(S)为在时间表S中最后加工工件的完工时间,即最大完工时间。

      引理1 给定G={J1, …, Jn}是在三阶段的流水车间进行加工的工件序列,其中Ji=(p1, i, p2, i, p3, i),令工件Ji各道工序的开工时间分别为T1, i, T2, i, T3, i,则有

      要想流水车间最大的完工时间最少,那么要求工件的加工不存在过多的等待;因此,工件的所有第一道工序的加工都是连续的,即前面工件的第一道工序完工之后马上开始后面工件的第一道工序。其次,开始加工工件的第二道工序不仅要等待前面工件的第二道工序完工,也要等到相应工件的第一道工序完工,因此,对于第二道工序存在间断那就意味着工件的第二道工序在等相应工件的第一道工序完工。最后,开始加工工件的第三道工序不仅要等待前面工件的第三道工序完工之后,也要等到相应工件的第二道工序完工,同样地,对于第三道工序存在间断那意味着工件的第三道工序在等相应工件的第二道工序完工。本文用β1, q, β2, q, β3, q分别表示流水车间Fq的三台机器的完工时间;对于一个新工件到来,这些完工时间都需要更新,因此给出指派工件的算法1。

      算法1

      输入:到达工件Ji=(p1, i, p2, i, p3, i),车间

       Fq=(β1, q, β2, q, β3, q)

      输出:指派工件JiFq上加工,并且更新

       Fq=(β1, q, β2, q, β3, q)

      β1, q =β1, q+ p1, i

      If β1, q < β2, q then β2, q =β2, q + p2, i;

       else β2, q =β1, q + p2, i;

      If β2, q < β3, q then β3, q=β3, q + p3, i;

       else β3, q =β2, q + p3, i;

    • 考虑n个三阶段工件在m个流水车间进行加工的排序问题,目标为最小化最大完工时间,其中m是任意数。不失一般性,我们将工件G={J1$,\cdots, $Jn}进行排序,其中序列{J1, …, Jt-1}记为G1,这部分工件满足:每一个工件的前两道工序所花时间之和不大于相应工件的第三道工序所花时间,即p1, i+p2, i$ \leqslant $p3, i并且这部分工件按照相应工件的第三道工序所花时间以非增的顺序进行排序;剩余工件{Jt$,\cdots, $Jn}记为G2,这些工件按任意顺序进行排序。本文定义集合σ={σ1$,\;\cdots, \;$ σm},其中σq代表的是当前已经指派工件到车间Fq进行加工的所有工件的第一道工序和第二道工序加工时间之和;同时也定义集合φ={φ1$,\;\cdots, \;$φm},其中φq代表的是当前已经指派工件到车间Fq进行加工的所有工件的第三道工序所花时间之和。结合上述的说明,给出算法2如下:

      算法2

      1:将所有即将要加工的工件进行排序形成新的序列G={J1$,\;\cdots,\; $Jn}={G1, G2}

      2:对于1≤ qm,给定初始值

      3:若工件JiG1, 找到最小的φq(1≤ qm)所对应的流水车间Fl,根据算法1将工件Ji指派到车间Fl上进行加工;更新φl = φl + p3, i

      4:若工件JiG2, 找到最小的σq (1≤ qm) 所对应的流水车间Fl,根据算法1将工件Ji指派到流水车间Fl上进行加工;更新σl =σl + p1, i+ p2, i

      5:输出按上述步骤所得时间表S以及最大值β3, q

      令Opt(G)是序列G最优的最大完工时间。在算法2所得的时间表S中,车间Fh上达到最大完工时间Cmax(S)。不失一般性,假设工件序列{J1$,\cdots, $Js}是在车间Fh上进行加工。车间Fh加工的工件中一定存在工件Jk满足:(1)工件Jk$,\;\cdots, \;$Js的第三道工序是被连续加工;(2)k是满足(1)的最小指标。同理,车间Fh加工的工件中一定存在工件Jr满足:(1)工件Jr$,\;\cdots,\; $Jk的第二道工序是被连续加工;(2)r是满足(1)的最小指标。易知,rk。基于JsJk,可以划分为三种情形来分析算法2的近似比:

      情形一:JsG1;

      情形二:JkG2, JsG2;

      情形三:JkG1, JsG2;

      根据算法2, JkG2, JsG1这种情形显然是不存在的。

    • 由于JsG1,则意味着所有在{J1$,\;\cdots,\; $Js}里的工件都属于G1,对于在车间Fh上进行加工的工件Ji,都有p1, i+p2, i$ \leqslant $p3, i,在工件集合G中,摒弃那些在工件Js之后指派的工件形成新的序列,并不影响分析算法的性能比:首先,由于工件Js是在车间Fh上的最后加工工件,所以最大完工时间不会改变;其次,摒弃工件集合G中的部分工件不会增大Opt(G)。因此假设G$ \subseteq $G1,由于G1中工件都是按工件第三道工序所花时间以非增顺序进行排序。对于工件Ji=(p1, i, p2, i, p3, i),在根据工件的第三道工序来构造新的工件Ji3=(0, 0, p3, i),令G3= (J13$,\;\cdots,\; $Jn3),显然有Opt(G)$ \geqslant $Opt(G3)。

      定理1 利用算法2,对n个三阶段工件在m个三阶段的流水车间进行加工,若G$\subseteq $G1,则φq (1≤qm)满足

      证明:若工件Ji=(p1, i, p2, i, p3, i)前面两道工序加工时间都为0,则可以将工件看成一阶段工件进行加工,这时算法2的步骤3就是著名的列表排序:在所有车间中找到最小的φq,并将工件Ji3=(0, 0, p3, i)指派到该车间进行加工。由于在加工任何工件之前G3是按第三道工序加工时间非增进行排序,因此,利用算法2,则G3的完工时间的上界为$\left({\dfrac{4}{3} \!-\! \dfrac{1}{{3m}}} \right){\rm{Opt}}\left({{{{G}}^3}} \right)$,故${\varphi _q}\! \le\! \left( {\dfrac{4}{3}\! -\! \dfrac{1}{{3m}}} \right) $${\rm{Opt}}\left( {{G}} \right)$

      对于情形一,假设G$\subseteq $G1并不影响对算法近似比的分析,因此由定理1可得到定理2

      定理2 对于情形一,利用算法2得到φq (1≤ qm),则满足${\varphi _q} \leqslant \left({\dfrac{4}{3} - \dfrac{1}{{3m}}} \right){\rm{Opt}}\left({{G}} \right),\;m \geqslant 2$

      基于以上的假设与分析,根据算法2在车间Fh达到最大完工时间Cmax(S),且在车间Fh进行加工的工件集合为{J1$,\;\cdots,\; $Js}, ${S_{10}} = \displaystyle \sum \limits_{i = 1}^{r - 1} {p_{1,\;i}}$是在车间Fh加工工件J1Jr-1的第一道工序时间之和;${S_{20}} =\displaystyle \sum \limits_{i = 1}^{r - 1} {p_{2,\;i}}$是在车间Fh加工工件J1Jr-1的第二道工序时间之和;${S_{30}} = \displaystyle \sum \limits_{i = 1}^{k - 1} {p_{3,\;i}}$是在车间Fh加工工件J1Jk-1的第三道工序时间的和。类似定义

      对于情形一的所有工件都满足p1, i+p2, i$ \leqslant $p3, i,所以为了方便书写,给出车间Fh的状态图1

      图  1  情形1中Fh加工的工件

      Figure 1.  Workpieces Fh in Case 1

      定理3 情形一,对于m ≥ 2,算法2的性能比为 $\left({\dfrac{7}{3} - \dfrac{1}{{3m}}} \right)$

      证明:通过算法2找到的时间表S在车间Fh上取得最大完工时间

      因为G$\subseteq $G1,所以

      从而有

      又因为

      所以

      从而有

      再根据定理2可知

      因此

      故得证。

    • 对于JkG2, JsG2,利用相同的符号

      又因为JkG2,所以在Jk之后的工件均有

      显然有${S_{11}} + {S_{22}} \geqslant \displaystyle \sum \limits_{i = k + 1}^{s - 1} ({p_{1,\;i}} + {p_{2,\;i}}) \geqslant {S_{31}}$在车间Fh上的状态如图2

      图  2  情形2中Fh上加工的工件

      Figure 2.  Workpieces Fh in Case 2

      定理4 情形二,对于m ≥ 2,

      证明:由于JkG2, JsG2,据算法2的步骤4,当工件Js被指派到车间Fh进行加工时,σh一定是最小值,在这里

      再根据列表排序规则可知:

      显然有:

      所以σh ≤ 2Opt(G),显然定理4成立。

      定理5 情形二,对于m ≥ 2,算法2的性能比为3

      证明:通过算法2找到的时间表S在车间Fh上取得最大完工时间

      因为

      显然有:

      再根据定理4:

      又因为

      所以

      综合以上不等式有:

    • 对于JkG1, JsG2,假设工件Jd是工件集合G1中最后一个在车间Fh加工的工件,本文利用类似的符号

      又因为JkG1, JsG2, 所以有p1, k+p2,kp3, k, p1,s+p2, sp3, s,对于在车间Fh加工工件Jd之后的工件都是在集合G2之内,显然有S12+S23S32在车间Fh上的状态如图3

      图  3  情形3中Fh上加工的工件

      Figure 3.  Workpieces Fh in Case 3

      定理6 情形三,对于m ≥ 2,

      证明:同定理4。

      定理7 情形三,对于m ≥ 2,

      证明:由于在车间Fh加工Jd+1之前的工件都是属于集合G1,所以有

      又因为

      所以有

      即结论成立。

      定理8 情形三,对于m ≥ 2,算法2的性能比为$\left({\dfrac{{23}}{6} - \dfrac{1}{{3m}}} \right)$

      证明:通过算法2找到的时间表S在车间Fh上取得最大完工时间

      由于在Jd之后的工件都是属于集合G2

      从而有

      根据定理6,7可知:

      又因为

      所以

      综合以上不等式有:

      故:

    • 本文研究了在m个三阶段的流水车间对n个三阶段工件进行加工的排序问题,其目标是最小化最大完工时间。据我们所知, 目前对这类问题并没有进行大量的研究,我们是第一个提出这个问题,且提供了有效的算法,时间复杂度为O(nlogn+mn),算法达到了$\left({\dfrac{{23}}{6} - \dfrac{1}{{3m}}} \right)$ 的近似比。

(3)  参考文献 (12) 相关文章 (20)

目录

    /

    返回文章