In this paper we consider an online scheduling of parallel jobs with preemption on identical machines, where jobs arrive over time. The objective is to minimize the makespan. For the problem that jobs have only two po...In this paper we consider an online scheduling of parallel jobs with preemption on identical machines, where jobs arrive over time. The objective is to minimize the makespan. For the problem that jobs have only two possible widths mj = 1 or m, we present an optimal online algorithm by using "temporary schedule".展开更多
基金Project supported by the National Natural Science Foundation of China (Grant No.10971131)the Shanghai Leading AcademicDiscipline Project (Grant No.S30104)the Innovation Foundation of Shanghai University (Grant No.SHUCX091077)
文摘In this paper we consider an online scheduling of parallel jobs with preemption on identical machines, where jobs arrive over time. The objective is to minimize the makespan. For the problem that jobs have only two possible widths mj = 1 or m, we present an optimal online algorithm by using "temporary schedule".