A GENETIC ALGORITHM BASED SOLUTION TO THE FLEXIBLE JOB SHOP SCHEDULING PROBLEM

ABSTRACT

In a flexible job shop, one of the biggest problems encountered is that of scheduling, which is a NP-hard problem. To solve the problem, the Genetic Algorithm (GA) approach was adopted. GA a theory of natural selection that uses operators such as reproduction, cross over and mutation in searching for the best global optimum solution to any optimization problem. GA is a very powerful tool capable of handling complex and practical optimization problems. Hence the aim of this paper is to minimise the tardiness of the jobs (𝑛∑𝑗=1𝑇𝑗) and the makespan (1≤𝑗≤𝑛 max 𝐶𝑗).

The methodology used for this research is the First in First out(FIFO) rule combined with shortest processing time and longest processing time to minimize the makespan and tardiness. A computer program was written using PHP to solve the GA of the flexible job shops.

The results obtained shows how robust the GA is, in solving both partial and total flexibility systems. In one of the instances, the FIFO and SPT rule gave a makespan and tardiness value of 17 and 10, the FIFO and LPT rule got makespan and tardiness values of 51 and 35 respectively. The genetic algorithm program provided an optimal value of 12 for makespan and 2 for tardiness.