A Best Possible Online Algorithm for the Parallel-Machine Scheduling to Minimize the Maximum Weighted Completion Time

Wenjie Li ()
Additional contact information
Wenjie Li: School of Mathematical Sciences, Luoyang Normal University, Luoyang, Henan 471022, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2015, vol. 32, issue 04, 1-10

Abstract: In this paper, we consider the online scheduling on m identical machines in which jobs arrive over time. The goal is to determine a nonpreemptive schedule that minimizes the weighted makespan, i.e., the maximum weighted completion time of jobs. When m = 1, we first present a lower bound 2, and then provide an online algorithm with a competitive ratio of 3. For the case in which m ≥ 1, and all jobs have a common processing time p > 0, we obtain a best possible online algorithm with a competitive ratio of $(1+\sqrt{5})/2$.

Keywords: Scheduling; online algorithms; weighted makespan; competitive ratio (search for similar items in EconPapers)
Date: 2015
References: View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S021759591550030X
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:32:y:2015:i:04:n:s021759591550030x

Ordering information: This journal article can be ordered from

DOI: 10.1142/S021759591550030X

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