Solving Industrial Based Job-Shop Scheduling Problem by Distributed Micro-Genetic Algorithm with Local Search

摘要

Genetic algorithms (GAs) have been found to be suitable for solving Job-Shop Scheduling Problem (JSSP). However, convergence in GAs is rather slow and thus new GA structures and techniques are currently widely investigated. In this paper, we propose to solve JSSP using distributed micro-genetic algorithm (micro-GA) with local search based on the Asynchronous Colony Genetic Algorithms (ACGA). We also developed a representation for the problem in order to refine the schedules using schedule builder which can change a semi-active schedule to active schedule. The proposed technique is applied to Muth and Thompson's 10x10 and 20x 5 problems as well as a real world JSSP. The results show that the distributed micro GA is able to give a good optimal makespan in a short time as compared to the manual schedule built for the real world JSSP.