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

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

作　　者：蒋义伟[1] 魏麒[2] 

机构地区：[1]浙江理工大学理学院,杭州310018 [2]浙江大学宁波理工学院,宁波315100

出　　处：《自动化学报》2011年第11期1381-1386,共6页Acta Automatica Sinica

基　　金：国家自然科学基金(11001242;11071220);浙江省自然科学基金(Y6090175;Y6090554)资助~~

摘　　要：考虑图形处理中的一类两台处理器上的Flow-shop调度问题,目标是极小化最早完工时间.每个任务包含两道工序,第一道工序可以在两台处理器中的任何一台上处理,而第二道则只能在第二台处理器上处理,且必须在第一道工序完工之后才能进行.对该问题,设计了一个改进的多项式时间近似算法,在绝对性能方面,该算法的最坏情况界为3/2;而从实例计算的平均效果方面,该算法所得的结果比原有的贪婪算法所得的结果要好20%左右.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.

关 键 词：调度 近似算法 最早完成时间 流水作业 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]