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

作　　者：Wei Qi He Yong 

机构地区：[1]Dept. of Math. ,Zhejiang Univ. ,Hangzhou 310027,China

出　　处：《Applied Mathematics(A Journal of Chinese Universities)》2005年第4期393-400,共8页高校应用数学学报（英文版）（B辑）

基　　金：ResearchsupportedbytheTeachingandResearchAwardProgramforOutstandingYoungTeachersinHigherEducationInstitutionsofMOE,China,andNSFC(10271110).

摘　　要：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.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.

关 键 词：flowshop scheduling computational complexity approximation algorithm worst-case ratio. 

分 类 号：O24[理学—计算数学]