Genetic algorithm approach to job shop scheduling and its use in real-time cases

In this paper we present a GA (Genetic Algorithm) approach combined with the concept of GT (Group Technology) to solve the job shop scheduling problems. The main idea is to organize all these jobs into groups using GT and solve such a group scheduling problem with GA. Due to the similarities between jobs within a group, scheduling (a group) can be treated easily as if it is a flow shop problem. Since the complexity of the problem has been simplified, the time spent in finding a feasible scheduling of the whole problem can be decreased. Ideas of using GA in real-time cases are discussed and explored. In particular, the concept of using a nearoptimal evolution generation n* in GA is introduced. The value of n* is related to the desired performance index, and using n* in GA may ensure more effective searching. An illustrative example is given at the end of the paper.