{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T06:09:34Z","timestamp":1757311774960,"version":"3.37.3"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,12,10]],"date-time":"2023-12-10T00:00:00Z","timestamp":1702166400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,12,10]],"date-time":"2023-12-10T00:00:00Z","timestamp":1702166400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["160364472","160364472"],"award-info":[{"award-number":["160364472","160364472"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100008007","name":"Universit\u00e4t Paderborn","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100008007","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Consider a set of jobs connected to a directed acyclic task graph with a fixed source and sink. The edges of this graph model precedence constraints and the jobs have to be scheduled with respect to those. We introduce the server cloud scheduling problem, in which the jobs have to be processed either on a single local machine or on one of infinitely many cloud machines. For each job, processing times both on the server and in the cloud are given. Furthermore, for each edge in the task graph, a communication delay is included in the input and has to be taken into account if one of the two jobs is scheduled on the server and the other in the cloud. The server processes jobs sequentially, whereas the cloud can serve as many as needed in parallel, but induces costs. We consider both makespan and cost minimization. The main results are an FPTAS for the makespan objective for graphs with a constant source and sink dividing cut and strong hardness for the case with unit processing times and delays.<\/jats:p>","DOI":"10.1007\/s00453-023-01189-x","type":"journal-article","created":{"date-parts":[[2023,12,10]],"date-time":"2023-12-10T09:02:07Z","timestamp":1702198927000},"page":"1210-1245","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Server Cloud Scheduling"],"prefix":"10.1007","volume":"86","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7918-6642","authenticated-orcid":false,"given":"Marten","family":"Maack","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Friedhelm","family":"Meyer auf der Heide","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4473-5215","authenticated-orcid":false,"given":"Simon","family":"Pukrop","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,12,10]]},"reference":[{"issue":"9","key":"1189_CR1","doi-asserted-by":"publisher","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"RL Graham","year":"1966","unstructured":"Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45(9), 1563\u20131581 (1966). https:\/\/doi.org\/10.1002\/j.1538-7305.1966.tb01709.x","journal-title":"Bell Syst. Tech. J."},{"key":"1189_CR2","doi-asserted-by":"publisher","unstructured":"Levey, E., Rothvoss, T.: A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies. In: Wichs, D., Mansour, Y. (eds.) Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18\u201321, 2016, pp. 168\u2013177 (2016). https:\/\/doi.org\/10.1145\/2897518.2897532","DOI":"10.1145\/2897518.2897532"},{"key":"1189_CR3","doi-asserted-by":"publisher","unstructured":"Garg, S.: Quasi-PTAS for scheduling with precedences using LP hierarchies. In: Chatzigiannakis, I., Kaklamanis, C., Marx, D., Sannella, D. (eds.) 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9\u201313, 2018, Prague, Czech Republic. LIPIcs, vol. 107, pp. 59\u201315913 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.59","DOI":"10.4230\/LIPIcs.ICALP.2018.59"},{"key":"1189_CR4","doi-asserted-by":"publisher","unstructured":"Kulkarni, J., Li, S., Tarnawski, J., Ye, M.: Hierarchy-based algorithms for minimizing makespan under precedence and communication constraints. In: Chawla, S. (ed.) Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5\u20138, 2020, pp. 2770\u20132789 (2020). https:\/\/doi.org\/10.1137\/1.9781611975994.169","DOI":"10.1137\/1.9781611975994.169"},{"key":"1189_CR5","doi-asserted-by":"publisher","unstructured":"Davies, S., Kulkarni, J., Rothvoss, T., Tarnawski, J., Zhang, Y.: Scheduling with communication delays via LP hierarchies and clustering. In: 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16\u201319, 2020, pp. 822\u2013833 (2020). https:\/\/doi.org\/10.1109\/FOCS46700.2020.00081","DOI":"10.1109\/FOCS46700.2020.00081"},{"key":"1189_CR6","doi-asserted-by":"publisher","unstructured":"Davies, S., Kulkarni, J., Rothvoss, T., Tarnawski, J., Zhang, Y.: Scheduling with communication delays via LP hierarchies and clustering II: weighted completion times on related machines. In: Marx, D. (ed.) Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10\u201313, 2021, pp. 2958\u20132977 (2021). https:\/\/doi.org\/10.1137\/1.9781611976465.176","DOI":"10.1137\/1.9781611976465.176"},{"key":"1189_CR7","doi-asserted-by":"publisher","unstructured":"Aba, M.A., Kordon, A.M., Pallez, G.: Scheduling on two unbounded resources with communication costs. In: Yahyapour, R. (ed.) Euro-Par 2019: Parallel Processing\u201425th International Conference on Parallel and Distributed Computing, G\u00f6ttingen, Germany, August 26\u201330, 2019, Proceedings. Lecture Notes in Computer Science, vol. 11725, pp. 117\u2013128 (2019). https:\/\/doi.org\/10.1007\/978-3-030-29400-7_9","DOI":"10.1007\/978-3-030-29400-7_9"},{"key":"1189_CR8","doi-asserted-by":"publisher","unstructured":"Saha, B.: Renting a cloud. In: Seth, A., Vishnoi, N.K. (eds.) IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2013, December 12\u201314, 2013, Guwahati, India. LIPIcs, vol. 24, pp. 437\u2013448 (2013). https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2013.437","DOI":"10.4230\/LIPIcs.FSTTCS.2013.437"},{"issue":"4","key":"1189_CR9","doi-asserted-by":"publisher","first-page":"1168","DOI":"10.1007\/s10878-017-0198-x","volume":"36","author":"A M\u00e4cker","year":"2018","unstructured":"M\u00e4cker, A., Malatyali, M., auf der Heide, F.M., Riechers, S.: Cost-efficient scheduling on machines from the cloud. J. Comb. Optim. 36(4), 1168\u20131194 (2018). https:\/\/doi.org\/10.1007\/s10878-017-0198-x","journal-title":"J. Comb. Optim."},{"key":"1189_CR10","doi-asserted-by":"publisher","unstructured":"Maack, M., auf\u00a0der Heide, F.M., Pukrop, S.: Server cloud scheduling. In: K\u00f6nemann, J., Peis, B. (eds.) Approximation and Online Algorithms\u201419th International Workshop, WAOA 2021, Lisbon, Portugal, September 6\u201310, 2021, Revised Selected Papers. Lecture Notes in Computer Science, vol. 12982, pp. 144\u2013164 (2021). https:\/\/doi.org\/10.1007\/978-3-030-92702-8_10","DOI":"10.1007\/978-3-030-92702-8_10"},{"key":"1189_CR11","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/S0167-5060(08)70743-X","volume":"1","author":"JK Lenstra","year":"1977","unstructured":"Lenstra, J.K., Kan, A.R., Brucker, P.: Complexity of machine scheduling problems. Ann. Discrete Math. 1, 343\u2013362 (1977). https:\/\/doi.org\/10.1016\/S0167-5060(08)70743-X","journal-title":"Ann. Discrete Math."},{"issue":"1","key":"1189_CR12","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1287\/opre.26.1.22","volume":"26","author":"JK Lenstra","year":"1978","unstructured":"Lenstra, J.K., Kan, A.H.G.R.: Complexity of scheduling under precedence constraints. Oper. Res. 26(1), 22\u201335 (1978). https:\/\/doi.org\/10.1287\/opre.26.1.22","journal-title":"Oper. Res."},{"issue":"5","key":"1189_CR13","doi-asserted-by":"publisher","first-page":"1258","DOI":"10.1137\/100810502","volume":"40","author":"O Svensson","year":"2011","unstructured":"Svensson, O.: Hardness of precedence constrained scheduling on identical machines. SIAM J. Comput. 40(5), 1258\u20131274 (2011). https:\/\/doi.org\/10.1137\/100810502","journal-title":"SIAM J. Comput."},{"key":"1189_CR14","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.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5, 287\u2013326 (1979). https:\/\/doi.org\/10.1016\/S0167-5060(08)70356-X","journal-title":"Ann. Discrete Math."},{"issue":"1","key":"1189_CR15","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.: A functional equation and its application to resource allocation and sequencing problems. Manag. Sci. 16(1), 77\u201384 (1969). https:\/\/doi.org\/10.1287\/mnsc.16.1.77","journal-title":"Manag. Sci."},{"issue":"1","key":"1189_CR16","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1145\/321921.321934","volume":"23","author":"S Sahni","year":"1976","unstructured":"Sahni, S.: Algorithms for scheduling independent tasks. J. ACM 23(1), 116\u2013127 (1976). https:\/\/doi.org\/10.1145\/321921.321934","journal-title":"J. ACM"},{"issue":"1","key":"1189_CR17","doi-asserted-by":"publisher","first-page":"219","DOI":"10.3934\/jimo.2014.10.219","volume":"10","author":"MO Adamu","year":"2014","unstructured":"Adamu, M.O., Adewumi, A.O.: A survey of single machine scheduling to minimize weighted number of tardy jobs. J. Ind. Manag. Optim. 10(1), 219 (2014). https:\/\/doi.org\/10.3934\/jimo.2014.10.219","journal-title":"J. Ind. Manag. Optim."},{"issue":"3","key":"1189_CR18","doi-asserted-by":"publisher","first-page":"540","DOI":"10.1016\/j.ejor.2013.10.052","volume":"235","author":"B Detienne","year":"2014","unstructured":"Detienne, B.: A mixed integer linear programming approach to minimize the number of late jobs with and without machine availability constraints. Eur. J. Oper. Res. 235(3), 540\u2013552 (2014). https:\/\/doi.org\/10.1016\/j.ejor.2013.10.052","journal-title":"Eur. J. Oper. Res."},{"issue":"2","key":"1189_CR19","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1016\/S0377-2217(02)00827-5","volume":"151","author":"M Sevaux","year":"2003","unstructured":"Sevaux, M., Dauz\u00e8re-P\u00e9r\u00e8s, S.: Genetic algorithms to minimize the weighted number of late jobs on a single machine. Eur. J. Oper. Res. 151(2), 296\u2013306 (2003). https:\/\/doi.org\/10.1016\/S0377-2217(02)00827-5","journal-title":"Eur. J. Oper. Res."},{"issue":"2","key":"1189_CR20","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1016\/j.ejor.2005.08.013","volume":"176","author":"R M\u2019Hallah","year":"2007","unstructured":"M\u2019Hallah, R., Bulfin, R.L.: Minimizing the weighted number of tardy jobs on a single machine with release dates. Eur. J. Oper. Res. 176(2), 727\u2013744 (2007). https:\/\/doi.org\/10.1016\/j.ejor.2005.08.013","journal-title":"Eur. J. Oper. Res."},{"key":"1189_CR21","doi-asserted-by":"publisher","unstructured":"M\u00f6hring, R.H., Sch\u00e4ffter, M.W., Schulz, A.S.: Scheduling jobs with communication delays: Using infeasible solutions for approximation (extended abstract). In: D\u00edaz, J., Serna, M.J. (eds.) Algorithms\u2014ESA \u201996, Fourth Annual European Symposium, Barcelona, Spain, September 25\u201327, 1996, Proceedings. Lecture Notes in Computer Science, vol. 1136, pp. 76\u201390 (1996). https:\/\/doi.org\/10.1007\/3-540-61680-2_48","DOI":"10.1007\/3-540-61680-2_48"},{"key":"1189_CR22","doi-asserted-by":"publisher","unstructured":"Legriel, J., Guernic, C.L., Cotton, S., Maler, O.: Approximating the pareto front of multi-criteria optimization problems. In: Esparza, J., Majumdar, R. (eds.) Tools and Algorithms for the Construction and Analysis of Systems, 16th International Conference, TACAS 2010, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2010, Paphos, Cyprus, March 20\u201328, 2010. Proceedings. Lecture Notes in Computer Science, vol. 6015, pp. 69\u201383 (2010). https:\/\/doi.org\/10.1007\/978-3-642-12002-2_6","DOI":"10.1007\/978-3-642-12002-2_6"},{"key":"1189_CR23","doi-asserted-by":"publisher","unstructured":"Papadimitriou, C.H., Yannakakis, M.: On the approximability of trade-offs and optimal access of web sources. In: 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12\u201314 November 2000, Redondo Beach, California, USA, pp. 86\u201392 (2000). https:\/\/doi.org\/10.1109\/SFCS.2000.892068","DOI":"10.1109\/SFCS.2000.892068"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01189-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01189-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01189-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,28]],"date-time":"2024-03-28T10:06:17Z","timestamp":1711620377000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01189-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,10]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,4]]}},"alternative-id":["1189"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01189-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2023,12,10]]},"assertion":[{"value":"17 November 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 November 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 December 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors are not aware of any conflict of interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of interest"}}]}}