Online Parallel-Machine Scheduling in KRT Environment to Minimize Total Weighted Completion Time

Wenjie Li, Hailing Liu () and Shisheng Li ()
Additional contact information
Wenjie Li: School of Mathematical Sciences, Luoyang Normal University, Luoyang 471934, Henan, P. R. China
Hailing Liu: College of Science, Henan Institute of Engineering, Zhengzhou 451191, Henan, P. R. China
Shisheng Li: Department of Information and Computation Science, Zhongyuan University of Technology, Zhengzhou, Henan 450007, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2018, vol. 35, issue 04, 1-12

Abstract: This paper studies online scheduling on m identical parallel machines under the KRT environment, where jobs arrive over time and “KRT” means that in the online setting no jobs can be released when all of the machines are busy. The goal is to determine a feasible schedule to minimize the total of weighted completion times. When m = 1, we prove that WSPT is an optimal online algorithm. When m ≥ 2, we first present a lower bound m2−2+m4 −4m+4 2m(m−1), and then show that WSPT is a 2-competitive online algorithm for the case m = 2. For the case in which m = 2 and all jobs have equal processing times, we provide a best possible online algorithm with a competitive ratio of 1+3 2.

Keywords: Scheduling; online algorithm; kind release time; total weighted completion time (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595918500240
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:35:y:2018:i:04:n:s0217595918500240

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595918500240

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