Task scheduling for directed cyclic graph using matching technique

• Main Authors: Ariffin, Wan Nor Munirah, Salleh, Shaharuddin
• Format: Article
• Published: Hikari Ltd. 2015
• Subjects: QA Mathematics
• Online Access: http://eprints.utm.my/id/eprint/58885/; http://dx.doi.org/10.12988/ces.2015.56193
• Institution: Universiti Teknologi Malaysia

The scheduling and mapping of task graph to processors is considered to be the most crucial NP-complete in parallel and distributed computing systems. In this paper, the theoretical graph application using matching is presented to assign a number of tasks onto two processors. This paper addresses a directed-weighted cyclic graph. The effort is to reduce the graph onto directed acyclic graph. A co-comparability graph is presented in order to assign the task onto two processors. Combining several innovative techniques lead to an efficient graph-mapping concept, called DCGSimplify. Our simulation model found that the proposed techniques and algorithms are easy to be implemented.