Solving Job-Shop Scheduling Problems by Genetic Algorithms Based on Building Block Hypothesis

In this paper, we propose a new genetic algorithm for job-shop scheduling problems(JSP). The proposed method uses the operation-based representation, based on schema theorem and building block hypothesis, a new crossover is proposed: By selecting short, low order highly fit schemas to genetic operator, the crossover can exchange meaningful ordering information of parents effectively and can search the global optimization. Simulation results on MT benchmark problem coded by C++ show that our genetic operators are very powerful and suitable to job-shop scheduling problems and our method outperforms the previous GA-based approaches.