{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T11:58:48Z","timestamp":1781092728374,"version":"3.54.1"},"reference-count":21,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2009,4]]},"abstract":"<jats:p> In scheduling with controllable processing times the actual processing time of each job is to be chosen from the interval between the smallest (compressed or fully crashed) value and the largest (decompressed or uncrashed) value. In the problems under consideration, the jobs are processed on a single machine and the quality of a schedule is measured by two functions: the maximum cost (that depends on job completion times) and the total compression cost. Our main model is bicriteria and is related to determining an optimal trade-off between these two objectives. Additionally, we consider a pair of associated single criterion problems, in which one of the objective functions is bounded while the other one is to be minimized. We reduce the bicriteria problem to a series of parametric linear programs defined over the intersection of a submodular polyhedron with a box. We demonstrate that the feasible region is represented by a so-called base polyhedron and the corresponding problem can be solved by the greedy algorithm that runs two orders of magnitude faster than known previously. For each of the associated single criterion problems, we develop algorithms that deliver the optimum faster than it can be deduced from a solution to the bicriteria problem. <\/jats:p>","DOI":"10.1142\/s0129054109006541","type":"journal-article","created":{"date-parts":[[2009,4,7]],"date-time":"2009-04-07T08:25:36Z","timestamp":1239092736000},"page":"247-269","source":"Crossref","is-referenced-by-count":16,"title":["SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES BY SUBMODULAR OPTIMIZATION"],"prefix":"10.1142","volume":"20","author":[{"given":"NATALIA V.","family":"SHAKHLEVICH","sequence":"first","affiliation":[{"name":"School of Computing, University of Leeds, Leeds LS2 9JT, U.K."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"AKIYOSHI","family":"SHIOURA","sequence":"additional","affiliation":[{"name":"Graduate School of Information Sciences, Tohoku University, Sendai 980-8579, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"VITALY A.","family":"STRUSEVICH","sequence":"additional","affiliation":[{"name":"School of Computing and Mathematical Sciences, University of Greenwich, Old Royal Naval College, Park Row, Greenwich, London SE10 9LS, U.K."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"219","published-online":{"date-parts":[[2012,4,30]]},"reference":[{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1979.1675432"},{"key":"rf3","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2001"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1007\/BF01589418"},{"key":"rf5","series-title":"Annals of Discrete Mathematics","volume-title":"Submodular Functions and Optimization","volume":"58","author":"Fujishige S.","year":"2005"},{"key":"rf6","first-page":"390","volume":"9","author":"Hochbaum D. S.","journal-title":"Math. Oper. Res."},{"key":"rf7","first-page":"269","volume":"69","author":"Hochbaum D. S.","journal-title":"Math. Program."},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-001-1441-x"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(96)00129-4"},{"key":"rf10","unstructured":"N.\u00a0Katoh and T.\u00a0Ibaraki, Handbook of Combinatorial Optimization\u00a02, eds. D.Z.\u00a0Du and P. M.\u00a0Pardalos (Kluwer, Dordrecht, 1998)\u00a0pp. 159\u2013260."},{"key":"rf11","unstructured":"J. Y.T.\u00a0Leung, Handbook of Scheduling: Algorithms, Models and Performance Analysis, ed. J. Y.T.\u00a0Leung (Chapman & Hall\/CRC, 2004)\u00a0pp. 34-1\u201334-16."},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(90)90105-L"},{"key":"rf13","volume-title":"Combinatorial Optimization: Polyhedra and Effciency","author":"Schrijver A.","year":"2003"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2007.02.003"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-005-6813-1"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9091-9"},{"key":"rf17","volume-title":"Multicriteria Scheduling: Theory, Models and Algorithms","author":"T'kindt V.","year":"2006"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(84)90181-2"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(94)90077-9"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(82)80008-8"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1080\/05695558008974515"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.05.004"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054109006541","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T12:40:13Z","timestamp":1565095213000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054109006541"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,4]]},"references-count":21,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2012,4,30]]},"published-print":{"date-parts":[[2009,4]]}},"alternative-id":["10.1142\/S0129054109006541"],"URL":"https:\/\/doi.org\/10.1142\/s0129054109006541","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,4]]}}}