关键词: 调度, 并行机, 遗传算法, 工件聚类

Abstract: A new genetic algorithm was presented for large-scale scheduling problems, in which the chromosomes were initiated and founded by the jobs clusters. Firstly, an advanced fuzzy C-means clustering algorithm was used to divide the jobs into different clusters according to important characteristics which affected the scheduling. Then, a encoding method based on double linear-linked-list was proposed to represent the processing sequences as well as the tasks'numbers of the jobs'clustering on the parallel machines. Corresponding crossover, mutation operators were also designed. Finally, this algorithm was testified by analysis and application. Results demonstrated that it could acquire a satisfactory optimization quality within a reasonable time period.

Key words: scheduling, parallel machines, genetic algorithms, job clustering