A TWO-STAGE SEMI-HYBRID FLOWSHOP PROBLEM IN GRAPHICS PROCESSING

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.

A two-stage semi-hybrid flowshop problem in graphics processing

In this paper, a two-stage semi-hybrid flowshop problem which appears in graphics processing is studied. For this problem, there are two machines M ₁ and M ₂, and a set of independent jobs J={J ₁ ,J ₂ ,...,J _n }. Each J _i consists of two tasks A _i and B _i , and task A _i must be completed before task B _i can start. Furthermore, task A _i can be processed on M ₁ for a _i time units, or on M ₂ for a′ _i time units, while task B _i can only be processed on M ₂ for b _i 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. Research supported by the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of MOE, China, and NSFC (10271110).