上海大学学报（英文版）
上海大學學報（英文版）
상해대학학보（영문판）
JOURNAL OF SHANGHAI UNIVERSITY (ENGLISH EDITION)
2007年
1期
33-38
,共6页
scheduling%fiexiable flowshop%identical machine%batch processor%complexity%approximation algorithm
A hybrid two-stage flowshop scheduling problem was considered which involves m identical parallel machines at Stage 1 and a burn-in processor M at Stage 2, and the makespan was taken as the minimization objective. This scheduling problem is NP-hard in general. We divide it into eight subcases. Except for the following two subcases: (1) b ≥ an, max{m, B} ＜ n;(2) a1 ≤ b ≤ an, m ≤B ＜ n, for all other subcases, their NP-hardness was proved or pointed out, corresponding approximation algorithms were conducted and their worst-case performances were estimated. In all these approximation algorithms, the Multifit and PTAS algorithms were respectively used, as the jobs were scheduled in m identical parallel machines.
