关键词: 跨单元调度, 超启发式算法, 决策块, 聚类, 蚁群算法

Abstract:

According to the actual production situation of China's manufacturing industry, a hyper-heuristic algorithm based on K-means clustering is proposed for inter-cell scheduling problem of flexible job-shop. K-means clustering is applied to group entities with similar attributes into the corresponding work cluster decision blocks, and the ant colony algorithm is used to select heuristic rules for each decision block. The optimal scheduling solutions are generated by using corresponding heuristic rules for scheduling of entities in each decision block. Computational results show that, the computational granularity is properly increased by the form of decision blocks, and the computational efficiency of the optimal algorithm is improved. The clustering algorithm could group the processed entities with similar attributes and the suitable rules for entities with different attributes are easy to be chosen. The proposed approach not only improves computational efficiency but also exhibits good optimization performance, and provides a scientific optimization solution for inter-cell scheduling problems.

Key words: inter-cell scheduling, hyper-heuristic algorithm, decision block, clustering, ant colony optimization