{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,17]],"date-time":"2026-01-17T03:33:04Z","timestamp":1768620784521,"version":"3.49.0"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,4,7]],"date-time":"2023-04-07T00:00:00Z","timestamp":1680825600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,4,7]],"date-time":"2023-04-07T00:00:00Z","timestamp":1680825600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/T01461X\/1"],"award-info":[{"award-number":["EP\/T01461X\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japanese Society for the Promotion of Science","doi-asserted-by":"crossref","award":["18K11177"],"award-info":[{"award-number":["18K11177"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001691","name":"Japanese Society for the Promotion of Science","doi-asserted-by":"crossref","award":["EP\/T01461X\/1"],"award-info":[{"award-number":["EP\/T01461X\/1"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001691","name":"Japanese Society for the Promotion of Science","doi-asserted-by":"crossref","award":["EP\/T01461X\/1"],"award-info":[{"award-number":["EP\/T01461X\/1"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2024,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In parallel machine scheduling, a size of a job is defined as the number of machines that are simultaneously required for its processing. This paper considers a scheduling problem in which the set of jobs consists of jobs of two sizes: the conventional jobs (each job requires a single machine for its processing) and parallel jobs (each job to be simultaneously processed on more than one machine). The processing times are controllable, and they have to be chosen from given intervals in order to guarantee the existence of a preemptive schedule in which all jobs are completed by a common deadline. The objective is to minimize the total compression cost which reflects possible reductions in processing times. Unlike problems of classical scheduling with conventional jobs, the model under consideration cannot be directly handled by submodular optimization methods. We reduce the problem to maximizing the total weighted work of all jobs parametrized with respect to total work of the parallel jobs. The solution is delivered by separately finding the breakpoints for the maximum total weighted work of the parallel jobs and for the maximum total weighted work of the conventional jobs. This results in a polynomial-time algorithm that is no slower than needed to perform sorting of jobs\u2019 parameters.\n<\/jats:p>","DOI":"10.1007\/s10951-023-00782-w","type":"journal-article","created":{"date-parts":[[2023,4,7]],"date-time":"2023-04-07T10:03:58Z","timestamp":1680861838000},"page":"203-224","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Preemptive scheduling of parallel jobs of two sizes with controllable processing times"],"prefix":"10.1007","volume":"27","author":[{"given":"Akiyoshi","family":"Shioura","sequence":"first","affiliation":[]},{"given":"Vitaly A.","family":"Strusevich","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5225-4008","authenticated-orcid":false,"given":"Natalia V.","family":"Shakhlevich","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,4,7]]},"reference":[{"key":"782_CR1","doi-asserted-by":"crossref","unstructured":"B\u0142a\u017eewicz, J., Drabowski, M., & W\u0119glarz, J. (1986). Scheduling multiprocessor tasks to minimize schedule length. IEEE Transactions on Computers, C-35, 389\u2013393.","DOI":"10.1109\/TC.1986.1676781"},{"key":"782_CR2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84882-310-5","volume-title":"Scheduling for Parallel Processing","author":"M Drozdowski","year":"2009","unstructured":"Drozdowski, M. (2009). Scheduling for Parallel Processing. London: Springer."},{"key":"782_CR3","unstructured":"Fujishige, S. (2005). Submodular functions and optimization, 2nd ed. Annals of Discrete Mathematics, 58."},{"key":"782_CR4","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1002\/nav.3800210113","volume":"21","author":"WA Horn","year":"1974","unstructured":"Horn, W. A. (1974). Some simple scheduling algorithms. Naval Research Logistics Quarterly, 21, 177\u2013185.","journal-title":"Naval Research Logistics Quarterly"},{"key":"782_CR5","doi-asserted-by":"publisher","first-page":"1565","DOI":"10.1016\/S0305-0548(03)00101-1","volume":"31","author":"K Jansen","year":"2004","unstructured":"Jansen, K., & Mastrolilli, M. (2004). Approximation schemes for parallel machine scheduling problems with controllable processing times. Computers and Operations Research, 31, 1565\u20131581.","journal-title":"Computers and Operations Research"},{"key":"782_CR6","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1007\/s10107-002-0361-7","volume":"95","author":"K Jansen","year":"2003","unstructured":"Jansen, K., & Porkolab, L. (2003). Computing optimal preemptive schedules for parallel tasks: Linear programming approaches. Mathematical Programming Series A, 95, 617\u2013630.","journal-title":"Mathematical Programming Series A"},{"key":"782_CR7","first-page":"159","volume-title":"Handbook of Combinatorial Optimization","author":"N Katoh","year":"1998","unstructured":"Katoh, N., & Ibaraki, T. (1998). Resource allocation problems. In D.-Z. Du & P. M. Pardalos (Eds.), Handbook of Combinatorial Optimization (Vol. 2, pp. 159\u2013260). Dordrecht: Kluwer."},{"key":"782_CR8","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1007\/s10951-020-00653-8","volume":"23","author":"A Kononov","year":"2020","unstructured":"Kononov, A., & Kovalenko, Y. (2020). Approximation algorithms for energy-efficient scheduling of parallel jobs. Jouirnal of Scheduling, 23, 693\u2013709.","journal-title":"Jouirnal of Scheduling"},{"key":"782_CR9","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/978-3-030-49988-4_20","volume":"12095","author":"A Kononov","year":"2020","unstructured":"Kononov, A., & Kovalenko, Y. (2020). Makespan minimization for parallel jobs with energy constraint. Lecture Notes in Computer Science, 12095, 289\u2013300.","journal-title":"Lecture Notes in Computer Science"},{"key":"782_CR10","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1023\/A:1009817206440","volume":"3","author":"K Li","year":"1999","unstructured":"Li, K. (1999). Analysis of the list scheduling algorithm for precedence constrained parallel tasks. Journal of Combinatorial Optimization, 3, 73\u201388.","journal-title":"Journal of Combinatorial Optimization"},{"key":"782_CR11","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/s11227-010-0416-0","volume":"60","author":"K Li","year":"2012","unstructured":"Li, K. (2012). Energy efficient scheduling of parallel tasks on multiprocessor computers. Journal of Supercomputing, 60, 223\u2013247.","journal-title":"Journal of Supercomputing"},{"key":"782_CR12","doi-asserted-by":"publisher","first-page":"3412","DOI":"10.1109\/TPDS.2016.2537821","volume":"27","author":"RV Lopes","year":"2016","unstructured":"Lopes, R. V., & Menasce, D. (2016). A taxonomy of job scheduling on distributed computing systems. IEEE Transactions on Parallel and Distributed Systems, 27, 3412\u20133428.","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"key":"782_CR13","unstructured":"MAGMA. (2022). 2.5.4 Web page (Matrix Algebra for GPU and Multicore Architectures). Retrieved January 19 https:\/\/icl.cs.utk.edu\/projectsfiles\/magma\/doxygen\/index.html."},{"key":"782_CR14","doi-asserted-by":"publisher","first-page":"744","DOI":"10.1287\/opre.47.5.744","volume":"47","author":"ST McCormick","year":"1999","unstructured":"McCormick, S. T. (1999). Fast algorithms for parametric scheduling come from extensions to parametric maximum flow. Operations Research, 47, 744\u2013756.","journal-title":"Operations Research"},{"key":"782_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/mnsc.6.1.1","volume":"12","author":"R McNaughton","year":"1959","unstructured":"McNaughton, R. (1959). Scheduling with deadlines and loss functions. Management Science, 12, 1\u201312.","journal-title":"Management Science"},{"key":"782_CR16","unstructured":"PETSc. (2022). Web page (Portable Extensible Toolkit for Scientific Computation). Retrieved January 19 https:\/\/petsc.org\/release\/"},{"key":"782_CR17","unstructured":"ScaLAPACK. (2022). Web page (Scalable Linear Algebra PACKage). Retrieved January 7 http:\/\/www.netlib.org\/scalapack\/"},{"key":"782_CR18","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A. (2003). Combinatorial Optimization: Polyhedra and Efficiency. Berlin: Springer."},{"key":"782_CR19","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1023\/B:TIME.0000045315.61234.1e","volume":"28","author":"L Sha","year":"2004","unstructured":"Sha, L., Abdelzaher, T., \u00c5rz\u00e9n, K.-E., Cervin, A., Baker, T., Burns, A., Buttazzo, G., Caccamo, M., Lehoczky, J., & Mok, A. K. (2004). Real time scheduling theory: a historical perspective. Real-Time Systems, 28, 101\u2013155.","journal-title":"Real-Time Systems"},{"key":"782_CR20","doi-asserted-by":"publisher","first-page":"1643","DOI":"10.1016\/j.dam.2007.02.003","volume":"155","author":"D Shabtay","year":"2007","unstructured":"Shabtay, D., & Steiner, G. (2007). A survey of scheduling with controllable processing times. Discrete Applied Mathematics, 155, 1643\u20131666.","journal-title":"Discrete Applied Mathematics"},{"key":"782_CR21","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/s00453-007-9091-9","volume":"51","author":"NV Shakhlevich","year":"2008","unstructured":"Shakhlevich, N. V., & Strusevich, V. A. (2008). Preemptive scheduling on uniform parallel machines with controllable job processing times. Algorithmica, 51, 451\u2013473.","journal-title":"Algorithmica"},{"key":"782_CR22","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1142\/S0129054109006541","volume":"20","author":"NV Shakhlevich","year":"2009","unstructured":"Shakhlevich, N. V., Shioura, A., & Strusevich, V. A. (2009). Single machine scheduling with controllable processing times by submodular optimization. International Journal of Foundations of Computer Science, 20, 247\u2013269.","journal-title":"International Journal of Foundations of Computer Science"},{"key":"782_CR23","doi-asserted-by":"crossref","unstructured":"Shioura, A., Shakhlevich, N. V., & Strusevich, V. A. (2013). A submodular optimization approach to bicriteria scheduling problems with controllable processing times on parallel machines. SIAM Journal on Discrete Mathematics, 27, 186\u2013204.","DOI":"10.1137\/110843836"},{"key":"782_CR24","doi-asserted-by":"crossref","unstructured":"Shioura, A., Shakhlevich, N. V., & Strusevich, V. A. (2015). Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times. Mathematical Programming Series A, 153, 495\u2013534.","DOI":"10.1007\/s10107-014-0814-9"},{"key":"782_CR25","doi-asserted-by":"publisher","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. (2016). Application of submodular optimization to single machine scheduling with controllable processing times subject to release dates and deadlines. INFORMS Journal on Computing, 28, 148\u2013161.","journal-title":"INFORMS Journal on Computing"},{"key":"782_CR26","doi-asserted-by":"crossref","unstructured":"Shioura, A., Shakhlevich, N. V., & Strusevich, V. A. (2017). Machine speed scaling by adapting methods for convex optimization with submodular constraints. INFORMS Journal on Computing, 29, 724\u2013736.","DOI":"10.1287\/ijoc.2017.0758"},{"key":"782_CR27","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1016\/j.ejor.2017.08.034","volume":"266","author":"A Shioura","year":"2018","unstructured":"Shioura, A., Shakhlevich, N. V., & Strusevich, V. A. (2018). Preemptive models of scheduling with controllable processing times and of scheduling imprecise computation: A review of solution approaches. European Journal of Operational Research, 266, 795\u2013818.","journal-title":"European Journal of Operational Research"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-023-00782-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-023-00782-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-023-00782-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,7]],"date-time":"2024-04-07T12:05:09Z","timestamp":1712491509000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-023-00782-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,7]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,4]]}},"alternative-id":["782"],"URL":"https:\/\/doi.org\/10.1007\/s10951-023-00782-w","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,4,7]]},"assertion":[{"value":"21 February 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 April 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}