Abstract: On the base of relaxation labeling, an algorithm of task scheduling in heterogeneous computing environments is presented. This new method maps data-processing tasks onto heterogeneous resources (i.e., processors and links of various capacities), and takes both computing requirement and communication needs into account. Relaxation labeling can handle a broad range of constraints and its key idea is that the label of a node is typically influenced by the features of the node's neighborhood in the graph. According to neighborhood restrictions, it can gradually get rid of uncorrelated factors and rapidly shrink the searching space. Experimental results show that it performs very well for applications that have high computing and communication requirements or communication-intensive requirements.