Improved Algorithms for Online Scheduling of Malleable Parallel Jobs on Two Identical Machines

Hao Zhou (), Ping Zhou () and Yiwei Jiang ()
Additional contact information
Hao Zhou: Department of Basic Science, Zhejiang Shuren University, Hangzhou 310015, P. R. China
Ping Zhou: School of Humanities, Zhejiang Business College, Hangzhou 310053, P. R. China
Yiwei Jiang: Department of Mathematics, Zhejiang Sci-Tech University, Hangzhou 310018, P. R. China

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

Abstract: This paper addresses online scheduling of malleable parallel jobs to minimize the maximum completion time, i.e., makespan. It is assumed that the execution time of a job Jj with processing time pj is pj/k + (k-1)c if the job is assigned to k machines, where c > 0 is a constant setup time. We consider online algorithms for the scheduling problem on two identical machines. Namely, the job Jj can be processed on one machine with execution time pj or alternatively two machines in parallel with execution time pj/2+c. For the asymptotical competitive ratio, we provide an improved online algorithm with makespan no more than (3/2)C* +c/2, where C* is the optimal makespan. For the strict competitive ratio, we propose an online algorithm with competitive ratio of 1.54, which is close to the lower bound of 1.5.

Keywords: Online algorithm; malleable parallel job; makespan; competitive ratio (search for similar items in EconPapers)
Date: 2015
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595915500347
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:05:n:s0217595915500347

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595915500347

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