Development of Improved Genetic Algorithm for Makespan Optimization of Flexible Job Shop Scheduling Problem

Abstract

Early product development is dire need of the current era of industrial revolution. Product development process has been accelerated using Flexible Manufacturing Systems (FMS). Allocation of resources to jobs and their scheduling in flexible manufacturing systems is a combinatorial optimization problem that has been proven to be NP-hard. The research area is so fascinating and challenging that a handsome amount of research has been published in the last two decades. This research is focused on the makespan optimization of the flexible job shop scheduling problem. Firstly an Improved Genetic Algorithm integrated with scheduling Rules (IGAR) is developed. This algorithm has an adaptive mutation and crossover probabilities for search optimization. Scheduling is done using classical scheduling rules like Shortest Processing Time and Longest Processing Time. An improved version of Most Work Remaining rule is also proposed. The algorithm is then implemented in MATLAB and tested on standard benchmark problems of Fattahi. Another novel configuration of GA is then proposed with Cantor Pairing (CPGA) is then proposed. This algorithm has novel chromosome representation along with crossover and mutation operators. The algorithm operates in an integrated manner and generates solutions for makespan optimization. This algorithm is also tested on similar benchmark problems. The results of two algorithms are compared with already published best-known results for the similar benchmark problems and improved results are presented. In the end, conclusions and future research directions are also identified.