DC Field | Value | Language |
---|---|---|
dc.contributor.author | Lee, K | - |
dc.contributor.author | Leung, JYT | - |
dc.contributor.author | Pinedoa, ML | - |
dc.date.accessioned | 2017-07-19T12:45:23Z | - |
dc.date.available | 2017-07-19T12:45:23Z | - |
dc.date.created | 2016-07-12 | - |
dc.date.issued | 2009-09-06 | - |
dc.identifier.issn | 0304-3975 | - |
dc.identifier.uri | https://oasis.postech.ac.kr/handle/2014.oak/36387 | - |
dc.description.abstract | We consider the online scheduling of a set of jobs on two uniform machines with the makespan as objective. The jobs are presented in a list. We consider two different eligibility constraint set assumptions, namely (i) arbitrary eligibility constraints and (ii) Grade of Service (GoS) eligibility constraints. In the first case, we prove that the High Speed Machine First (HSF) algorithm, which assigns jobs to the eligible machine that has the highest speed, is optimal. With regard to the second case, we point out an error in [M. Liu et al., Online scheduling on two uniform machines to minimize the makespan, Theoretical Computer Science 410 (21-23)(2009) 2099-2109]; we then provide tighter lower bounds and present algorithms with worst-case analysis for various ranges of machine speeds. (C) 2009 Elsevier B.V. All rights reserved. | - |
dc.language | English | - |
dc.publisher | ELSEVIER SCIENCE BV | - |
dc.relation.isPartOf | THEORETICAL COMPUTER SCIENCE | - |
dc.title | Online Scheduling on Two Uniform Machines subject to Eligibility Constraints | - |
dc.type | Article | - |
dc.identifier.doi | 10.1016/J.TCS.2009.06.032 | - |
dc.type.rims | ART | - |
dc.identifier.bibliographicCitation | THEORETICAL COMPUTER SCIENCE, v.410, no.38-40, pp.3975 - 3981 | - |
dc.identifier.wosid | 000269683400035 | - |
dc.date.tcdate | 2019-02-01 | - |
dc.citation.endPage | 3981 | - |
dc.citation.number | 38-40 | - |
dc.citation.startPage | 3975 | - |
dc.citation.title | THEORETICAL COMPUTER SCIENCE | - |
dc.citation.volume | 410 | - |
dc.contributor.affiliatedAuthor | Lee, K | - |
dc.identifier.scopusid | 2-s2.0-68249084307 | - |
dc.description.journalClass | 1 | - |
dc.description.journalClass | 1 | - |
dc.description.wostc | 7 | - |
dc.description.scptc | 8 | * |
dc.date.scptcdate | 2018-05-121 | * |
dc.type.docType | Article | - |
dc.subject.keywordAuthor | Online scheduling | - |
dc.subject.keywordAuthor | Uniform machines | - |
dc.subject.keywordAuthor | Eligibility constraints | - |
dc.subject.keywordAuthor | Grade of service eligibility | - |
dc.subject.keywordAuthor | Competitive ratio | - |
dc.relation.journalWebOfScienceCategory | Computer Science, Theory & Methods | - |
dc.description.journalRegisteredClass | scie | - |
dc.description.journalRegisteredClass | scopus | - |
dc.relation.journalResearchArea | Computer Science | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
library@postech.ac.kr Tel: 054-279-2548
Copyrights © by 2017 Pohang University of Science ad Technology All right reserved.