TY - JOUR
T1 - An Extension of Edge Zeroing Heuristic for Scheduling Precedence Constrained Task Graphs
AU - Abhishek Mishra and Anil Kumar Tripathi
JO - Journal of Information and Computing Science
VL - 2
SP - 083
EP - 096
PY - 2024
DA - 2024/01
SN - 6
DO - http://doi.org/
UR - https://global-sci.org/intro/article_detail/jics/22681.html
KW - clustering, homogeneous systems, parallel processing, scheduling, task allocation. 

AB -  Sarkar's  edge  zeroing  heuristic  for  scheduling  precedence  constrained  task  graphs  on  parallel 
systems  can  be  viewed  as  a  priority  based  algorithm  in  which  the  priority  is  assigned  to  edges.  In  this 
algorithm,  the  priority  is  taken  as  the  edge  weight.  This  can  also  be  viewed  as  a  task  dependent  priority 
function  that  is  defined  for  pairs  of  tasks.  We  have  extended  this  idea  in  which  the  priority  is  a  cluster 
dependent  function  of  pairs  of  clusters  (of  tasks).  Using  this  idea  we  propose  an  algorithm  of  complexity 
O(|V||E|(|V|+|E|)) and compare it with some well known algorithms.