{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T09:03:58Z","timestamp":1725872638786},"publisher-location":"Cham","reference-count":34,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319449135"},{"type":"electronic","value":"9783319449142"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-44914-2_7","type":"book-chapter","created":{"date-parts":[[2016,11,29]],"date-time":"2016-11-29T21:56:02Z","timestamp":1480456562000},"page":"74-90","source":"Crossref","is-referenced-by-count":1,"title":["Handling Scheduling Problems with Controllable Parameters by Methods of Submodular Optimization"],"prefix":"10.1007","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":[[2016,9,10]]},"reference":[{"key":"7_CR1","doi-asserted-by":"crossref","first-page":"906","DOI":"10.1137\/S0097539791199334","volume":"23","author":"RK Ahuja","year":"1994","unstructured":"Ahuja, R.K., Orlin, J.B., Stein, C., Tarjan, R.E.: Improved algorithms for bipartite network flow. SIAM J. Comput. 23, 906\u2013933 (1994)","journal-title":"SIAM J. Comput."},{"key":"7_CR2","unstructured":"Brucker, P.: Scheduling Algorithms, 5th edn, p. 371. Springer, Heidelberg (2007)"},{"key":"7_CR3","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1287\/mnsc.32.3.341","volume":"32","author":"A Federgruen","year":"1986","unstructured":"Federgruen, A., Groenevelt, H.: Preemptive scheduling of uniform machines by ordinary network flow techniques. Manag. Sci. 32, 341\u2013349 (1986)","journal-title":"Manag. Sci."},{"key":"7_CR4","series-title":"Annals of Discrete Mathematics","volume-title":"Submodular Functions and Optimization","author":"S Fujishige","year":"2005","unstructured":"Fujishige, S.: Submodular Functions and Optimization. Annals of Discrete Mathematics, vol. 58, 2nd edn. Elsevier, Amsterdam (2005)","edition":"2"},{"key":"7_CR5","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1137\/0218003","volume":"18","author":"G Gallo","year":"1989","unstructured":"Gallo, G., Grigoriadis, M.D., Tarjan, R.E.: A fast parametric maximum flow algorithm and applications. SIAM J. Comput. 18, 30\u201355 (1989)","journal-title":"SIAM J. Comput."},{"key":"7_CR6","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":"7_CR7","unstructured":"Gordon, V.S., Tanaev, V.S.: Deadlines in single-stage deterministic scheduling. Optimization of Systems for Collecting, Transfer and Processing of Analogous and Discrete Data in Local Information Computing Systems. Materials of the 1st Joint Soviet-Bulgarian seminar (Institute of Engineering Cybernetics of Academy of Sciences of BSSR - Institute of Engineering Cybernetics of Bulgarian Academy of Sciences, Minsk), pp. 53\u201358 (1973) (in Russian)"},{"key":"7_CR8","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/0166-218X(90)90093-R","volume":"28","author":"DS Hochbaum","year":"1990","unstructured":"Hochbaum, D.S., Shamir, R.: Minimizing the number of tardy job units under release time constraints. Discr. Appl. Math. 28, 45\u201357 (1990)","journal-title":"Discr. Appl. Math."},{"key":"7_CR9","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1002\/nav.3800210113","volume":"21","author":"W Horn","year":"1974","unstructured":"Horn, W.: Some simple scheduling algorithms. Naval Res. Logist. Q. 21, 177\u2013185 (1974)","journal-title":"Naval Res. Logist. Q."},{"key":"7_CR10","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":"7_CR11","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":"7_CR12","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":"7_CR13","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":"7_CR14","series-title":"Logistics of Production and Inventory","first-page":"445","volume-title":"Handbooks in Operations Research and Management Science","author":"EL Lawler","year":"1993","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)"},{"key":"7_CR15","doi-asserted-by":"crossref","first-page":"34-1","DOI":"10.1201\/9780203489802","volume-title":"Handbook of Scheduling: Algorithms, Models and Performance Analysis","author":"JYT Leung","year":"2004","unstructured":"Leung, J.Y.T.: Minimizing total weighted error for imprecise computation tasks. In: Leung, J.Y.T. (ed.) Handbook of Scheduling: Algorithms, Models and Performance Analysis, pp. 34-1\u201334-16. Chapman & Hall\/CRC, Boca Raton (2004)"},{"key":"7_CR16","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1016\/0166-218X(92)00037-M","volume":"51","author":"JY-T Leung","year":"1994","unstructured":"Leung, J.Y.-T., Yu, V.K.M., Wei, W.-D.: Minimizing the weighted number of tardy task units. Discr. Appl. Math. 51, 307\u2013316 (1994)","journal-title":"Discr. Appl. Math."},{"key":"7_CR17","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":"7_CR18","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. Manage. Sci. 12, 1\u201312 (1959)","journal-title":"Manage. Sci."},{"key":"7_CR19","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":"7_CR20","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. Discr. Appl. Math. 26, 271\u2013287 (1990)","journal-title":"Discr. Appl. Math."},{"key":"7_CR21","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. Discr. Appl. Math. 63, 237\u2013256 (1995)","journal-title":"Discr. Appl. Math."},{"key":"7_CR22","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":"7_CR23","doi-asserted-by":"crossref","first-page":"550","DOI":"10.1145\/322203.322214","volume":"27","author":"S Sahni","year":"1980","unstructured":"Sahni, S., Cho, Y.: Scheduling independent tasks with due times on a uniform processor system. J. ACM 27, 550\u2013563 (1980)","journal-title":"J. ACM"},{"key":"7_CR24","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":"7_CR25","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency, p. 1879. Springer, Heidelberg (2003)"},{"key":"7_CR26","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. Discr. Appl. Math. 155, 1643\u20131666 (2007)","journal-title":"Discr. Appl. Math."},{"key":"7_CR27","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":"7_CR28","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":"7_CR29","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":"7_CR30","doi-asserted-by":"crossref","unstructured":"Shih, W.-K., Lee, C.-R., Tang, C.H.: A fast algorithm for scheduling imprecise computations with timing constraints to minimize weighted error. In: Proceedings of 21th IEEE Real-Time Systems Symposium (RTSS 2000), pp. 305\u2013310 (2000)","DOI":"10.1109\/REAL.2000.896019"},{"key":"7_CR31","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. Discr. Math. 27, 186\u2013204 (2013)","journal-title":"SIAM J. Discr. Math."},{"key":"7_CR32","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1007\/s10107-014-0814-9","volume":"153","author":"A Shioura","year":"2015","unstructured":"Shioura, A., Shakhlevich, N.V., Strusevich, V.A.: Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times. Math. Progr. A 153, 495\u2013534 (2015)","journal-title":"Math. Progr. A"},{"key":"7_CR33","unstructured":"Shioura, A., Shakhlevich, N.V., Strusevich, V.A.: Scheduling imprecise computation tasks on parallel machines to minimize linear and non-linear error penalties: reviews, links and improvements. University of Greenwich, London, Report SORG-04-2015 (2015)"},{"key":"7_CR34","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1287\/ijoc.2015.0660","volume":"28","author":"A Shioura","year":"2016","unstructured":"Shioura, A., Shakhlevich, N.V., Strusevich, V.A.: Application of submodular optimization to single machine scheduling with controllable processing times subject to release dates and deadlines. INFORMS J. Comput. 28, 148\u2013161 (2016)","journal-title":"INFORMS J. Comput."}],"container-title":["Lecture Notes in Computer Science","Discrete Optimization and Operations Research"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-44914-2_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,15]],"date-time":"2022-07-15T14:08:01Z","timestamp":1657894081000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-44914-2_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319449135","9783319449142"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-44914-2_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}