File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1016/j.jda.2006.07.005
- Scopus: eid_2-s2.0-39149105634
- WOS: WOS:000213937500002
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: On-line scheduling of parallel jobs on two machines
Title | On-line scheduling of parallel jobs on two machines |
---|---|
Authors | |
Keywords | Competitive Analysis Jobs scheduling Online algorithms |
Issue Date | 2008 |
Publisher | Elsevier 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? |
Abstract | We 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 Identifier | http://hdl.handle.net/10722/89023 |
ISSN | 2020 SCImago Journal Rankings: 0.387 |
ISI Accession Number ID | |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chan, WT | en_HK |
dc.contributor.author | Chin, FYL | en_HK |
dc.contributor.author | Ye, D | en_HK |
dc.contributor.author | Zhang, G | en_HK |
dc.contributor.author | Zhang, Y | en_HK |
dc.date.accessioned | 2010-09-06T09:51:25Z | - |
dc.date.available | 2010-09-06T09:51:25Z | - |
dc.date.issued | 2008 | en_HK |
dc.identifier.citation | Journal Of Discrete Algorithms, 2008, v. 6 n. 1, p. 3-10 | en_HK |
dc.identifier.issn | 1570-8667 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/89023 | - |
dc.description.abstract | We 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.language | eng | en_HK |
dc.publisher | Elsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/jda | en_HK |
dc.relation.ispartof | Journal of Discrete Algorithms | en_HK |
dc.rights | Journal of Discrete Algorithms . Copyright © Elsevier BV. | en_HK |
dc.subject | Competitive Analysis | en_HK |
dc.subject | Jobs scheduling | en_HK |
dc.subject | Online algorithms | en_HK |
dc.title | On-line scheduling of parallel jobs on two machines | en_HK |
dc.type | Article | en_HK |
dc.identifier.openurl | http://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+machines | en_HK |
dc.identifier.email | Chin, FYL:chin@cs.hku.hk | en_HK |
dc.identifier.authority | Chin, FYL=rp00105 | en_HK |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1016/j.jda.2006.07.005 | en_HK |
dc.identifier.scopus | eid_2-s2.0-39149105634 | en_HK |
dc.identifier.hkuros | 140903 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-39149105634&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 6 | en_HK |
dc.identifier.issue | 1 | en_HK |
dc.identifier.spage | 3 | en_HK |
dc.identifier.epage | 10 | en_HK |
dc.identifier.isi | WOS:000213937500002 | - |
dc.publisher.place | Netherlands | en_HK |
dc.identifier.scopusauthorid | Chan, WT=7403918060 | en_HK |
dc.identifier.scopusauthorid | Chin, FYL=7005101915 | en_HK |
dc.identifier.scopusauthorid | Ye, D=16023572800 | en_HK |
dc.identifier.scopusauthorid | Zhang, G=7405271610 | en_HK |
dc.identifier.scopusauthorid | Zhang, Y=7601329213 | en_HK |
dc.identifier.issnl | 1570-8667 | - |