{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,20]],"date-time":"2025-12-20T22:03:16Z","timestamp":1766268196132},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2008,8,23]],"date-time":"2008-08-23T00:00:00Z","timestamp":1219449600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2008,10]]},"DOI":"10.1007\/s10951-008-0078-4","type":"journal-article","created":{"date-parts":[[2008,8,22]],"date-time":"2008-08-22T16:45:43Z","timestamp":1219423543000},"page":"381-404","source":"Crossref","is-referenced-by-count":21,"title":["Minimizing the stretch when scheduling flows of divisible requests"],"prefix":"10.1007","volume":"11","author":[{"given":"Arnaud","family":"Legrand","sequence":"first","affiliation":[]},{"given":"Alan","family":"Su","sequence":"additional","affiliation":[]},{"given":"Fr\u00e9d\u00e9ric","family":"Vivien","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2008,8,23]]},"reference":[{"key":"78_CR1","volume-title":"Introduction to sequencing and scheduling","author":"K.\u00a0R. Baker","year":"1974","unstructured":"Baker, K.\u00a0R. (1974). Introduction to sequencing and scheduling. New York: Wiley."},{"issue":"2","key":"78_CR2","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1287\/opre.31.2.381","volume":"31","author":"K.\u00a0R. Baker","year":"1983","unstructured":"Baker, K.\u00a0R., Lawler, E.\u00a0L., Lenstra, J.\u00a0K., & Rinnooy Kan, A.\u00a0H.\u00a0G. (1983). Preemptive scheduling of a single machine to minimize maximum cost subject to release dates and precedence constraints. Operations Research, 31(2), 381\u2013386.","journal-title":"Operations Research"},{"issue":"2","key":"78_CR3","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/s10951-006-0006-4","volume":"10","author":"P. Baptiste","year":"2007","unstructured":"Baptiste, P., Brucker, P., Chrobak, M., D\u00fcrr, C., Kravchenko, S.\u00a0A., & Sourd, F. (2007). The complexity of mean flow time scheduling problems with release times. Journal of Scheduling, 10(2), 139\u2013146.","journal-title":"Journal of Scheduling"},{"key":"78_CR4","unstructured":"Bender, M.\u00a0A. (1998). New algorithms and metrics for scheduling. Ph.D. thesis, Harvard University, May 1998."},{"key":"78_CR5","first-page":"270","volume-title":"Proceedings of the 9th annual ACM-SIAM symposium on discrete algorithms (SODA\u201998)","author":"M.\u00a0A. Bender","year":"1998","unstructured":"Bender, M.\u00a0A., Chakrabarti, S., & Muthukrishnan, S. (1998). Flow and stretch metrics for scheduling continuous job streams. In Proceedings of the 9th annual ACM-SIAM symposium on discrete algorithms (SODA\u201998) (pp.\u00a0270\u2013279). Philadelphia: SIAM."},{"key":"78_CR6","first-page":"762","volume-title":"SODA\u201902: Proceedings of the thirteenth annual ACM-SIAM symposium on discrete algorithms","author":"M.\u00a0A. Bender","year":"2002","unstructured":"Bender, M.\u00a0A., Muthukrishnan, S., & Rajaraman, R. (2002). Improved algorithms for stretch scheduling. In SODA\u201902: Proceedings of the thirteenth annual ACM-SIAM symposium on discrete algorithms (pp.\u00a0762\u2013771). Philadelphia, PA, USA, 2002. Philadelphia: SIAM."},{"issue":"3","key":"78_CR7","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1023\/B:JOSH.0000019681.52701.8b","volume":"7","author":"M.\u00a0A. Bender","year":"2004","unstructured":"Bender, M.\u00a0A., Muthukrishnan, S., & Rajaraman, R. (2004). Approximation algorithms for average stretch scheduling. Journal of Scheduling, 7(3), 195\u2013222.","journal-title":"Journal of Scheduling"},{"key":"78_CR8","volume-title":"Data networks","author":"D. Bertsekas","year":"1987","unstructured":"Bertsekas, D., & Gallager, R. (1987). Data networks. Englewood Cliffs: Prentice Hall."},{"key":"78_CR9","volume-title":"Scheduling divisible loads in parallel and distributed systems","author":"V. Bharadwaj","year":"1996","unstructured":"Bharadwaj, V., Ghose, D., Mani, V., & Robertazzi, T.\u00a0G. (1996). Scheduling divisible loads in parallel and distributed systems. Los Alamitos: IEEE Comput. Soc."},{"issue":"3","key":"78_CR10","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1093\/bioinformatics\/16.3.286","volume":"16","author":"C. Blanchet","year":"2000","unstructured":"Blanchet, C., Combet, C., Geourjon, C., & Del\u00e9age, G. (2000). MPSA: integrated system for multiple protein sequence analysis with client\/server capabilities. Bioinformatics, 16(3), 286\u2013287.","journal-title":"Bioinformatics"},{"key":"78_CR11","first-page":"57","volume-title":"Modelling and performance evaluation of computer systems (Proceedings of the international workshop)","author":"J. Blazewicz","year":"1977","unstructured":"Blazewicz, J. (1977). Scheduling dependent tasks with different arrival times to meet deadlines. In H. Beilner & E. Gelenbe (Eds.), Modelling and performance evaluation of computer systems (Proceedings of the international workshop) (pp.\u00a057\u201365). Amsterdam: North-Holland."},{"key":"78_CR12","series-title":"International handbooks on information systems","volume-title":"Handbook on scheduling: from theory to applications","author":"J. Blazewicz","year":"2007","unstructured":"Blazewicz, J., Ecker, K.\u00a0H., Pesch, E., Schmidt, G., & Weglarz, J. (2007). Handbook on scheduling: from theory to applications. International handbooks on information systems. Berlin: Springer. ISBN: 978-3-540-28046-0."},{"issue":"6","key":"78_CR13","doi-asserted-by":"crossref","first-page":"745","DOI":"10.1016\/S0167-739X(00)00057-1","volume":"17","author":"R.\u00a0C. Braun","year":"2001","unstructured":"Braun, R.\u00a0C., Pedretti, K.\u00a0T., Casavant, T.\u00a0L., Scheetz, T.\u00a0E., Birkett, C.\u00a0L., & Roberts, C.\u00a0A. (2001). Parallelization of local BLAST service on workstation clusters. Future Generation Computer Systems, 17(6), 745\u2013754.","journal-title":"Future Generation Computer Systems"},{"key":"78_CR14","first-page":"297","volume-title":"Proceedings of the 34th annual ACM symposium on theory of computing","author":"C. Chekuri","year":"2002","unstructured":"Chekuri, C., & Khanna, S. (2002). Approximation schemes for preemptive weighted flow time. In Proceedings of the 34th annual ACM symposium on theory of computing (pp.\u00a0297\u2013305). New York: Assoc. Comput. Mach."},{"key":"78_CR15","unstructured":"Darling, A.\u00a0E., Carey, L., & Feng, W. Ch. (2003). The design, implementation, and evaluation of mpiBLAST. In Proceedings of ClusterWorld 2003."},{"key":"78_CR16","unstructured":"Dertouzos, M.\u00a0L. (1974). Control robotics: the procedural control of physical processes. In Proceedings of IFIP congress (pp.\u00a0897\u2013813)."},{"key":"78_CR17","volume-title":"Computers and intractability, a guide to the theory of NP-completeness","author":"M.\u00a0R. Garey","year":"1991","unstructured":"Garey, M.\u00a0R., & Johnson, D.\u00a0S. (1991). Computers and intractability, a guide to the theory of NP-completeness. New York: Freeman."},{"issue":"4","key":"78_CR18","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1145\/321978.321985","volume":"23","author":"T. Gonzalez","year":"1976","unstructured":"Gonzalez, T., & Sahni, S. (1976). Open shop scheduling to minimize finish time. Journal of the Association for Computing Machinery, 23(4), 665\u2013679.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"78_CR19","unstructured":"GriPPS webpage at http:\/\/gripps.ibcp.fr\/ (2005)."},{"key":"78_CR20","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D.\u00a0S. Johnson","year":"1974","unstructured":"Johnson, D.\u00a0S. (1974). Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 9, 256\u2013278.","journal-title":"Journal of Computer and System Sciences"},{"key":"78_CR21","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/B978-0-12-566780-7.50020-9","volume-title":"Progress in combinatorial optimization","author":"J. Labetoulle","year":"1984","unstructured":"Labetoulle, J., Lawler, E.\u00a0L., Lenstra, J.\u00a0K., & Rinnooy Kan, A.\u00a0H.\u00a0G. (1984). Preemptive scheduling of uniform machines subject to release dates. In W.\u00a0R. Pulleyblank (Ed.), Progress in combinatorial optimization (pp.\u00a0245\u2013261). San Diego: Academic Press."},{"issue":"4","key":"78_CR22","doi-asserted-by":"crossref","first-page":"612","DOI":"10.1145\/322092.322101","volume":"25","author":"E.\u00a0L. Lawler","year":"1978","unstructured":"Lawler, E.\u00a0L., & Labetoulle, J. (1978). On preemptive scheduling of unrelated parallel processors by linear programming. Journal of the Association for Computing Machinery, 25(4), 612\u2013619.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"78_CR23","doi-asserted-by":"crossref","unstructured":"Legrand, A., Marchal, L., & Casanova, H. (2003). Scheduling distributed applications: the SimGrid simulation framework. In Proceedings of the 3rd IEEE symposium on cluster computing and the grid.","DOI":"10.1109\/CCGRID.2003.1199362"},{"key":"78_CR24","unstructured":"Legrand, A., Su, A., & Vivien, F. (2004). Off-line scheduling of divisible requests on an heterogeneous collection of databanks (Research Report 5386). INRIA, November 2004. Also available as LIP, ENS Lyon, Research Report 2004-51."},{"key":"78_CR25","volume-title":"Proceedings of the 14th heterogeneous computing workshop","author":"A. Legrand","year":"2005","unstructured":"Legrand, A., Su, A., & Vivien, F. (2005). Off-line scheduling of divisible requests on an heterogeneous collection of databanks. In Proceedings of the 14th heterogeneous computing workshop, Denver, Colorado, USA, April 2005. Los Alamitos: IEEE Comput. Soc."},{"key":"78_CR26","volume-title":"Symposium on parallelism in algorithms and architectures SPAA\u20192006","author":"A. Legrand","year":"2006","unstructured":"Legrand, A., Su, A., & Vivien, F. (2006). Minimizing the stretch when scheduling flows of biological requests. In Symposium on parallelism in algorithms and architectures SPAA\u20192006. New York: Assoc. Comput. Mach."},{"key":"78_CR27","unstructured":"Legrand, A., Su, A., & Vivien, F. (2008). Minimizing the stretch when scheduling flows of divisible requests (Research Report RR2008-08). LIP, \u00c9cole Normale Sup\u00e9rieure de Lyon, February 2008. This is a revised version of the LIP Research Report RR2006-19. Also available as INRIA Research Report 6002 http:\/\/hal.inria.fr\/inria-00108524 ."},{"key":"78_CR28","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/S0167-5060(08)70743-X","volume":"1","author":"J.\u00a0K. Lenstra","year":"1977","unstructured":"Lenstra, J.\u00a0K., Rinnooy Kan, A.\u00a0H.\u00a0G., & Brucker, P. (1977). Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1, 343\u2013362.","journal-title":"Annals of Discrete Mathematics"},{"issue":"3","key":"78_CR29","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1109\/TNET.2002.1012364","volume":"10","author":"L. Massouli\u00e9","year":"2002","unstructured":"Massouli\u00e9, L., & Roberts, J. (2002). Bandwidth sharing: objectives and algorithms. Transactions on Networking, 10(3), 320\u2013328.","journal-title":"Transactions on Networking"},{"key":"78_CR30","unstructured":"Megow, N. (2002). Performance analysis of on-line algorithms in machine scheduling. Diplomarbeit, Technische Universit\u00e4t Berlin, April 2002."},{"issue":"1","key":"78_CR31","first-page":"71","volume":"7","author":"P.\u00a0L. Miller","year":"1991","unstructured":"Miller, P.\u00a0L., Nadkarni, P.\u00a0M., & Carriero, N.\u00a0M. (1991). Parallel computation and FASTA: confronting the problem of parallel database search for a fast sequence comparison algorithm. Computer Applications in the Biosciences, 7(1), 71\u201378.","journal-title":"Computer Applications in the Biosciences"},{"key":"78_CR32","doi-asserted-by":"crossref","unstructured":"Muthukrishnan, S., Rajaraman, R., Shaheen, A., & Gehrke, J. (1999). Online scheduling to minimize average stretch. In IEEE symposium on foundations of computer science (pp.\u00a0433\u2013442).","DOI":"10.1109\/SFFCS.1999.814615"},{"issue":"1","key":"78_CR33","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1016\/0022-0000(80)90046-X","volume":"21","author":"M. Protasi","year":"1980","unstructured":"Protasi, M. Ausiello, G. D\u2019Atri, A. (1980). Structure preserving reductions among convex optimization problems. Journal of Computer and System Sciences, 21(1), 136\u2013153.","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"78_CR34","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1002\/jos.93","volume":"5","author":"A.\u00a0S. Schulz","year":"2002","unstructured":"Schulz, A.\u00a0S., & Skutella, M. (2002). The power of \u03b1-points in preemptive single machine scheduling. Journal of Scheduling, 5(2), 121\u2013133. DOI: 10.1002\/jos.093 .","journal-title":"Journal of Scheduling"},{"issue":"1","key":"78_CR35","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/j.jalgor.2004.06.011","volume":"57","author":"R. Sitters","year":"2005","unstructured":"Sitters, R. (2005). Complexity of preemptive minsum scheduling on unrelated parallel machines. Journal of Algorithms, 57(1), 37\u201348.","journal-title":"Journal of Algorithms"},{"key":"78_CR36","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1145\/237814.237991","volume-title":"STOC\u201996: Proceedings of the twenty-eighth annual ACM symposium on theory of computing","author":"P. Slav\u00edk","year":"1996","unstructured":"Slav\u00edk, P. (1996). A tight analysis of the greedy algorithm for set cover. In STOC\u201996: Proceedings of the twenty-eighth annual ACM symposium on theory of computing (pp.\u00a0435\u2013441). New York: Assoc. Comput. Mach."},{"key":"78_CR37","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/nav.3800030106","volume":"3","author":"W.\u00a0E. Smith","year":"1956","unstructured":"Smith, W.\u00a0E. (1956). Various optimizers for single-stage production. Naval Research Logistics Quarterly, 3, 59\u201366.","journal-title":"Naval Research Logistics Quarterly"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-008-0078-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10951-008-0078-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-008-0078-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,19]],"date-time":"2023-05-19T18:20:44Z","timestamp":1684520444000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10951-008-0078-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8,23]]},"references-count":37,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2008,10]]}},"alternative-id":["78"],"URL":"https:\/\/doi.org\/10.1007\/s10951-008-0078-4","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,8,23]]}}}