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

摘要： 针对传统作业车间调度瓶颈识别方法划定多瓶颈候选集时缺乏科学的划分范围、划分层次和划分依据等问题，提出机器簇、瓶颈簇、主瓶颈簇及阶次的概念，建立了作业车间瓶颈簇的识别模型。考虑机器的主次之分和多维特征属性，基于聚类思想及多属性决策理论提出了作业车间瓶颈簇的识别方法。选择识别瓶颈的机器特征属性，采用免疫进化算法获得调度优化方案并计算机器的特征属性值；采用层次聚类法，获得不同距离下机器簇的集合及其树状结构图；基于理想解相似度顺序偏好法确定并比较机器簇的簇中心，识别出瓶颈簇和非瓶颈簇；对瓶颈簇的子簇依次进行比较，通过多次识别逐步确定出多阶主瓶颈簇集合。最后，采用24组作业车间调度问题标准算例，将所提方法与移动瓶颈识别法、正交试验识别法、机器负荷识别法等进行比较，证明了其可行性及优势。

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