{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,20]],"date-time":"2026-06-20T01:32:27Z","timestamp":1781919147280,"version":"3.54.5"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2022,9,22]],"date-time":"2022-09-22T00:00:00Z","timestamp":1663804800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,9,22]],"date-time":"2022-09-22T00:00:00Z","timestamp":1663804800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003065","name":"University of Vienna","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003065","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This paper addresses the problem of scheduling chain-like structures of tasks on a single multiprocessor resource. In fact, sub-tasks of unit-time length and predefined size are aggregated to composite tasks that have to be scheduled without preemption, but subject to flexibility concerning resource allocation. This setting most closely resembles the problem of malleable task scheduling, with sub-tasks being the smallest atomic unit of allocation. The specific type of malleability is realized using precedence constraints with minimum and maximum time lags. A bin packing model is established for this scheduling problem and a corresponding, dedicated branch-and-bound algorithm is devised, alongside problem-specific bound tightening, symmetry breaking and dominance concepts. The efficacy of the solution approach is demonstrated based on extensive computational experiments, including randomized instances, adapted benchmark instances from the literature, and a small real-world data set. In comparison to mixed-integer and constraint programming formulations, the new method is able to achieve a considerably higher percentage of optimal solutions at computation times that are up to orders of magnitude smaller.<\/jats:p>","DOI":"10.1007\/s10951-022-00750-w","type":"journal-article","created":{"date-parts":[[2022,9,22]],"date-time":"2022-09-22T21:02:36Z","timestamp":1663880556000},"page":"675-704","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Packing-based branch-and-bound for discrete malleable task scheduling"],"prefix":"10.1007","volume":"25","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4086-229X","authenticated-orcid":false,"given":"Roland","family":"Braune","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,9,22]]},"reference":[{"key":"750_CR1","doi-asserted-by":"publisher","unstructured":"Artigues, C., & Lopez, P. (2015). Energetic reasoning for energy-constrained scheduling with a continuous resource. Journal of Scheduling, 18(3), 225\u2013241. https:\/\/doi.org\/10.1007\/s10951-014-0404-y","DOI":"10.1007\/s10951-014-0404-y"},{"issue":"1","key":"750_CR2","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.ijpe.2010.09.030","volume":"143","author":"C Artigues","year":"2013","unstructured":"Artigues, C., Lopez, P., & Ha\u00eft, A. (2013). The energy scheduling problem: Industrial case-study and constraint propagation techniques. International Journal of Production Economics, 143(1), 13\u201323.","journal-title":"International Journal of Production Economics"},{"key":"750_CR3","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1023\/A:1018995000688","volume":"92","author":"P Baptiste","year":"1999","unstructured":"Baptiste, P., Le Pape, C., & Nuijten, W. (1999). Satisfiability tests and time-bound adjustments for cumulative scheduling problems. Annals of Operations Research, 92, 305\u2013333. https:\/\/doi.org\/10.1023\/A:1018995000688","journal-title":"Annals of Operations Research"},{"key":"750_CR4","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0377-2217(96)00126-9","volume":"94","author":"J Blazewicz","year":"1996","unstructured":"Blazewicz, J., & Liu, Z. (1996). Scheduling multiprocessor tasks with chain constraints. European Journal of Operational Research, 94, 231\u2013241.","journal-title":"European Journal of Operational Research"},{"issue":"5","key":"750_CR5","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1109\/TC.1986.1676781","volume":"35","author":"J Blazewicz","year":"1986","unstructured":"Blazewicz, J., Drabowski, M., & Weglarz, J. (1986). Scheduling multiprocessor tasks to minimize schedule length. IEEE Transactions on Computers C, 35(5), 389\u2013393.","journal-title":"IEEE Transactions on Computers C"},{"issue":"1\u20134","key":"750_CR6","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1023\/B:ANOR.0000030682.25673.c0","volume":"129","author":"J Blazewicz","year":"2004","unstructured":"Blazewicz, J., Machowiak, M., Weglarz, J., Kovalyov, M., & Trystram, D. (2004). Scheduling malleable tasks on parallel processors to minimize the makespan. Annals of Operations Research, 129(1\u20134), 65\u201380. https:\/\/doi.org\/10.1023\/B:ANOR.0000030682.25673.c0","journal-title":"Annals of Operations Research"},{"issue":"4","key":"750_CR7","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1109\/TC.2006.58","volume":"55","author":"J Blazewicz","year":"2006","unstructured":"Blazewicz, J., Kovalyov, M., Machowiak, M., Trystram, D., & Weglarz, J. (2006). Preemptable malleable task scheduling problem. IEEE Transactions on Computers, 55(4), 486\u2013490.","journal-title":"IEEE Transactions on Computers"},{"key":"750_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0377-2217(95)00362-2","volume":"33","author":"JW Blazewicz","year":"1996","unstructured":"Blazewicz, J. W., Domschke, W., & Pesch, E. (1996). The job shop scheduling problem: Conventional and new solution techniques. European Journal of Operational Research, 33, 1\u201333.","journal-title":"European Journal of Operational Research"},{"key":"750_CR9","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/j.cor.2015.11.009","volume":"69","author":"F Brandao","year":"2016","unstructured":"Brandao, F., & Pedroso, J. P. (2016). Bin packing and related problems: General arc-flow formulation with graph compression. Computers & Operations Research, 69, 56\u201367.","journal-title":"Computers & Operations Research"},{"issue":"1","key":"750_CR10","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/j.ejor.2018.10.004","volume":"274","author":"R Braune","year":"2019","unstructured":"Braune, R. (2019). Lower bounds for a bin packing problem with linear usage cost. European Journal of Operational Research, 274(1), 49\u201364. https:\/\/doi.org\/10.1016\/j.ejor.2018.10.004","journal-title":"European Journal of Operational Research"},{"key":"750_CR11","doi-asserted-by":"crossref","unstructured":"Cambazard, H., Mehta, D., O\u2019Sullivan, B., & Simonis, H. (2013). Bin packing with linear usage costs - an application to energy management in data centres. Lecture Notes in Computer Science. In C. Schulte (Ed.), Principles and practice of constraint programming, (Vol. 8124, pp. 47\u201362). Springer.","DOI":"10.1007\/978-3-642-40627-0_7"},{"key":"750_CR12","unstructured":"Caramia, M., & Drozdowski, M. (2006). Scheduling malleable tasks for mean flow time criterion. In: Abstracts of the 10th international workshop on project management and scheduling, (pp. 106\u2013109)"},{"issue":"1","key":"750_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0207001","volume":"7","author":"EG Coffman Jr","year":"1978","unstructured":"Coffman, E. G., Jr., Garey, M. R., & Johnson, D. S. (1978). An application of bin-packing to multiprocessor scheduling. SIAM Journal on Computing, 7(1), 1\u201317. https:\/\/doi.org\/10.1137\/0207001","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"750_CR14","doi-asserted-by":"publisher","first-page":"1491","DOI":"10.1287\/opre.1120.1109","volume":"60","author":"M Dell\u2019Amico","year":"2012","unstructured":"Dell\u2019Amico, M., Diaz, J. C. D., & Iori, M. (2012). The bin packing problem with precedence constraints. Operations Research, 60(6), 1491\u20131504.","journal-title":"Operations Research"},{"issue":"1","key":"750_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2016.04.030","volume":"255","author":"M Delorme","year":"2016","unstructured":"Delorme, M., Iori, M., & Martello, S. (2016). Bin packing and cutting stock problems: Mathematical models and exact algorithms. European Journal of Operational Research, 255(1), 1\u201320.","journal-title":"European Journal of Operational Research"},{"key":"750_CR16","series-title":"Computer Communications and Networks","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. Computer Communications and NetworksSpringer Verlag."},{"issue":"6","key":"750_CR17","doi-asserted-by":"publisher","first-page":"571","DOI":"10.1016\/S0305-0548(99)00048-9","volume":"27","author":"M Drozdowski","year":"2000","unstructured":"Drozdowski, M., & Dell\u2019Olmo, P. (2000). Scheduling multiprocessor tasks for mean flow time criterion. Computers & Operations Research, 27(6), 571\u2013585.","journal-title":"Computers & Operations Research"},{"key":"750_CR18","doi-asserted-by":"crossref","unstructured":"Fukunaga, A. S., & Korf, R. E. (2007). Bin completion algorithms for multicontainer packing, knapsack, and covering problems. Journal of Artificial Intelligence Research, 28(1), 393\u2013429.http:\/\/dl.acm.org\/citation.cfm?id=1622591.1622602","DOI":"10.1613\/jair.2106"},{"key":"750_CR19","unstructured":"Gabay, M. (2014). High-multiplicity scheduling and packing problems. PhD thesis, Universit\u00e9 Joseph Fourier"},{"issue":"3","key":"750_CR20","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/0097-3165(76)90001-7","volume":"21","author":"M Garey","year":"1976","unstructured":"Garey, M., Graham, R., Johnson, D., & Yao, A. C. (1976). Resource constrained scheduling as generalized bin packing. Journal of Combinatorial Theory, Series A, 21(3), 257\u2013298. https:\/\/doi.org\/10.1016\/0097-3165(76)90001-7","journal-title":"Journal of Combinatorial Theory, Series A"},{"key":"750_CR21","doi-asserted-by":"crossref","unstructured":"Goemans, MX., & Rothvo\u00df, T. (2014). Polynomiality for bin packing with a constant number of item types. In Proceedings of the twenty-fifth annual ACM-SIAM Symposium on discrete algorithms, society for industrial and applied mathematics, (pp. 830-839) USA, SODA \u201914,","DOI":"10.1137\/1.9781611973402.61"},{"key":"750_CR22","first-page":"187","volume":"5","author":"RL Graham","year":"1979","unstructured":"Graham, R. L., Lawler, E. L., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Operations Research, 5, 187\u2013326.","journal-title":"Annals of Operations Research"},{"issue":"4","key":"750_CR23","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/s10951-013-0341-1","volume":"18","author":"Y Hendel","year":"2015","unstructured":"Hendel, Y., Kubiak, W., & Trystram, D. (2015). Scheduling semi-malleable jobs to minimize mean flow time. Journal of Scheduling, 18(4), 335\u2013343. https:\/\/doi.org\/10.1007\/s10951-013-0341-1","journal-title":"Journal of Scheduling"},{"key":"750_CR24","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1007\/978-3-319-57586-5_2","volume-title":"Algorithms and Complexity","author":"K Jansen","year":"2017","unstructured":"Jansen, K. (2017). New algorithmic results for bin packing and scheduling. In D. Fotakis, A. Pagourtzis, & V. T. Paschos (Eds.), Algorithms and Complexity (pp. 10\u201315). Springer International Publishing."},{"key":"750_CR25","unstructured":"Jouglet, A. (2002). The one machine total cost sequencing problem. PhD thesis, Universit\u00e9 de Technologie de Compi\u00e8gne, Compi\u00e8gne, France"},{"key":"750_CR26","unstructured":"Jouglet, A., Baptiste, P., & Carlier, J. (2004). Branch-and-bound algorithms for total weighted tardiness. In J.T. Leung (ed) Handbook of Scheduling, CRC Press, chap\u00a013"},{"key":"750_CR27","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/s10107-004-0551-6","volume":"103","author":"T Kis","year":"2005","unstructured":"Kis, T. (2005). A branch-and-cut algorithm for scheduling of projects with variable-intensity activities. Mathematical Programming Series A, 103, 515\u2013539.","journal-title":"Mathematical Programming Series A"},{"issue":"4","key":"750_CR28","doi-asserted-by":"publisher","first-page":"616","DOI":"10.1287\/opre.39.4.616","volume":"39","author":"M Labb\u00e9","year":"1991","unstructured":"Labb\u00e9, M., Laporte, G., & Mercure, H. (1991). Capacitated vehicle routing on trees. Operations Research, 39(4), 616-622.","journal-title":"Operations Research"},{"issue":"1","key":"750_CR29","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1287\/opre.29.1.189","volume":"29","author":"EL Lloyd","year":"1981","unstructured":"Lloyd, E. L. (1981). Concurrent task systems. Operations Research, 29(1), 189\u2013201.","journal-title":"Operations Research"},{"key":"750_CR30","volume-title":"Knapsack problems: algorithms and computer implementations","author":"S Martello","year":"1990","unstructured":"Martello, S., & Toth, P. (1990). Knapsack problems: algorithms and computer implementations. New York: John Wiley and Sons."},{"key":"750_CR31","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.disopt.2016.01.005","volume":"19","author":"DR Morrison","year":"2016","unstructured":"Morrison, D. R., Jacobson, S. H., Sauppe, J. J., & Sewell, E. C. (2016). Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning. Discrete Optimization, 19, 79\u2013102. https:\/\/doi.org\/10.1016\/j.disopt.2016.01.005","journal-title":"Discrete Optimization"},{"issue":"3","key":"750_CR32","doi-asserted-by":"publisher","first-page":"794","DOI":"10.1016\/j.ejor.2015.10.048","volume":"250","author":"J Pereira","year":"2016","unstructured":"Pereira, J. (2016). Procedures for the bin packing problem with precedence constraints. European Journal of Operational Research, 250(3), 794\u2013806. https:\/\/doi.org\/10.1016\/j.ejor.2015.10.048","journal-title":"European Journal of Operational Research"},{"key":"750_CR33","doi-asserted-by":"publisher","unstructured":"Sadykov, R. (2012). A dominant class of schedules for malleable jobs in the problem to minimize the total weighted completion time. Computers & Operations Research, 39(6), 1265\u20131270. https:\/\/doi.org\/10.1016\/j.cor.2011.02.023, special Issue on Scheduling in Manufacturing Systems","DOI":"10.1016\/j.cor.2011.02.023"},{"issue":"02","key":"750_CR34","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1142\/S0218213094000108","volume":"03","author":"T Schiex","year":"1994","unstructured":"Schiex, T., & Verfaillie, G. (1994). Nogood recording for static and dynamic constraint satisfaction problems. International Journal on Artificial Intelligence Tools, 03(02), 187\u2013207. https:\/\/doi.org\/10.1142\/S0218213094000108","journal-title":"International Journal on Artificial Intelligence Tools"},{"issue":"7","key":"750_CR35","doi-asserted-by":"publisher","first-page":"627","DOI":"10.1016\/S0305-0548(96)00082-2","volume":"24","author":"A Scholl","year":"1997","unstructured":"Scholl, A., Klein, R., & J\u00fcrgens, C. (1997). Bison: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem. Computers & Operations Research, 24(7), 627\u2013645. https:\/\/doi.org\/10.1016\/S0305-0548(96)00082-2","journal-title":"Computers & Operations Research"},{"issue":"3","key":"750_CR36","doi-asserted-by":"publisher","first-page":"688","DOI":"10.1016\/j.ejor.2009.01.049","volume":"200","author":"A Scholl","year":"2010","unstructured":"Scholl, A., Fliedner, M., & Boysen, N. (2010). Absalom: Balancing assembly lines with assignment restrictions. European Journal of Operational Research, 200(3), 688\u2013701. https:\/\/doi.org\/10.1016\/j.ejor.2009.01.049","journal-title":"European Journal of Operational Research"},{"issue":"3","key":"750_CR37","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/s10951-012-0285-x","volume":"16","author":"A Schutt","year":"2013","unstructured":"Schutt, A., Feydy, T., Stuckey, P., & Wallace, M. (2013). Solving RCPSP\/max by lazy clause generation. Journal of Scheduling, 16(3), 273\u2013289. https:\/\/doi.org\/10.1007\/s10951-012-0285-x","journal-title":"Journal of Scheduling"},{"key":"750_CR38","doi-asserted-by":"publisher","first-page":"648","DOI":"10.1007\/978-3-540-30201-8_47","volume-title":"Principles and practice of constraint programming - CP 2004","author":"P Shaw","year":"2004","unstructured":"Shaw, P. (2004). A constraint for bin packing. In M. Wallace (Ed.), Principles and practice of constraint programming - CP 2004 (pp. 648\u2013662). Springer."},{"issue":"6","key":"750_CR39","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1007\/s10951-018-0563-3","volume":"21","author":"K Wang","year":"2018","unstructured":"Wang, K., Chau, V., & Li, M. (2018). Scheduling fully parallel jobs. Journal of Scheduling, 21(6), 619\u2013631. https:\/\/doi.org\/10.1007\/s10951-018-0563-3","journal-title":"Journal of Scheduling"},{"key":"750_CR40","doi-asserted-by":"publisher","unstructured":"Zhang, Q., Wu, W., & Li, M. (2013). Minimizing the total weighted completion time of fully parallel jobs with integer parallel units. Theoretical Computer Science 507, 34\u201340, https:\/\/doi.org\/10.1016\/j.tcs.2013.02.017, combinatorial Optimization and Applications","DOI":"10.1016\/j.tcs.2013.02.017"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-022-00750-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-022-00750-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-022-00750-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,31]],"date-time":"2022-10-31T18:30:21Z","timestamp":1667241021000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-022-00750-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,22]]},"references-count":40,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["750"],"URL":"https:\/\/doi.org\/10.1007\/s10951-022-00750-w","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,9,22]]},"assertion":[{"value":"25 July 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 September 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}