中文摘要：

在这篇论文，出现在图形处理的一个二阶段的半混血儿流动商店问题被学习。为这个问题，有二台机器 M_1 和 M_2，和一套独立工作 J={ J_1， J_2，…， J_n } 。每 J_i 由二项任务组成在任务 B_i 能开始以前， A_i 和 B_i，和任务 A_i 必须被完成。而且，任务 A_i 能为 a_i 时间单位在 M_1 上被处理，否则在为′ _ 的 M_2 上，我预定单位，当任务 B_i 能仅仅为 b_i 时间单位在 M_2 上被处理时。工作和机器在时间零点是可得到的，没有先买权被允许。目的是最小化最大的工作结束时间。这个问题是 NP 难的，这被显示出。并且 apseudo 多项式时间最佳的算法被介绍。有 2 也是的最坏的比率的一个多项式时间近似算法介绍了。

英文摘要：

In this paper,a two-stage semi-hybrid flowshop problem which appears in graphics processing is studied. For this problem, there are two machines M1 and M2, and a set of independent jobs J= {J1 ,J2 ,…,Jn }. Each Ji consists of two tasks Ai and Bi ,and task Ai must be completed before task Bi can start. Furthermore ,task Ai can be processed on M1 for ai time units ,or on Mw for ai^J time units ,while task Bi can only be processed on M2 for bi time units. Jobs and machines are available at time zero and no preemption is allowed. The objective is to minimize the maximum job completion time. It is showed that this problem is NP-hard. And a pseudo-polynomial time optimal algorithm is presented. A polynomial time approximation algorithm with worst-case ratio 2 is also presented.