MAPPING STRATEGIES FOR SCHEDULING PRECEDENCE GRAPHS ON MULTIPROCESSOR SYSTEMS

Abstract

This work discusses and implements the practical optimization/approximation algorithms for scheduling a set of partially ordered computational tasks, represented in the form of a precedence graph, onto a multiprocessor system so that the overall job response time will be minimized. Problem taken. up in this work belongs to the class of strong NP-hard problems. This work implements two heuristic algorithm's named ETF (Earliest Task First) and HMWBM (Heuristic Mapping with Weighted Bipartite Matching). These allow us to efficiently solve very large scale problems. Numerical examples are also included to demonstrate the effectiveness of these algorithms. III