Online Batch Scheduling of Incompatible Job Families with Variable Lookahead Interval

Wenhua Li, Libo Wang () and Hang Yuan ()
Additional contact information
Wenhua Li: School of Mathematics and Statistics, Zhengzhou University, Zhengzhou, 450001, P. R. China
Libo Wang: School of Mathematics and Statistics, Zhengzhou University, Zhengzhou, 450001, P. R. China
Hang Yuan: Department of Economics, State University of New York at Binghamton, Binghamton, NY 13902, USA

Asia-Pacific Journal of Operational Research (APJOR), 2023, vol. 40, issue 01, 1-15

Abstract: We consider online parallel-batch scheduling of f incompatible unit-length job families with variable lookahead interval to minimize the maximum completion time, where f is the number of job families which is known in advance. Incompatible job family means that a batch only contains the jobs from the same job family. At any time t, an online algorithm can foresee the information of the jobs arriving in the time interval (t,t + Δ(t)], where Δ(t) = (λ − 1)t + β is variable. When the batch capacity b = ∞ and f ≥ 1, we provide a best possible online algorithm with competitive ratio 1 + αf for 0 ≤ β < 1 and 1 ≤ λ ≤ 1 + β, where αf is a positive root of λfαf2 + (λf + β + 1 − f)α f + β − f = 0. When the batch capacity (f <) b < ∞ and f ≥ 2, we give an online algorithm with competitive ratio 1 +max{ f fαf+f, f λfαf+β+1} for 0 ≤ β < 1 and λ ≥ 1, and prove that it is the best possible for λ = 1 and 0 ≤ β ≤ f+1−f2 +1 2.

Keywords: Batch scheduling; online algorithm; variable lookahead interval; incompatible job families; competitive ratio (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595922400127
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:40:y:2023:i:01:n:s0217595922400127

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595922400127

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 ().