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

Abstract: To solve the large-scale identical parallel machine scheduling problem with release dates, the objectives of minimizing the total tardy number of jobs, and the total tardiness, a job-clustering-based genetic algorithm was presented. In this algorithm, the whole scheduling process was divided into two phases: the job-clustering phase and the job-sequencing phase. In the job-clustering phase, based on important scheduling characteristics affecting parallel machine scheduling performance, the clustering vector set was formed and all unscheduled jobs were clustered to different job sets by a modified Fuzzy C-Means (FCM) algorithm. In the job-sequencing phase, a rule coding based genetic algorithm was adopted to optimize the job sequence in each cluster. Results of numerical computations on different parallel machine scheduling problems and practical applications showed that the proposed algorithm was suitable for larger-scale parallel machine scheduling problems with release dates.

Key words: parallel machine, scheduling, clustering, genetic algorithm, textile