免疫アルゴリズムによるジョブショップスケジューリング問題の最適化

概要

論文の詳細を見る
The job-shop problem is a classical but yet modern problem. Because it belongs to the NP-hard problem and it is almost impossible to find out the exact solution, many heuristic methods have been proposed. Although dispatching rule methods have been adopted to determine the practical schedules for a long time, their performance is limited. Recently, the genetic algorithm has been proposed as a powerful tool to solve the problem. Authors have applied the genetic algorithm to the job-shop problem by introducing the new chromosome representation, as well. While the genetic algorithm obtains a good approximate solution, it only searches for one local solution. In making a good schedule depending on the manufacturing situation, it is often necessary to present various types of schedules. The purpose of this study is to develop the new method, which allows us to represent a various types of schedules. The immune algorithm is employed in solving the job-shop problem to achieve this purpose. The immune algorithm can be found out in a creature as well as the genetic algorithm. Its main feature is to store the solution as immunity into the memory and to suppress the similar solution by use of the stored solution. The genetic algorithm is used as a searching procedure for the solution. Numerical experiments verify that the immune algorithm obtains various types of schedules.
旭川工業高等専門学校の論文
2004-03-20