Journal of the Operations Research Society of China >
2018 , Vol. 6 >Issue 3: 455 - 466
DOI: https://doi.org/https://doi.org/10.1007/s40305-017-0179-x
Online Scheduling on Bounded Batch Machines to Minimize the MaximumWeighted Completion Time
Online published: 2018-09-30
Supported by
This research was supported by the National Natural Science Foundation of China (Nos. 11571321 and 11401065) and 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 . Moreover, when restricted to dense-algorithms, we present a best possible dense-algorithm with a competitive ratio of 2.
Wen-Hua Li, Xing Chai . Online Scheduling on Bounded Batch Machines to Minimize the MaximumWeighted Completion Time[J]. Journal of the Operations Research Society of China, 2018 , 6(3) : 455 -466 . DOI: https://doi.org/10.1007/s40305-017-0179-x
/
| 〈 |
|
〉 |
