Abstract: An improved genetic algorithm (GA) is presented for the job-shop scheduling problem, and the chromosome representation of the problem is based on the operation-based representation. In view of the limitation of the traditional types of scheduling, a new type of scheduling—full active schedule (FAS) and the schedule generation procedure based on the operation-based representation are presented. In order to avoid premature convergence of the conventional GA, the precedence operation crossover (POX) and approach of the generation alteration model are proposed for the improved GA. The improved GA is applied to solving the classical scheduling, due-dates scheduling and E/T scheduling problems, and the effectiveness of the active schedule, semi-active schedule and full active schedule decoding procedures for optimization algorithm is studied.

Key words: Due-dates scheduling, Earliness/Tardiness scheduling problem, Genetic algorithm, Job-shop scheduling