Semi-Online Scheduling on Two Identical Parallel Machines with Initial-Lookahead Information
Feifeng Zheng (),
Yuhong Chen (),
Ming Liu and
Yinfeng Xu ()
Additional contact information
Feifeng Zheng: Glorious Sun School of Business and Management, Donghua University, Shanghai 200051, P. R. China
Yuhong Chen: Glorious Sun School of Business and Management, Donghua University, Shanghai 200051, P. R. China
Ming Liu: School of Economics and Management, Tongji University, Shanghai 200092, P. R. China
Yinfeng Xu: School of Management, Xi’an Jiaotong University, Xi’an, Shaanxi 710049, P. R. China
Asia-Pacific Journal of Operational Research (APJOR), 2024, vol. 41, issue 01, 1-20
Abstract:
This work investigates a new semi-online scheduling problem with lookahead. We focus on job scheduling on two identical parallel machines, where deterministic online algorithms only know the information of k initial jobs (i.e., the initial-lookahead information), while the following jobs still arrive one-by-one in an over-list fashion. We consider makespan minimization as the objective. The study aims at revealing the value of knowing k initial jobs, which are used to improve the competitive performance of those online algorithms without such initial-lookahead information. We provide the following findings: (1) For the scenario where the k initial jobs are all the largest jobs with length Δ, we prove that the classical LIST algorithm is optimal with competitive ratio (k + 3)/(k + 2); (2) For the scenario where the total length of these k (> 1) jobs is at least Δ, we show that any online algorithm has a competitive ratio at least 3/2, implying that the initial-lookahead knowledge is powerless since there exists a 3/2-competitive online algorithm without such information; (3) For the scenario where the total length of these k (> α) jobs is at least αΔ (α ≥ 2), we propose an online algorithm, named as LPT-LIST, with competitive ratio of (α + 2)/(α + 1), implying that the initial-lookahead information indeed helps to improve the competitiveness of those online algorithms lacking such information.
Keywords: Parallel machine scheduling; semi-online algorithm; initial lookahead; competitive ratio; value of information (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:
Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595923500033
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:41:y:2024:i:01:n:s0217595923500033
Ordering information: This journal article can be ordered from
DOI: 10.1142/S0217595923500033
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 ().