论文部分内容阅读
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) al- gorithms 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 on-line scheduling uses the FCFS (first come, first served), SWSC (special window for special customers), and FFFS (first fit, first served) al- gorithms to The paper proves that FCFS has a competitive ratio of m, where m is the number of parallel machines, and this bound is asymptotically tight, the SWSC has a competitive ratio of 2 and FFFS has a competitive ratio of 3 ? 2 / m, and these bounds are tight.