We investigate the online scheduling problem on identical parallel-batch machines to minimize the maximum weighted completion time.In this problem,jobs arrive over time and the processing times(of the jobs)are identic...We investigate the online scheduling problem on identical parallel-batch machines to minimize the maximum weighted completion time.In this problem,jobs arrive over time and the processing times(of the jobs)are identical,and the batch capacity is bounded.For this problem,we provide a best possible online algorithm with a competitive ratio of(√5+1)/2.Moreover,when restricted to dense-algorithms,we present a best possible dense-algorithm with a competitive ratio of 2.展开更多
基金This research was supported by the National Natural Science Foundation of China(Nos.11571321 and 11401065)the Natural Science Foundation of Henan Province(No.15IRTSTHN006).
文摘We investigate the online scheduling problem on identical parallel-batch machines to minimize the maximum weighted completion time.In this problem,jobs arrive over time and the processing times(of the jobs)are identical,and the batch capacity is bounded.For this problem,we provide a best possible online algorithm with a competitive ratio of(√5+1)/2.Moreover,when restricted to dense-algorithms,we present a best possible dense-algorithm with a competitive ratio of 2.
