{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T10:13:09Z","timestamp":1780481589043,"version":"3.54.1"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,8,8]],"date-time":"2025-08-08T00:00:00Z","timestamp":1754611200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,8,8]],"date-time":"2025-08-08T00:00:00Z","timestamp":1754611200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001774","name":"University of Sydney","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001774","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2026,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We study scheduling problems subject to supporting precedence, where each job requires a set of preparatory operations, referred to as supporting tasks. Motivated by diverse real-world applications featuring sequential and hierarchical processes, we introduce a nested structure for all supporting tasks. The objective function exclusively accounts for jobs, including total completion time and the weighted and unweighted number of late jobs. By leveraging the optimality properties unique to this structure, we develop efficient polynomial and pseudo-polynomial dynamic programming algorithms to solve single-agent problems in a single-machine setting, including an extension to the case allowing for job rejection. Then we consider two-agent problems with a constrained optimization form. These algorithms are adapted to tackle the additional complexity of the competing interests of two agents. The extension to the proportionate flow-shop problems highlights their inequivalence against counterpart problems in the single-machine setting in the presence of supporting precedence. We show that the problems are significantly more complex than their single-machine counterparts, namely that problems with due-date-based criteria are strongly\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\mathcal{N}\\mathcal{P}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>N<\/mml:mi>\n                            <mml:mi>P<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    -hard.\n                  <\/jats:p>","DOI":"10.1007\/s10951-025-00855-y","type":"journal-article","created":{"date-parts":[[2025,8,8]],"date-time":"2025-08-08T08:39:33Z","timestamp":1754642373000},"page":"245-260","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Single-machine and flow-shop scheduling with supporting tasks in a nested structure"],"prefix":"10.1007","volume":"29","author":[{"given":"Renjie","family":"Yu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2571-6676","authenticated-orcid":false,"given":"Daniel","family":"Oron","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bertrand M. T.","family":"Lin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,8,8]]},"reference":[{"issue":"3","key":"855_CR1","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1137\/0125042","volume":"25","author":"D Adolphson","year":"1973","unstructured":"Adolphson, D., & Hu, T. C. (1973). Optimal linear ordering. SIAM Journal on Applied Mathematics, 25(3), 403\u2013423.","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"855_CR2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41880-8","volume-title":"Multiagent scheduling: Models and algorithms","author":"A Agnetis","year":"2014","unstructured":"Agnetis, A., Billaut, J.-C., Pacciarelli, D., Soukhal, A., & Gawiejnowicz, S. (2014). Multiagent scheduling: Models and algorithms (1st ed.). Springer.","edition":"1"},{"issue":"2","key":"855_CR3","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1287\/opre.1030.0092","volume":"52","author":"A Agnetis","year":"2004","unstructured":"Agnetis, A., Mirchandani, P. B., Pacciarelli, D., & Pacifici, A. (2004). Scheduling problems with two competing agents. Operations Research, 52(2), 229\u2013242.","journal-title":"Operations Research"},{"issue":"3","key":"855_CR4","doi-asserted-by":"publisher","first-page":"904","DOI":"10.1016\/j.eswa.2013.08.021","volume":"41","author":"R Bart\u00e1k","year":"2014","unstructured":"Bart\u00e1k, R., & Rovensk\u1ef3, V. (2014). On verification of nested workflows with extra constraints: From theory to practice. Expert Systems with Applications, 41(3), 904\u2013918.","journal-title":"Expert Systems with Applications"},{"issue":"1","key":"855_CR5","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1137\/S0895480196300522","volume":"13","author":"Y Bartal","year":"2000","unstructured":"Bartal, Y., Leonardi, S., Marchetti-Spaccamela, A., Sgall, J., & Stougie, L. (2000). Multiprocessor scheduling with rejection. SIAM Journal on Discrete Mathematics, 13(1), 64\u201378.","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"6","key":"855_CR6","doi-asserted-by":"publisher","first-page":"1197","DOI":"10.1016\/j.cor.2010.09.018","volume":"39","author":"B Cesaret","year":"2012","unstructured":"Cesaret, B., O\u011fuz, C., & Salman, F. S. (2012). A tabu search algorithm for order acceptance and scheduling. Computers & Operations Research, 39(6), 1197\u20131205.","journal-title":"Computers & Operations Research"},{"issue":"22","key":"855_CR7","doi-asserted-by":"publisher","first-page":"4705","DOI":"10.3390\/math11224705","volume":"11","author":"M-T Chao","year":"2023","unstructured":"Chao, M.-T., & Lin, B. M. (2023). Scheduling of software test to minimize the total completion time. Mathematics, 11(22), 4705.","journal-title":"Mathematics"},{"issue":"6","key":"855_CR8","doi-asserted-by":"publisher","first-page":"632","DOI":"10.1016\/j.orl.2023.10.005","volume":"51","author":"I Doron-Arad","year":"2023","unstructured":"Doron-Arad, I., Kulik, A., & Shachnai, H. (2023). An fptas for budgeted laminar matroid independent set. Operations Research Letters, 51(6), 632\u2013637.","journal-title":"Operations Research Letters"},{"key":"855_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.peva.2017.07.001","volume":"116","author":"K Gardner","year":"2017","unstructured":"Gardner, K., Harchol-Balter, M., Hyyti\u00e4, E., & Righter, R. (2017). Scheduling for efficiency and fairness in systems with redundancy. Performance Evaluation, 116, 1\u201325.","journal-title":"Performance Evaluation"},{"key":"855_CR10","doi-asserted-by":"publisher","first-page":"109317","DOI":"10.1016\/j.cie.2023.109317","volume":"181","author":"X-N Geng","year":"2023","unstructured":"Geng, X.-N., Sun, X., Wang, J., & Pan, L. (2023). Scheduling on proportionate flow shop with job rejection and common due date assignment. Computers & Industrial Engineering, 181, 109317.","journal-title":"Computers & Industrial Engineering"},{"key":"855_CR11","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"RL Graham","year":"1979","unstructured":"Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. R. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5, 287\u2013326.","journal-title":"Annals of Discrete Mathematics"},{"issue":"3","key":"855_CR12","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/s10951-021-00687-6","volume":"24","author":"F Happach","year":"2021","unstructured":"Happach, F. (2021). Makespan minimization with or-precedence constraints. Journal of Scheduling, 24(3), 319\u2013328.","journal-title":"Journal of Scheduling"},{"key":"855_CR13","doi-asserted-by":"crossref","unstructured":"Karp, R. (1972). Reducibility among combinatorial problems. In Miller, R. & Thatcher, J. (Eds.), Complexity of computer computations (pp. 85\u2013103).","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"3","key":"855_CR14","doi-asserted-by":"publisher","first-page":"698","DOI":"10.1016\/j.cor.2007.10.025","volume":"36","author":"E-S Kim","year":"2009","unstructured":"Kim, E.-S., Sung, C.-S., & Lee, I.-S. (2009). Scheduling of parallel machines to minimize total completion time subject to s-precedence constraints. Computers & Operations Research, 36(3), 698\u2013710.","journal-title":"Computers & Operations Research"},{"key":"855_CR15","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/j.disopt.2015.05.001","volume":"17","author":"AV Kononov","year":"2015","unstructured":"Kononov, A. V., Lin, B. M., & Fang, K.-T. (2015). Single-machine scheduling with supporting tasks. Discrete Optimization, 17, 69\u201379.","journal-title":"Discrete Optimization"},{"key":"855_CR16","doi-asserted-by":"crossref","unstructured":"Lawler, E. L. (1978). Sequencing jobs to minimize total weighted completion time subject to precedence constraints. In Annals of discrete mathematics (Vol.\u00a02, pp. 75\u201390). Elsevier.","DOI":"10.1016\/S0167-5060(08)70323-6"},{"issue":"1","key":"855_CR17","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1287\/mnsc.16.1.77","volume":"16","author":"EL Lawler","year":"1969","unstructured":"Lawler, E. L., & Moore, J. M. (1969). A functional equation and its application to resource allocation and sequencing problems. Management Science, 16(1), 77\u201384.","journal-title":"Management Science"},{"issue":"4","key":"855_CR18","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/s40314-024-02753-z","volume":"43","author":"M-H Li","year":"2024","unstructured":"Li, M.-H., Lv, D.-Y., Lv, Z.-G., Zhang, L.-H., & Wang, J.-B. (2024). A two-agent resource allocation scheduling problem with slack due-date assignment and general deterioration function. Computational and Applied Mathematics, 43(4), 229.","journal-title":"Computational and Applied Mathematics"},{"issue":"6","key":"855_CR19","doi-asserted-by":"publisher","first-page":"2311","DOI":"10.1007\/s11590-020-01670-4","volume":"15","author":"D-Y Lv","year":"2021","unstructured":"Lv, D.-Y., & Wang, J.-B. (2021). Study on proportionate flowshop scheduling with due-date assignment and position-dependent weights. Optimization Letters, 15(6), 2311\u20132319.","journal-title":"Optimization Letters"},{"key":"855_CR20","first-page":"1","volume":"8","author":"G Mosheiov","year":"2023","unstructured":"Mosheiov, G., & Sarig, A. (2023). A common due-date assignment problem with job rejection on parallel uniform machines. International Journal of Production Research, 8, 1\u201310.","journal-title":"International Journal of Production Research"},{"key":"855_CR21","doi-asserted-by":"publisher","first-page":"102313","DOI":"10.1016\/j.omega.2020.102313","volume":"102","author":"D Oron","year":"2021","unstructured":"Oron, D. (2021). Two-agent scheduling problems under rejection budget constraints. Omega, 102, 102313.","journal-title":"Omega"},{"issue":"3","key":"855_CR22","doi-asserted-by":"publisher","first-page":"1017","DOI":"10.1016\/j.ejor.2023.04.019","volume":"310","author":"J Ou","year":"2023","unstructured":"Ou, J., Lu, L., & Zhong, X. (2023). Parallel-batch scheduling with rejection: Structural properties and approximation algorithms. European Journal of Operational Research, 310(3), 1017\u20131032.","journal-title":"European Journal of Operational Research"},{"issue":"7","key":"855_CR23","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1002\/nav.21666","volume":"62","author":"S Panwalkar","year":"2015","unstructured":"Panwalkar, S., & Koulamas, C. (2015). On equivalence between the proportionate flow shop and single-machine scheduling problems. Naval Research Logistics (NRL), 62(7), 595\u2013603.","journal-title":"Naval Research Logistics (NRL)"},{"issue":"1","key":"855_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2013.09.017","volume":"235","author":"P Perez-Gonzalez","year":"2014","unstructured":"Perez-Gonzalez, P., & Framinan, J. M. (2014). A common framework and taxonomy for multicriteria scheduling problems with interfering and competing jobs: Multi-agent scheduling problems. European Journal of Operational Research, 235(1), 1\u201316.","journal-title":"European Journal of Operational Research"},{"key":"855_CR25","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-26580-3","volume-title":"Scheduling: Theory, algorithms, and systems","author":"ML Pinedo","year":"2016","unstructured":"Pinedo, M. L. (2016). Scheduling: Theory, algorithms, and systems (5th ed.). Springer. https:\/\/doi.org\/10.1007\/978-3-319-26580-3","edition":"5"},{"issue":"1","key":"855_CR26","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s10951-017-0519-z","volume":"21","author":"D Prot","year":"2018","unstructured":"Prot, D., & Bellenguez-Morineau, O. (2018). A survey on how the structure of precedence constraints may change the complexity class of scheduling problems. Journal of Scheduling, 21(1), 3\u201316.","journal-title":"Journal of Scheduling"},{"key":"855_CR27","doi-asserted-by":"publisher","DOI":"10.1201\/9781315367965","volume-title":"Aerospace manufacturing processes","author":"PK Saha","year":"2016","unstructured":"Saha, P. K. (2016). Aerospace manufacturing processes. CRC Press."},{"key":"855_CR28","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s10951-012-0303-z","volume":"16","author":"D Shabtay","year":"2013","unstructured":"Shabtay, D., Gaspar, N., & Kaspi, M. (2013). A survey on offline scheduling with rejection. Journal of Scheduling, 16, 3\u201328.","journal-title":"Journal of Scheduling"},{"issue":"5","key":"855_CR29","doi-asserted-by":"publisher","first-page":"752","DOI":"10.1057\/jors.2015.95","volume":"67","author":"D Shabtay","year":"2016","unstructured":"Shabtay, D., & Oron, D. (2016). Proportionate flow-shop scheduling with rejection. Journal of the Operational Research Society, 67(5), 752\u2013769.","journal-title":"Journal of the Operational Research Society"},{"issue":"3","key":"855_CR30","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1002\/(SICI)1099-1425(1998100)1:3<157::AID-JOS12>3.0.CO;2-Y","volume":"1","author":"N Shakhlevich","year":"1998","unstructured":"Shakhlevich, N., Hoogeveen, H., & Pinedo, M. (1998). Minimizing total weighted completion time in a proportionate flow shop. Journal of Scheduling, 1(3), 157\u2013168.","journal-title":"Journal of Scheduling"},{"key":"855_CR31","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/s10479-020-03653-1","volume":"292","author":"X Sun","year":"2020","unstructured":"Sun, X., Geng, X.-N., & Liu, T. (2020). Due-window assignment scheduling in the proportionate flow shop setting. Annals of Operations Research, 292, 113\u2013131.","journal-title":"Annals of Operations Research"},{"issue":"12","key":"855_CR32","doi-asserted-by":"publisher","first-page":"2674","DOI":"10.1080\/01605682.2020.1806746","volume":"72","author":"X Sun","year":"2021","unstructured":"Sun, X., Geng, X.-N., & Liu, F. (2021). Flow shop scheduling with general position weighted learning effects to minimize total weighted completion time. Journal of the Operational Research Society, 72(12), 2674\u20132689.","journal-title":"Journal of the Operational Research Society"},{"issue":"3","key":"855_CR33","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1080\/0305215X.2021.1876041","volume":"54","author":"J-B Wang","year":"2022","unstructured":"Wang, J.-B., Xu, J.-X., Guo, F., & Liu, M. (2022). Single-machine scheduling problems with job rejection, deterioration effects and past-sequence-dependent setup times. Engineering Optimization, 54(3), 471\u2013486.","journal-title":"Engineering Optimization"},{"issue":"2","key":"855_CR34","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1016\/j.ejor.2019.09.041","volume":"282","author":"A Zhang","year":"2020","unstructured":"Zhang, A., Qi, X., & Li, G. (2020). Machine scheduling with soft precedence constraints. European Journal of Operational Research, 282(2), 491\u2013505.","journal-title":"European Journal of Operational Research"},{"key":"855_CR35","doi-asserted-by":"publisher","first-page":"106780","DOI":"10.1016\/j.cor.2024.106780","volume":"170","author":"Y Zinder","year":"2024","unstructured":"Zinder, Y., Berli\u0144ska, J., & Lin, B. M. (2024). Scheduling jobs with shared additional operations on parallel identical machines. Computers & Operations Research, 170, 106780.","journal-title":"Computers & Operations Research"},{"issue":"4","key":"855_CR36","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1108\/14714170910995921","volume":"9","author":"O Zwikael","year":"2009","unstructured":"Zwikael, O. (2009). Critical planning processes in construction projects. Construction Innovation, 9(4), 372\u2013387.","journal-title":"Construction Innovation"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-025-00855-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-025-00855-y","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-025-00855-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T09:23:41Z","timestamp":1780478621000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-025-00855-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,8]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["855"],"URL":"https:\/\/doi.org\/10.1007\/s10951-025-00855-y","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,8,8]]},"assertion":[{"value":"4 July 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 August 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}