List Scheduling in Order of α-Points on a Single Machine. Skutella, M. In Bampis, E., Jansen, K., & Kenyon, C., editors, Efficient Approximation and Online Algorithms, of Lecture Notes in Computer Science, pages 250--291. Springer Berlin Heidelberg, 2006. ![List Scheduling in Order of α-Points on a Single Machine [link]](https://bibbase.org/img/filetypes/link.svg "link")
Paper abstract bibtex Many approximation results for single machine scheduling problems rely on the conversion of preemptive schedules into (preemptive or non-preemptive) solutions. The initial preemptive schedule is usually an optimal solution to a combinatorial relaxation or a linear programming relaxation of the scheduling problem under consideration. It therefore provides a lower bound on the optimal objective function value. However, it also contains structural information which is useful for the construction of provably good feasible schedules. In this context, list scheduling in order of so-called α-points has evolved as an important and successful tool. We give a survey and a uniform presentation of several approximation results for single machine scheduling with total weighted completion time objective from the last years which rely on the concept of α-points.
@incollection{skutella_list_2006,
series = {Lecture {Notes} in {Computer} {Science}},
title = {List {Scheduling} in {Order} of α-{Points} on a {Single} {Machine}},
copyright = {©2006 Springer-Verlag Berlin Heidelberg},
isbn = {978-3-540-32212-2, 978-3-540-32213-9},
url = {http://link.springer.com/chapter/10.1007/11671541_9},
abstract = {Many approximation results for single machine scheduling problems rely on the conversion of preemptive schedules into (preemptive or non-preemptive) solutions. The initial preemptive schedule is usually an optimal solution to a combinatorial relaxation or a linear programming relaxation of the scheduling problem under consideration. It therefore provides a lower bound on the optimal objective function value. However, it also contains structural information which is useful for the construction of provably good feasible schedules. In this context, list scheduling in order of so-called α-points has evolved as an important and successful tool. We give a survey and a uniform presentation of several approximation results for single machine scheduling with total weighted completion time objective from the last years which rely on the concept of α-points.},
language = {en},
number = {3484},
urldate = {2015-04-30TZ},
booktitle = {Efficient {Approximation} and {Online} {Algorithms}},
publisher = {Springer Berlin Heidelberg},
author = {Skutella, Martin},
editor = {Bampis, Evripidis and Jansen, Klaus and Kenyon, Claire},
year = {2006},
keywords = {Algorithm Analysis and Problem Complexity, Computer Communication Networks, Computer Graphics, Discrete Mathematics in Computer Science, Numeric Computing, algorithms},
pages = {250--291}
}
Downloads: 0
{"_id":"wwq3J5st9A9mY99yt","bibbaseid":"skutella-listschedulinginorderofpointsonasinglemachine-2006","downloads":0,"creationDate":"2016-12-19T20:50:58.214Z","title":"List Scheduling in Order of α-Points on a Single Machine","author_short":["Skutella, M."],"year":2006,"bibtype":"incollection","biburl":"http://bibbase.org/zotero/verschae","bibdata":{"bibtype":"incollection","type":"incollection","series":"Lecture Notes in Computer Science","title":"List Scheduling in Order of α-Points on a Single Machine","copyright":"©2006 Springer-Verlag Berlin Heidelberg","isbn":"978-3-540-32212-2, 978-3-540-32213-9","url":"http://link.springer.com/chapter/10.1007/11671541_9","abstract":"Many approximation results for single machine scheduling problems rely on the conversion of preemptive schedules into (preemptive or non-preemptive) solutions. The initial preemptive schedule is usually an optimal solution to a combinatorial relaxation or a linear programming relaxation of the scheduling problem under consideration. It therefore provides a lower bound on the optimal objective function value. However, it also contains structural information which is useful for the construction of provably good feasible schedules. In this context, list scheduling in order of so-called α-points has evolved as an important and successful tool. We give a survey and a uniform presentation of several approximation results for single machine scheduling with total weighted completion time objective from the last years which rely on the concept of α-points.","language":"en","number":"3484","urldate":"2015-04-30TZ","booktitle":"Efficient Approximation and Online Algorithms","publisher":"Springer Berlin Heidelberg","author":[{"propositions":[],"lastnames":["Skutella"],"firstnames":["Martin"],"suffixes":[]}],"editor":[{"propositions":[],"lastnames":["Bampis"],"firstnames":["Evripidis"],"suffixes":[]},{"propositions":[],"lastnames":["Jansen"],"firstnames":["Klaus"],"suffixes":[]},{"propositions":[],"lastnames":["Kenyon"],"firstnames":["Claire"],"suffixes":[]}],"year":"2006","keywords":"Algorithm Analysis and Problem Complexity, Computer Communication Networks, Computer Graphics, Discrete Mathematics in Computer Science, Numeric Computing, algorithms","pages":"250--291","bibtex":"@incollection{skutella_list_2006,\n\tseries = {Lecture {Notes} in {Computer} {Science}},\n\ttitle = {List {Scheduling} in {Order} of α-{Points} on a {Single} {Machine}},\n\tcopyright = {©2006 Springer-Verlag Berlin Heidelberg},\n\tisbn = {978-3-540-32212-2, 978-3-540-32213-9},\n\turl = {http://link.springer.com/chapter/10.1007/11671541_9},\n\tabstract = {Many approximation results for single machine scheduling problems rely on the conversion of preemptive schedules into (preemptive or non-preemptive) solutions. The initial preemptive schedule is usually an optimal solution to a combinatorial relaxation or a linear programming relaxation of the scheduling problem under consideration. It therefore provides a lower bound on the optimal objective function value. However, it also contains structural information which is useful for the construction of provably good feasible schedules. In this context, list scheduling in order of so-called α-points has evolved as an important and successful tool. We give a survey and a uniform presentation of several approximation results for single machine scheduling with total weighted completion time objective from the last years which rely on the concept of α-points.},\n\tlanguage = {en},\n\tnumber = {3484},\n\turldate = {2015-04-30TZ},\n\tbooktitle = {Efficient {Approximation} and {Online} {Algorithms}},\n\tpublisher = {Springer Berlin Heidelberg},\n\tauthor = {Skutella, Martin},\n\teditor = {Bampis, Evripidis and Jansen, Klaus and Kenyon, Claire},\n\tyear = {2006},\n\tkeywords = {Algorithm Analysis and Problem Complexity, Computer Communication Networks, Computer Graphics, Discrete Mathematics in Computer Science, Numeric Computing, algorithms},\n\tpages = {250--291}\n}\n\n","author_short":["Skutella, M."],"editor_short":["Bampis, E.","Jansen, K.","Kenyon, C."],"key":"skutella_list_2006","id":"skutella_list_2006","bibbaseid":"skutella-listschedulinginorderofpointsonasinglemachine-2006","role":"author","urls":{"Paper":"http://link.springer.com/chapter/10.1007/11671541_9"},"keyword":["Algorithm Analysis and Problem Complexity","Computer Communication Networks","Computer Graphics","Discrete Mathematics in Computer Science","Numeric Computing","algorithms"],"downloads":0,"html":""},"search_terms":["list","scheduling","order","points","single","machine","skutella"],"keywords":["algorithm analysis and problem complexity","computer communication networks","computer graphics","discrete mathematics in computer science","numeric computing","algorithms"],"authorIDs":[],"dataSources":["TJDe75XCoX4GYYsBX"]}