Parallel Machine Scheduling with Special Jobs  

作　　者：王振波 邢文训 

机构地区：[1]Department of Mathematical Sciences, Tsinghua University,Beijing 100084, China

出　　处：《Tsinghua Science and Technology》2006年第1期107-110,共4页清华大学学报（自然科学版（英文版）

基　　金：Supported by the National Natural Science Foundation of China (No.70471008)

摘　　要：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.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.

关 键 词：parallel machine scheduling ON-LINE worst-case analysis HEURISTICS 

分 类 号：TH16[机械工程—机械制造及自动化]