Journal of Advanced Research in Science and Technology
Volume 6, Numéro 1, Pages 949-961
2019-02-28

Tabu Search & Gpu-based Genetic Algorithm To Solve The Job Shop Scheduling Problem With Blocking

Authors : Aitzai Abdelhakim . Dabah Adel . Boudhar Mourad .

Abstract

This paper deals with the resolution of the job shop problem with blocking, where the machines have a limited or no storage space. To solve this problem, we compare between two different metaheuristics based on Tabu Search TS and Genetic Algorithms GA. The first one lays on a very efficient neighbourhood exploring and evaluation techniques, which improve the reliability of the method. These techniques operate on the critical path found in the alternative graph and always construct feasible solutions. The second lays on two different paradigms of parallelization with GA. The first uses a network computers and the second use GPU with CUDA technology. The results are very interesting. In both methods, we obtain a very significant reduction of computation time compared with the existing literature results.

Keywords

Job shop, Blocking, Tabu search, Neighborhood, Genetic algorithm, GPU;