This paper considers a hybrid two-stage flow-shop scheduling problem with m identical parallel machines on one stage and a batch processor on the other stage. The processing time of job Jj on any of m identical parall...This paper considers a hybrid two-stage flow-shop scheduling problem with m identical parallel machines on one stage and a batch processor on the other stage. The processing time of job Jj on any of m identical parallel machines is aj≡a （j∈N）, and the processing time of job Jj is bj（j∈N） on a batch processorM. We take makespan （Cmax） as our minimization objective. In this paper, for the problem of FSMP-BI （m identical parallel machines on the first stage and a batch processor on the second stage）, based on the algorithm given by Sung and Choung for the problem of 1 ｜ri, BI｜Cmax under the constraint of the given processing sequence, we develop an optimal dynamic programming Algorithm H1 for it in max {O（nlogn）, O（nB）} time. A max {O（nlogn） , O（nB）}time symmetric Algorithm H2 is given then for the problem of BI-FSMP （a batch processor on the first stage and m identical parallel machines on the second stage）.展开更多
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. Thi...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.展开更多
基金Sponsored by the Innovation Foundation of Shanghai University(Grant No.A.10-0101-07 -406)NNSF of China(Grant No.60874039)
文摘This paper considers a hybrid two-stage flow-shop scheduling problem with m identical parallel machines on one stage and a batch processor on the other stage. The processing time of job Jj on any of m identical parallel machines is aj≡a （j∈N）, and the processing time of job Jj is bj（j∈N） on a batch processorM. We take makespan （Cmax） as our minimization objective. In this paper, for the problem of FSMP-BI （m identical parallel machines on the first stage and a batch processor on the second stage）, based on the algorithm given by Sung and Choung for the problem of 1 ｜ri, BI｜Cmax under the constraint of the given processing sequence, we develop an optimal dynamic programming Algorithm H1 for it in max {O（nlogn）, O（nB）} time. A max {O（nlogn） , O（nB）}time symmetric Algorithm H2 is given then for the problem of BI-FSMP （a batch processor on the first stage and m identical parallel machines on the second stage）.
基金Project supported by the Science and Technology Development Fund of Shanghai University(Grant No.A.10-0101-06-0017)
文摘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.
