Application of Genetic Algorithm in Loading
In order to explain the implementation of genetic algorithm above machine loading problem, an example data set comprising of 8 tasks and 4 machines are taken. Each the concerns information of the tasks and initial capacity of the machines are described in Tables no.1 and 2, respectively. As stated previous, the process of genetic algorithm starts along with the initialization of population such are randomly produced. In machine loading context, every individual corresponds to the whole number of the jobs such are to be assigned on the machine in a sequential way. Afterward the initialization, fitness consequent to each individual in the complete population is estimated for the selection of the parents such will take part in the reproduction process to produce the individuals for next generation. In machine loading context, fitness of the individuals is computed on the basis of overall objective function such is the weighted combination of throughput values and system balance. Fitter individuals have the best chance for the selection and vice-versa.
Table no.2: Description of a Sample Loading Dataset
|
Job No.
|
Batch Size
|
Operation
Number
|
Unit Processing Time
|
Machine
Number
|
Tool Slot
Needed
|
|
1
|
8
|
1
|
18
|
3
|
1
|
|
2
|
9
|
1
|
25
|
1, 4
|
1
|
|
2
|
24
|
4
|
1
|
|
3
|
22
|
2
|
1
|
|
3
|
13
|
1
|
26
|
4, 1
|
2
|
|
2
|
11
|
3
|
3
|
|
4
|
6
|
1
|
14
|
3
|
1
|
|
2
|
19
|
4
|
1
|
|
5
|
9
|
1
|
22
|
2, 3
|
2
|
|
2
|
25
|
2
|
1
|
|
6
|
10
|
1
|
16
|
4
|
1
|
|
2
|
7
|
4, 2, 3
|
1
|
|
3
|
21
|
2, 1
|
1
|
|
7
|
12
|
1
|
19
|
3, 2, 4
|
1
|
|
2
|
13
|
2, 3, 1
|
1
|
|
3
|
23
|
4
|
3
|
|
8
|
13
|
1
|
25
|
1, 2, 3
|
1
|
|
2
|
7
|
2, 1
|
1
|
|
3
|
24
|
1
|
3
|
Detailed Computation
Given are the steps to apply genetic algorithm upon the machine-loading problem over the sample dataset shown in given Tables no.1 and 2.
Step 1: Initialization of the Control Parameters
(a) Population size (pop_ size) = 4
(b) Crossover probability (Cp) = 0.4
(c) Mutation probability (Cm) = 0.1
(d) Maximum number of generations (max_gen) = 30
Step 2: Initialization
In this step the population is initialized by random sequence of the jobs. Assume the initial sequence of the four populations is as given below:
Pop_ size 1 = [1 7 4 8 5 6 3 2];
Pop_ size 2 = [6 8 5 4 2 3 1 7];
Pop_ size 3 = [1 3 6 58 7 2 4];
Pop_ size 4 = [8 4 3 6 7 5 2 1].
Step 3: Evaluation
Estimate the value of the objective function equally for the whole population size.
Step 4: Crossover
Now, we have considered the two point crossover that is defined as given below.
Assume the first parent is Pop_ size 2 = [6 8 5 4 2 3 1 7] other one is Pop_size 4 = [8 4 3 6 7 5 2 1]. The produced child because of the crossover are child 1 = [8 4 5 4 2 5 2 1] and child 2 = [6 8 3 6 7 3 1 7].
Step 5: Mutation
Suppose that on parent 1 = [1 7 4 8 5 6 3 2] the mutation operator is applied. After that the child generated as a result of it is child 1 = [1 7 4 5 8 6 3 2].
Step 6: Selection and Evaluations
After the crossover application and mutation genetic operators, double the population size of chromosomes are generated. After that they are sorted in order of the raising value of the objective function and suitable are chosen equal to the population size.
Step 7: Stopping Criteria and Results
After specific pre-determine number of iterations, algorithm stops and the suitable objective function value is acquired.
Last Results
a) The best job sequence = [1 7 3 5 4 6 2 8].
b) Fitness value consequent to the best sequence = 0.796354.
c) System unbalance = 14.
d) Throughput = 48.