This assignment involves the use of the genetic algorithm to solve a task-scheduling problems. A set of tasks must be performed on a set of processors. Each task consists of two times: time to execute the task, and time to communicate the results to the master processor, p0. All processors share one or more communication lines; each line can send only one message at a time. Tasks that are run on the master processor require no communication time. When no communication channels are available, a processor must wait to perform the communication portion of its current task. The goal is to determine a schedule, i.e., a set of assignments of tasks to processors, that minimizes the total completion time of the task set.
The use of GA's to solve this problem requires two basic components:
1. individuals representing schedules and populations of schedules
2 a simulator that computes total completion times for schedules
The first component is easily created using EVOKE. Read Kidwell's paper (ICGA, 1993) for a few tips on representations of schedules.
The simulator will require a bit more effort. It need not be a complicated simulator, but it should handle a user-defined number of processors and communication lines. Its only purpose is to compute total completion times, which will serve as the basis for each schedule's fitness.
Run your schedule-evolving system on the sample task in Kidwell's paper:
(7 16) (11 22) (12 40) (15 22) (17 23)
(17 23) (19 23) (20 28) (20 27) (26 27)
(28 31) (36 37) (31 29) (28 22) (23 19)
(22 18) (22 17) (29 16) (27 16) (35 15)
Here, each pair represents the execution and communication times for a task. According to Kidwell, the minimum completion time for this task set on 3 processors (1 communication line) is 202 timesteps. Can your GA find the solution? It's not easy! Proper choice of fitness function is important.
Formally, your assignment is to write the simulator and the EVOKE subclasses and to run your system many times while varying key parameters such as the mutation and crossover rates, the number of crossover points, the population size and the selection mechanism. Describe your search for the magical 202 in terms of the parameter settings that were more and less successful. Explain why you think various settings were good/bad. Achieving 202 is NOT a requirement for getting full credit for this assignment.