| Parallel Machine Scheduling with Special Jobs |
| |
| 作者姓名： | 王振波 邢文训 |
| |
| 作者单位： | Department of Mathematical Sciences Tsinghua University，Beijing 100084 China，Department of Mathematical Sciences Tsinghua University，Beijing 100084 China |
| |
| 基金项目： | Supported by the National Natural Science Foundation of China (No.70471008) |
| |
| 摘 要： | Introduction Parallel machine scheduling problems arise in many fields, including service and manufacturing systems. A parallel machine scheduling problem has a sequence of n jobs with processing times { p1 , p 2 , ... , p n } to be processed on m paralle…
|
| 关 键 词： | 并行机器排程 最坏情况分析 启发式方法 数学规划 |
| 收稿时间： | 2004-06-01 |
| 修稿时间： | 2004-06-012005-01-18 |
Parallel Machine Scheduling with Special Jobs |
| |
| WANG Zhenbo,XING Wenxun.Parallel Machine Scheduling with Special Jobs[J].Tsinghua Science and Technology,2006,11(1):107-110. |
| |
| Authors: | WANG Zhenbo XING Wenxun |
| |
| Institution: | Department of Mathematical Sciences, Tsinghua University, Beijing 100084, China |
| |
| Abstract: | This paper considers parallel machine scheduling with special jobs. Normal jobs can be processed on any of the parallel machines, while the special jobs can only be processed on one machine. The problem is analyzed for various manufacturing conditions and service requirements. The off-line scheduling problem is transformed into a classical parallel machine scheduling problem. The on-line scheduling uses the FCFS (first come, first served), SWSC (special window for special customers), and FFFS (first fit, first served) algorithms to satisfy the various requirements. Furthermore, this paper proves that FCFS has a competitive ratio of m, where m is the number of parallel machines, and this bound is asymptotically tight, SWSC has a competitive ratio of 2 and FFFS has a competitive ratio of 3–2/m, and these bounds are tight. |
| |
| Keywords: | parallel machine scheduling on-line worst-case analysis heuristics |
| 本文献已被 CNKI 维普 万方数据 ScienceDirect 等数据库收录！ |
