Genetic Algorithms and Simulated Annealing

Dr Christian Hicks, Department of MMM Engineering,
Stephenson Building, University of Newcastle upon Tyne, Newcastle NE1 7RU.

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 [20].

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 [21].

Bi-criteria Genetic Algorithms (BCGA) for scheduling complex products

In this research, the general procedure for Genetic Algorithms developed by Goldberg (1989) was modified. A repair process based upon precedence adjustment was used in order to rectify infeasible schedules that can be produced by genetic operations. This ensures the appropriate co-ordination of component manufacture and assembly operations. The algorithm is illustrated in figure 1.

Figure 1. A general structure of Genetic Algorithms developed for production scheduling

Encoding Gene
Each operation is encoded into a gene that is represented using an alphanumeric string which has two parts. The first denotes the current operation number and the second is the part code, which is the primary key through which process times, due date and assembly relationships are obtained. 

Generating 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

Genetic Operations
Chromosomes are then randomly selected from the population to perform either crossover or mutation operations. Crossover combines the characteristics of two parents to produce an offspring, whilst mutation produces random changes in a single chromosome. However, the offspring produced by a genetic operation may represent an infeasible schedule due to an impossible routing or assembly sequence. 

Repair Processes
Repair procedures are included that identify and rectify infeasible schedules. There are four stages:

·Check 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 shown.
 



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;

·Check 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. 
·Check capacity and adjust timing:a sequence of operations does not become a schedule until all timing constraints are satisfied, since it is not possible to start an operation until the previous operation has been completed. When a part has operations on more than one resource, the schedule may need modification to ensure that capacity is not exceeded. The start set-up operation cannot take place until the previous operation on the part is completed and the previous operation on the sub-chromosome (resource) is also finished. These timings are calculated using the sequences of operations on each chromosome, together with information on the duration of operations. This may introduce a delay between operations.
·Identify and avoid deadlock:when multiple resources are scheduled, it is possible that machine i is unable to perform an operation, as it is awaiting the part from machine j, whilst machine j cannot perform its operation as it is awaiting a part from machine i. This situation occurs for parts 11 and 12 shown in figure 2. The procedure for identifying the deadlock situation starts from the first operation of sub-chromosome 1. Operations that have no precedence relationship can be performed. They are therefore added to a list of legal operations. The logic then moves to the next gene within the sub-chromosome. If this is a second or subsequent operation a check is made to ensure that the previous operation appears in the list of legal operations. If the precedence constraint is satisfied the operation is added to the list. Otherwise the control moves to the next sub-chromosome when the process is repeated. At the end of this process a pointer will identify the first deadlocked operation on each resource. The program will then randomly select a sub-chromosome. The deadlocked operation is then swapped with its successive operation. The process is then repeated until all operations appear in the list of legal operations. 

Fitness Function
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)

Where:
Ec= max (0, Dc - Fc)
Ep= max (0, Dp - Fp)
Tp= max (0, Fp - Dp)

Notation
Pe= Penalty rate of earliness (pounds per day)
Ec= Earliness of component (days)
Ep= Earliness of final product (days)
Pt= Penalty rate of tardiness (pounds per day)
Tp= Tardiness of final product (days)
Dc= Due date of component
Fc= Finish time of component (date)
Dp= Due date of final product
Fp= Finish time of final product (date)

Roulette Wheel
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).

Study Opportunities

We have a continuing interest in schedule optmisation, particularly in the capital goods industry. We have also applied the Simulated Annealing Optimisation approach to manufacturing layout. We continue to explore a range of methods including Genetic Algorithms, Simulated Annealing and Taboo Search.

Chris Hicks Home Page

© Dr Christian Hicks & Pupong Pongcharoen, Department of Mechanical, Materials and Manufacturing Engineering, University of Newcastle upon Tyne