{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:38:07Z","timestamp":1759639087453,"version":"3.40.3"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030046507"},{"type":"electronic","value":"9783030046514"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-030-04651-4_23","type":"book-chapter","created":{"date-parts":[[2018,11,15]],"date-time":"2018-11-15T19:56:50Z","timestamp":1542311810000},"page":"341-356","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Makespan Minimization on Unrelated Parallel Machines with Simple Job-Intersection Structure and Bounded Job Assignments"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6317-7431","authenticated-orcid":false,"given":"Daniel R.","family":"Page","sequence":"first","affiliation":[]},{"given":"Roberto","family":"Solis-Oba","sequence":"additional","affiliation":[]},{"given":"Marten","family":"Maack","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,11,16]]},"reference":[{"issue":"3","key":"23_CR1","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/BF02523189","volume":"17","author":"N Alon","year":"1997","unstructured":"Alon, N., Yuster, R., Zwick, U.: Finding and counting given length cycles. Algorithmica 17(3), 209\u2013223 (1997)","journal-title":"Algorithmica"},{"issue":"1","key":"23_CR2","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1007\/s10878-009-9276-z","volume":"22","author":"Y Asahiro","year":"2011","unstructured":"Asahiro, Y., Jansson, J., Miyano, E., Ono, H., Zenmyo, K.: Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree. J. Comb. Optim. 22(1), 78\u201396 (2011)","journal-title":"J. Comb. Optim."},{"issue":"7","key":"23_CR3","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1016\/j.dam.2010.11.003","volume":"159","author":"Y Asahiro","year":"2011","unstructured":"Asahiro, Y., Miyano, E., Ono, H.: Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree. Discret. Appl. Math. 159(7), 498\u2013508 (2011)","journal-title":"Discret. Appl. Math."},{"key":"23_CR4","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey","author":"A Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V., Spinrad, J.: Graph Classes: A Survey. SIAM, Philadelphia (1999)"},{"key":"23_CR5","doi-asserted-by":"crossref","unstructured":"Chakrabarty, D., Khanna, S., Li, S.: On (1, $$\\varepsilon $$)-restricted assignment makespan minimization. In: 26th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1087\u20131101 (2015)","DOI":"10.1137\/1.9781611973730.73"},{"issue":"19","key":"23_CR6","doi-asserted-by":"publisher","first-page":"4211","DOI":"10.1080\/00207540410001711863","volume":"42","author":"PY Chang","year":"2004","unstructured":"Chang, P.Y., Damodaran, P., Melouk, S.: Minimizing makespan on parallel batch processing machines. Int. J. Prod. Res. 42(19), 4211\u20134220 (2004)","journal-title":"Int. J. Prod. Res."},{"key":"23_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1007\/978-3-319-48749-6_44","volume-title":"Combinatorial Optimization and Applications","author":"L Chen","year":"2016","unstructured":"Chen, L., Jansen, K., Luo, W., Zhang, G.: An efficient PTAS for parallel machine scheduling with capacity constraints. In: Chan, T.-H.H., Li, M., Wang, L. (eds.) COCOA 2016. LNCS, vol. 10043, pp. 608\u2013623. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-48749-6_44"},{"issue":"1","key":"23_CR8","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1007\/s00453-012-9668-9","volume":"68","author":"T Ebenlendr","year":"2014","unstructured":"Ebenlendr, T., Kr\u010d\u00e1l, M., Sgall, J.: Graph balancing: a special case of scheduling unrelated parallel machines. Algorithmica 68(1), 62\u201380 (2014)","journal-title":"Algorithmica"},{"key":"23_CR9","unstructured":"Ebenlendr, T., Kr\u010d\u00e1l, M., Sgall, J.: Graph balancing: a special case of scheduling unrelated parallel machines. In: 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 483\u2013490 (2008)"},{"issue":"1","key":"23_CR10","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.tcs.2007.02.056","volume":"380","author":"M Gairing","year":"2007","unstructured":"Gairing, M., Monien, B., Woclaw, A.: A faster combinatorial approximation algorithm for scheduling unrelated parallel machines. Theor. Comput. Sci. 380(1), 87\u201399 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"23_CR11","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1002\/nav.20202","volume":"54","author":"C Glass","year":"2007","unstructured":"Glass, C., Kellerer, H.: Parallel machine scheduling with job assignment restrictions. Nav. Res. Logist. (NRL) 54(3), 250\u2013257 (2007)","journal-title":"Nav. Res. Logist. (NRL)"},{"key":"23_CR12","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"R Graham","year":"1979","unstructured":"Graham, R., Lawler, E., Lenstra, J., Rinnooy, K.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discret. Math. 5, 287\u2013326 (1979)","journal-title":"Ann. Discret. Math."},{"key":"23_CR13","unstructured":"Huang, C., Ott, S.: A combinatorial approximation algorithm for graph balancing with light hyper edges. In: 24th Annual European Symposium on Algorithms. LIPIcs, vol. 57, pp. 49:1\u201349:15 (2016)"},{"key":"23_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/978-3-319-57586-5_30","volume-title":"Algorithms and Complexity","author":"K Jansen","year":"2017","unstructured":"Jansen, K., Maack, M., Solis-Oba, R.: Structural parameters for scheduling with assignment restrictions. In: Fotakis, D., Pagourtzis, A., Paschos, V.T. (eds.) CIAC 2017. LNCS, vol. 10236, pp. 357\u2013368. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-57586-5_30"},{"key":"23_CR15","unstructured":"Jansen, K., Maack, M., Solis-Oba, R.: Structural parameters for scheduling with assignment restrictions. CoRR abs\/1701.07242 (2017). http:\/\/arxiv.org\/abs\/1701.07242"},{"issue":"3\u20134","key":"23_CR16","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/S0020-0190(00)00047-8","volume":"74","author":"T Kloks","year":"2000","unstructured":"Kloks, T., Kratsch, D., M\u00fcller, H.: Finding and counting small induced subgraphs efficiently. Inf. Process. Lett. 74(3\u20134), 115\u2013121 (2000)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"23_CR17","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1016\/j.ipl.2009.09.015","volume":"110","author":"K Lee","year":"2009","unstructured":"Lee, K., Leung, J.Y.T., Pinedo, M.: A note on graph balancing problems with restrictions. Inf. Process. Lett. 110(1), 24\u201329 (2009)","journal-title":"Inf. Process. Lett."},{"issue":"1\u20133","key":"23_CR18","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/BF01585745","volume":"46","author":"J Lenstra","year":"1990","unstructured":"Lenstra, J., Shmoys, D., Tardos, E.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46(1\u20133), 259\u2013271 (1990)","journal-title":"Math. Program."},{"key":"23_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ijpe.2014.09.038","volume":"175","author":"JYT Leung","year":"2016","unstructured":"Leung, J.Y.T., Li, C.L.: Scheduling with processing set restrictions: a literature update. Int. J. Prod. Econ. 175, 1\u201311 (2016)","journal-title":"Int. J. Prod. Econ."},{"issue":"1","key":"23_CR20","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/j.dam.2004.11.004","volume":"148","author":"S Li","year":"2005","unstructured":"Li, S., Li, G., Zhang, S.: Minimizing makespan with release times on identical parallel batching machines. Discret. Appl. Math. 148(1), 127\u2013134 (2005)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"23_CR21","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/S0377-2217(02)00914-1","volume":"156","author":"Y Lin","year":"2004","unstructured":"Lin, Y., Li, W.: Parallel machine scheduling of machine-dependent jobs with unit-length. Eur. J. Oper. Res. 156(1), 261\u2013266 (2004)","journal-title":"Eur. J. Oper. Res."},{"issue":"2","key":"23_CR22","doi-asserted-by":"publisher","first-page":"38","DOI":"10.3390\/a9020038","volume":"9","author":"DR Page","year":"2016","unstructured":"Page, D.R., Solis-Oba, R.: A 3\/2-approximation algorithm for the graph balancing problem with two weights. Algorithms 9(2), 38 (2016)","journal-title":"Algorithms"},{"key":"23_CR23","unstructured":"Saha, B., Srinivasan, A.: A new approximation technique for resource-allocation problems. In: 1st Annual Symposium on Innovations in Computer Science, pp. 342\u2013357 (2010)"},{"key":"23_CR24","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/j.orl.2004.05.004","volume":"33","author":"E Shchepin","year":"2005","unstructured":"Shchepin, E., Vakhania, N.: An optimal rounding gives a better approximation for scheduling unrelated machines. Oper. Res. Lett. 33, 127\u2013133 (2005)","journal-title":"Oper. Res. Lett."},{"key":"23_CR25","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735","volume-title":"The Design of Approximation Algorithms","author":"D Williamson","year":"2011","unstructured":"Williamson, D., Shmoys, D.: The Design of Approximation Algorithms. Cambridge University Press, Cambridge (2011)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-04651-4_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T15:49:36Z","timestamp":1710344976000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-04651-4_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783030046507","9783030046514"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-04651-4_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"16 November 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Combinatorial Optimization and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Atlanta, GA","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 December 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 December 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoa2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/spacl.kennesaw.edu\/cocoa2018\/cfp.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}