{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T04:07:09Z","timestamp":1777954029182,"version":"3.51.4"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2015,4,13]],"date-time":"2015-04-13T00:00:00Z","timestamp":1428883200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Deutsche Forschungsgemeinschaft (DFG) as part of the Priority Program \u201cAlgorithm Engineering"},{"name":"fellowship within the Postdoc-Programme of the German Academic Exchange Service"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2015,6,23]]},"abstract":"<jats:p>\n            We consider a single-machine scheduling problem. Given some continuous, nondecreasing cost function, we aim to compute a schedule minimizing the weighted total cost, where the cost of each job is determined by the cost function value at its completion time. This problem is closely related to scheduling a single machine with nonuniform processing speed. We show that for piecewise linear cost functions it is strongly NP-hard. The main contribution of this article is a tight analysis of the approximation guarantee of Smith\u2019s rule under any convex or concave cost function. More specifically, for these wide classes of cost functions we reduce the task of determining a worst-case problem instance to a continuous optimization problem, which can be solved by standard algebraic or numerical methods. For polynomial cost functions with positive coefficients, it turns out that the tight approximation ratio can be calculated as the root of a univariate polynomial. We show that this approximation ratio is asymptotically equal to\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>\n              (\n              <jats:italic>k<\/jats:italic>\n              \u2212 1)\/(\n              <jats:italic>k<\/jats:italic>\n              + 1)\n            <\/jats:sup>\n            , denoting by\n            <jats:italic>k<\/jats:italic>\n            the degree of the cost function. To overcome unrealistic worst-case instances, we also give tight bounds for the case of integral processing times that are parameterized by the maximum and total processing time.\n          <\/jats:p>","DOI":"10.1145\/2629652","type":"journal-article","created":{"date-parts":[[2015,4,14]],"date-time":"2015-04-14T12:32:19Z","timestamp":1429014739000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["On the Performance of Smith\u2019s Rule in Single-Machine Scheduling with Nonlinear Cost"],"prefix":"10.1145","volume":"11","author":[{"given":"Wiebke","family":"H\u00f6hn","sequence":"first","affiliation":[{"name":"Technische Universit\u00e4t Berlin, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tobias","family":"Jacobs","sequence":"additional","affiliation":[{"name":"NEC Laboratories Europe, Heidelberg Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,4,13]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS\u201999)","author":"Afrati F. N.","unstructured":"F. N. Afrati , E. Bampis , C. Chekuri , D. R. Karger , C. Kenyon , S. Khanna , I. Milis , M. Queyranne , M. Skutella , C. Stein , and M. Sviridenko . 1999. Approximation schemes for minimizing average weighted completion time with release dates . In Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS\u201999) . IEEE, 32--44. F. N. Afrati, E. Bampis, C. Chekuri, D. R. Karger, C. Kenyon, S. Khanna, I. Milis, M. Queyranne, M. Skutella, C. Stein, and M. Sviridenko. 1999. Approximation schemes for minimizing average weighted completion time with release dates. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS\u201999). IEEE, 32--44."},{"key":"e_1_2_1_2_1","unstructured":"S. Albers S. K. Baruah R. H. M\u00f6hring and K. Pruhs (Eds.). 2010. Open Problems\u2014Scheduling. Number 10071 in Dagstuhl Seminar Proceedings. Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik Germany. Retrieved from http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2010\/2536.  S. Albers S. K. Baruah R. H. M\u00f6hring and K. Pruhs (Eds.). 2010. Open Problems\u2014Scheduling. Number 10071 in Dagstuhl Seminar Proceedings. Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik Germany. Retrieved from http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2010\/2536."},{"key":"e_1_2_1_3_1","first-page":"633","article-title":"A node elimination procedure for Townsend\u2019s algorithm for solving the single machine quadratic penalty function scheduling problem. Manage","volume":"26","author":"Bagga P. C.","year":"1980","unstructured":"P. C. Bagga and K. R. Kalra . 1980 . A node elimination procedure for Townsend\u2019s algorithm for solving the single machine quadratic penalty function scheduling problem. Manage . Sci. 26 (1980), 633 -- 636 . P. C. Bagga and K. R. Kalra. 1980. A node elimination procedure for Townsend\u2019s algorithm for solving the single machine quadratic penalty function scheduling problem. Manage. Sci. 26 (1980), 633--636.","journal-title":"Sci."},{"key":"e_1_2_1_4_1","volume-title":"Introduction to Sequencing and Scheduling","author":"Baker J. K.","unstructured":"J. K. Baker . 1974. Introduction to Sequencing and Scheduling . John Wiley & amp; Sons. J. K. Baker. 1974. Introduction to Sequencing and Scheduling. John Wiley &amp; Sons."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1333875.1334231"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.46"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/090772228"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.1110.0393"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2005.12.001"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2013.05.008"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509954"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 14th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX\u201911)","volume":"6845","author":"Cheung M.","unstructured":"M. Cheung and D. B. Shmoys . 2011. A primal-dual approximation algorithm for min-sum single-machine scheduling problems . In Proceedings of the 14th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX\u201911) . Lecture Notes in Computer Science , Vol. 6845 . Springer, 135--146. M. Cheung and D. B. Shmoys. 2011. A primal-dual approximation algorithm for min-sum single-machine scheduling problems. In Proceedings of the 14th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX\u201911). Lecture Notes in Computer Science, Vol. 6845. Springer, 135--146."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1002\/1520-6750(199512)42:8<1263::AID-NAV3220420810>3.0.CO;2-A"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/110844210"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70356-X"},{"key":"e_1_2_1_16_1","first-page":"644","article-title":"On the single machine scheduling problem with quadratic penalty function of completion times: An improved branching procedure. Manage","volume":"30","author":"Gupta S. K.","year":"1984","unstructured":"S. K. Gupta and T. Sen . 1984 . On the single machine scheduling problem with quadratic penalty function of completion times: An improved branching procedure. Manage . Sci. 30 (1984), 644 -- 647 . S. K. Gupta and T. Sen. 1984. On the single machine scheduling problem with quadratic penalty function of completion times: An improved branching procedure. Manage. Sci. 30 (1984), 644--647.","journal-title":"Sci."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 14th Workshop on Algorithm Engineering and Experiments (ALENEX\u201912)","author":"H\u00f6hn W.","unstructured":"W. H\u00f6hn and T. Jacobs . 2012a. An experimental and analytical study of order constraints for single machine scheduling with quadratic cost . In Proceedings of the 14th Workshop on Algorithm Engineering and Experiments (ALENEX\u201912) . SIAM, 103--117. W. H\u00f6hn and T. Jacobs. 2012a. An experimental and analytical study of order constraints for single machine scheduling with quadratic cost. In Proceedings of the 14th Workshop on Algorithm Engineering and Experiments (ALENEX\u201912). SIAM, 103--117."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29344-3_41"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 23rd Annual Symposium on Discrete Algorithms (SODA\u201912)","author":"Im S.","unstructured":"S. Im , B. Moseley , and K. Pruhs . 2012. Online scheduling with general cost function . In Proceedings of the 23rd Annual Symposium on Discrete Algorithms (SODA\u201912) . SIAM, 1254--1265. S. Im, B. Moseley, and K. Pruhs. 2012. Online scheduling with general cost function. In Proceedings of the 23rd Annual Symposium on Discrete Algorithms (SODA\u201912). SIAM, 1254--1265."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.09.026"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/347476.347479"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796305778"},{"key":"e_1_2_1_23_1","volume-title":"Progress in Combinatorial Optimization","author":"Labetoulle J.","unstructured":"J. Labetoulle , E. L. Lawler , J. K. Lenstra , and A. H. G. Rinnooy Kan . 1984. Preemptive scheduling of uniform machines subject to release dates . In Progress in Combinatorial Optimization . Academic Press , Toronto , 245--261. J. Labetoulle, E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan. 1984. Preemptive scheduling of uniform machines subject to release dates. In Progress in Combinatorial Optimization. Academic Press, Toronto, 245--261."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70742-8"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70743-X"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_63"},{"key":"e_1_2_1_27_1","unstructured":"J. Mestre and J. Verschae. 2014. A 4-approximation for scheduling on a single machine with general cost function. CoRR abs\/1403.0298.  J. Mestre and J. Verschae. 2014. A 4-approximation for scheduling on a single machine with general cost function. CoRR abs\/1403.0298."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(99)00207-6"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36694-9_24"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1057\/jors.2009.2"},{"key":"e_1_2_1_31_1","first-page":"437","article-title":"Scheduling independent tasks on parallel processors. Manage","volume":"12","author":"Rothkopf H.","year":"1966","unstructured":"Michael H. Rothkopf . 1966 . Scheduling independent tasks on parallel processors. Manage . Sci. 12 (1966), 437 -- 447 . Michael H. Rothkopf. 1966. Scheduling independent tasks on parallel processors. Manage. Sci. 12 (1966), 437--447.","journal-title":"Sci."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.32.2.451"},{"key":"e_1_2_1_33_1","first-page":"73","article-title":"Scheduling tasks with deadlines and non-linear loss functions. Manage","volume":"9","author":"Schild A.","year":"1962","unstructured":"A. Schild and I. J. Fredman . 1962 . Scheduling tasks with deadlines and non-linear loss functions. Manage . Sci. 9 (1962), 73 -- 81 . A. Schild and I. J. Fredman. 1962. Scheduling tasks with deadlines and non-linear loss functions. Manage. Sci. 9 (1962), 73--81.","journal-title":"Sci."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-188X(90)90121-W"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800030106"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 21st International Symposium on Algorithms and Computation (ISAAC\u201910)","volume":"6507","author":"Stiller S.","unstructured":"S. Stiller and A. Wiese . 2010. Increasing speed scheduling and flow scheduling . In Proceedings of the 21st International Symposium on Algorithms and Computation (ISAAC\u201910) . Lecture Notes in Computer Science , Vol. 6507 . Springer, 279--290. S. Stiller and A. Wiese. 2010. Increasing speed scheduling and flow scheduling. In Proceedings of the 21st International Symposium on Algorithms and Computation (ISAAC\u201910). Lecture Notes in Computer Science, Vol. 6507. Springer, 279--290."},{"key":"e_1_2_1_37_1","first-page":"530","article-title":"The single machine problem with quadratic penalty function of completion times: A branch-and-bound solution. Manage","volume":"24","author":"Townsend W.","year":"1978","unstructured":"W. Townsend . 1978 . The single machine problem with quadratic penalty function of completion times: A branch-and-bound solution. Manage . Sci. 24 (1978), 530 -- 534 . W. Townsend. 1978. The single machine problem with quadratic penalty function of completion times: A branch-and-bound solution. Manage. Sci. 24 (1978), 530--534.","journal-title":"Sci."},{"key":"e_1_2_1_38_1","first-page":"328","article-title":"The NP-hardness of the single machine common due date weighted tardiness problem. System Sci","volume":"5","author":"Yuan J.","year":"1992","unstructured":"J. Yuan . 1992 . The NP-hardness of the single machine common due date weighted tardiness problem. System Sci . Math. Sci. 5 (1992), 328 -- 333 . J. Yuan. 1992. The NP-hardness of the single machine common due date weighted tardiness problem. System Sci. Math. Sci. 5 (1992), 328--333.","journal-title":"Math. Sci."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629652","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2629652","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:13:30Z","timestamp":1750227210000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629652"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4,13]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,6,23]]}},"alternative-id":["10.1145\/2629652"],"URL":"https:\/\/doi.org\/10.1145\/2629652","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,4,13]]},"assertion":[{"value":"2013-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-04-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}