Abstract:Task scheduling is one of the crucial factors influencing the efficiency of a network of workstations. Fork-Join task graphs can represent many parallel structures. All of the existing algorithms which schedule Fork-Join task graphs have ignored the problem that communications cannot be executed in parallel in non-fully-connected NOW, and some of algorithms with high efficiency even did not take the problem of how to save the processors into account. In this paper, a new static task scheduling algorithm called TSA_FJ is proposed,which is based on task duplication and trying to synthetically take the problems of schedule length shortening,unparallel communications and processor saving into account.By randomly generating the task execution time and communication time,several fork-Join task graphs are got and the scheduling results of TSA_FJ are compared with that of other algorithms for the generated task graphs.It shows that TSA_FJ algorithm has the shortest scheduling length and uses much less processors.It is much suitable to non-fully-connected NOW.