A Hybrid Genetic Algorithm and Parallel Variable Neighborhood Search for Job Shop Scheduling with an Assembly Stage

In this research, a job shop scheduling problem with an assembly stage is studied. The objective function is to find a schedule that minimizes the completion time of all products. At first, a linear model is introduced to express the problem. Then, in order to confirm the accuracy of the model and to explore the efficiency of the algorithms,the model is solved by GAMS. Since the job shop scheduling problem with an assembly stage is considered as an NP-hard problem, a hybrid algorithm is used to solve the problem in medium to large sizes in a reasonable amount of time. This algorithm is based on genetic algorithm and parallel variable neighborhood search. The results of the proposed algorithms are compared with those of genetic algorithm. Computational results showed that, for small problems, both HGAPVNS and GA have approximately the same performance. In addition, in medium to large problems, HGAPVNS outperforms GA.

Keywords:

Job shop , Genetic Algorithm , Parallel Variable Neighborhood Search.