关键词: 瓶颈识别, 瓶颈簇, 聚类算法, 作业车间调度, 多属性决策

Abstract: Traditional bottleneck identification methods in job shops lack of scientific method and theoretical basis defining the size, classification and hierarchy of multiple bottleneck candidates. To address the issue, a set of innovative concepts including Machine Cluster,Bottleneck Cluster, Primary Bottleneck Cluster and Primary Bottleneck Cluster Order was proposed and a job shop bottleneck cluster identification model was established. Considering the fact that there exist primary and secondary relationships among machines, and machine itself owns naturally multidimensional feature attributes, an identification approach for bottleneck cluster in a job shop was proposed based on hierarchical clustering algorithm and multi-attribute decision making theory. First, the feature attributes of machine were selected and their attributes values were calculated based on the optimal scheduling solution obtained by using immune evolutionary algorithm. Second, using hierarchical clustering algorithm, the set of machine clusters and the corresponding dendrogram were gained corresponding to different clustering distances. Third, using TOPSIS, the cluster centers of the two sub-clusters under the final machine cluster with the biggest distance were determined, and then compared to identify the bottleneck cluster and non-bottleneck cluster. Fourth, through conducting identification multiple times, their sub-clusters under the bottleneck cluster were gradually compared to gain the set of multi-order primary bottleneck clusters. Finally, 24 benchmarks of job shop scheduling were selected and compared between the proposed approach with the existing approaches, such as Shifting Bottleneck Detection Method and Bottleneck Detection Method based on Orthogonal Experiment and machine workload indicator. The results showed that this approach was feasible and prominent.

Key words: bottleneck identification, bottleneck cluster, clustering algorithm, job shop scheduling problem, multiple attribute decision making, theory of constraints