Online Scheduling on a Bounded Batch Machine with Same-Length-Job Families

Libo Wang (), Wenhua Li, Xing Chai (), Yanhong Gao () and Dan Yu ()
Additional contact information
Libo Wang: School of Mathematics and Statistics, Zhengzhou University, Zhengzhou, Henan 450001, P. R. China
Wenhua Li: School of Mathematics and Statistics, Zhengzhou University, Zhengzhou, Henan 450001, P. R. China
Xing Chai: School of Mathematics and Statistics, Henan University of Technology, Zhengzhou, Henan 450001, P. R. China
Yanhong Gao: School of Mathematics and Statistics, Zhengzhou University, Zhengzhou, Henan 450001, P. R. China
Dan Yu: School of Mathematics and Statistics, Zhengzhou University, Zhengzhou, Henan 450001, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2025, vol. 42, issue 05, 1-19

Abstract: We investigate an online scheduling problem on a bounded batch machine with f incompatible job families, in which the jobs are released over time and the jobs belonging to the same family have the same processing times. The goal is to minimize the maximum completion time. A machine can process at most b jobs simultaneously as a batch, where b is finite. A batch only contains the jobs from the same family. KRT setting means that no job is released when the machine is busy. In this paper, we consider the above model under two environments: (1) KRT setting and (2) general setting. In the KRT setting, we provide the lower bounds 1 + f2 −f+1−1 f for b ≥ f and min 2f+1 f+2 , 2b b+1 for 2 ≤ b < f. In the general setting, we provide the lower bounds 1 + 4f2 +1−1 2f for b ≥ f + 1 and 2b b+1 for 2 ≤ b < f + 1. We further present an online algorithm, which is the best possible when b ≥ f for the KRT setting and when b ≥ f + 1 for the general setting.

Keywords: Online algorithm; bounded batch; incompatible job families; KRT setting; competitive ratio (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595925500046
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:42:y:2025:i:05:n:s0217595925500046

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595925500046

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().