| Abstract: | Grids or multicluster computing environments are becoming increasingly popular to both scientific and commercial applications. Process scheduling remains a central issue to be effectively resolved in order to exploit the full potential that the grid or multicluster environment can offer. We use a directed acyclic graph (DAG) to model a process or an application where the nodes of the DAG represent the tasks of the process. Prior to the execution of a process in a multicluster environment, the tasks are required to be mapped onto the clusters. In this article, it is shown that the algorithm developed by He et al. L. He, S.A. Jarvis, D.P. Spooner, D. Bacigalupo, G. Tan, and G.R. Nudd, Mapping DAG-based applications to multiclusters with background workload, Proceedings of the 2005 IEEE International Symposium on Cluster Computing and the Grid, Cardiff, 2005, pp 855–862.] for the multicluster DAG mapping problem can be significantly improved by incorporating the task duplication strategy. The proposed process scheduling algorithm has a time complexity O(| V|2(r+d+1)), where |V| represents the number of tasks; r, the number of clusters; and d, the maximum in-degree of tasks. |
