中文摘要：

考虑图形处理中的一类两台处理器上的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.