Applying Genetic Algorithms to the Load-Balancing Problem

In the Parallel Processing literature, the Load-Balancing Problem consists of distributing evenly a set of tasks among the processors of a parallel machine or a distributed system, so that the total execution time of all tasks is minimized. Hence, we want to minimize the parallel processing time (PPT) of a set of n tasks — each of them with a previously-known execution time — on m processors (m ≥ 2 and n > m), given by the following objective function: PPT=max{Ti},i=1,2,…n, where Ti is the processing time assigned to processor i, that is the total execution time of all tasks scheduled to processor i.