摘要
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.
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.
基金
Project supported by the Science and Technology Development Fund of Shanghai University(Grant No.A.10-0101-06-0017)
