Online Algorithms for Scheduling Unit Length Jobs on Unbounded Parallel-Batch Machines with Linearly Lookahead

Chengwen Jiao, Jinjiang Yuan () and Qi Feng ()
Additional contact information
Chengwen Jiao: College of Science, Zhongyuan University of Technology, Zhengzhou, Henan 450007, P. R. China
Jinjiang Yuan: School of Mathematics and Statistics, Zhengzhou University, Zhengzhou, Henan 450001, P. R. China
Qi Feng: College of Science, Zhongyuan University of Technology, Zhengzhou, Henan 450007, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2019, vol. 36, issue 05, 1-8

Abstract: In this paper, we propose a new online scheduling model with linear lookahead intervals, which has the character that at any time t, one can foresee the jobs that will coming in the time interval (t,λt + β] in which λ > 1,β > 0. In this new lookahead model, the length of the lookahead intervals are variable as the time going on and the number of jobs increasing, and has the tend of steady growth. In this paper, we consider online scheduling of unit length jobs on m identical parallel-batch machines under this new lookahead model to minimize makespan. The batch capacity is unbounded, that is b = ∞. We present an optimal online algorithm for λ > 1,β ≥ λ−1 λm−1, and provide a best possible online algorithm of competitive ratio 1 + αm for λ > 1, 0 < β < λ−1 λm−1, where αm is the positive root of (1 + αm)m+1λm + (1 + β − λ)∑ i=1m(1 + α m)iλi−1 = 2 + α m.

Keywords: Online scheduling; parallel batch; linearly lookahead; competitive ratio (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595919500246
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:36:y:2019:i:05:n:s0217595919500246

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595919500246

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