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

 引用本文: 曹移林, 余炜. 平行三阶段流水作业问题的近似算法[J]. 华东理工大学学报（自然科学版）, 2019, 45(6): 989-994.
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.

• 中图分类号: 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. [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. [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. [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. [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. [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. [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.

##### 计量
• 文章访问数:  6751
• HTML全文浏览量:  2725
• PDF下载量:  20
• 被引次数: 0
##### 出版历程
• 收稿日期:  2018-02-06
• 网络出版日期:  2019-09-27
• 刊出日期:  2019-12-01

/

• 分享
• 用微信扫码二维码

分享至好友和朋友圈