| 组成于平行机和批处理机的二阶段混合流水作业问题 |
| |
| 引用本文： | 何龙敏,孙世杰.组成于平行机和批处理机的二阶段混合流水作业问题[J].上海大学学报(英文版),2007,11(1):33-33. |
| |
| 作者姓名： | 何龙敏 孙世杰 |
| |
| 作者单位： | Department of Mathematics, College of Sciences, Shanghai University, Shanghai 200444, P. R. China |
| |
| 基金项目： | 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.
|
| 关 键 词： | 平行机 批处理机 二阶段 混合流水作业 |
| 收稿时间： | 2005-01-04 |
| 修稿时间： | 2006-03-11 |
A hybrid two-stage flexible flowshop scheduling problem with m identical parallel machines and a burn-in processor separately |
| |
| Long-min He PhD,Shi-jie Sun.A hybrid two-stage flexible flowshop scheduling problem with m identical parallel machines and a burn-in processor separately[J].Journal of Shanghai University(English Edition),2007,11(1):33-33. |
| |
| Authors: | Long-min He PhD Shi-jie Sun |
| |
| Institution: | Department of Mathematics, College of Sciences, Shanghai University, Shanghai 200444, P. R. China |
| |
| Abstract: | 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 ⩾ a
n, max{m B} < n; (2) a
1 ⩽ b ⩽ a
n, 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) |
| |
| Keywords: | scheduling fiexiable flowshop identical machine batch processor complexity approximation algorithm |
| 本文献已被 维普 万方数据 SpringerLink 等数据库收录！ |
| 点击此处可从《上海大学学报(英文版)》浏览原始摘要信息 |
| 点击此处可从《上海大学学报(英文版)》下载免费的PDF全文 |
