Online scheduling of malleable parallel jobs with setup times on two identical machines

Shouwei Guo and Liying Kang

European Journal of Operational Research, 2010, vol. 206, issue 3, 555-561

Abstract: In this paper we consider online scheduling of malleable parallel jobs on two identical machines, where jobs arrive over time. Each job Jj has an execution time tj=pj/kj+(kj-1)cj when it is processed on kj machines, where pj>0 and cj>0 are the length and setup time of job Jj. The objective is to minimize the makespan. For the problem with two machines, we present an online algorithm with competitive ratio of 1+[alpha], where . We show that 1+[alpha] is a lower bound on the competitive ratio of any online algorithm for the problem with machines. So our algorithm is optimal for the case of two machines.

Keywords: Scheduling; Parallel; jobs; Setup; times; Online; algorithm; Competitive; analysis (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377-2217(10)00175-X
Full text for ScienceDirect subscribers only

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:eee:ejores:v:206:y:2010:i:3:p:555-561

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().