Online Scheduling on a Parallel Batch Machine with Delivery Times and Limited Restarts

doi:10.1007/s40305-021-00356-7

Journal of the Operations Research Society of China ›› 2022, Vol. 10 ›› Issue (1): 113-131.doi: 10.1007/s40305-021-00356-7

收稿日期:2020-09-04 修回日期:2020-12-17 出版日期:2022-03-30 发布日期:2022-03-23
基金资助:
This research was supported by the National Natural Science Foundation of China (Nos. 11701148, 11871213 and 11571321) and Henan University of Engineering (No. D2016017).

Online Scheduling on a Parallel Batch Machine with Delivery Times and Limited Restarts

Hai-Ling Liu^1,2, Xi-Wen Lu¹

1 Department of Mathematics, East China University of Science and Technology, Shanghai 200237, China;
2 College of Science, Henan University of Engineering, Zhengzhou 451191, Henan, China

Received:2020-09-04 Revised:2020-12-17 Online:2022-03-30 Published:2022-03-23
Contact: Xi-Wen Lu, Hai-Ling Liu E-mail:xwlu@ecust.edu.cn;companyion-34@163.com

摘要/Abstract

Abstract: The online scheduling on an unbounded parallel batch machine with delivery times and limited restarts is studied in this paper. Here, online means that jobs arrive over time and the characteristics of a job become known until it arrives. Limited restarts mean that once a running batch contains at least one restarted job, it cannot be restarted again. The goal is to minimize the time by which all jobs have been delivered. We consider a restricted model that the delivery time of each job is no more than its processing time. We present a best possible online algorithm with a competitive ratio of 3/2 for the problem.

Key words: Online scheduling, Parallel batch, Limited restart, Delivery time

中图分类号:

90B35

. [J]. Journal of the Operations Research Society of China, 2022, 10(1): 113-131.

Hai-Ling Liu, Xi-Wen Lu. Online Scheduling on a Parallel Batch Machine with Delivery Times and Limited Restarts[J]. Journal of the Operations Research Society of China, 2022, 10(1): 113-131.

参考文献

相关文章 9

[1]	. [J]. Journal of the Operations Research Society of China, 2021, 9(4): 909-914.
[2]	. [J]. Journal of the Operations Research Society of China, 2021, 9(2): 359-373.
[3]	. [J]. Journal of the Operations Research Society of China, 2021, 9(1): 63-77.
[4]	. [J]. Journal of the Operations Research Society of China, 2020, 8(3): 457-476.
[5]	. [J]. Journal of the Operations Research Society of China, 2020, 8(1): 133-143.
[6]	. [J]. Journal of the Operations Research Society of China, 2020, 8(1): 165-175.
[7]	. [J]. Journal of the Operations Research Society of China, 2019, 7(3): 475-484.
[8]	. [J]. Journal of the Operations Research Society of China, 2019, 7(3): 485-500.
[9]	. [J]. Journal of the Operations Research Society of China, 2019, 7(2): 303-319.

Online Scheduling on a Parallel Batch Machine with Delivery Times and Limited Restarts

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 9

编辑推荐

Metrics

本文评价