A DAG scheduling scheme on heterogeneous computing systems using double molecular structure-based chemical reaction optimization

• Applying CRO to solve DAG scheduling problems in heterogeneous computing systems.
• Developing DMSCRO by adapting the conventional CRO framework.
• Designing a new solution encoding method for DAG scheduling.
• Designing new operations for performing elementary chemical reactions in this work.
• Conducting experiments to verify the effectiveness and efficiency of the DMSCRO.

A new meta-heuristic method, called Chemical Reaction Optimization (CRO), has been proposed very recently. The method encodes solutions as molecules and mimics the interactions of molecules in chemical reactions to search the optimal solutions. The CRO method has demonstrated its capability in solving NP-hard optimization problems. In this paper, the CRO scheme is used to formulate the scheduling of Directed Acyclic Graph (DAG) jobs in heterogeneous computing systems, and a Double Molecular Structure-based Chemical Reaction Optimization (DMSCRO) method is developed. There are two molecular structures in DMSCRO: one is used to encode the execution order of the tasks in a DAG job, and the other to encode the task-to-computing-node mapping. The DMSCRO method also designs four elementary chemical reaction operations and the fitness function suitable for the scenario of DAG scheduling. In this paper, we have also conducted the simulation experiments to verify the effectiveness and efficiency of DMSCRO over a large set of randomly generated graphs and the graphs for real-world problems.