Implementation and Evaluation of Novel Parallel Hybrid Approach for Solving Job Shop Scheduling Problem

Since from last three decades, genetic algorithms (GA) are most popular approach for solving number of optimization research problems. The shop scheduling problem is well known and widely studied problem in which the number of jobs should be processed over the set of available machines so that optimization criteria should be satisfied. To solve the problem of job shop scheduling (JSS) problem, there are number of methods already proposed with goal of improving the efficiency and performance of problem solving. The efficiency of JSS problem solutions is evaluated in terms of three time related performance metrics such as flow average time, waiting time and total execution time. The aim of any JSS problem solution is to minimize the performance of these three metrics. In this paper, we designed novel solution for solving the job shop scheduling problem using genetic algorithm. The proposed solution is based on parallel genetic algorithm in which modified crossover and mutation operations introduced. The processing of genetic algorithm is performed parallel which helps in reduction of time performance while solving any of JSS problem. In this paper we implemented the proposed approach using MATLAB and evaluated the performance on different test cases of JSS problems such as Dmu07, YN01, YN04, LA38, 3x3 and 6x6.