高级检索

  • 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

  • 摘要: 研究了n个三阶段工件在m个流水车间进行加工的排序问题,目标为最小化最大完工时间。当m是定值时,该问题是NP困难;当m>2时,问题是强NP困难。将问题分解成3种情形,情形1给出了$\dfrac{ 7}{ 3}-\dfrac {1}{3m} $的近似比;情形2给出了一个3的近似比;情形3给出了近似比为$\dfrac{23}6-\dfrac 1{3m} $。结合3种情形,最终给出了性能比为$\dfrac{23}6-\dfrac 1{3m} $的算法。
  • 图 FIG. 155.  FIG. 155.

    Figure FIG. 155..  FIG. 155.

    图 1  情形1中Fh中的工件

    Figure 1.  Workpieces in the Fh workshop in case 1

    图 2  情形2中Fh中的工件

    Figure 2.  Workpieces in the Fh workshop in case 2

    图 3  情形3中Fh中的工件

    Figure 3.  Workpieces in the Fh workshop in case 3

  • [1] HE D W, KUSIAK A, ARTIBA A. A scheduling problem in glass manufacturing[J]. IIE Transactions, 1996, 28(2): 129-139. doi: 10.1080/07408179608966258
    [2] WU G W, CHEN J E, WANG J X. On approximation algorithms for two-stage scheduling problems[C]// International Workshop on Frontiers in Algorithmics. Chengdu, China: [s.n.], 2017: 241-253.
    [3] GAREY M R, JOHNSON D S. Computers and Intractability: A Guide to the Theory of NP-Completeness[M]. New York: The MIT press, 1979.
    [4] GRAHAM R L. Bounds for certain multiprocessing anomalies[J]. Bell System Technical Journal, 1966, 45(9): 1563-1581. doi: 10.1002/j.1538-7305.1966.tb01709.x
    [5] GRAHAM R L. Bounds on multiprocessing timing anomalies[J]. SIAM Journal on Applied Mathematics, 1969, 17(2): 416-429. doi: 10.1137/0117039
    [6] SAHNI S K. Algorithms for scheduling independent tasks[J]. Journal of the ACM, 1976, 23(1): 116-127. doi: 10.1145/321921.321934
    [7] HOCHBAUM D S, SHMOYS D B. Using dual approximation algorithms for scheduling problems theoretical and practical results[J]. Journal of the ACM, 1987, 34(1): 144-162. doi: 10.1145/7531.7535
    [8] VAIRAKTARAKIS G, ELHAFSI M. The use of flowlines to simplify routing complexity in two-stage flowshops[J]. IIE Transactions, 2000, 32(8): 687-699.
    [9] ZHANG X D, VELDE STEEF VAN DE. Approximation algorithms for the parallel flow shop problem[J]. European Journal of Operational Research, 2012, 216(3): 544-552. doi: 10.1016/j.ejor.2011.08.007
    [10] DONG J, TONG W, LUO T, et al. An FPTAS for the parallel two-stage flowshop problem[J]. Theoretical Computer Science, 2017, 657: 64-72. doi: 10.1016/j.tcs.2016.04.046
    [11] TONG W T, MIYANO E, GOEBEL R, et al. A PTAS for the multiple parallel identical multi-stage flow-shops to minimize the makespan[C]// International Workshop on Frontiers in Algorithmics. Damingzhu, Sergey Berreg: [s.n.], 2016: 227–237.
    [12] WU G, WANG J. Approximation algorithms for two-stage scheduling problems[C]// [s.l.]: [s.n.] International Computing and Combinatorics Conference, 2017: 516-528.
  • [1] 于中宝邵方明 . 并行系统中排列图的可靠性近似算法. 华东理工大学学报(自然科学版), 2019, 45(): 1-5. doi: 10.14135/j.cnki.1006-3080.20180531001
    [2] 黄佳琳张丫丫顾幸生 . 基于改进生物地理学优化算法的分布式装配置换流水车间调度问题. 华东理工大学学报(自然科学版), 2019, 45(): 1-12. doi: 10.14133/j.cnki.1006-3080.20190828001
    [3] 徐震浩周畅张凌波顾幸生 . 柔性作业车间的成套订单调度问题. 华东理工大学学报(自然科学版), 2020, 46(1): 58-67. doi: 10.14135/j.cnki.1006-3080.20181109001
    [4] 陈丹丹王薇徐以汎 . 基于降维的全局优化近似解法. 华东理工大学学报(自然科学版), 2019, 45(6): 995-1000. doi: 10.14135/j.cnki.1006-3080.2018071700
    [5] 赵菡诸葛晶晶林家骏 . 飞行状态敏感的关联门调节算法. 华东理工大学学报(自然科学版), 2019, 45(5): 795-800. doi: 10.14135/j.cnki.1006-3080.20180622003
    [6] 吉祥虞慧群范贵生孙怀英 . 基于蚁群算法的延时感知VANET路由协议. 华东理工大学学报(自然科学版), 2020, 46(1): 128-134. doi: 10.14135/j.cnki.1006-3080.20181116001
    [7] 王德勋虞慧群范贵生 . 基于深度学习的面部动作单元识别算法. 华东理工大学学报(自然科学版), 2020, 46(2): 269-276. doi: 10.14135/j.cnki.1006-3080.20190107003
    [8] 宋振振陈兰岚娄晓光 . 基于时序卷积网络的情感识别算法. 华东理工大学学报(自然科学版), 2020, 46(4): 574-582. doi: 10.14135/j.cnki.1006-3080.20190508001
    [9] 高天阳虞慧群范贵生 . 基于模拟退火遗传算法的云资源调度方法. 华东理工大学学报(自然科学版), 2019, 45(3): 471-477. doi: 10.14135/j.cnki.1006-3080.20180416001
    [10] 陈立皇程华房一泉 . 基于注意力机制的DGA域名检测算法. 华东理工大学学报(自然科学版), 2019, 45(3): 478-485. doi: 10.14135/j.cnki.1006-3080.20180326002
    [11] 王学武闵永顾幸生 . 基于密度聚类的多目标粒子群优化算法. 华东理工大学学报(自然科学版), 2019, 45(3): 449-457. doi: 10.14135/j.cnki.1006-3080.20180321005
    [12] 常青张天宇赵冰冰 . 基于机器视觉的手机异形主板非标自动化检测算法. 华东理工大学学报(自然科学版), 2019, 45(4): 632-638. doi: 10.14135/j.cnki.1006-3080.20180416006
    [13] 颜建军刘章鹏刘国萍郭睿王忆勤付晶晶钱鹏 . 基于深度森林算法的慢性胃炎中医证候分类. 华东理工大学学报(自然科学版), 2019, 45(4): 593-599. doi: 10.14135/j.cnki.1006-3080.20180410001
    [14] 高炳舒刘士荣 . 基于BoW模型的RGB-D SLAM算法的运动轨迹估计. 华东理工大学学报(自然科学版), 2019, 45(4): 623-631. doi: 10.14135/j.cnki.1006-3080.20180419001
    [15] 曹雅茜黄海燕 . 基于代价敏感大间隔分布机的不平衡数据分类算法. 华东理工大学学报(自然科学版), 2019, 45(4): 606-613. doi: 10.14135/j.cnki.1006-3080.20180515001
    [16] 孙佩袁伟娜程华 . 一种新的基于异步NOMA的串行干扰消除算法. 华东理工大学学报(自然科学版), 2019, 45(5): 783-788. doi: 10.14135/j.cnki.1006-3080.20180412008
    [17] 张剑超杜文莉覃水 . 基于新型自适应采样算法的催化重整过程代理模型. 华东理工大学学报(自然科学版), 2019, 45(6): 928-937. doi: 10.14135/j.cnki.1006-3080.20180915001
    [18] 陈鹏罗娜 . 基于竞争机制差分进化算法的无分流换热网络优化. 华东理工大学学报(自然科学版), 2019, 45(6): 970-979. doi: 10.14135/j.cnki.1006-3080.20181015004
    [19] 叶贞成王鑫梅华 . 基于改进差分进化算法的裂解反应动力学系数辨识. 华东理工大学学报(自然科学版), 2019, 45(): 1-10. doi: 10.14135/j.cnki.1006-3080.20190910002
    [20] 王学武夏泽龙顾幸生 . 基于事件触发的自适应邻域多目标进化算法. 华东理工大学学报(自然科学版), 2020, 46(1): 48-57. doi: 10.14135/j.cnki.1006-3080.20181120005
  • 加载中
