@article{correa_lp-based_????,
	title = {{LP}-based online scheduling: from single to parallel machines},
	shorttitle = {{LP}-based online scheduling},
	url = {http://dx.doi.org/10.1007/s10107-007-0204-7},
	doi = {10.1007/s10107-007-0204-7},
	abstract = {Abstract  We study classic machine sequencing problems in an online setting. Specifically, we look at deterministic and randomized algorithms for the problem of scheduling jobs with release dates on identical parallel machines, to minimize the sum of weighted completion times: Both preemptive and non-preemptive versions of the problem are analyzed. Using linear programming techniques, borrowed from the single machine case, we are able to design a 2.62-competitive deterministic algorithm for the non-preemptive version of the problem, improving upon the 3.28-competitive algorithm of Megow and Schulz. Additionally, we show how to combine randomization techniques with the linear programming approach to obtain randomized algorithms for both versions of the problem with competitive ratio strictly smaller than 2 for any number of machines (but approaching two as the number of machines grows). Our algorithms naturally extend several approaches for single and parallel machine scheduling. We also present a brief computational study, for randomly generated problem instances, which suggests that our algorithms perform very well in practice.},
	urldate = {2008-12-04TZ},
	journal = {Mathematical Programming},
	author = {Correa, José and Wagner, Michael}
}

{"_id":"HpGfkcaWmrqWJHH37","bibbaseid":"correa-wagner-lpbasedonlineschedulingfromsingletoparallelmachines","downloads":0,"creationDate":"2016-12-19T20:50:58.882Z","title":"LP-based online scheduling: from single to parallel machines","author_short":["Correa, J.","Wagner, M."],"year":null,"bibtype":"article","biburl":"http://bibbase.org/zotero/verschae","bibdata":{"bibtype":"article","type":"article","title":"LP-based online scheduling: from single to parallel machines","shorttitle":"LP-based online scheduling","url":"http://dx.doi.org/10.1007/s10107-007-0204-7","doi":"10.1007/s10107-007-0204-7","abstract":"Abstract We study classic machine sequencing problems in an online setting. Specifically, we look at deterministic and randomized algorithms for the problem of scheduling jobs with release dates on identical parallel machines, to minimize the sum of weighted completion times: Both preemptive and non-preemptive versions of the problem are analyzed. Using linear programming techniques, borrowed from the single machine case, we are able to design a 2.62-competitive deterministic algorithm for the non-preemptive version of the problem, improving upon the 3.28-competitive algorithm of Megow and Schulz. Additionally, we show how to combine randomization techniques with the linear programming approach to obtain randomized algorithms for both versions of the problem with competitive ratio strictly smaller than 2 for any number of machines (but approaching two as the number of machines grows). Our algorithms naturally extend several approaches for single and parallel machine scheduling. We also present a brief computational study, for randomly generated problem instances, which suggests that our algorithms perform very well in practice.","urldate":"2008-12-04TZ","journal":"Mathematical Programming","author":[{"propositions":[],"lastnames":["Correa"],"firstnames":["José"],"suffixes":[]},{"propositions":[],"lastnames":["Wagner"],"firstnames":["Michael"],"suffixes":[]}],"bibtex":"@article{correa_lp-based_????,\n\ttitle = {{LP}-based online scheduling: from single to parallel machines},\n\tshorttitle = {{LP}-based online scheduling},\n\turl = {http://dx.doi.org/10.1007/s10107-007-0204-7},\n\tdoi = {10.1007/s10107-007-0204-7},\n\tabstract = {Abstract We study classic machine sequencing problems in an online setting. Specifically, we look at deterministic and randomized algorithms for the problem of scheduling jobs with release dates on identical parallel machines, to minimize the sum of weighted completion times: Both preemptive and non-preemptive versions of the problem are analyzed. Using linear programming techniques, borrowed from the single machine case, we are able to design a 2.62-competitive deterministic algorithm for the non-preemptive version of the problem, improving upon the 3.28-competitive algorithm of Megow and Schulz. Additionally, we show how to combine randomization techniques with the linear programming approach to obtain randomized algorithms for both versions of the problem with competitive ratio strictly smaller than 2 for any number of machines (but approaching two as the number of machines grows). Our algorithms naturally extend several approaches for single and parallel machine scheduling. We also present a brief computational study, for randomly generated problem instances, which suggests that our algorithms perform very well in practice.},\n\turldate = {2008-12-04TZ},\n\tjournal = {Mathematical Programming},\n\tauthor = {Correa, José and Wagner, Michael}\n}\n\n","author_short":["Correa, J.","Wagner, M."],"key":"correa_lp-based_????","id":"correa_lp-based_????","bibbaseid":"correa-wagner-lpbasedonlineschedulingfromsingletoparallelmachines","role":"author","urls":{"Paper":"http://dx.doi.org/10.1007/s10107-007-0204-7"},"downloads":0,"html":""},"search_terms":["based","online","scheduling","single","parallel","machines","correa","wagner"],"keywords":[],"authorIDs":[],"dataSources":["TJDe75XCoX4GYYsBX"]}