Online Scheduling on Bounded Batch Machines to Minimize the MaximumWeighted Completion Time

doi:https://doi.org/10.1007/s40305-017-0179-x

Journal of the Operations Research Society of China ›› 2018, Vol. 6 ›› Issue (3): 455-466.doi: https://doi.org/10.1007/s40305-017-0179-x

所属专题： Management Science

出版日期:2018-09-30 发布日期:2018-09-30

Online Scheduling on Bounded Batch Machines to Minimize the MaximumWeighted Completion Time

Wen-Hua Li^1,2 ·，Xing Chai¹

1 School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China
2 Henan Key Laboratory of Financial Engineering, Zhengzhou 450001, China

Online:2018-09-30 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).

摘要/Abstract

Abstract:

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 $(\sqrt{5} + 1) / 2$ . Moreover, when restricted to dense-algorithms, we present a best possible dense-algorithm with a competitive ratio of 2.

Key words: Scheduling ·, Online algorithms ·, Maximum weighted completion time ·, Competitive ratio

. [J]. Journal of the Operations Research Society of China, 2018, 6(3): 455-466.

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.

Online Scheduling on Bounded Batch Machines to Minimize the MaximumWeighted Completion Time

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

编辑推荐

Metrics

本文评价