{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T02:10:33Z","timestamp":1740103833593,"version":"3.37.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,11,27]],"date-time":"2018-11-27T00:00:00Z","timestamp":1543276800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001804","name":"Canada Research Chairs","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001804","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2019,4]]},"DOI":"10.1007\/s10951-018-0591-z","type":"journal-article","created":{"date-parts":[[2018,11,27]],"date-time":"2018-11-27T02:15:50Z","timestamp":1543284950000},"page":"239-253","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Scheduling problems over a network of machines"],"prefix":"10.1007","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4039-3235","authenticated-orcid":false,"given":"Zachary","family":"Friggstad","sequence":"first","affiliation":[]},{"given":"Arnoosh","family":"Golestanian","sequence":"additional","affiliation":[]},{"given":"Kamyar","family":"Khodamoradi","sequence":"additional","affiliation":[]},{"given":"Christopher","family":"Martin","sequence":"additional","affiliation":[]},{"given":"Mirmahdi","family":"Rahgoshay","sequence":"additional","affiliation":[]},{"given":"Mohsen","family":"Rezapour","sequence":"additional","affiliation":[]},{"given":"Mohammad R.","family":"Salavatipour","sequence":"additional","affiliation":[]},{"given":"Yifeng","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,11,27]]},"reference":[{"key":"591_CR1","unstructured":"Antoniadis, A., Barcelo, N., Cole, D., Fox, K., Moseley, B., Nugent, M., & Pruhs, K. (2014). Packet forwarding algorithms in a line network. In LATIN 2014: Theoretical informatics\u201411th Latin American symposium, Montevideo, Uruguay, March 31\u2014April 4, 2014. Proceedings (pp. 610\u2013621)."},{"issue":"2","key":"591_CR2","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1287\/moor.1060.0189","volume":"31","author":"N Bansal","year":"2006","unstructured":"Bansal, N., Kimbrel, T., & Sviridenko, M. (2006). Job shop scheduling with unit processing times. Mathematics of Operations Research, 31(2), 381\u2013389.","journal-title":"Mathematics of Operations Research"},{"key":"591_CR3","doi-asserted-by":"crossref","unstructured":"Bhattacharya, S., Kulkarni, J. & Mirrokni, V. S. (2014). Coordination mechanisms for selfish routing over time on a tree. In Automata, languages, and programming\u201441st international colloquium, ICALP 2014, Copenhagen, Denmark, July 8\u201311, 2014, Proceedings, Part I (pp. 186\u2013197).","DOI":"10.1007\/978-3-662-43948-7_16"},{"key":"591_CR4","doi-asserted-by":"crossref","unstructured":"Chaudhuri, K., Godfrey, B., Rao, S., & Talwar, K. (2003). Paths, trees, and minimum latency tours. In 44th symposium on foundations of computer science (FOCS 2003), October 11\u201314, 2003, Cambridge, MA, USA, proceedings (pp. 36\u201345).","DOI":"10.1109\/SFCS.2003.1238179"},{"key":"591_CR5","volume-title":"Combinatorial optimization","author":"WJ Cook","year":"1998","unstructured":"Cook, W. J., Cunningham, W. H., Pulleyblank, W. R., & Schrijver, A. (1998). Combinatorial optimization. New York, NY: Wiley."},{"issue":"3","key":"591_CR6","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/s004930200018","volume":"22","author":"Uriel Feige","year":"2002","unstructured":"Feige, Uriel, & Scheideler, Christian. (2002). Improved bounds for acyclic job shop scheduling. Combinatorica, 22(3), 361\u2013399.","journal-title":"Combinatorica"},{"issue":"1","key":"591_CR7","doi-asserted-by":"publisher","first-page":"11:1","DOI":"10.1145\/1328911.1328922","volume":"4","author":"R Gandhi","year":"2008","unstructured":"Gandhi, R., Halld\u00f3rsson, M. M., Kortsarz, G., & Shachnai, H. (2008). Improved bounds for scheduling conflicting jobs with minsum criteria. ACM Transactions on Algorithms, 4(1), 11:1\u201311:20.","journal-title":"ACM Transactions on Algorithms"},{"issue":"1","key":"591_CR8","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1007\/s00453-007-9118-2","volume":"54","author":"R Gandhi","year":"2009","unstructured":"Gandhi, R., & Mestre, J. (2009). Combinatorial algorithms for data migration to minimize average completion time. Algorithmica, 54(1), 54\u201371.","journal-title":"Algorithmica"},{"issue":"2","key":"591_CR9","doi-asserted-by":"publisher","first-page":"22:1","DOI":"10.1145\/1921659.1921668","volume":"7","author":"MM Halld\u00f3rsson","year":"2011","unstructured":"Halld\u00f3rsson, M. M., Kortsarz, G., & Sviridenko, M. (2011). Sum edge coloring of multigraphs via configuration LP. ACM Transactions on Algorithms, 7(2), 22:1\u201322:21.","journal-title":"ACM Transactions on Algorithms"},{"key":"591_CR10","doi-asserted-by":"crossref","unstructured":"Harris, D.G., & Srinivasan, A. (2013). Constraint satisfaction, packet routing, and the lovasz local lemma. In Symposium on theory of computing conference, STOC\u201913, Palo Alto, CA, USA, June 1\u20134, 2013 (pp. 685\u2013694).","DOI":"10.1145\/2488608.2488696"},{"key":"591_CR11","doi-asserted-by":"crossref","unstructured":"Im, S., & Moseley, B. (2015). Scheduling in bandwidth constrained tree networks. In Proceedings of the 27th ACM on symposium on parallelism in algorithms and architectures, SPAA 2015, Portland, OR, USA, June 13\u201315, 2015 (pp. 171\u2013180).","DOI":"10.1145\/2755573.2755576"},{"issue":"2","key":"591_CR12","doi-asserted-by":"publisher","first-page":"777","DOI":"10.1007\/s11590-013-0613-x","volume":"8","author":"DR Kowalski","year":"2014","unstructured":"Kowalski, D. R., Nussbaum, E., Segal, M., & Milyeykovski, V. (2014). Scheduling problems in transportation networks of line topology. Optimization Letters, 8(2), 777\u2013799.","journal-title":"Optimization Letters"},{"key":"591_CR13","doi-asserted-by":"crossref","unstructured":"Kowalski, D. R., Nutov, Z., & Segal, M. (2012). Scheduling of vehicles in transportation networks. In Communication technologies for vehicles\u20144th international workshop, Nets4Cars\/Nets4Trains 2012, Vilnius, Lithuania, April 25\u201327, 2012. Proceedings (pp. 124\u2013136).","DOI":"10.1007\/978-3-642-29667-3_11"},{"key":"591_CR14","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511977152","volume-title":"Iterative methods in combinatorial optimization","author":"L-C Lau","year":"2011","unstructured":"Lau, L.-C., Ravi, R., & Singh, M. (2011). Iterative methods in combinatorial optimization (1st ed.). New York, NY: Cambridge University Press.","edition":"1"},{"issue":"2","key":"591_CR15","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/BF01215349","volume":"14","author":"FT Leighton","year":"1994","unstructured":"Leighton, F. T., Maggs, B. M., & Rao, S. (1994). Packet routing and job-shop scheduling in O(congestion + dilation) steps. Combinatorica, 14(2), 167\u2013186.","journal-title":"Combinatorica"},{"issue":"3","key":"591_CR16","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/s004930050061","volume":"19","author":"FT Leighton","year":"1999","unstructured":"Leighton, F. T., Maggs, B. M., & Richa, A. W. (1999). Fast algorithms for finding O(congestion + dilation) packet routing schedules. Combinatorica, 19(3), 375\u2013401.","journal-title":"Combinatorica"},{"issue":"2","key":"591_CR17","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1006\/jpdc.1996.0057","volume":"34","author":"JY-T Leung","year":"1996","unstructured":"Leung, J. Y.-T., Tam, T. W., & Young, G. H. (1996). On-line routing of real-time messages. Journal of Parallel and Distributed Computing, 34(2), 211\u2013217.","journal-title":"Journal of Parallel and Distributed Computing"},{"issue":"6","key":"591_CR18","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1007\/s10951-006-8790-4","volume":"9","author":"W Li","year":"2006","unstructured":"Li, W., Queyranne, M., Sviridenko, M., & Yuan, J. (2006). Approximation algorithms for shop scheduling problems with minsum objective: A correction. Journal of Scheduling, 9(6), 569\u2013570.","journal-title":"Journal of Scheduling"},{"issue":"5","key":"591_CR19","doi-asserted-by":"publisher","first-page":"20:1","DOI":"10.1145\/2027216.2027218","volume":"58","author":"M Mastrolilli","year":"2011","unstructured":"Mastrolilli, M., & Svensson, O. (2011). Hardness of approximating flow and job shop scheduling problems. Journal of the ACM, 58(5), 20:1\u201320:32.","journal-title":"Journal of the ACM"},{"key":"591_CR20","unstructured":"Peis, B., Skutella, M., & Wiese, A. (2009). Packet routing: Complexity and algorithms. In 7th international workshop on approximation and online algorithms, WAOA 2009, Copenhagen, Denmark, September 10\u201311, 2009. Revised papers (pp. 217\u2013228)."},{"key":"591_CR21","unstructured":"Peis, B., Skutella,, M., & Wiese, A. (2010). Packet routing on the grid. In LATIN 2010: Theoretical informatics, 9th Latin American symposium, Oaxaca, Mexico, April 19\u201323, 2010. Proceedings (pp. 120\u2013130)."},{"key":"591_CR22","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/BF02392606","volume":"15","author":"J Petersen","year":"1891","unstructured":"Petersen, J. (1891). Die theorie der regul aren graphs. Acta Mathematica, 15, 193\u2013220.","journal-title":"Acta Mathematica"},{"issue":"4","key":"591_CR23","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1002\/jos.96","volume":"5","author":"M Queyranne","year":"2002","unstructured":"Queyranne, M., & Sviridenko, M. (2002). Approximation algorithms for shop scheduling problems with minsum objective. Journal of Scheduling, 5(4), 287\u2013305.","journal-title":"Journal of Scheduling"},{"issue":"3","key":"591_CR24","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":"591_CR25","unstructured":"Shepherd, F.\u00a0B., & Vetta, A. (2002). The demand matching problem. In Integer programming and combinatorial optimization: 9th international IPCO conference, Cambridge, MA, USA, May 27\u201329, 2002, Proceedings (pp. 457\u2013474)."},{"issue":"3","key":"591_CR26","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1137\/S009753979222676X","volume":"23","author":"DB Shmoys","year":"1994","unstructured":"Shmoys, D. B., Stein, C., & Wein, J. (1994). Improved approximation algorithms for shop scheduling problems. SIAM Journal on Computing, 23(3), 617\u2013632.","journal-title":"SIAM Journal on Computing"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-018-0591-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10951-018-0591-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-018-0591-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,11,26]],"date-time":"2019-11-26T19:17:50Z","timestamp":1574795870000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10951-018-0591-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11,27]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,4]]}},"alternative-id":["591"],"URL":"https:\/\/doi.org\/10.1007\/s10951-018-0591-z","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"type":"print","value":"1094-6136"},{"type":"electronic","value":"1099-1425"}],"subject":[],"published":{"date-parts":[[2018,11,27]]},"assertion":[{"value":"27 November 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}