File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: On-line scheduling of parallel jobs on two machines

TitleOn-line scheduling of parallel jobs on two machines
Authors
KeywordsCompetitive Analysis
Jobs scheduling
Online algorithms
Issue Date2008
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/jda
Citation
Journal Of Discrete Algorithms, 2008, v. 6 n. 1, p. 3-10 How to Cite?
AbstractWe study the problem of on-line scheduling of parallel jobs on two machines. The jobs are parallel in the sense that each of them specifies the number of processors, in this case 1 or 2, required for simultaneous processing. The jobs are presented one by one. Upon receiving a job, we must assign the job to a time slot in the schedule before the next job is presented. No re-assignment is allowed. The goal is to minimize the makespan of the final schedule. There is a straightforward algorithm which achieves a competitive ratio of 2. In this paper we show that no on-line algorithm can have a competitive ratio less than 1 + sqrt(2 / 3)(≈ 1.816) . We also study two special cases of the problem: (i) Jobs arrive in a non-decreasing order of processing times where we give an optimal algorithm with competitive ratio 3/2; (ii) Jobs arrive in a non-increasing order of processing times where we show that no on-line algorithm has a competitive ratio less than 9/7 and give a greedy algorithm with a competitive ratio 4/3. © 2006 Elsevier B.V. All rights reserved.
Persistent Identifierhttp://hdl.handle.net/10722/89023
ISSN
2015 SCImago Journal Rankings: 0.764
References

 

DC FieldValueLanguage
dc.contributor.authorChan, WTen_HK
dc.contributor.authorChin, FYLen_HK
dc.contributor.authorYe, Den_HK
dc.contributor.authorZhang, Gen_HK
dc.contributor.authorZhang, Yen_HK
dc.date.accessioned2010-09-06T09:51:25Z-
dc.date.available2010-09-06T09:51:25Z-
dc.date.issued2008en_HK
dc.identifier.citationJournal Of Discrete Algorithms, 2008, v. 6 n. 1, p. 3-10en_HK
dc.identifier.issn1570-8667en_HK
dc.identifier.urihttp://hdl.handle.net/10722/89023-
dc.description.abstractWe study the problem of on-line scheduling of parallel jobs on two machines. The jobs are parallel in the sense that each of them specifies the number of processors, in this case 1 or 2, required for simultaneous processing. The jobs are presented one by one. Upon receiving a job, we must assign the job to a time slot in the schedule before the next job is presented. No re-assignment is allowed. The goal is to minimize the makespan of the final schedule. There is a straightforward algorithm which achieves a competitive ratio of 2. In this paper we show that no on-line algorithm can have a competitive ratio less than 1 + sqrt(2 / 3)(≈ 1.816) . We also study two special cases of the problem: (i) Jobs arrive in a non-decreasing order of processing times where we give an optimal algorithm with competitive ratio 3/2; (ii) Jobs arrive in a non-increasing order of processing times where we show that no on-line algorithm has a competitive ratio less than 9/7 and give a greedy algorithm with a competitive ratio 4/3. © 2006 Elsevier B.V. All rights reserved.en_HK
dc.languageengen_HK
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/jdaen_HK
dc.relation.ispartofJournal of Discrete Algorithmsen_HK
dc.rightsJournal of Discrete Algorithms . Copyright © Elsevier BV.en_HK
dc.subjectCompetitive Analysisen_HK
dc.subjectJobs schedulingen_HK
dc.subjectOnline algorithmsen_HK
dc.titleOn-line scheduling of parallel jobs on two machinesen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1570-8667&volume=6&issue=1&spage=3&epage=10&date=2008&atitle=On-line+scheduling+of+parallel+jobs+on+two+machinesen_HK
dc.identifier.emailChin, FYL:chin@cs.hku.hken_HK
dc.identifier.authorityChin, FYL=rp00105en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1016/j.jda.2006.07.005en_HK
dc.identifier.scopuseid_2-s2.0-39149105634en_HK
dc.identifier.hkuros140903en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-39149105634&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume6en_HK
dc.identifier.issue1en_HK
dc.identifier.spage3en_HK
dc.identifier.epage10en_HK
dc.publisher.placeNetherlandsen_HK
dc.identifier.scopusauthoridChan, WT=7403918060en_HK
dc.identifier.scopusauthoridChin, FYL=7005101915en_HK
dc.identifier.scopusauthoridYe, D=16023572800en_HK
dc.identifier.scopusauthoridZhang, G=7405271610en_HK
dc.identifier.scopusauthoridZhang, Y=7601329213en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats