{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,16]],"date-time":"2025-10-16T09:54:15Z","timestamp":1760608455598},"reference-count":55,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2007,6,1]],"date-time":"2007-06-01T00:00:00Z","timestamp":1180656000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Supercomput"],"published-print":{"date-parts":[[2008,1]]},"DOI":"10.1007\/s11227-007-0139-z","type":"journal-article","created":{"date-parts":[[2007,5,31]],"date-time":"2007-05-31T18:43:41Z","timestamp":1180637021000},"page":"77-97","source":"Crossref","is-referenced-by-count":61,"title":["A performance study of multiprocessor task scheduling algorithms"],"prefix":"10.1007","volume":"43","author":[{"given":"Shiyuan","family":"Jin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guy","family":"Schiavone","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Damla","family":"Turgut","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,6,1]]},"reference":[{"issue":"2","key":"139_CR1","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1109\/71.265940","volume":"5","author":"E Hou","year":"1994","unstructured":"Hou E, Ansari N, Ren H (1994) A\u00a0genetic algorithm for multiprocessor scheduling. IEEE Trans Parallel Distrib Syst 5(2):113\u2013120","journal-title":"IEEE Trans Parallel Distrib Syst"},{"key":"139_CR2","doi-asserted-by":"crossref","first-page":"825","DOI":"10.1109\/71.790600","volume":"10","author":"R Correa","year":"1999","unstructured":"Correa R, Ferreira A, Rebreyend P (1999) Scheduling multiprocessor tasks with genetic algorithms. IEEE Trans Parallel Distrib Syst 10:825\u2013837","journal-title":"IEEE Trans Parallel Distrib Syst"},{"issue":"3","key":"139_CR3","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1109\/TC.1981.1675756","volume":"30","author":"S Bokhari","year":"1999","unstructured":"Bokhari S (1999) On the mapping problem. IEEE Trans Comput 30(3):207\u2013214","journal-title":"IEEE Trans Comput"},{"issue":"2","key":"139_CR4","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1145\/322003.322011","volume":"24","author":"O Ibarra","year":"1977","unstructured":"Ibarra O, Kim C (1977) Heuristic algorithms for scheduling independent tasks on non-identical processors. J\u00a0Assoc Comput Mach 24(2):280\u2013289","journal-title":"J\u00a0Assoc Comput Mach"},{"issue":"9","key":"139_CR5","doi-asserted-by":"crossref","first-page":"1197","DOI":"10.1016\/S0167-8191(96)00041-5","volume":"22","author":"G Djordjevic","year":"1996","unstructured":"Djordjevic G, Tosic M (1996) A heuristic for scheduling task graphs with communication delays onto multiprocessors. Parallel Comput 22(9):1197\u20131214","journal-title":"Parallel Comput"},{"key":"139_CR6","unstructured":"Russell S, Norvig P (2003) Artificial intelligence, a modern approach. Pearson Education, Ch\u00a05, pp\u00a0139\u2013172"},{"key":"139_CR7","doi-asserted-by":"crossref","unstructured":"Chamberlain R, Edelman M, Franklin M, Witte E (1988) Simulated annealing on a multiprocessor. In: Proceedings of the 1988 IEEE international conferences on computer design: VLSI in computers and processors, pp\u00a0540\u2013544","DOI":"10.1109\/ICCD.1988.25758"},{"key":"139_CR8","unstructured":"Tian Y, Sannomiya N, Xu Y (2000) A tabu search with a new neighborhood search technique applied to flow shop scheduling problems. In: Proceedings of the 39th IEEE conference on decision and control, vol\u00a05, pp\u00a04606\u20134611"},{"key":"139_CR9","doi-asserted-by":"crossref","unstructured":"Macey B, Zomaya A (1998) A performance evaluation of CP list scheduling heuristics for communication intensive task graphs. In: Proc joint 12th intl parallel processing symp and ninth symp parallel and distributed prog, pp\u00a0538\u2013541","DOI":"10.1109\/IPPS.1998.669968"},{"key":"139_CR10","doi-asserted-by":"crossref","first-page":"685","DOI":"10.1145\/361604.361619","volume":"17","author":"T Adam","year":"1974","unstructured":"Adam T, Chandy K, Dickson J (1974) A comparison of list schedules for parallel processing systems. ACM Commun 17:685\u2013690","journal-title":"ACM Commun"},{"key":"139_CR11","unstructured":"Kruatrachue B, Lewis T (1987) Duplication scheduling heuristic DSH: A\u00a0new precedence task scheduler for parallel processing systems. PhD thesis, Oregon State University, Corvallis, OR"},{"issue":"1","key":"139_CR12","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1109\/52.1991","volume":"5","author":"B Kruatrachue","year":"1998","unstructured":"Kruatrachue B, Lewis T (1998) Grain size determination for parallel processing. IEEE Softw 5(1):23\u201332","journal-title":"IEEE Softw"},{"issue":"4","key":"139_CR13","first-page":"407","volume":"31","author":"Y Hwok","year":"1999","unstructured":"Hwok Y, Ahmad I (1999) Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Comput Surv 31(4):407\u2013471","journal-title":"ACM Comput Surv"},{"key":"139_CR14","doi-asserted-by":"crossref","unstructured":"Braun T, Siegel H, Beck N et al (1999) A\u00a0comparison study of static mapping heuristics for a class of meta-tasks on heterogeneous computing system. In: Eighth heterogeneous computing workshop (HWC), pp\u00a015\u201323","DOI":"10.1109\/HCW.1999.765093"},{"key":"139_CR15","doi-asserted-by":"crossref","first-page":"2155","DOI":"10.1016\/j.cor.2005.01.005","volume":"33","author":"T Davidovic","year":"2006","unstructured":"Davidovic T, Crainic T (2006) Benchmark-problem instances for static scheduling of task graphs with communication delays on homogeneous multiprocessor systems. Comput Oper Res 33:2155\u20132177","journal-title":"Comput Oper Res"},{"issue":"8","key":"139_CR16","doi-asserted-by":"crossref","first-page":"795","DOI":"10.1109\/71.790598","volume":"10","author":"A Zomaya","year":"1999","unstructured":"Zomaya A, Ward C, Macey B (1999) Genetic scheduling for parallel processor systems comparative studies and performance issues. IEEE Trans Parallel Distrib Syst 10(8):795\u2013812","journal-title":"IEEE Trans Parallel Distrib Syst"},{"issue":"9","key":"139_CR17","doi-asserted-by":"crossref","first-page":"824","DOI":"10.1109\/TPDS.2004.38","volume":"15","author":"A Wu","year":"2004","unstructured":"Wu A, Yu H, Jin S, Lin K, Schiavone G (2004) An incremental genetic algorithm approach to multiprocessor scheduling. IEEE Trans Parallel Distrib Syst 15(9):824\u2013834","journal-title":"IEEE Trans Parallel Distrib Syst"},{"key":"139_CR18","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1016\/j.parco.2003.12.005","volume":"30","author":"M Moore","year":"2004","unstructured":"Moore M (2004) An accurate parallel genetic algorithm to schedule tasks on a cluster. Parallel Comput 30:567\u2013583","journal-title":"Parallel Comput"},{"key":"139_CR19","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/j.micpro.2003.10.002","volume":"28","author":"W Yao","year":"2004","unstructured":"Yao W, You J, Li B (2004) Main sequences genetic scheduling for multiprocessor systems using task duplication. Microprocess Microsyst 28:85\u201394","journal-title":"Microprocess Microsyst"},{"issue":"1","key":"139_CR20","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1006\/jpdc.1997.1395","volume":"47","author":"Y Kwok","year":"1997","unstructured":"Kwok Y, Ahmad I (1997) Efficient scheduling of arbitrary task graphs to multiprocessors using a parallel genetic algorithm. J Parallel Distrib Comput 47(1):58\u201377","journal-title":"J Parallel Distrib Comput"},{"key":"139_CR21","doi-asserted-by":"crossref","unstructured":"Ceyda O, Ercan M (2004) A genetic algorithm for multilayer multiprocessor task scheduling. In: TENCON 2004. IEEE region 10 conference, vol\u00a02, pp\u00a068\u2013170","DOI":"10.1109\/TENCON.2004.1414558"},{"key":"139_CR22","doi-asserted-by":"crossref","unstructured":"Cheng S, Huang Y (2003) Scheduling multi-processor tasks with resource and timing constraints using genetic algorithm. In: 2003 IEEE international symposium on computational intelligence in robotics and automation, vol\u00a02, pp\u00a0624\u2013629","DOI":"10.1109\/CIRA.2003.1222253"},{"key":"139_CR23","doi-asserted-by":"crossref","unstructured":"Auyeung A, Gondra I, Dai H (2003) Evolutionary computing and optimization: Multi-heuristic list scheduling genetic algorithm for task scheduling. In: Proceedings of the 2003 ACM symposium on applied computing, pp\u00a0721\u2013724","DOI":"10.1145\/952532.952673"},{"issue":"3","key":"139_CR24","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1016\/0167-8191(95)00068-2","volume":"22","author":"I Ahmad","year":"1996","unstructured":"Ahmad I, Dhodhi M (1996) Multiprocessor scheduling in a genetic paradigm. Parallel Comput 22(3):395\u2013406","journal-title":"Parallel Comput"},{"key":"139_CR25","doi-asserted-by":"crossref","first-page":"1515","DOI":"10.1016\/j.jpdc.2005.05.028","volume":"65","author":"Y Kwoka","year":"2005","unstructured":"Kwoka Y, Ahmad I (2005) On multiprocessor task scheduling using efficient state space search approaches. J\u00a0Parallel Distrib Comput 65:1515\u20131532","journal-title":"J\u00a0Parallel Distrib Comput"},{"key":"139_CR26","unstructured":"Borriello G, Miles D (1994) Task scheduling for real-time multi-processor simulations real-time operating systems and software. In: Proceedings of RTOSS \u201994, 11th IEEE workshop, pp\u00a070\u201373"},{"issue":"3","key":"139_CR27","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1023\/A:1024299011109","volume":"25","author":"E Onbasioglu","year":"2003","unstructured":"Onbasioglu E, Ozdamar L (2003) Optimization of data distribution and processor allocation problem using simulated annealing. J Supercomput 25(3):237\u2013253","journal-title":"J Supercomput"},{"issue":"1","key":"139_CR28","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1142\/S012905339500004X","volume":"7","author":"S Porto","year":"1995","unstructured":"Porto S, Ribeiro C (1995) A tabu search approach to task scheduling on heterogeneous processors under precedence constraints. Int J High-Speed Comput 7(1):45\u201371","journal-title":"Int J High-Speed Comput"},{"key":"139_CR29","doi-asserted-by":"crossref","first-page":"2071","DOI":"10.1016\/S0305-0548(02)00116-8","volume":"30","author":"P Baptiste","year":"2003","unstructured":"Baptiste P (2003) A note on scheduling multiprocessor tasks with identical processing times. Comput Oper Res 30:2071\u20132078","journal-title":"Comput Oper Res"},{"key":"139_CR30","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/S0020-0190(01)00148-X","volume":"80","author":"S Baruah","year":"2001","unstructured":"Baruah S (2001) Scheduling periodic tasks on uniform multiprocessors. Inf Process Lett 80:97\u2013104","journal-title":"Inf Process Lett"},{"key":"139_CR31","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/S0167-6377(01)00077-3","volume":"29","author":"G Singh","year":"2001","unstructured":"Singh G (2001) Performance of critical path type algorithms for scheduling on parallel processors. Oper Res Lett 29:17\u201330","journal-title":"Oper Res Lett"},{"key":"139_CR32","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/S0166-218X(00)00179-7","volume":"108","author":"C Hanen","year":"2001","unstructured":"Hanen C, Munier A (2001) An approximation algorithm for scheduling dependent tasks on m processors with small communication delays. Discrete Appl Math 108:239\u2013257","journal-title":"Discrete Appl Math"},{"key":"139_CR33","doi-asserted-by":"crossref","first-page":"1195","DOI":"10.1016\/S0167-8191(00)00035-1","volume":"26","author":"J Blazewicz","year":"2000","unstructured":"Blazewicz J, Drozdowski M, Formanowicz P, Kubiak W, Schmidt G (2000) Scheduling preemptable tasks on parallel processors with limited availability. Parallel Comput 26:1195\u20131211","journal-title":"Parallel Comput"},{"key":"139_CR34","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/S0167-8191(00)00096-X","volume":"27","author":"S Manoharan","year":"2001","unstructured":"Manoharan S (2001) Effect of task scheduling on the assignment of dependency graphs. Parallel Comput 27:257\u2013268","journal-title":"Parallel Comput"},{"key":"139_CR35","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/S0167-8191(98)00102-1","volume":"25","author":"A Amoura","year":"1999","unstructured":"Amoura A, Bampis E, Manoussakis Y, Tuza Z (1999) A\u00a0comparison of heuristics for scheduling multiprocessor tasks on three dedicated processors. Parallel Comput 25:49\u201361","journal-title":"Parallel Comput"},{"key":"139_CR36","doi-asserted-by":"crossref","first-page":"824","DOI":"10.1109\/70.897792","volume":"16","author":"X Cai","year":"2000","unstructured":"Cai X, Lee C, Wong T (2000) Multiprocessor task scheduling to minimize the maximum tardiness and the total completion time. IEEE Trans Robotics Autom 16:824\u2013830","journal-title":"IEEE Trans Robotics Autom"},{"key":"139_CR37","doi-asserted-by":"crossref","unstructured":"Bandyopadhyay T, Basak S, Bhattacharya S (2004) Multiprocessor scheduling algorithm for tasks with precedence relation. In: TENCON 2004. 2004 IEEE region 10 conference, vol\u00a02, pp\u00a0164\u2013167","DOI":"10.1109\/TENCON.2004.1414557"},{"key":"139_CR38","doi-asserted-by":"crossref","unstructured":"Lundberg L (2002) Analyzing fixed-priority global multiprocessor scheduling. In: Proceedings of eighth IEEE on real-time and embedded technology and applications symposium, pp\u00a0145\u2013153","DOI":"10.1109\/RTTAS.2002.1137389"},{"issue":"1","key":"139_CR39","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1023\/A:1022856623227","volume":"25","author":"Y Kwok","year":"2003","unstructured":"Kwok Y (2003) On exploiting heterogeneity for cluster based parallel multithreading using task duplication. J Supercomput 25(1):63\u201372","journal-title":"J Supercomput"},{"key":"139_CR40","doi-asserted-by":"crossref","unstructured":"Ahmad I, Kwok Y (1994) A new approach to scheduling parallel program using task duplication. In: Proceedings of international conference on parallel processing, vol\u00a02, pp\u00a047\u201351","DOI":"10.1109\/ICPP.1994.37"},{"issue":"1","key":"139_CR41","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/S0167-8191(02)00181-3","volume":"29","author":"O Kang","year":"2003","unstructured":"Kang O, Kim S (2003) A task duplication based scheduling algorithm for shared memory multiprocessors. Parallel Comput 29(1):161\u2013166","journal-title":"Parallel Comput"},{"key":"139_CR42","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1006\/jpdc.1997.1376","volume":"46","author":"S Darbha","year":"1997","unstructured":"Darbha S, Agrawal D (1997) A task duplication based scalable scheduling algorithm for distributed memory systems. J\u00a0Parallel Distrib Comput 46:15\u201326","journal-title":"J\u00a0Parallel Distrib Comput"},{"key":"139_CR43","unstructured":"Kruatrachue B (1987) Static task scheduling and grain packing in parallel processing systems. PhD thesis, Electrical and Computer Engineering Department, Oregon State University"},{"key":"139_CR44","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/S0141-9331(98)00079-9","volume":"22","author":"T Tsuchiya","year":"1998","unstructured":"Tsuchiya T, Osada T, Kikuno T (1998) Genetics-based multiprocessor scheduling using task duplication. Microprocess Microsyst 22:197\u2013207","journal-title":"Microprocess Microsyst"},{"key":"139_CR45","doi-asserted-by":"crossref","unstructured":"Park G, Shirazi B, Marquis J (1998) Mapping of parallel tasks to multiprocessors with duplication. In: Proceedings of the thirty-first Hawaii international conference on system sciences, vol\u00a07, pp\u00a096\u2013105","DOI":"10.1109\/HICSS.1998.649185"},{"issue":"7","key":"139_CR46","doi-asserted-by":"crossref","first-page":"679","DOI":"10.1109\/71.707547","volume":"9","author":"A Amoura","year":"1998","unstructured":"Amoura A, Bampis E, K\u00f6nig J-C (1998) Scheduling algorithms for parallel Gaussian elimination with communication costs. IEEE Trans Parallel Distrib Syst 9(7):679\u2013686","journal-title":"IEEE Trans Parallel Distrib Syst"},{"key":"139_CR47","unstructured":"Surma D, Sha EH-M (1995) Compile-time communication scheduling on parallel systems. Research report TR-95-3, Dept of Computer Science and Engineering, University of Notre Dame"},{"issue":"1","key":"139_CR48","first-page":"11","volume":"5","author":"D Surma","year":"1998","unstructured":"Surma D, Sha EH-M, Passos N (1998) Collision graph based communication reduction techniques for parallel systems. Int J Comput Appl 5(1):11\u201322","journal-title":"Int J Comput Appl"},{"key":"139_CR49","unstructured":"Surma D, Sha EH-M (1995) Application specific communication scheduling on parallel systems. In: Eighth international conference on parallel and distributed computing systems, pp\u00a0137\u2013139"},{"key":"139_CR50","doi-asserted-by":"crossref","first-page":"863","DOI":"10.1016\/S0167-8191(98)00037-4","volume":"24","author":"Z Liu","year":"1998","unstructured":"Liu Z (1998) Worst-case analysis of scheduling heuristics of parallel systems. Parallel Comput 24:863\u2013891","journal-title":"Parallel Comput"},{"key":"139_CR51","doi-asserted-by":"crossref","unstructured":"Kafil M, Ahmad I (1997) Optimal task assignment in heterogeneous computing systems. In: 6th heterogeneous computing workshop (HCW\u201997), p\u00a0135","DOI":"10.1109\/HCW.1997.581416"},{"key":"139_CR52","doi-asserted-by":"crossref","first-page":"953","DOI":"10.1109\/33.62568","volume":"13","author":"R Eliasi","year":"1990","unstructured":"Eliasi R, Elperin T, Bar-Cohen A (1990) Monte Carlo thermal optimization of populated printed circuit board. IEEE Trans Components, Hybrids, Manuf Technol 13:953\u2013960","journal-title":"IEEE Trans Components, Hybrids, Manuf Technol"},{"issue":"9","key":"139_CR53","doi-asserted-by":"crossref","first-page":"872","DOI":"10.1109\/71.722221","volume":"9","author":"I Ahmad","year":"1998","unstructured":"Ahmad I, Kwok Y (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":"139_CR54","first-page":"1","volume":"5","author":"Y Gao","year":"1998","unstructured":"Gao Y (1998) An upper bound on the convergence rates of canonical genetic algorithms. Complex Int 5:1\u201314","journal-title":"Complex Int"},{"issue":"1","key":"139_CR55","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1109\/72.265964","volume":"5","author":"G Rudolph","year":"1994","unstructured":"Rudolph G (1994) Convergence analysis of canonical genetic algorithms. IEEE Trans Neural Networks 5(1):96\u2013101","journal-title":"IEEE Trans Neural Networks"}],"container-title":["The Journal of Supercomputing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-007-0139-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11227-007-0139-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-007-0139-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,12]],"date-time":"2023-05-12T03:34:05Z","timestamp":1683862445000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11227-007-0139-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,6,1]]},"references-count":55,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,1]]}},"alternative-id":["139"],"URL":"https:\/\/doi.org\/10.1007\/s11227-007-0139-z","relation":{},"ISSN":["0920-8542","1573-0484"],"issn-type":[{"value":"0920-8542","type":"print"},{"value":"1573-0484","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,6,1]]}}}