Solutions to Parallel and Distributed Computing Problems: Lessons from Biological Sciences

5.3 THE PROPOSED APPROACH

Generally, the strength of the GT approach lies in the simplicity of the representation of the problem, while the strength of the GAs lies in their robust capability as an optimization tool [21]. Also, the parallel nature of GAs enable the use of parallel processors to speed up computations [3], thus reducing the overall computational cost and speeding up the convergence rate. In this section, we propose a structured-genetic (StrucGene) approach will capture the strengths of both the GT approach as well as the robust nature of GAs.

The StrucGene framework employs a structured method to represent the scheduling problem in a simple and elegant fashion. This is followed by using a GA to obtain near-optimal solutions in a reasonable amount of time.

The StrucGene framework was developed with the following objectives in mind:

1. The cost function is a function of the communication overhead, the processing costs, and the precedence constraints
2. A near-optimal solution can be found rapidly
3. An extension to an arbitrary number of processors can be easily achieved
4. A mechanism for load balancing is built into the cost function
5. Consider the queuing delays at the receiving end

5.3.1 Representation of the Scheduling Problem

The model offers simplicity in representation by exploiting the use of matrices. The model has been developed with the following assumptions:

1. It is comprised of an arbitrary number m of processing elements
2. The processing elements are connected via ...