Abstract: Considering that fact the structure of parallel program can induce the randomcity of tasks＇ computing and communication cost,the definition of stochastic DAG is expanded. Some researches on parallel tasks scheduling algorithms have been done based on this

Key words: Expanded stochastic DAG, EST, SCP algorithm, SSCP algorithm