{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T21:33:04Z","timestamp":1781386384246,"version":"3.54.1"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2020,5,28]],"date-time":"2020-05-28T00:00:00Z","timestamp":1590624000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Comput. Surv."],"published-print":{"date-parts":[[2021,5,31]]},"abstract":"<jats:p>The evolution in the design of modern parallel platforms leads to revisit the scheduling jobs on distributed heterogeneous resources. The goal of this survey is to present the main existing algorithms, to classify them based on their underlying principles, and to propose unified implementations to enable their fair comparison, in terms of running time and quality of schedules, on a large set of common benchmarks that we made available for the community. Beyond this comparison, our goal is also to understand the main difficulties that heterogeneity conveys and the shared principles that guide the design of efficient algorithms.<\/jats:p>","DOI":"10.1145\/3387110","type":"journal-article","created":{"date-parts":[[2020,5,29]],"date-time":"2020-05-29T04:28:26Z","timestamp":1590726506000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Scheduling on Two Types of Resources"],"prefix":"10.1145","volume":"53","author":[{"given":"Olivier","family":"Beaumont","sequence":"first","affiliation":[{"name":"INRIA Bordeaux, Talence, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Louis-Claude","family":"Canon","sequence":"additional","affiliation":[{"name":"FEMTO-ST, Universit\u00e9 de Bourgogne Franche-Comt\u00e9, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lionel","family":"Eyraud-Dubois","sequence":"additional","affiliation":[{"name":"INRIA Bordeaux, Talence, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Giorgio","family":"Lucarelli","sequence":"additional","affiliation":[{"name":"LCOMS, University of Lorraine, Metz, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Loris","family":"Marchal","sequence":"additional","affiliation":[{"name":"CNRS, Univ. Lyon, LIP, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cl\u00e9ment","family":"Mommessin","sequence":"additional","affiliation":[{"name":"Univ. Grenoble Alpes, CNRS, INRIA, Grenoble INP, LIG, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bertrand","family":"Simon","sequence":"additional","affiliation":[{"name":"University of Bremen, Bremen, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2623-6922","authenticated-orcid":false,"given":"Denis","family":"Trystram","sequence":"additional","affiliation":[{"name":"Univ. Grenoble Alpes, CNRS, INRIA, Grenoble INP, LIG, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,5,28]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Task-based FMM for heterogeneous architectures. Concurr. Comput.: Pract. Exper. 28, 9","author":"Agullo Emmanuel","year":"2016","unstructured":"Emmanuel Agullo , Berenger Bramas , Olivier Coulaud , Eric Darve , Matthias Messner , and Toru Takahashi . 2016. Task-based FMM for heterogeneous architectures. Concurr. Comput.: Pract. Exper. 28, 9 ( 2016 ). Emmanuel Agullo, Berenger Bramas, Olivier Coulaud, Eric Darve, Matthias Messner, and Toru Takahashi. 2016. Task-based FMM for heterogeneous architectures. Concurr. Comput.: Pract. Exper. 28, 9 (2016)."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 2018 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW\u201918)","author":"Aba Massinissa Ait","year":"2018","unstructured":"Massinissa Ait Aba , Lilia Zaourar , and Alix Munier . 2018 . Approximation algorithm for scheduling applications on hybrid multi-core machines with communications delays . In Proceedings of the 2018 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW\u201918) . 36--45. Massinissa Ait Aba, Lilia Zaourar, and Alix Munier. 2018. Approximation algorithm for scheduling applications on hybrid multi-core machines with communications delays. In Proceedings of the 2018 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW\u201918). 36--45."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-64203-1_16"},{"key":"e_1_2_1_4_1","volume-title":"Generic algorithms for scheduling applications on heterogeneous platforms. Concurr. Comput.: Pract. Exper. 31, 15","author":"Amaris Marcos","year":"2019","unstructured":"Marcos Amaris , Giorgio Lucarelli , Cl\u00e9ment Mommessin , and Denis Trystram . 2019. Generic algorithms for scheduling applications on heterogeneous platforms. Concurr. Comput.: Pract. Exper. 31, 15 ( 2019 ). Marcos Amaris, Giorgio Lucarelli, Cl\u00e9ment Mommessin, and Denis Trystram. 2019. Generic algorithms for scheduling applications on heterogeneous platforms. Concurr. Comput.: Pract. Exper. 31, 15 (2019)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.1631"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.23"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2017.71"},{"key":"e_1_2_1_8_1","volume-title":"Fast approximation algorithms for task-based runtime systems. Concurr. Comput.: Pract. Exper. 30, 17","author":"Beaumont Olivier","year":"2018","unstructured":"Olivier Beaumont , Lionel Eyraud-Dubois , and Suraj Kumar . 2018. Fast approximation algorithms for task-based runtime systems. Concurr. Comput.: Pract. Exper. 30, 17 ( 2018 ). Olivier Beaumont, Lionel Eyraud-Dubois, and Suraj Kumar. 2018. Fast approximation algorithms for task-based runtime systems. Concurr. Comput.: Pract. Exper. 30, 17 (2018)."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 2010 18th Euromicro Conference on Parallel, Distributed and Network-based Processing. 27--34","author":"Bittencourt Luiz F.","unstructured":"Luiz F. Bittencourt , Rizos Sakellariou , and Edmundo R. M. Madeira . 2010. Dag scheduling using a lookahead variant of the heterogeneous earliest finish time algorithm . In Proceedings of the 2010 18th Euromicro Conference on Parallel, Distributed and Network-based Processing. 27--34 . Luiz F. Bittencourt, Rizos Sakellariou, and Edmundo R. M. Madeira. 2010. Dag scheduling using a lookahead variant of the heterogeneous earliest finish time algorithm. In Proceedings of the 2010 18th Euromicro Conference on Parallel, Distributed and Network-based Processing. 27--34."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-09873-9_47"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2017.2675891"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.3359"},{"key":"e_1_2_1_13_1","volume-title":"Scheduling unrelated machines of few different types. arXiv preprint arXiv:1205.0974","author":"Bonifaci Vincenzo","year":"2012","unstructured":"Vincenzo Bonifaci and Andreas Wiese . 2012. Scheduling unrelated machines of few different types. arXiv preprint arXiv:1205.0974 ( 2012 ). Vincenzo Bonifaci and Andreas Wiese. 2012. Scheduling unrelated machines of few different types. arXiv preprint arXiv:1205.0974 (2012)."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2013.98"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.2000.1714"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2019.2942909"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-64203-1_17"},{"key":"e_1_2_1_18_1","volume-title":"A Dense Linear Algebra Software for Heterogeneous Architectures. Retrieved","author":"Chameleon","year":"2019","unstructured":"Chameleon : A Dense Linear Algebra Software for Heterogeneous Architectures. Retrieved June 2019 from https:\/\/project.inria.fr\/chameleon. Chameleon: A Dense Linear Algebra Software for Heterogeneous Architectures. Retrieved June 2019 from https:\/\/project.inria.fr\/chameleon."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054114500312"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2015.36"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0987"},{"key":"e_1_2_1_22_1","unstructured":"Michel Cosnard and Denis Trystram. 1994. Parallel Algorithms and Architectures. Thomson Learning.  Michel Cosnard and Denis Trystram. 1994. Parallel Algorithms and Architectures. Thomson Learning."},{"key":"e_1_2_1_23_1","volume-title":"Scheduling for Parallel Processing","author":"Drozdowski Maciej","unstructured":"Maciej Drozdowski . 2009. Scheduling for Parallel Processing . Springer . Maciej Drozdowski. 2009. Scheduling for Parallel Processing. Springer."},{"key":"e_1_2_1_24_1","volume-title":"pmtool: Post-mortem Analysis Tool for starpu Scheduling Studies. Retrieved","author":"Eyraud-Dubois Lionel","year":"2019","unstructured":"Lionel Eyraud-Dubois . pmtool: Post-mortem Analysis Tool for starpu Scheduling Studies. Retrieved June 2019 from https:\/\/gitlab.inria.fr\/eyrauddu\/pmtool. Lionel Eyraud-Dubois. pmtool: Post-mortem Analysis Tool for starpu Scheduling Studies. Retrieved June 2019 from https:\/\/gitlab.inria.fr\/eyrauddu\/pmtool."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.056"},{"key":"e_1_2_1_26_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1990","unstructured":"Michael R. Garey and David S . Johnson . 1990 . Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman 8 Co., New York, NY. Michael R. Garey and David S. Johnson. 1990. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman 8 Co., New York, NY."},{"key":"e_1_2_1_27_1","volume-title":"Stefan EJ Kraft, and Jakob Schikowski","author":"Gehrke Jan Clemens","year":"2016","unstructured":"Jan Clemens Gehrke , Klaus Jansen , Stefan EJ Kraft, and Jakob Schikowski . 2016 . A PTAS for scheduling unrelated machines of few different types. In SOSFEM: Theory and Practice of Computer Science. Springer , 290--301. Jan Clemens Gehrke, Klaus Jansen, Stefan EJ Kraft, and Jakob Schikowski. 2016. A PTAS for scheduling unrelated machines of few different types. In SOSFEM: Theory and Practice of Computer Science. Springer, 290--301."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0117039"},{"key":"e_1_2_1_29_1","series-title":"Annals of Discrete Mathematics","volume-title":"Rinnooy Kan","author":"Graham Ronald L.","year":"1979","unstructured":"Ronald L. Graham , Eugene L. Lawler , Jan K. Lenstra , and Alexander H. G . Rinnooy Kan . 1979 . Optimization and approximation in deterministic sequencing and scheduling: A survey. In Discrete Optimization II, volume 5 of Annals of Discrete Mathematics . Elsevier , 287--326. Ronald L. Graham, Eugene L. Lawler, Jan K. Lenstra, and Alexander H. G. Rinnooy Kan. 1979. Optimization and approximation in deterministic sequencing and scheduling: A survey. In Discrete Optimization II, volume 5 of Annals of Discrete Mathematics. Elsevier, 287--326."},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 30th Annual Symposium on Foundations of Computer Science. 134--139","author":"Leslie","unstructured":"Leslie A. Hall and David B. Shmoys. 1989. Approximation schemes for constrained scheduling problems . In Proceedings of the 30th Annual Symposium on Foundations of Computer Science. 134--139 . Leslie A. Hall and David B. Shmoys. 1989. Approximation schemes for constrained scheduling problems. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science. 134--139."},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Dorit S. Hochbaum editor. 1997. Approximation Algorithms for NP-hard Problems. PWS Boston MA USA.  Dorit S. Hochbaum editor. 1997. Approximation Algorithms for NP-hard Problems. PWS Boston MA USA.","DOI":"10.1145\/261342.571216"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/7531.7535"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-003-0011-9"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2014.59"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1142\/S012905411850003X"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2015.119"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585745"},{"key":"e_1_2_1_38_1","volume-title":"Handbook of Scheduling: Algorithms, Models, and Performance Analysis","author":"Leung Joseph Y. T.","unstructured":"Joseph Y. T. Leung . 2004. Handbook of Scheduling: Algorithms, Models, and Performance Analysis . CRC Press . Joseph Y. T. Leung. 2004. Handbook of Scheduling: Algorithms, Models, and Performance Analysis. CRC Press."},{"key":"e_1_2_1_39_1","volume-title":"Retrieved","author":"Manager Torque Resource","year":"2019","unstructured":"Torque Resource Manager . Retrieved June 2019 http:\/\/www.adaptivecomputing.com\/products\/torque\/. Torque Resource Manager. Retrieved June 2019 http:\/\/www.adaptivecomputing.com\/products\/torque\/."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2017.8057205"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2788396"},{"key":"e_1_2_1_42_1","first-page":"191","volume-title":"Proceedings of the International Conference on Parallel and Distributed Computing (Euro-Par\u201909)","author":"Nascimento Aline","unstructured":"Aline de P. Nascimento , Alexandre da C. Sena , Cristina Boeres , and Vinod E. F. Rebello . 2009. On the feasibility of dynamically scheduling dag applications on shared heterogeneous systems . In Proceedings of the International Conference on Parallel and Distributed Computing (Euro-Par\u201909) , Henk Sips, Dick Epema, and Hai-Xiang Lin, eds.. Springer, Berlin , pp. 191 -- 202 . Aline de P. Nascimento, Alexandre da C. Sena, Cristina Boeres, and Vinod E. F. Rebello. 2009. On the feasibility of dynamically scheduling dag applications on shared heterogeneous systems. In Proceedings of the International Conference on Parallel and Distributed Computing (Euro-Par\u201909), Henk Sips, Dick Epema, and Hai-Xiang Lin, eds.. Springer, Berlin, pp. 191--202."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1177\/1094342009106195"},{"key":"e_1_2_1_44_1","first-page":"72","article-title":"A survey on techniques for cooperative cpu-gpu computing","volume":"19","author":"Raju K.","year":"2018","unstructured":"K. Raju and Niranjan N. Chiplunkar . 2018 . A survey on techniques for cooperative cpu-gpu computing . Sust. Comput.: Inf. Syst. 19 (2018), 72 -- 85 . K. Raju and Niranjan N. Chiplunkar. 2018. A survey on techniques for cooperative cpu-gpu computing. Sust. Comput.: Inf. Syst. 19 (2018), 72--85.","journal-title":"Sust. Comput.: Inf. Syst."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2004.05.004"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/3113606.3113856"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/100810502"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2015.07.002"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/HCW.1999.765092"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.993206"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.308533"},{"key":"e_1_2_1_52_1","volume-title":"Dongarra","author":"YarKhan Azim","year":"2011","unstructured":"Azim YarKhan , Jakub Kurzak , and Jack J . Dongarra . 2011 . QUARK Users\u2019 Guide: Q Ueueing and Runtime for Kernels. UTK ICL. Azim YarKhan, Jakub Kurzak, and Jack J. Dongarra. 2011. QUARK Users\u2019 Guide: QUeueing and Runtime for Kernels. UTK ICL."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/10968987_3"}],"container-title":["ACM Computing Surveys"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3387110","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3387110","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:33:26Z","timestamp":1750199606000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3387110"}},"subtitle":["A Survey"],"short-title":[],"issued":{"date-parts":[[2020,5,28]]},"references-count":53,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,5,31]]}},"alternative-id":["10.1145\/3387110"],"URL":"https:\/\/doi.org\/10.1145\/3387110","relation":{},"ISSN":["0360-0300","1557-7341"],"issn-type":[{"value":"0360-0300","type":"print"},{"value":"1557-7341","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,5,28]]},"assertion":[{"value":"2019-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-05-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}