Using A Learning Architecture Based On Symbiotic Genetic Algorithm To Solving Flexible Job-Shop Scheduling Problems

Job-shop Problem (JSP) is the simplified model of many factual problems, and to find a best approach to solve JSP is an important task in scheduling and optimization areas. But JSP is an NP-hard problem. It's almost impossible to find an algorithm with polynomial computational complexity. Genetic algorithms (GA) , which is an global random searching algorithm, has been widely used in solving JSP by transforming it's possible results to the searching space that GA can identify. GA can produce new chromosomes by reform old individuals with crossover and mutation operation, and by updating population all the while, the algorithm can finally find the best results.In GA's evolving process, two parent chromosomes always reduce new individuals by exchanging their parts of chromosome. If we can conserve the best traits of parent chromosomes and make it appear in offspring, then we may get the optimal solutions more easily and enhance GA's efficiency.In this article, we get many optimal chromosomes by using GA to solve JSP for many times. After analyzing the problem, we summarize some concept attributes that can express the problem well and give a new concept hierarchy. We then extract knowledge from these optimal chromosomes with data mining algorithm based on these attribute, and finally get some sets of scheduler rules, which approximates the genetic algorithm's scheduler. Those rules just reflect the common traits of chromosomes. If we can identify these traits when it comes out first time and copy it to the offspring, the later population will have a high quality and the efficiency of algorithm will be enhanced.At the last section of this article, we try to solving a flexible job shop schedule problem with only operation flexibility with above idea. According the character of problem, we improve genetic algorithm based on symbiotic mechanism and then integrate it to an effective learning architecture. We propose an efficient genetic representation and a set of self-adaptive probability function; we also improve the learning architecture to make it more efficient in learning the good traits. We divide the problem into two sub-problems, and encode them into two different populations in symbiotic GA. An individual in a population represents a partial solution to the entire problem. So an entire solution is constructed by combining two such partial solutions. During evolving progress, this architecture can extract best traits from best chromosomes in current population and these traits will be used in offspring. The experimental results show that the proposed algorithm performs well in quality of schedules.