图(4)
计量
  • 文章访问数:  6199
  • HTML全文浏览量:  2433
  • PDF下载量:  10
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-02-06
  • 网络出版日期:  2019-09-27
  • 刊出日期:  2019-12-01

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

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

摘要: 研究了n个三阶段工件在m个流水车间进行加工的排序问题,目标为最小化最大完工时间。当m是定值时,该问题是NP困难;当m>2时,问题是强NP困难。将问题分解成3种情形,情形1给出了\begin{document}$\dfrac{ 7}{ 3}-\dfrac {1}{3m} $\end{document}的近似比;情形2给出了一个3的近似比;情形3给出了近似比为\begin{document}$\dfrac{23}6-\dfrac 1{3m} $\end{document}。结合3种情形,最终给出了性能比为\begin{document}$\dfrac{23}6-\dfrac 1{3m} $\end{document}的算法。

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-\dfrac 1 m $的近似比,后来他对算法进行了一定的改进,并且将近似比改为$\dfrac 4 3-\dfrac 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问题并给出了$\dfrac{ 3}{ 2} $近似比,同时还对(3, 2)-PFS问题给出了$\dfrac{12}{7} $近似算法,这些都是利用Johnoson's算法将工件分成几类。另外,Dong等[10]利用动态规划原理解决了(m, 2)-PFS问题,其中m是定值,并且给出了完全多项式时间近似方案;对于(m, k)-PFS这类问题,当mk都是定值时,Lin等[11]给出了多项式时间近似方案。对于(m, 2)-PFS这类问题 (m是任意数),Wu等[12]给出了一个近似比为$\dfrac{17}{6} $的近似算法。

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

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

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

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

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

      (4) 每个工件都必须指派给某个流水车间进行加工,从而每个工件的3道工序都在相同的流水车间加工。如果工件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的3台机器的完工时间;当一个新工件到来,这些完工时间都需要更新,因此给出指派工件的算法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,给定初始值$\;{\beta _{3,\;q}} = 0,\;{\sigma _q} = 0$$ {\varphi _q} = 0 $

      (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的第3道工序是被连续加工;

      (2) k是满足(1)的最小指标。

      同理,车间Fh加工的工件中一定存在工件Jr满足:

      (1)工件Jr$,\;\cdots,\; $Jk的第2道工序是被连续加工;

      (2) r是满足(1)的最小指标。

      易知rk。基于JsJk,可以划分为3种情形来分析算法2的近似比:

      情形1:JsG1;

      情形2:JkG2, JsG2;

      情形3: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中工件都是按工件第3道工序所花时间以非增顺序进行排序。对于工件Ji=(p1, i, p2, i, p3, i),在根据工件的第3道工序来构造新的工件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是按第3道工序加工时间非增进行排序,因此,利用算法2,则G3的完工时间的上界为$\left({\dfrac{4}{3} \!-\! \dfrac{1}{{3m}}} \right) {\rm{Opt}}\left({{{{G}}^3}} \right)$,故${\varphi _q}\! \leqslant\! \left( {\dfrac{4}{3}\! -\! \dfrac{1}{{3m}}} \right) $${\rm{Opt}}\left( {{G}} \right)$

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

      定理2 对于情形1,利用算法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的第1道工序时间之和;${S_{20}} =\displaystyle \sum \limits_{i = 1}^{r - 1} {p_{2,\;i}}$是在车间Fh加工工件J1Jr−1的第2道工序时间之和;${S_{30}} = \displaystyle \sum \limits_{i = 1}^{k - 1} {p_{3,\;i}}$是在车间Fh加工工件J1Jk−1的第3道工序时间的和。类似定义

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

      图  1  情形1中Fh中的工件

      Figure 1.  Workpieces in the Fh workshop in case 1

      定理3 情形1,对于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 in the Fh workshop in case 2

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

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

      根据列表排序规则可知:

      显然有

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

      定理5 情形2,对于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 in the Fh workshop in case 3

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

      证明:同定理4。

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

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

      又因为

      所以有

      即结论成立。

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

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

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

      从而有

      根据定理6和定理7可知:

      又因为

      所以

      综合以上不等式有

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

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

目录

    /

    返回文章