Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/474
DC Field | Value | Language |
---|---|---|
dc.contributor | Department of Logistics and Maritime Studies | - |
dc.creator | Cheng, TCE | - |
dc.creator | Ng, CTD | - |
dc.creator | Kotov, V | - |
dc.date.accessioned | 2014-12-11T08:27:30Z | - |
dc.date.available | 2014-12-11T08:27:30Z | - |
dc.identifier.issn | 0020-0190 | - |
dc.identifier.uri | http://hdl.handle.net/10397/474 | - |
dc.language.iso | en | en_US |
dc.publisher | Elsevier | en_US |
dc.rights | Information Processing Letters © 2006 Elsevier. The journal web site is located at http://www.sciencedirect.com. | en_US |
dc.subject | Online algorithms | en_US |
dc.subject | Competitive ratio | en_US |
dc.subject | Multi-machine scheduling | en_US |
dc.subject | Uniform machines | en_US |
dc.title | A new algorithm for online uniform-machine scheduling to minimize the makespan | en_US |
dc.type | Journal/Magazine Article | en_US |
dc.description.otherinformation | Author name used in this publication: T.C.E. Cheng | en_US |
dc.description.otherinformation | Author name used in this publication: C. T. Ng | en_US |
dc.identifier.spage | 102 | - |
dc.identifier.epage | 105 | - |
dc.identifier.volume | 99 | - |
dc.identifier.issue | 3 | - |
dc.identifier.doi | 10.1016/j.ipl.2006.02.012 | - |
dcterms.abstract | We consider the online scheduling problem with m−1, m≥2, uniform machines each with a processing speed of 1, and one machine with a speed of s, 1≤s≤2, to minimize the makespan. The well-known list scheduling (LS) algorithm has a worst-case bound of (3m-1)/(m+1) [Y. Cho, S. Sahni, Bounds for list schedules on uniform processors, SIAM J. Comput. 9 (1980) 91-103]. An algorithm with a better competitive ratio was proposed in [R. Li, L. Shi, An on-line algorithm for some uniform processor scheduling, SIAM J. Comput. 27 (1998) 414-422]. It has a worst-case bound of 2.8795 for a big m and s=2. In this note we present a 2.45-competitive algorithm for m≥4 and any s, 1≤ s≤ 2. | - |
dcterms.accessRights | open access | en_US |
dcterms.bibliographicCitation | Information processing letters, Aug. 2006, v. 99, no. 3, p. 102-105 | - |
dcterms.isPartOf | Information processing letters | - |
dcterms.issued | 2006-08-16 | - |
dc.identifier.isi | WOS:000238478300005 | - |
dc.identifier.scopus | 2-s2.0-33646841815 | - |
dc.identifier.rosgroupid | r28615 | - |
dc.description.ros | 2005-2006 > Academic research: refereed > Publication in refereed journal | - |
dc.description.oa | Accepted Manuscript | en_US |
dc.identifier.FolderNumber | OA_IR/PIRA | en_US |
dc.description.pubStatus | Published | en_US |
Appears in Collections: | Journal/Magazine Article |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
on-line_uniform9.pdf | Pre-published version | 157.55 kB | Adobe PDF | View/Open |
Page views
98
Last Week
2
2
Last month
Citations as of Apr 14, 2024
Downloads
205
Citations as of Apr 14, 2024
SCOPUSTM
Citations
11
Last Week
0
0
Last month
0
0
Citations as of Apr 19, 2024
WEB OF SCIENCETM
Citations
13
Last Week
0
0
Last month
0
0
Citations as of Apr 18, 2024
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.