View in EDS

Best possible algorithms for online scheduling on identical batch machines with periodic pulse interruptions.

Saved in:
Bibliographic Details
Title: Best possible algorithms for online scheduling on identical batch machines with periodic pulse interruptions.
Authors: Lin, Ran1,2 (AUTHOR), Wang, Jun-Qiang1,2 (AUTHOR) wangjq@nwpu.edu.cn, Liu, Zhixin3 (AUTHOR), Xu, Jun1,2 (AUTHOR)
Source: European Journal of Operational Research. Aug2023, Vol. 309 Issue 1, p53-64. 12p.
Subjects: Online algorithms, Batch processing, Machinery, Scheduling, Production scheduling
Abstract: • Propose an online batch scheduling problem with periodic pulse interruptions. • Analyze the lower bounds on competitive ratios for the online problem. • Design the best possible online algorithms using a waiting strategy. • Prove the competitive ratios of the online algorithms. We consider an online scheduling problem on identical batch machines to minimize the makespan with periodic pulse interruptions. Periodic pulse interruptions are machine unavailable intervals with negligible length and divide the scheduling horizon into available intervals. Jobs are released online over time and processed simultaneously as batches with the same processing times on identical batch machines. Every batch must be entirely processed in an available interval without any preemption. For unbounded machine capacity, we design best possible online algorithms with the competitive ratios of 1 + η and 2 m for a single machine (m = 1) and m identical parallel machines (m ≥ 2), respectively, where η ≈ 0.8019 is the positive root of η 3 + 2 η 2 − η = 1. For bounded machine capacity, we derive a best possible online algorithm with a competitive ratio of 1 + η. [ABSTRACT FROM AUTHOR]
Copyright of European Journal of Operational Research is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Description
Abstract:• Propose an online batch scheduling problem with periodic pulse interruptions. • Analyze the lower bounds on competitive ratios for the online problem. • Design the best possible online algorithms using a waiting strategy. • Prove the competitive ratios of the online algorithms. We consider an online scheduling problem on identical batch machines to minimize the makespan with periodic pulse interruptions. Periodic pulse interruptions are machine unavailable intervals with negligible length and divide the scheduling horizon into available intervals. Jobs are released online over time and processed simultaneously as batches with the same processing times on identical batch machines. Every batch must be entirely processed in an available interval without any preemption. For unbounded machine capacity, we design best possible online algorithms with the competitive ratios of 1 + η and 2 m for a single machine (m = 1) and m identical parallel machines (m ≥ 2), respectively, where η ≈ 0.8019 is the positive root of η 3 + 2 η 2 − η = 1. For bounded machine capacity, we derive a best possible online algorithm with a competitive ratio of 1 + η. [ABSTRACT FROM AUTHOR]
ISSN:03772217
DOI:10.1016/j.ejor.2023.01.027