@article{choshmhen22,
	abstract = {One of the oldest results in scheduling theory is that the Shortest Processing Time (SPT) rule finds an
optimal solution to the problem of scheduling jobs on identical parallel machines to minimize average
job completion times. We present a new proof of correctness of SPT based on linear programming (LP).
Our proof relies on a generalization of a single-machine result that yields an equivalence between two
scheduling problems. We first identify and solve an appropriate variant of our problem, then map its
solutions to solutions for our original problem to establish SPT optimality. Geometric insights used
therein may find further uses; we demonstrate two applications of the same principle in generalized
settings.},
	author = {Woo-Hyung Cho and David B. Shmoys and Shane G. Henderson},
	date-added = {2022-02-07 14:53:59 -0500},
	date-modified = {2024-04-04 15:47:05 +1030},
	journal = {Operations Research Letters},
	pages = {99-104},
	title = {{SPT} optimality (mostly) via linear programming},
	url = {https://doi.org/10.1016/j.orl.2022.12.007},
	volume = {51},
	year = {2023},
	bdsk-url-1 = {https://doi.org/10.1016/j.orl.2022.12.007}}

{"_id":"HCZEsWtcZdb4ZCgs2","bibbaseid":"cho-shmoys-henderson-sptoptimalitymostlyvialinearprogramming-2023","author_short":["Cho, W.","Shmoys, D. B.","Henderson, S. G."],"bibdata":{"bibtype":"article","type":"article","abstract":"One of the oldest results in scheduling theory is that the Shortest Processing Time (SPT) rule finds an optimal solution to the problem of scheduling jobs on identical parallel machines to minimize average job completion times. We present a new proof of correctness of SPT based on linear programming (LP). Our proof relies on a generalization of a single-machine result that yields an equivalence between two scheduling problems. We first identify and solve an appropriate variant of our problem, then map its solutions to solutions for our original problem to establish SPT optimality. Geometric insights used therein may find further uses; we demonstrate two applications of the same principle in generalized settings.","author":[{"firstnames":["Woo-Hyung"],"propositions":[],"lastnames":["Cho"],"suffixes":[]},{"firstnames":["David","B."],"propositions":[],"lastnames":["Shmoys"],"suffixes":[]},{"firstnames":["Shane","G."],"propositions":[],"lastnames":["Henderson"],"suffixes":[]}],"date-added":"2022-02-07 14:53:59 -0500","date-modified":"2024-04-04 15:47:05 +1030","journal":"Operations Research Letters","pages":"99-104","title":"SPT optimality (mostly) via linear programming","url":"https://doi.org/10.1016/j.orl.2022.12.007","volume":"51","year":"2023","bdsk-url-1":"https://doi.org/10.1016/j.orl.2022.12.007","bibtex":"@article{choshmhen22,\n\tabstract = {One of the oldest results in scheduling theory is that the Shortest Processing Time (SPT) rule finds an\noptimal solution to the problem of scheduling jobs on identical parallel machines to minimize average\njob completion times. We present a new proof of correctness of SPT based on linear programming (LP).\nOur proof relies on a generalization of a single-machine result that yields an equivalence between two\nscheduling problems. We first identify and solve an appropriate variant of our problem, then map its\nsolutions to solutions for our original problem to establish SPT optimality. Geometric insights used\ntherein may find further uses; we demonstrate two applications of the same principle in generalized\nsettings.},\n\tauthor = {Woo-Hyung Cho and David B. Shmoys and Shane G. Henderson},\n\tdate-added = {2022-02-07 14:53:59 -0500},\n\tdate-modified = {2024-04-04 15:47:05 +1030},\n\tjournal = {Operations Research Letters},\n\tpages = {99-104},\n\ttitle = {{SPT} optimality (mostly) via linear programming},\n\turl = {https://doi.org/10.1016/j.orl.2022.12.007},\n\tvolume = {51},\n\tyear = {2023},\n\tbdsk-url-1 = {https://doi.org/10.1016/j.orl.2022.12.007}}\n\n","author_short":["Cho, W.","Shmoys, D. B.","Henderson, S. G."],"key":"choshmhen22","id":"choshmhen22","bibbaseid":"cho-shmoys-henderson-sptoptimalitymostlyvialinearprogramming-2023","role":"author","urls":{"Paper":"https://doi.org/10.1016/j.orl.2022.12.007"},"metadata":{"authorlinks":{}},"downloads":3},"bibtype":"article","biburl":"https://people.orie.cornell.edu/shane/ShanePubs.bib","dataSources":["ZCuKDjctePZJeeaBw"],"keywords":[],"search_terms":["spt","optimality","mostly","via","linear","programming","cho","shmoys","henderson"],"title":"SPT optimality (mostly) via linear programming","year":2023,"downloads":3}