An effective genetic algorithm for Job shop scheduling problem.

  • Nguyễn Hữu Mùi
  • Vũ Đình Hòa

Abstract

This paper presents an new genetic algorithm for the job shop scheduling problem - JSP.

This new algorithm has its innovations follow: A schedule is encoded by natural numbers; the priority rules of Giffler and Thompson is used to create active schedules; the mutation is implemented on potential individuals and combined with neighborhood search technique; new crossover combines the uniform crossover with GT algorithm and implemented on 3 parents. Một thuật toán di truyền hiệu quảcho bài toán lập lịch Job shop 579 Based on the proposed method, we implement a program to find an approximation optimal schedule for JSP. The program ran on Muth and Thompson’s benchmark problems. Our proposed method is preeminent in comparison with other methods, they are calculation time and ratio of the findable optimal solutions. To prove those, we present an empirical experiment and to compare our results with results of Yamada in the section 4.

điểm /   đánh giá
Published
2014-11-12
Section
Articles