Genetic Algorithms for Job-Shop Scheduling

Autor: Heng-Lei ,Su, 蘇恆磊
Rok vydání: 2002
Druh dokumentu: 學位論文 ; thesis
Popis: 90
The job-shop scheduling problem is an important problem in the operation production management. During the last few decades, an efficient algorithm hasn’t been found yet for optimizing it in polynomial time. Based on the genetic algorithms is used to solve job-shop scheduling problem in this thesis. Firstly, to describe operation process, limits, performance, and the rule on dispatch in the job-shop scheduling problem. Secondly, to introduce the basic framework and important parameters such as crossover rate, mutation rate and population in genetic algorithms. According the genetic algorithm with three different crossover mechanisms such as partial-mapped crossover, one-point crossover, job-based order crossover, a program has been complemented in Fortran 90.The program is verified through four bench-mark instances of the job-shop scheduling problem having minizing makespan from paper by D. C. Mattfeld and R. J. M. Vaessens. Finally, the influence of the parameters in three genetic algorithms in this thesis on the makespan for the job-shop scheduling problems are studied and discussed.
Databáze: Networked Digital Library of Theses & Dissertations