{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:39:00Z","timestamp":1740123540722,"version":"3.37.3"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2020,2,18]],"date-time":"2020-02-18T00:00:00Z","timestamp":1581984000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,2,18]],"date-time":"2020-02-18T00:00:00Z","timestamp":1581984000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Supercomput"],"published-print":{"date-parts":[[2020,11]]},"DOI":"10.1007\/s11227-020-03208-y","type":"journal-article","created":{"date-parts":[[2020,2,18]],"date-time":"2020-02-18T19:02:40Z","timestamp":1582052560000},"page":"9142-9167","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["An efficient multi-functional duplication-based scheduling framework for multiprocessor systems"],"prefix":"10.1007","volume":"76","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1722-3839","authenticated-orcid":false,"given":"Qi","family":"Tang","sequence":"first","affiliation":[]},{"given":"Li-Hua","family":"Zhu","sequence":"additional","affiliation":[]},{"given":"Jin","family":"Lian","sequence":"additional","affiliation":[]},{"given":"Li","family":"Zhou","sequence":"additional","affiliation":[]},{"given":"Ji-Bo","family":"Wei","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,2,18]]},"reference":[{"issue":"9","key":"3208_CR1","doi-asserted-by":"publisher","first-page":"3373","DOI":"10.1007\/s11227-015-1438-4","volume":"71","author":"F Wu","year":"2015","unstructured":"Wu F, Wu Q, Tan Y (2015) Workflow scheduling in cloud: a survey. J Supercomput 71(9):3373\u20133418","journal-title":"J Supercomput"},{"issue":"6","key":"3208_CR2","doi-asserted-by":"publisher","first-page":"2059","DOI":"10.1007\/s11227-014-1335-2","volume":"72","author":"Z Tang","year":"2016","unstructured":"Tang Z, Liu M, Ammar A, Li K (2016) An optimized MapReduce workflow scheduling algorithm for heterogeneous computing. J Supercomput 72(6):2059\u20132079","journal-title":"J Supercomput"},{"issue":"4","key":"3208_CR3","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/s10586-006-0010-7","volume":"9","author":"AF Alkaya","year":"2006","unstructured":"Alkaya AF, Topcuoglu HR (2006) A task scheduling algorithm for arbitrarily-connected processors with awareness of link contention. Clust Comput 9(4):417\u2013431","journal-title":"Clust Comput"},{"issue":"2","key":"3208_CR4","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1137\/0218016","volume":"18","author":"J-J Hwang","year":"1989","unstructured":"Hwang J-J, Chow Y-C, Anger FD, Lee C-Y (1989) Scheduling precedence graphs in systems with interprocessor communication times. SIAM J Comput 18(2):244\u2013257","journal-title":"SIAM J Comput"},{"issue":"3","key":"3208_CR5","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1109\/71.993206","volume":"13","author":"H Topcuoglu","year":"2002","unstructured":"Topcuoglu H, Hariri S, Wu M-Y (2002) Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Trans Parallel Distrib Syst 13(3):260\u2013274","journal-title":"IEEE Trans Parallel Distrib Syst"},{"issue":"5","key":"3208_CR6","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1109\/71.503776","volume":"7","author":"Y-K Kwok","year":"1996","unstructured":"Kwok Y-K, Ahmad I (1996) Dynamic critical-path scheduling: an effective technique for allocating task graphs to multiprocessors. IEEE Trans Parallel Distrib Syst 7(5):506\u2013521","journal-title":"IEEE Trans Parallel Distrib Syst"},{"issue":"2","key":"3208_CR7","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1016\/0743-7315(90)90042-N","volume":"9","author":"H El-Rewini","year":"1990","unstructured":"El-Rewini H, Lewis TG (1990) Scheduling parallel program tasks onto arbitrary target machines. J Parallel Distrib Comput 9(2):138\u2013153","journal-title":"J Parallel Distrib Comput"},{"issue":"2","key":"3208_CR8","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1109\/71.207593","volume":"4","author":"GC Sih","year":"1993","unstructured":"Sih GC, Lee EA (1993) A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures. IEEE Trans Parallel Distrib Syst 4(2):175\u2013187","journal-title":"IEEE Trans Parallel Distrib Syst"},{"issue":"6","key":"3208_CR9","doi-asserted-by":"publisher","first-page":"911","DOI":"10.1109\/TCAD.2010.2048354","volume":"29","author":"F Ferrandi","year":"2010","unstructured":"Ferrandi F, Lanzi PL, Pilato C, Sciuto D, Tumeo A (2010) Ant colony heuristic for mapping and scheduling tasks and communications on heterogeneous embedded systems. IEEE Trans Comput Aided Des Integr Circuits Syst 29(6):911\u2013924","journal-title":"IEEE Trans Comput Aided Des Integr Circuits Syst"},{"issue":"1","key":"3208_CR10","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.jpdc.2009.09.009","volume":"70","author":"FA Omara","year":"2010","unstructured":"Omara FA, Arafa MM (2010) Genetic algorithms for task scheduling problem. J Parallel Distrib Comput 70(1):13\u201322","journal-title":"J Parallel Distrib Comput"},{"issue":"1\u20134","key":"3208_CR11","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/s00170-011-3610-1","volume":"60","author":"L Wang","year":"2012","unstructured":"Wang L, Zhou G, Xu Y, Wang S, Liu M (2012) An effective artificial bee colony algorithm for the flexible job-shop scheduling problem. Int J Adv Manuf Technol 60(1\u20134):303\u2013315","journal-title":"Int J Adv Manuf Technol"},{"issue":"1","key":"3208_CR12","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1109\/TPDS.2014.2308175","volume":"26","author":"S Venugopalan","year":"2015","unstructured":"Venugopalan S, Sinnen O (2015) ILP formulations for optimal task scheduling with communication delays on parallel systems. IEEE Trans Parallel Distrib Syst 26(1):142\u2013151","journal-title":"IEEE Trans Parallel Distrib Syst"},{"issue":"3","key":"3208_CR13","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1007\/s11227-010-0395-1","volume":"51","author":"AZS Shahul","year":"2010","unstructured":"Shahul AZS, Sinnen O (2010) Scheduling task graphs optimally with A*. J Supercomput 51(3):310\u2013332","journal-title":"J Supercomput"},{"issue":"2","key":"3208_CR14","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1007\/s11227-007-0152-2","volume":"44","author":"KC Lai","year":"2008","unstructured":"Lai KC, Yang CT (2008) A dominant predecessor duplication scheduling algorithm for heterogeneous systems. J Supercomput 44(2):126\u2013145","journal-title":"J Supercomput"},{"key":"3208_CR15","doi-asserted-by":"publisher","first-page":"822","DOI":"10.1007\/978-3-540-24680-0_131","volume":"3033","author":"W Yao","year":"2004","unstructured":"Yao W, Xie X, You J (2004) Link-contention-aware genetic scheduling using task duplication in grid environments. Lect Notes Comput Sci 3033:822\u2013829","journal-title":"Lect Notes Comput Sci"},{"issue":"6","key":"3208_CR16","doi-asserted-by":"publisher","first-page":"857","DOI":"10.1109\/TPDS.2008.260","volume":"20","author":"D Bozdag","year":"2009","unstructured":"Bozdag D, Ozguner F, Catalyurek UV (2009) Compaction of schedules and a two-stage approach for duplication-based DAG scheduling. IEEE Trans Parallel Distrib Syst 20(6):857\u2013871","journal-title":"IEEE Trans Parallel Distrib Syst"},{"issue":"6","key":"3208_CR17","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1109\/TPDS.2003.1206502","volume":"14","author":"S Bansal","year":"2003","unstructured":"Bansal S, Kumar P, Singh K (2003) An improved duplication strategy for scheduling precedence constrained graphs in multiprocessor systems. IEEE Trans Parallel Distrib Syst 14(6):533\u2013544","journal-title":"IEEE Trans Parallel Distrib Syst"},{"issue":"9","key":"3208_CR18","doi-asserted-by":"publisher","first-page":"872","DOI":"10.1109\/71.722221","volume":"9","author":"I Ahmad","year":"1998","unstructured":"Ahmad I, Kwok Y-K (1998) On exploiting task duplication in parallel program scheduling. IEEE Trans Parallel Distrib Syst 9(9):872\u2013892","journal-title":"IEEE Trans Parallel Distrib Syst"},{"key":"3208_CR19","doi-asserted-by":"crossref","unstructured":"Bozdag D, Ozguner F, Ekici E, Catalyurek U (2005) A task duplication based scheduling algorithm using partial schedules. In: 2005 International Conference on Parallel Processing (ICPP\u201905), pp 630\u2013637","DOI":"10.1109\/ICPP.2005.15"},{"key":"3208_CR20","doi-asserted-by":"crossref","unstructured":"Bozdag D, Catalyurek U, Ozguner F (2006) A task duplication based bottom-up scheduling algorithm for heterogeneous environments. In: Proceedings of International Parallel and Distributed Processing Symposium. ACM","DOI":"10.1109\/IPDPS.2006.1639389"},{"issue":"1","key":"3208_CR21","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/j.jpdc.2010.10.004","volume":"71","author":"O Sinnen","year":"2011","unstructured":"Sinnen O, To A, Kaur M (2011) Contention-aware scheduling with task duplication. J Parallel Distrib Comput 71(1):77\u201386","journal-title":"J Parallel Distrib Comput"},{"issue":"3","key":"3208_CR22","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1109\/TPDS.2016.2599166","volume":"28","author":"Q Tang","year":"2017","unstructured":"Tang Q, Wu SF, Shi JW, Wei JB (2017) Optimization of duplication-based schedules on network-on-chip based multi-processor system-on-chips. IEEE Trans Parallel Distrib Syst 28(3):826\u2013837","journal-title":"IEEE Trans Parallel Distrib Syst"},{"issue":"3","key":"3208_CR23","doi-asserted-by":"publisher","first-page":"1347","DOI":"10.1007\/s11227-014-1090-4","volume":"68","author":"J Mei","year":"2014","unstructured":"Mei J, Li K, Li K (2014) A resource-aware scheduling algorithm with reduced task duplication on heterogeneous computing systems. J Supercomput 68(3):1347\u20131377","journal-title":"J Supercomput"},{"issue":"4","key":"3208_CR24","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1016\/j.jpdc.2010.01.003","volume":"70","author":"X Tang","year":"2010","unstructured":"Tang X, Li K, Liao G, Li R (2010) List scheduling with duplication for heterogeneous computing systems. J Parallel Distrib Comput 70(4):323\u2013329","journal-title":"J Parallel Distrib Comput"},{"key":"3208_CR25","doi-asserted-by":"crossref","unstructured":"Singh J, Mangipudi B, Betha S, Auluck N (2012) Restricted duplication based MILP formulation for scheduling task graphs on unrelated parallel machines. In: Proceedings\u2014International Symposium on Parallel Architectures, Algorithms and Programming, PAAP, pp 202\u2013209","DOI":"10.1109\/PAAP.2012.37"},{"key":"3208_CR26","doi-asserted-by":"crossref","unstructured":"Agarwal A, Kumar P (2009) Economical duplication based task scheduling for heterogeneous and homogeneous computing systems. In: 2009 IEEE International Advance Computing Conference, pp 87\u201393","DOI":"10.1109\/IADCC.2009.4808986"},{"issue":"8","key":"3208_CR27","doi-asserted-by":"publisher","first-page":"1146","DOI":"10.1016\/j.jpdc.2008.04.001","volume":"68","author":"K Shin","year":"2008","unstructured":"Shin K, Cha M, Jang M, Jung J, Yoon W, Choi S (2008) Task scheduling algorithm using minimized duplications in homogeneous systems. J Parallel Distrib Comput 68(8):1146\u20131156","journal-title":"J Parallel Distrib Comput"},{"key":"3208_CR28","doi-asserted-by":"crossref","unstructured":"Song I, Yoon W, Jang E, Choi S (2011) Task scheduling algorithm with minimal redundant duplications in homogeneous multiprocessor system. In: Grid and Distributed Computing. Springer, pp 238\u2013245","DOI":"10.1007\/978-3-642-27180-9_29"},{"key":"3208_CR29","doi-asserted-by":"crossref","unstructured":"Mei J, Li K (2012) Multi-copy deleting approach for duplication based scheduling on heterogeneous computing systems. In: Proceedings of the International Conference on Parallel Processing Workshops, pp 610\u2013613","DOI":"10.1109\/ICPPW.2012.93"},{"key":"3208_CR30","first-page":"3","volume-title":"Job Scheduling Strategies for Parallel Processing. JSSPP 2015. Lecture Notes in Computer Science","author":"J Singh","year":"2017","unstructured":"Singh J, Auluck N (2017) Controlled duplication scheduling of real-time precedence tasks on heterogeneous multiprocessors. In: Desai N, Cirne W (eds) Job Scheduling Strategies for Parallel Processing. JSSPP 2015. Lecture Notes in Computer Science, vol 10353. Springer, Berlin, pp 3\u201321"},{"issue":"5","key":"3208_CR31","first-page":"170","volume":"46","author":"J Singh","year":"2014","unstructured":"Singh J, Auluck N (2014) DVFS and duplication based scheduling for optimizing power and performance in heterogeneous multiprocessors. Simul Ser 46(5):170\u2013177","journal-title":"Simul Ser"},{"key":"3208_CR32","doi-asserted-by":"crossref","unstructured":"Tosun S, Ozturk O, Ozen M (2009) An ILP formulation for application mapping onto network-on-chips. In: International Conference on Application of Information and Communication Technologies, pp 1\u20135","DOI":"10.1109\/ICAICT.2009.5372524"},{"key":"3208_CR33","doi-asserted-by":"publisher","first-page":"494","DOI":"10.1007\/s11227-017-2076-9","volume":"75","author":"W Zhang","year":"2019","unstructured":"Zhang W, Hu Y, He H, Liu Y, Chen A (2019) Linear and dynamic programming algorithms for real-time task scheduling with task duplication. J Supercomput 75:494","journal-title":"J Supercomput"},{"issue":"8","key":"3208_CR34","doi-asserted-by":"publisher","first-page":"1382","DOI":"10.1109\/TPDS.2010.204","volume":"22","author":"W Liu","year":"2011","unstructured":"Liu W, Gu Z, Xu J, Wu X, Ye Y (2011) Satisfiability modulo graph theory for task mapping and scheduling on multiprocessor systems. IEEE Trans Parallel Distrib Syst 22(8):1382\u20131389","journal-title":"IEEE Trans Parallel Distrib Syst"},{"issue":"4","key":"3208_CR35","doi-asserted-by":"publisher","first-page":"65:1","DOI":"10.1145\/2950051","volume":"15","author":"W Liu","year":"2016","unstructured":"Liu W, Xiao C (2016) An efficient technique of application mapping and scheduling on real-time multiprocessor systems for throughput optimization. ACM Trans Embed Comput Syst 15(4):65:1\u201365:25","journal-title":"ACM Trans Embed Comput Syst"},{"key":"3208_CR36","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/j.cor.2017.08.012","volume":"89","author":"A Malik","year":"2018","unstructured":"Malik A, Walker C, O\u2019Sullivan M, Sinnen O (2018) Satisfiability modulo theory (SMT) formulation for optimal scheduling of task graphs with communication delay. Comput Oper Res 89:113\u2013126","journal-title":"Comput Oper Res"},{"key":"3208_CR37","doi-asserted-by":"crossref","unstructured":"Tendulkar P, Poplavko P, Galanommatis Ioannis, Maler O (2014) Many-core scheduling of data parallel applications using SMT solvers. In: Proceedings of the 2014 17th Euromicro Conference on Digital System Design","DOI":"10.1109\/DSD.2014.10"},{"issue":"5","key":"3208_CR38","doi-asserted-by":"publisher","first-page":"1251","DOI":"10.1109\/TPDS.2014.2322354","volume":"26","author":"J Singh","year":"2015","unstructured":"Singh J, Betha S, Mangipudi B, Auluck N (2015) Contention aware energy efficient scheduling on heterogeneous multiprocessors. IEEE Trans Parallel Distrib Syst 26(5):1251\u20131264","journal-title":"IEEE Trans Parallel Distrib Syst"},{"key":"3208_CR39","first-page":"337","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems. TACAS 2008. Lecture Notes in Computer Science","author":"L De Moura","year":"2008","unstructured":"De Moura L, Bj\u00f8rner N (2008) Z3: an efficient SMT solver. In: Ramakrishnan CR, Rehof J (eds) Tools and Algorithms for the Construction and Analysis of Systems. TACAS 2008. Lecture Notes in Computer Science, vol 4963. Springer, Berlin, pp 337\u2013340 (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)"},{"issue":"1","key":"3208_CR40","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/s11227-011-0720-3","volume":"62","author":"S Tosun","year":"2012","unstructured":"Tosun S (2012) Energy- and reliability-aware task scheduling onto heterogeneous mpsoc architectures. J Supercomput 62(1):265\u2013289","journal-title":"J Supercomput"},{"key":"3208_CR41","doi-asserted-by":"crossref","unstructured":"Mei J, Li K (2012) Energy-aware scheduling algorithm with duplication on heterogeneous computing systems. In Proceedings\u2014IEEE\/ACM International Workshop on Grid Computing, pp 122\u2013129","DOI":"10.1109\/Grid.2012.32"},{"issue":"4","key":"3208_CR42","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1504\/IJCAET.2014.065419","volume":"6","author":"S Mittal","year":"2014","unstructured":"Mittal S (2014) A survey of techniques for improving energy efficiency in embedded computing systems. Int J Comput Aided Eng Technol 6(4):450\u2013459","journal-title":"Int J Comput Aided Eng Technol"},{"issue":"3","key":"3208_CR43","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1109\/TC.2010.216","volume":"60","author":"Z Zong","year":"2011","unstructured":"Zong Z, Manzanares A, Ruan X, Qin X (2011) EAD and PEBD: two energy-aware duplication scheduling algorithms for parallel tasks on homogeneous clusters. IEEE Trans Comput 60(3):360\u2013374","journal-title":"IEEE Trans Comput"},{"key":"3208_CR44","doi-asserted-by":"crossref","unstructured":"Ohrimenko O, Stuckey PJ, Codish M (2007) Propagation = lazy clause generation. In: Principles and practice of constraint programming, pp 1\u201315","DOI":"10.1007\/978-3-540-74970-7_39"},{"key":"3208_CR45","unstructured":"Martin SM, Flautner K, Mudge T, Blaauw D (2002) Combined dynamic voltage scaling and adaptive body biasing for lower power microprocessors under dynamic workloads. In: Proceedings of the 2002 IEEE\/ACM International Conference on Computer-Aided Design, pp 721\u2013725"},{"key":"3208_CR46","volume-title":"Euro-Par 2019: Parallel Processing. Euro-Par 2019. Lecture Notes in Computer Science","author":"LC Canon","year":"2019","unstructured":"Canon LC, El Sayah M (2019) A comparison of random task graph generation methods for scheduling problems. In: Yahyapour R (ed) Euro-Par 2019: Parallel Processing. Euro-Par 2019. Lecture Notes in Computer Science, vol 11725. Springer, Cham"}],"container-title":["The Journal of Supercomputing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-020-03208-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11227-020-03208-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-020-03208-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,19]],"date-time":"2021-02-19T05:10:25Z","timestamp":1613711425000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11227-020-03208-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,18]]},"references-count":46,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2020,11]]}},"alternative-id":["3208"],"URL":"https:\/\/doi.org\/10.1007\/s11227-020-03208-y","relation":{},"ISSN":["0920-8542","1573-0484"],"issn-type":[{"type":"print","value":"0920-8542"},{"type":"electronic","value":"1573-0484"}],"subject":[],"published":{"date-parts":[[2020,2,18]]},"assertion":[{"value":"18 February 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}