图形处理中一类 Flow-shop 问题的改进算法

蒋义伟; 魏麒

doi:10.3724/SP.J.1004.2011.01381

图形处理中一类 Flow-shop 问题的改进算法

doi: 10.3724/SP.J.1004.2011.01381

蒋义伟^1, ,,
魏麒²

1.
浙江理工大学理学院杭州 310018;
2.
浙江大学宁波理工学院宁波 315100

详细信息

通讯作者:
蒋义伟浙江理工大学理学院副教授. 2007年获浙江大学数学系博士学位. 主要研究方向为组合优化, 调度理论, 算法设计与分析. E-mail: mathjyw@yahoo.com.cn

计量
- 文章访问数: 2141
- HTML全文浏览量: 30
- PDF下载量: 778
- 被引次数: 0
出版历程
- 收稿日期: 2011-01-21
- 修回日期: 2011-06-13
- 刊出日期: 2011-11-20

An Improved Algorithm for a Hybrid Flow-shop Problem in Graphics Processing

JIANG Yi-Wei^{1
, ,},
WEI Qi²

1.
Faculty of Science, Zhejiang Sci-Tech University, Hangzhou 310018;
2.
Ningbo Institute of Technology, Zhejiang University, Ningbo 315100

摘要

摘要: 考虑图形处理中的一类两台处理器上的Flow-shop调度问题, 目标是极小化最早完工时间. 每个任务包含两道工序, 第一道工序可以在两台处理器中的任何一台上处理, 而第二道则只能在第二台处理器上处理, 且必须在第一道工序完工之后才能进行. 对该问题, 设计了一个改进的多项式时间近似算法, 在绝对性能方面, 该算法的最坏情况界为3/2; 而从实例计算的平均效果方面, 该算法所得的结果比原有的贪婪算法所得的结果要好20% 左右.
- 调度 /
- 近似算法 /
- 最早完成时间 /
- 流水作业
Abstract: This paper considers a variant of scheduling problem of minimizing makespan in a two-machine flow-shop. In this variant, each job has two tasks. The first task can be processed on either machine while the second task must be processed on the second machine and cannot be processed unless the first task has been processed. The second task is allowed to be processed at any time after completing the first task. We present an improved polynomial time approximation algorithm with worst-case ratio of 3/2, which is 20% better than the greedy-like algorithm in the average case.
- Scheduling /
- approximation algorithm /
- makespan /
- flow-shop

HTML全文

参考文献(1)

[1]

Wei Q, He Y. A two-stage semi-hybrid flowshop problem in graphics processing. Applied Mathematics —— A Journal of Chinese Universities, 2005, 20(4): 393-400[2] Kouvelis P, Vairaktarakis G. Flowshops with processing flexibility across production stages. IIE Transactions, 1998, 30(8): 735-746[3] Vairaktarakis G, Lee C Y. Analysis of algorithms for two-stage flowshops with multi-processor task flexibility. Naval Research Logistics, 2004, 51(1): 44-59[4] Boudhar M, Meziani N. Two-stage hybrid flow shop with recirculation. International Transactions in Operational Research, 2010, 17(2): 239-255[5] Besbes W, Teghem J, Loukil T. Scheduling hybrid flow shop problem with non-fixed availability constraints. European Journal of Industrial Engineering, 2010, 4(4): 413-433[6] Wang Wan-Liang, Yao Ming-Hai, Wu Yun-Gao, Wu Qi-Di. Hybrid flow-shop scheduling approach based on genetic algorithm. Journal of System Simulation, 2002, 14(7): 863-869(王万良, 姚明海, 吴云高, 吴启迪. 基于遗传算法的混合Flow-shop调度方法. 系统仿真学报, 2002, 14(7): 863-869)[7] Oguz C, Ercan M F. A genetic algorithm hybrid flow-shop scheduling with multiprocessor tasks. Journal of Scheduling, 2005, 8(4): 323-351[8] Zhang Y, Li X P, Wang Q. Hybrid genetic algorithm for permutation flowshop scheduling problems with total flowtime minimization. European Journal of Operational Research, 2009, 196(3): 869-876[9] Zhan Y, Qiu C H, Xue K. A hybrid genetic algorithm for hybrid flow shop scheduling with load balancing. Key Engineering Materials, 2009, 392-394: 250-255[10] Hu Rong, Qian Bin. A hybrid differential evolution algorithm for stochastic flow shop scheduling with limited buffers. Acta Automatica Sinica, 2009, 35(12): 1580-1586(胡蓉, 钱斌. 一种求解随机有限缓冲区流水线调度的混合差分进化算法. 自动化学报, 2009, 35(12): 1580-1586)[11] Gupta J N D, Koulamas C P, Kyparisis G J, Potts C N, Strusevich V A. Scheduling three-operation jobs in a two-machine flow shop to minimize makespan. Annals of Operations Research, 2004, 129(1-4): 171-185[12] Wei Qi, Jiang Yi-Wei. Approximation algorithms for a two-stage hybrid flow shop. Journal of Software, to be published[13] Johnson S M. . Naval Research Logistics Quarterly, 1954, 1(1): 61-68[14] Graham R L. Bounds for certain multiprocessing anomalies. Bell System Technical Journal, 1966, 45(9): 1563-1581

施引文献

资源附件(0)

访问统计