Genetic Algorithms and Simulated Annealing
Dr Christian Hicks, Department of MMM
Genetic Algorithms (GA) are stochastic search techniques for approximating optimal solutions within complex search spaces (Goldberg 1989). The technique is based upon an analogy with biological evolution, in which the fitness of individual determines its ability to survive and reproduce. The GA mechanism starts by encoding the problem to produce a list of genes. The genes are represented by either numeric (binary or real), or alphanumeric characters. The genes are then randomly combined to produce a population of chromosomes, each of which represents a possible solution. Genetic operations are performed on chromosomes that are randomly selected from the population. This produces offspring. The fitness of these chromosomes is then measured and the probability of their survival is determined by their fitness.
Genetic Algorithms have been widely applied to scheduling problems (Croce et al. 1995, Reeves 1995, Kim and Kim 1996, Tsujimura 1997). Each gene represents an operation, whilst the chromosome represents the sequence of the entire schedule. Croce et al. and Reeves compared GAs with other methods for solving production scheduling problems. Reeves found that GAs obtained better solutions more quickly than Simulated Annealing. Croce found that GAs produced better results than the shifting bottleneck procedure (Adams et al. 1988), Simulated Annealing and Taboo Search. However, this was at the expense of longer computational times. Conventional optimisation techniques, Simulated Annealing and Taboo Search perform a unidirectional search using a single candidate solution. Genetic Algorithms perform a multidirectional search by maintaining and using a population of potential solutions. Each iteration of the GA process therefore exploits the best solutions within the population and also explores different parts of the solution space simultaneously .
Kim et al. (1996) used GAs for production scheduling in job shops. They used an aggregate production planning method that assumed all activities took place in either a machine shop or an assembly shop. This model therefore contained only two resources. The inherent assumption is that all machining and assembly resources have similar capabilities. In practical situations, this assumption is often inappropriate. Tsujimura et al. (1997) proposed a method of encoding chromosomes that guaranteed that feasible and active schedules were produced by the evolutionary process. Their chromosomes consisted of a series of part codes. If a job had n operations the part code would appear n times in the chromosome. These were latter mapped onto the routing which was always in predefined order. This approach did not include part precedence or assembly relationships.
A good schedule co-ordinates the supply of components to meet assembly requirements and ensures that capacity constraints are not exceeded. The manufacture of components, assemblies and subassemblies may require the completion of many operations, which may require multiple resources. This gives rise to precedence relationships associated with operation and assembly sequences. Each operation may also consist of a number of activities of varying duration, such as set-up, machining and transfer, which also have precedence relationships. This breakdown of operations is important in batch production environments, or when the activities are not of uniform duration. Many job shop studies have ignored set-up and transfer times. The models used have, therefore not been valid representations of real manufacturing systems .
Figure 1. A general structure of Genetic Algorithms developed for production scheduling
an Initial Population of Chromosomes
The genes are then randomly combined to produce a population of chromosomes (candidate solutions). Each chromosome is divided into n sub-chromosomes that represent the sequence of work for n resource (see figure 2).
Figure 2. Sub-chromosome representation
and reorder operations:
this identifies impossible routings and converts them into a feasible sequence
of operations. For example, in figure 3, the sequence of operations has
the second operation on part 11 before the first operation. This stage
of the repair process swaps these operations using the copying mechanism
Figure 3. Check and reorder operations repair process
The procedure starts by checking number of operations required for the each part. If there is more than one operation, the sequence of operations needs to be checked. If the operations are not in sequence they are copied to a temporary string, they are then reordered in the correct order and then copied back into the chromosome. This procedure is repeated for all parts;
and reorder precedence, which
ensures that all components and subassemblies are sequenced before their
subsequent assembly. The procedure starts with a chromosome that may represent
either a feasible or infeasible schedule. The chromosome consists of a
set of sub-chromosomes that represent the sequence of operations on each
resource. The repair process is based upon the copying mechanism shown
in figure 4, which is performed on each sub-chromosome.
a) Copying Sub-Chromosomeb) Product Structure
Figure 4. Check and reorder part precedence repair process
The procedure starts at the beginning of the sub-chromosome and checks the level of each item in the product structure. Items at the bottom level are copied in the same order that they appear in the sub-chromosome. The procedure then repeats this process for each higher level of the product structure. This approach places operations associated with lower levels of product structure at the beginning of the sequence. Operations performed on items at higher levels will be copied to the end of the revised sequence.
The schedule represented by each chromosome is evaluated using the objective function given in equation (1). This function aggregates the penalty cost of both earliness and tardiness. The optimum solution achieves minimum total cost:
Total costs =earliness costs + lateness costs
=å Pe(Ec+Ep) + å Pt(Tp)(1)
Ec= max (0, Dc - Fc)
Ep= max (0, Dp - Fp)
Tp= max (0, Fp - Dp)
Pe= Penalty rate of earliness (pounds per day)
Tp= Tardiness of final product (days)
Fc= Finish time of component (date)
The final stage of the Genetic Algorithm is to select the same number of chromosomes that are included in the initial population for the next generation. The probability of survival, and the number of replicates of a chromosome in the next generation, is determined by the fitness using the roulette wheel approach (Goldberg 1989).
Chris Hicks Home Page
© Dr Christian Hicks & Pupong Pongcharoen, Department of Mechanical, Materials and Manufacturing Engineering, University of Newcastle upon Tyne