Conference
Scheduling with explorable uncertainty
| العنوان: | Scheduling with explorable uncertainty |
|---|---|
| المؤلفون: | Dürr, Christoph, Erlebach, Thomas, Megow, Nicole, Meißner, Julie |
| بيانات النشر: | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
| سنة النشر: | 2018 |
| المجموعة: | University of Leicester: Leicester Research Archive (LRA) |
| مصطلحات موضوعية: | online scheduling, explorable uncertainty, competitive ratio, makespan, sum of completion times |
| الوصف: | We introduce a novel model for scheduling with explorable uncertainty. In this model, the processing time of a job can potentially be reduced (by an a priori unknown amount) by testing the job. Testing a job j takes one unit of time and may reduce its processing time from the given upper limit p j (which is the time taken to execute the job if it is not tested) to any value between 0 and pj. This setting is motivated e.g. by applications where a code optimizer can be run on a job before executing it. We consider the objective of minimizing the sum of completion times on a single machine. All jobs are available from the start, but the reduction in their processing times as a result of testing is unknown, making this an online problem that is amenable to competitive analysis. The need to balance the time spent on tests and the time spent on job executions adds a novel flavor to the problem. We give the first and nearly tight lower and upper bounds on the competitive ratio for deterministic and randomized algorithms. We also show that minimizing the makespan is a considerably easier problem for which we give optimal deterministic and randomized online algorithms. ; This research was carried out in the framework of Matheon supported by Einstein Foundation Berlin, the German Science Foundation (DFG) under contract ME 3825/1 and the Bayerisch-Französisches Hochschulzentrum (BFHZ). The second author was supported by a study leave granted by University of Leicester. ; Peer-reviewed ; Publisher Version ; 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), MIT, Cambridge, Massachusetts, USA |
| نوع الوثيقة: | conference object |
| اللغة: | English |
| ردمك: | 978-3-95977-060-6 3-95977-060-X |
| تدمد: | 1868-8969 |
| Relation: | Leibniz International Proceedings in Informatics, LIPIcs, 2018, 94; http://drops.dagstuhl.de/opus/volltexte/2018/8336/; http://hdl.handle.net/2381/42259 |
| DOI: | 10.4230/LIPIcs.ITCS.2018.30 |
| الاتاحة: | http://drops.dagstuhl.de/opus/volltexte/2018/8336/ http://hdl.handle.net/2381/42259 https://doi.org/10.4230/LIPIcs.ITCS.2018.30 |
| Rights: | Copyright © the authors, 2018. This is an open-access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited. |
| رقم الانضمام: | edsbas.BE9DF368 |
| قاعدة البيانات: | BASE |
| ResultId |
1 |
|---|---|
| Header |
edsbas BASE edsbas.BE9DF368 897 3 Conference conference 896.885437011719 |
| PLink |
https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&scope=site&db=edsbas&AN=edsbas.BE9DF368&custid=s6537998&authtype=sso |
| FullText |
Array
(
[Availability] => 0
)
Array ( [0] => Array ( [Url] => http://drops.dagstuhl.de/opus/volltexte/2018/8336/# [Name] => EDS - BASE [Category] => fullText [Text] => View record in BASE [MouseOverText] => View record in BASE ) ) |
| Items |
Array
(
[Name] => Title
[Label] => Title
[Group] => Ti
[Data] => Scheduling with explorable uncertainty
)
Array ( [Name] => Author [Label] => Authors [Group] => Au [Data] => <searchLink fieldCode="AR" term="%22Dürr%2C+Christoph%22">Dürr, Christoph</searchLink><br /><searchLink fieldCode="AR" term="%22Erlebach%2C+Thomas%22">Erlebach, Thomas</searchLink><br /><searchLink fieldCode="AR" term="%22Megow%2C+Nicole%22">Megow, Nicole</searchLink><br /><searchLink fieldCode="AR" term="%22Meißner%2C+Julie%22">Meißner, Julie</searchLink> ) Array ( [Name] => Publisher [Label] => Publisher Information [Group] => PubInfo [Data] => Schloss Dagstuhl - Leibniz-Zentrum für Informatik ) Array ( [Name] => DatePubCY [Label] => Publication Year [Group] => Date [Data] => 2018 ) Array ( [Name] => Subset [Label] => Collection [Group] => HoldingsInfo [Data] => University of Leicester: Leicester Research Archive (LRA) ) Array ( [Name] => Subject [Label] => Subject Terms [Group] => Su [Data] => <searchLink fieldCode="DE" term="%22online+scheduling%22">online scheduling</searchLink><br /><searchLink fieldCode="DE" term="%22explorable+uncertainty%22">explorable uncertainty</searchLink><br /><searchLink fieldCode="DE" term="%22competitive+ratio%22">competitive ratio</searchLink><br /><searchLink fieldCode="DE" term="%22makespan%22">makespan</searchLink><br /><searchLink fieldCode="DE" term="%22sum+of+completion+times%22">sum of completion times</searchLink> ) Array ( [Name] => Abstract [Label] => Description [Group] => Ab [Data] => We introduce a novel model for scheduling with explorable uncertainty. In this model, the processing time of a job can potentially be reduced (by an a priori unknown amount) by testing the job. Testing a job j takes one unit of time and may reduce its processing time from the given upper limit p j (which is the time taken to execute the job if it is not tested) to any value between 0 and pj. This setting is motivated e.g. by applications where a code optimizer can be run on a job before executing it. We consider the objective of minimizing the sum of completion times on a single machine. All jobs are available from the start, but the reduction in their processing times as a result of testing is unknown, making this an online problem that is amenable to competitive analysis. The need to balance the time spent on tests and the time spent on job executions adds a novel flavor to the problem. We give the first and nearly tight lower and upper bounds on the competitive ratio for deterministic and randomized algorithms. We also show that minimizing the makespan is a considerably easier problem for which we give optimal deterministic and randomized online algorithms. ; This research was carried out in the framework of Matheon supported by Einstein Foundation Berlin, the German Science Foundation (DFG) under contract ME 3825/1 and the Bayerisch-Französisches Hochschulzentrum (BFHZ). The second author was supported by a study leave granted by University of Leicester. ; Peer-reviewed ; Publisher Version ; 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), MIT, Cambridge, Massachusetts, USA ) Array ( [Name] => TypeDocument [Label] => Document Type [Group] => TypDoc [Data] => conference object ) Array ( [Name] => Language [Label] => Language [Group] => Lang [Data] => English ) Array ( [Name] => ISBN [Label] => ISBN [Group] => ISBN [Data] => 978-3-95977-060-6<br />3-95977-060-X ) Array ( [Name] => ISSN [Label] => ISSN [Group] => ISSN [Data] => 1868-8969 ) Array ( [Name] => NoteTitleSource [Label] => Relation [Group] => SrcInfo [Data] => Leibniz International Proceedings in Informatics, LIPIcs, 2018, 94; http://drops.dagstuhl.de/opus/volltexte/2018/8336/; http://hdl.handle.net/2381/42259 ) Array ( [Name] => DOI [Label] => DOI [Group] => ID [Data] => 10.4230/LIPIcs.ITCS.2018.30 ) Array ( [Name] => URL [Label] => Availability [Group] => URL [Data] => http://drops.dagstuhl.de/opus/volltexte/2018/8336/<br />http://hdl.handle.net/2381/42259<br />https://doi.org/10.4230/LIPIcs.ITCS.2018.30 ) Array ( [Name] => Copyright [Label] => Rights [Group] => Cpyrght [Data] => Copyright © the authors, 2018. This is an open-access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited. ) Array ( [Name] => AN [Label] => Accession Number [Group] => ID [Data] => edsbas.BE9DF368 ) |
| RecordInfo |
Array
(
[BibEntity] => Array
(
[Identifiers] => Array
(
[0] => Array
(
[Type] => doi
[Value] => 10.4230/LIPIcs.ITCS.2018.30
)
)
[Languages] => Array
(
[0] => Array
(
[Text] => English
)
)
[Subjects] => Array
(
[0] => Array
(
[SubjectFull] => online scheduling
[Type] => general
)
[1] => Array
(
[SubjectFull] => explorable uncertainty
[Type] => general
)
[2] => Array
(
[SubjectFull] => competitive ratio
[Type] => general
)
[3] => Array
(
[SubjectFull] => makespan
[Type] => general
)
[4] => Array
(
[SubjectFull] => sum of completion times
[Type] => general
)
)
[Titles] => Array
(
[0] => Array
(
[TitleFull] => Scheduling with explorable uncertainty
[Type] => main
)
)
)
[BibRelationships] => Array
(
[HasContributorRelationships] => Array
(
[0] => Array
(
[PersonEntity] => Array
(
[Name] => Array
(
[NameFull] => Dürr, Christoph
)
)
)
[1] => Array
(
[PersonEntity] => Array
(
[Name] => Array
(
[NameFull] => Erlebach, Thomas
)
)
)
[2] => Array
(
[PersonEntity] => Array
(
[Name] => Array
(
[NameFull] => Megow, Nicole
)
)
)
[3] => Array
(
[PersonEntity] => Array
(
[Name] => Array
(
[NameFull] => Meißner, Julie
)
)
)
)
[IsPartOfRelationships] => Array
(
[0] => Array
(
[BibEntity] => Array
(
[Dates] => Array
(
[0] => Array
(
[D] => 01
[M] => 01
[Type] => published
[Y] => 2018
)
)
[Identifiers] => Array
(
[0] => Array
(
[Type] => isbn-print
[Value] => 9783959770606
)
[1] => Array
(
[Type] => isbn-print
[Value] => 395977060X
)
[2] => Array
(
[Type] => issn-print
[Value] => 18688969
)
[3] => Array
(
[Type] => issn-locals
[Value] => edsbas
)
[4] => Array
(
[Type] => issn-locals
[Value] => edsbas.oa
)
)
)
)
)
)
)
|
| IllustrationInfo |