高级检索

  • ISSN 1006-3080
  • CN 31-1691/TQ

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

曹移林 余炜

曹移林, 余炜. 平行三阶段流水作业问题的近似算法[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

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

doi: 10.14135/j.cnki.1006-3080.20180206001
基金项目: 中央高校基本科研业务费(22220184028)
详细信息
    作者简介:

    曹移林(1990-),男,硕士生,主要研究方向为排序与组合优化。E-mail:Caoyilin0908@163.com

    通讯作者:

    余 炜,E-mail:yuwei@ecust.edu.cn

  • 中图分类号: O223

An Approximation Algorithm for the Parallel Three-Stage Flowshop Scheduling

  • 摘要: 研究了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} $的算法。

     

  • 图  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.
  • 加载中
图(3)
计量
  • 文章访问数:  6751
  • HTML全文浏览量:  2725
  • PDF下载量:  20
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-02-06
  • 网络出版日期:  2019-09-27
  • 刊出日期:  2019-12-01

目录

    /

    返回文章
    返回