{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T18:41:08Z","timestamp":1775068868265,"version":"3.50.1"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2014,9,17]],"date-time":"2014-09-17T00:00:00Z","timestamp":1410912000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2015,11]]},"DOI":"10.1007\/s10107-014-0814-9","type":"journal-article","created":{"date-parts":[[2014,9,16]],"date-time":"2014-09-16T09:37:04Z","timestamp":1410860224000},"page":"495-534","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times"],"prefix":"10.1007","volume":"153","author":[{"given":"Akiyoshi","family":"Shioura","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Natalia V.","family":"Shakhlevich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vitaly A.","family":"Strusevich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,9,17]]},"reference":[{"key":"814_CR1","volume-title":"Scheduling Algorithms","author":"P Brucker","year":"2007","unstructured":"Brucker, P.: Scheduling Algorithms, 5th edn. Springer, Berlin (2007)","edition":"5"},{"key":"814_CR2","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0377-2217(94)90208-9","volume":"74","author":"YL Chen","year":"1994","unstructured":"Chen, Y.L.: Scheduling jobs to minimize total cost. Eur. J. Oper. Res. 74, 111\u2013119 (1994)","journal-title":"Eur. J. Oper. Res."},{"key":"814_CR3","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1287\/moor.5.2.186","volume":"5","author":"S Fujishige","year":"1980","unstructured":"Fujishige, S.: Lexicographically optimal base of a polymatroid with respect to a weight factor. Math. Oper. Res. 5, 186\u2013196 (1980)","journal-title":"Math. Oper. Res."},{"key":"814_CR4","unstructured":"Fujishige, S.: Submodular Functions and Optimization. Annals of Discrete Mathematics, vol. 58, 2nd edn. Elsevier, Amsterdam (2005)"},{"key":"814_CR5","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1145\/322047.322055","volume":"25","author":"TF Gonzales","year":"1978","unstructured":"Gonzales, T.F., Sahni, S.: Preemptive scheduling of uniform processor systems. J. ACM 25, 92\u2013101 (1978)","journal-title":"J. ACM"},{"key":"814_CR6","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/0377-2217(91)90300-K","volume":"54","author":"H Groenevelt","year":"1991","unstructured":"Groenevelt, H.: Two algorithms for maximizing a separable concave function over a polymatroid feasible region. Eur. J. Oper. Res. 54, 227\u2013236 (1991)","journal-title":"Eur. J. Oper. Res."},{"key":"814_CR7","doi-asserted-by":"crossref","first-page":"761","DOI":"10.1145\/502090.502096","volume":"48","author":"S Iwata","year":"2001","unstructured":"Iwata, S., Fleischer, L., Fujishige, S.: A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions. J. ACM 48, 761\u2013777 (2001)","journal-title":"J. ACM"},{"key":"814_CR8","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1016\/0377-2217(96)00129-4","volume":"94","author":"A Janiak","year":"1996","unstructured":"Janiak, A., Kovalyov, M.Y.: Single machine scheduling with deadlines and resource dependent processing times. Eur. J. Oper. Res. 94, 284\u2013291 (1996)","journal-title":"Eur. J. Oper. Res."},{"key":"814_CR9","doi-asserted-by":"crossref","first-page":"1565","DOI":"10.1016\/S0305-0548(03)00101-1","volume":"31","author":"K Jansen","year":"2004","unstructured":"Jansen, K., Mastrolilli, M.: Approximation schemes for parallel machine scheduling problems with controllable processing times. Comput. Oper. Res. 31, 1565\u20131581 (2004)","journal-title":"Comput. Oper. Res."},{"key":"814_CR10","first-page":"159","volume-title":"Handbook of Combinatorial Optimization","author":"N Katoh","year":"1998","unstructured":"Katoh, N., Ibaraki, T.: Resource allocation problems. In: Du, D.-Z., Pardalos, P.M. (eds.) Handbook of Combinatorial Optimization, vol. 2, pp. 159\u2013260. Kluwer, Dordrecht (1998)"},{"key":"814_CR11","doi-asserted-by":"crossref","unstructured":"Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.: Sequencing and scheduling: algorithms and complexity. In: Graves, S.C., Rinnooy Kan, A.H.G., Zipkin, P.H. (eds.) Handbooks in Operations Research and Management Science. Logistics of Production and Inventory, vol. 4, pp. 445\u2013522. Elsevier, Amsterdam (1993)","DOI":"10.1016\/S0927-0507(05)80189-6"},{"key":"814_CR12","unstructured":"Leung, J.Y.-T.: Minimizing total weighted error for imprecise computation tasks. In: Leung, J.Y.-T. (eds.) Handbook of Scheduling: Algorithms, Models and Performance Analysis, pp. 34-1\u201334-16. Chapman & Hall\/CRC, London (2004)"},{"key":"814_CR13","doi-asserted-by":"crossref","first-page":"744","DOI":"10.1287\/opre.47.5.744","volume":"47","author":"ST McCormick","year":"1999","unstructured":"McCormick, S.T.: Fast algorithms for parametric scheduling come from extensions to parametric maximum flow. Oper. Res. 47, 744\u2013756 (1999)","journal-title":"Oper. Res."},{"key":"814_CR14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/mnsc.6.1.1","volume":"12","author":"R McNaughton","year":"1959","unstructured":"McNaughton, R.: Scheduling with deadlines and loss functions. Manag. Sci. 12, 1\u201312 (1959)","journal-title":"Manag. Sci."},{"key":"814_CR15","doi-asserted-by":"crossref","DOI":"10.1002\/9781118627372","volume-title":"Integer and Combinatorial Optimization","author":"GL Nemhauser","year":"1988","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, New York (1988)"},{"key":"814_CR16","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1016\/0166-218X(90)90105-L","volume":"26","author":"E Nowicki","year":"1990","unstructured":"Nowicki, E., Zdrza\u0142ka, S.: A survey of results for sequencing problems with controllable processing times. Discrete Appl. Math. 26, 271\u2013287 (1990)","journal-title":"Discrete Appl. Math."},{"key":"814_CR17","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0166-218X(94)00071-5","volume":"63","author":"E Nowicki","year":"1995","unstructured":"Nowicki, E., Zdrza\u0142ka, S.: A bicriterion approach to preemptive scheduling of parallel machines with controllable job processing times. Discrete Appl. Math. 63, 237\u2013256 (1995)","journal-title":"Discrete Appl. Math."},{"key":"814_CR18","doi-asserted-by":"crossref","first-page":"925","DOI":"10.1287\/opre.27.5.925","volume":"27","author":"S Sahni","year":"1979","unstructured":"Sahni, S.: Preemptive scheduling with due dates. Oper. Res. 27, 925\u2013934 (1979)","journal-title":"Oper. Res."},{"key":"814_CR19","doi-asserted-by":"crossref","unstructured":"Sahni, S., Cho, Y.: Scheduling independent tasks with due times on a uniform processor system. J. ACM 27, 550\u2013563 (1980)","DOI":"10.1145\/322203.322214"},{"key":"814_CR20","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1006\/jctb.2000.1989","volume":"80","author":"A Schrijver","year":"2000","unstructured":"Schrijver, A.: A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Comb. Theory B 80, 346\u2013355 (2000)","journal-title":"J. Comb. Theory B"},{"key":"814_CR21","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin (2003)"},{"key":"814_CR22","doi-asserted-by":"crossref","first-page":"1643","DOI":"10.1016\/j.dam.2007.02.003","volume":"155","author":"D Shabtay","year":"2007","unstructured":"Shabtay, D., Steiner, G.: A survey of scheduling with controllable processing times. Discrete Appl. Math. 155, 1643\u20131666 (2007)","journal-title":"Discrete Appl. Math."},{"key":"814_CR23","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1007\/s10951-005-6813-1","volume":"8","author":"NV Shakhlevich","year":"2005","unstructured":"Shakhlevich, N.V., Strusevich, V.A.: Pre-emptive scheduling problems with controllable processing times. J. Sched. 8, 233\u2013253 (2005)","journal-title":"J. Sched."},{"key":"814_CR24","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1007\/s00453-007-9091-9","volume":"51","author":"NV Shakhlevich","year":"2008","unstructured":"Shakhlevich, N.V., Strusevich, V.A.: Preemptive scheduling on uniform parallel machines with controllable job processing times. Algorithmica 51, 451\u2013473 (2008)","journal-title":"Algorithmica"},{"key":"814_CR25","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1142\/S0129054109006541","volume":"20","author":"NV Shakhlevich","year":"2009","unstructured":"Shakhlevich, N.V., Shioura, A., Strusevich, V.A.: Single machine scheduling with controllable processing times by submodular optimization. Int. J. Found. Comput. Sci. 20, 247\u2013269 (2009)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"814_CR26","doi-asserted-by":"crossref","unstructured":"Shakhlevich, N.V., Shioura, A., Strusevich, V.A.: Fast divide-and-conquer algorithms for preemptive scheduling problems with controllable processing times\u2014a polymatroidal approach. In: Halperin, D., Mehlhorn, K. (eds.) Lecture Notes Computer Science 5193, ESA 2008, pp. 756\u2013767. Springer, Berlin (2008)","DOI":"10.1007\/978-3-540-87744-8_63"},{"key":"814_CR27","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1137\/110843836","volume":"27","author":"A Shioura","year":"2013","unstructured":"Shioura, A., Shakhlevich, N.V., Strusevich, V.A.: A submodular optimization approach to bicriteria scheduling problems with controllable processing times on parallel machines. SIAM J. Discrete Math. 27, 186\u2013204 (2013)","journal-title":"SIAM J. Discrete Math."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-014-0814-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-014-0814-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-014-0814-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,26]],"date-time":"2019-03-26T22:52:21Z","timestamp":1553640741000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-014-0814-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,9,17]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,11]]}},"alternative-id":["814"],"URL":"https:\/\/doi.org\/10.1007\/s10107-014-0814-9","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,9,17]]}}}