高级检索

    曹移林, 余炜. 平行三阶段流水作业问题的近似算法[J]. 华东理工大学学报(自然科学版), 2019, 45(6): 989-994. DOI: 10.14135/j.cnki.1006-3080.20180206001
    引用本文: 曹移林, 余炜. 平行三阶段流水作业问题的近似算法[J]. 华东理工大学学报(自然科学版), 2019, 45(6): 989-994. DOI: 10.14135/j.cnki.1006-3080.20180206001
    CAO Yilin, YU Wei. An Approximation Algorithm for the Parallel Three-Stage Flowshop Scheduling[J]. Journal of East China University of Science and Technology, 2019, 45(6): 989-994. DOI: 10.14135/j.cnki.1006-3080.20180206001
    Citation: CAO Yilin, YU Wei. An Approximation Algorithm for the Parallel Three-Stage Flowshop Scheduling[J]. Journal of East China University of Science and Technology, 2019, 45(6): 989-994. DOI: 10.14135/j.cnki.1006-3080.20180206001

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

    An Approximation Algorithm for the Parallel Three-Stage Flowshop Scheduling

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

       

      Abstract: The problem that schedules n three-stage jobs on m three-stage flowshops with the objective of minimizing the makespan was studied. When m is fixed, the problem is NP-hard; When m is arbitrary larger than 2, the problem is strongly NP-hard. For this problem, the present work is divided into three situations for discussion: In case 1, we gave an approximate ratio of \dfrac 7 3-\dfrac 13m ; in case 2, we gave an approximate ratio of three; while in case three, there was an approximate ratio of \dfrac 236-\dfrac 13m . Finaly we gave an approximation algorithm with a worst case ratio of \dfrac 236-\dfrac 13m .

       

    /

    返回文章
    返回