A class of generalized multiprocessor scheduling problems

The paper discusses a class of generalized multiprocessor scheduling problems which is to arrange some independent jobs on almost identical processors. It is different from the classical multiprocessor scheduling, as each job may only be processed by some processors, not all. In this paper, we first prove that the problems of minimizing makespan and minimizing the total weighted completion time can be solved by polynomial algorithms if all processing times are unit times. Then for arbitrary processing time, we try to analyze the worst performance of the list schedule method and longest processing time method when there are only two machines involved. We show that the bounds for the list schedule and longest processing time are exactly two.