Conference Paper (Genetic Algorithm)

A genetic algorithm (GA) is a search technique used in computing to find true or approximate solutions to optimization and search problems. Genetic algorithm is categorized as a global search heuristics. Genetic algorithm is a particular class of evolutionary algorithm that use techniques inspired by evolutionary biology such as inheritance, mutation, selection and crossover.

An initial schedule is generated using FIFO technique. Genetic algorithm is used as an optimizer to alter the initial schedule to find a minimum processing time.

Chromosome Strings

Parameters that are taken from initial FIFO schedule will be transformed into a population of ignition chromosomes. The parameter is a pair of an operation and its corresponding set of equipments to choose from.

The first part of the strings is responsible to keep the identification of operation. The second part keeps the corresponding set of equipments to choose from. An operation will choose equipment from the set to execute the operation.

Crossover

A biological analogy to crossover is having parents with blue and brown eyes will determined the eyes colour of their children. In the system, only the equipment string in the chromosome is involved in crossover.

A crossover point on the parent will be randomly selected. All data beyond that point will be swapped between the two selected parents. The two parents are chose randomly using a Roulette Wheel selection method. After the process, there will be two new children chromosomes.

Mutation

Mutation is a transforming process of a single chromosome. The algorithm will choose a chromosome randomly and alters one bit of the string in the chromosome. However this method isn’t guaranteed to produce a better schedule.