{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T08:03:05Z","timestamp":1761897785420,"version":"3.37.3"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,9,12]],"date-time":"2022-09-12T00:00:00Z","timestamp":1662940800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,9,12]],"date-time":"2022-09-12T00:00:00Z","timestamp":1662940800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100004731","name":"Natural Science Foundation of Zhejiang Province","doi-asserted-by":"publisher","award":["LY21A010014"],"award-info":[{"award-number":["LY21A010014"]}],"id":[{"id":"10.13039\/501100004731","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11771114","11971139"],"award-info":[{"award-number":["11771114","11971139"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2023,4]]},"DOI":"10.1007\/s11590-022-01928-z","type":"journal-article","created":{"date-parts":[[2022,9,12]],"date-time":"2022-09-12T15:02:37Z","timestamp":1662994957000},"page":"753-769","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["An improved algorithm for parallel machine scheduling under additional resource constraints"],"prefix":"10.1007","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2622-5158","authenticated-orcid":false,"given":"An","family":"Zhang","sequence":"first","affiliation":[]},{"given":"Tan","family":"Zhen","sequence":"additional","affiliation":[]},{"given":"Yong","family":"Chen","sequence":"additional","affiliation":[]},{"given":"Guangting","family":"Chen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,9,12]]},"reference":[{"issue":"2","key":"1928_CR1","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1137\/0204015","volume":"4","author":"MR Garey","year":"1975","unstructured":"Garey, M.R., Graham, R.L.: Bounds for multiprocessor scheduling with resource constraints. SIAM J. Comput. 4(2), 187\u2013200 (1975)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"1928_CR2","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1137\/0204035","volume":"4","author":"MR Garey","year":"1975","unstructured":"Garey, M.R., Johnson, D.S.: Complexity results for multiprocessor scheduling under resource constraints. SIAM J. Comput. 4(4), 397\u2013411 (1975)","journal-title":"SIAM J. Comput."},{"key":"1928_CR3","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/j.dam.2016.07.003","volume":"215","author":"E Hebrard","year":"2016","unstructured":"Hebrard, E., Huguet, M.-J., Jozefowiez, N., Maillard, A., Pralet, C., Verfaillie, G.: Approximation of the parallel machine scheduling problem with additional unit resources. Discret. Appl. Math. 215, 126\u2013135 (2016)","journal-title":"Discret. Appl. Math."},{"issue":"9","key":"1928_CR4","doi-asserted-by":"publisher","first-page":"2135","DOI":"10.1080\/01605682.2020.1772019","volume":"72","author":"Vitaly A Strusevich","year":"2021","unstructured":"Strusevich, Vitaly A.: Approximation algorithms for makespan minimization on identical parallel machines under resource constraints. J. Oper. Res. Soc. 72(9), 2135\u20132146 (2021)","journal-title":"J. Oper. Res. Soc."},{"key":"1928_CR5","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/j.cor.2019.01.005","volume":"105","author":"T Chung","year":"2019","unstructured":"Chung, T., Gupta, J.N.D., Zhao, H., Werner, F.: Minimizing the makespan on two identical parallel machines with mold constraints. Comput. Oper. Res. 105, 141\u2013155 (2019)","journal-title":"Comput. Oper. Res."},{"issue":"1","key":"1928_CR6","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0166-218X(83)90012-4","volume":"5","author":"J Blazewicz","year":"1983","unstructured":"Blazewicz, J., Lenstra, J.K., Kan, A.R.: Scheduling subject to resource constraints: classification and complexity. Discret. Appl. Math. 5(1), 11\u201324 (1983)","journal-title":"Discret. Appl. Math."},{"key":"1928_CR7","unstructured":"Blazewicz, J., Brauner, N., Finke, G.: Scheduling with discrete resource constraints. In Leung, J.Y.-T. (Ed.) Handbook of Scheduling: Algorithms, Models and Performance Analysis, pp. 23-1\u201323-18. CRC (2004)"},{"issue":"3","key":"1928_CR8","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1016\/j.ejor.2013.02.042","volume":"230","author":"EB Edis","year":"2013","unstructured":"Edis, E.B., Oguz, C., Ozkarahan, I.: Parallel machine scheduling with additional resources: notation, classification, models and solution methods. Eur. J. Oper. Res. 230(3), 449\u2013463 (2013)","journal-title":"Eur. J. Oper. Res."},{"key":"1928_CR9","doi-asserted-by":"crossref","unstructured":"Blazewicz, J., Ecker, K.H., Pesch, E., Schmidt, G., Sterna, M., Weglarz, J.: Scheduling under resource constraints. In: Handbook of Scheduling. From Theory to Practice, Chapter 13, pp. 475\u2013525. Springer (2019)","DOI":"10.1007\/978-3-319-99849-7_13"},{"key":"1928_CR10","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman (1979)"},{"key":"1928_CR11","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1016\/S0377-2217(02)00246-1","volume":"147","author":"H Kellerer","year":"2003","unstructured":"Kellerer, H., Strusevich, V.A.: Scheduling parallel dedicated machines under a single non-shared resource. Eur. J. Oper. Res. 147, 345\u2013367 (2003)","journal-title":"Eur. J. Oper. Res."},{"issue":"5","key":"1928_CR12","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1002\/nav.20292","volume":"55","author":"H Kellerer","year":"2008","unstructured":"Kellerer, H., Strusevich, V.A.: Scheduling parallel dedicated machines with the speeding-up resource. Nav. Res. Logist. 55(5), 377\u2013389 (2008)","journal-title":"Nav. Res. Logist."},{"key":"1928_CR13","doi-asserted-by":"publisher","first-page":"831","DOI":"10.1016\/j.ipl.2011.05.022","volume":"111","author":"H Xu","year":"2011","unstructured":"Xu, H., Chen, L., Ye, D., Zhang, G.: Scheduling on two identical machines with a speed-up resource. Inf. Process. Lett. 111, 831\u2013835 (2011)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"1928_CR14","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1016\/j.ejor.2020.12.045","volume":"293","author":"D Briskorn","year":"2021","unstructured":"Briskorn, D., Davari, M., Matuschke, J.: Single-machine scheduling with an external resource. Eur. J. Oper. Res. 293(2), 457\u2013468 (2021)","journal-title":"Eur. J. Oper. Res."},{"issue":"2","key":"1928_CR15","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/s10951-008-0089-1","volume":"12","author":"G Even","year":"2009","unstructured":"Even, G., Halld\u00f3rsson, M.M., Kaplan, L., Ron, D.: Scheduling with conflicts: online and offline algorithms. J. Sched. 12(2), 199\u2013224 (2009)","journal-title":"J. Sched."},{"issue":"2","key":"1928_CR16","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1016\/j.cor.2011.04.014","volume":"39","author":"M Bendraouche","year":"2012","unstructured":"Bendraouche, M., Boudhar, M.: Scheduling jobs on identical machines with agreement graph. Comput. Oper. Res. 39(2), 382\u2013390 (2012)","journal-title":"Comput. Oper. Res."},{"key":"1928_CR17","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/BF01202286","volume":"4","author":"E Petrank","year":"1994","unstructured":"Petrank, E.: The hardness of approximation: gap location. Comput. Complex. 4, 133\u2013157 (1994)","journal-title":"Comput. Complex."},{"key":"1928_CR18","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/j.tcs.2018.08.016","volume":"760","author":"G Dosa","year":"2019","unstructured":"Dosa, G., Kellerer, H., Tuza, Z.: Restricted assignment scheduling with resource constraints. Theoret. Comput. Sci. 760, 72\u201387 (2019)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"1928_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3302250","volume":"15","author":"K Jansen","year":"2019","unstructured":"Jansen, K., Maack, M., Rau, M.: Approximation schemes for machine scheduling with resource (in-)dependent processing times. ACM Trans. Algorithms 15(3), 1\u201328 (2019)","journal-title":"ACM Trans. Algorithms"},{"key":"1928_CR20","unstructured":"Jansen, K., Rau, M.: Closing the gap for single resource constraint scheduling. In: Proceedings of the 31st Annual European Symposium on Algorithms (ESA 2021) (to appear)"},{"issue":"3","key":"1928_CR21","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0166-218X(94)90009-4","volume":"55","author":"H Bodlaender","year":"1994","unstructured":"Bodlaender, H., Jansen, K., Woeginger, G.: Scheduling with incompatible jobs. Discret. Appl. Math. 55(3), 219\u2013232 (1994)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"1928_CR22","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/0304-3975(95)00057-4","volume":"148","author":"H Bodlaender","year":"1995","unstructured":"Bodlaender, H., Jansen, K.: Restrictions of graph partition problems. Part I. Theor. Comput. Sci. 148(1), 93\u2013109 (1995)","journal-title":"Theor. Comput. Sci."},{"key":"1928_CR23","unstructured":"Das, S., Wiese, A.: On Minimizing the makespan when some jobs cannot be assigned on the same machine. In: Proceedings of the 25th Annual European Symposium on Algorithms (ESA 2017), 87, 31: 1C31: 14 (2017)"},{"key":"1928_CR24","doi-asserted-by":"crossref","unstructured":"Grage, K., Jansen, K., Klein, K.-M.: An EPTAS for machine scheduling with bag-Constraints. In: Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2019), 135C144 (2019)","DOI":"10.1145\/3323165.3323192"},{"key":"1928_CR25","doi-asserted-by":"crossref","unstructured":"Page, D., Solis-Oba, R.: Makespan minimization on unrelated parallel machines with a few bags. Theor. Comput. Sci. 821, 34C44 (2020)","DOI":"10.1016\/j.tcs.2020.03.013"},{"key":"1928_CR26","doi-asserted-by":"crossref","unstructured":"Pikies, T., Turowski, K., Kubale, M.: Scheduling with complete multipartite incompatibility graph on prallel machines. In: Proceedings of the 31st International Conference on Automated Planning and Scheduling (ICAPS 2021), pp. 262\u2013270 (2021)","DOI":"10.1609\/icaps.v31i1.15970"},{"key":"1928_CR27","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/S0167-5060(08)70323-6","volume":"2","author":"EL Lawler","year":"1978","unstructured":"Lawler, E.L.: Sequencing jobs to minimize total weighted completion time subject to precedence constraints. Ann. Discret. Math. 2, 75\u201390 (1978)","journal-title":"Ann. Discret. Math."},{"issue":"4","key":"1928_CR28","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1137\/0203025","volume":"3","author":"DS Johnson","year":"1974","unstructured":"Johnson, D.S., Demers, A.J., Ullman, J.D., Garey, M.R., Graham, R.L.: Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput. 3(4), 299\u2013325 (1974)","journal-title":"SIAM J. Comput."},{"key":"1928_CR29","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.: Scheduling: Theory, Algorithms, and Systems, 5th edn. Springer, New York (2016)","edition":"5"}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-022-01928-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-022-01928-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-022-01928-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,8]],"date-time":"2023-03-08T12:17:23Z","timestamp":1678277843000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-022-01928-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,12]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,4]]}},"alternative-id":["1928"],"URL":"https:\/\/doi.org\/10.1007\/s11590-022-01928-z","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"type":"print","value":"1862-4472"},{"type":"electronic","value":"1862-4480"}],"subject":[],"published":{"date-parts":[[2022,9,12]]},"assertion":[{"value":"15 August 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 August 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 September 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}