View in EDS

Optimal algorithms for online batch scheduling with all possible equal-processing times under periodic pulse interruptions.

Saved in:
Bibliographic Details
Title: Optimal algorithms for online batch scheduling with all possible equal-processing times under periodic pulse interruptions.
Authors: Lin, Ran1 (AUTHOR), Feng, Huiyan1 (AUTHOR), Li, Wenhua1 (AUTHOR) liwenhua@zzu.edu.cn
Source: Discrete Applied Mathematics. Jul2025, Vol. 370, p71-83. 13p.
Subjects: Production scheduling, Online algorithms, Scheduling, Machinery, Time
Abstract: We address an online scheduling problem on a batch machine to minimize the makespan. Jobs are released online over time and can be grouped into batches simultaneously with equal-processing times. This batch machine has periodic pulse interruptions, which are machine unavailable periods with negligible length. The pulse interruptions divide the scheduling horizon into periodic available intervals. A batch can be processed only within an available interval without any preemption. For all possible equal-processing times, we develop the lower bounds on competitive ratios and provide optimal online algorithms when the batch capacity is unbounded and bounded, respectively. • We study an online batch scheduling problem with periodic pulse interruptions. • We give the lower bounds for all possible equal-processing times. • We develop the optimal online algorithms for unbounded and bounded capacity. • We show the competitive ratios of the optimal online algorithms. [ABSTRACT FROM AUTHOR]
Copyright of Discrete Applied Mathematics 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:We address an online scheduling problem on a batch machine to minimize the makespan. Jobs are released online over time and can be grouped into batches simultaneously with equal-processing times. This batch machine has periodic pulse interruptions, which are machine unavailable periods with negligible length. The pulse interruptions divide the scheduling horizon into periodic available intervals. A batch can be processed only within an available interval without any preemption. For all possible equal-processing times, we develop the lower bounds on competitive ratios and provide optimal online algorithms when the batch capacity is unbounded and bounded, respectively. • We study an online batch scheduling problem with periodic pulse interruptions. • We give the lower bounds for all possible equal-processing times. • We develop the optimal online algorithms for unbounded and bounded capacity. • We show the competitive ratios of the optimal online algorithms. [ABSTRACT FROM AUTHOR]
ISSN:0166218X
DOI:10.1016/j.dam.2025.03.008