Production Scheduling Approaches

4.1. Genetic Algorithms (GAs)

The methodology of a GAs - based on the evolutionary strategy- trasforms a population (set) of individual objects, each with an associated fitness value, into a new generation of the population occurring genetic operations such as crossover (sexual recombination) and mutation (fig. 3).

The theory of evolutionary computing was formalized by Holland in 1975. GAs are stochastic search procedures for combinatorial optimization problems based on Darwinian principle of natural reproduction, survival and environment's adaptability. The theory of evolution is biologically explained, the individuals with a stronger fitness are considered better able to survive. Cells, with one or more strings of DNA (i.e., a chromosome), make up an individual. The gene (i.e., a bit of chromosome located into its particular locus) is, responsible for encoding traits (i.e., alleles). Physical manifestations are raised into genotype (i.e., disposition of genes). Each genotype has is physical manifestation into phenotype. According to these parameters is possible to define a fitness value. Combining individuals through a crossover (i.e., recombination of genetic characteristics of parents) across the sexual reproduction, the chromosomal inheritance process performs to offspring. In each epoch a stochastic mutation procedure occurs. The implemented algorithm is able to simulate the natural process of evolution, coupling solution of scheduling route in order to determinate an optimal tasks assignment. Generally, GA has different basic component: representation, initial population, evaluation function, the reproduction selection scheme, genetic operators (mutation and crossover) and stopping criteria. Central to success of any GA is the suitability of its representation to the problem at hand. This is the encoding from the solution of the problem domain to the genetic representation.

During the last decades, different representation's schemata for JS have been proposed, such as permutation with repetition. It uses sequence of repeated jobs identifier (e.g., its corresponding cardinal number) to represent solutions. According to the instance in issue, each of the N jobs identifiers will be repeated M times, once for each task. The first time that job's identifier, reading from left to right, will appear means the first task of that job. In this way, precedence constraints are satisfied. The redundancy is the most common caveat of this representation. A proposal of permutation with repetition applying a Generalized Order crossover (GOX) with band |2 3 1 1| of parent 1 moves from PARENT1 [3 2 3 1 1 1 3 2 2] and PARENT2 [2 3 2 1 3 3 2 1 1] to CHILD1 [2 3 1 1 3 2 3 2 1] and CHILD2 [3 2 1 3 2 1 1 3 2].

Figure 3.
The Genetic Algorithms (GAs) model; 3a. the pseudo-code of a GA; 3b. the flow chart of a general GA.

A mutation operator is applied changing the genes into the same genotype (in order to generate only feasible solutions, i.e., without the rejection procedure). Mutation allows to diversify the search over a broader solution domain and it is needed when there is low level of crossover. Among solutions, the allocation with favourable fitness will have higher probability to be selected through the selection mechanisms.

Another important issue for the GA is the selection mechanism (e.g., Tournament Selection procedure and Roulette Wheel as commonly used - their performances are quite similar attending in the convergence time). The tournament selection procedure is based on analogy with competition field, between the genotypes in tournament, the individual which will win (e.g., the one with the best fitness value) is placed in the mating pool. Likewise, in the roulette wheel selection mechanism each individual of population has a selection’s likelihood proportional to its objective score (in analogy with the real roulette item) and with a probability equal to one of a ball in a roulette, one of the solutions is chosen.

It is very important, for the GAs success, to select the correct ratio between crossover and mutation, because the first one allows to allows to diversify a search field, while a mutation to modify a solution.