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