作业车间瓶颈簇的识别方法研究
1
摘要:针对传统 Job Shop 瓶颈识别方法划定瓶颈候选集时缺乏科学的划分范围、划分层次
以及划分依据等问题,提出了机器簇、瓶颈簇、主瓶颈簇及阶次的概念。考虑机器的主次
之分和多维特征属性,基于聚类思想及多属性决策理论提出了作业车间瓶颈簇的识别方法
第一,确定识别瓶颈的机器特征属性,并采用免疫进化算法获得调度优化方案以计算机器
的特征属性值。第二,采用层次聚类法获得不同距离下机器簇的集合及其树状结构图。第
三,基于 TOPSIS 法确定并比较机器簇的簇中心确定瓶颈簇和非瓶颈簇。第四,立足瓶颈
簇依次进行子簇比较,逐步确定出多阶主瓶颈簇集合。最后,采用 24 组 JSSP 标准算例,
将本方法与移动瓶颈识别法和正交试验识别法进行对比,证明了本方法的可行性及优势。
关键词:瓶颈识别;瓶颈簇;聚类算法;作业车间调度;多属性决策
中图分类号:TP166 文献标识码:A
An identification approach for bottleneck cluster in Job Shop
bstract: Traditional bottleneck identification methods in job shops lack of scientific method and
theoretical basis defining the size, classification and hierarchy of bottleneck candidate set. This
paper thus proposes a set of innovative concepts including Machine Cluster, Bottleneck Cluster,
Primary Bottleneck Cluster and Machine Cluster Order. Base on the order of importance and
multidimensional feature attributes of machines, an identification approach for bottleneck cluster
in job shop has been proposed based on hierarchical clustering algorithm and multi-attribute
decision making theory. First, The feature attributes of machine are chosen and their attributes
values are calculated based on the optimal scheduling solution obtained by using immune
evolutionary algorithm. Second, using hierarchical clustering algorithm, the set of machine cluster
and dendrogram are established corresponding to different distance. Third, using TOPSIS, the
cluster center of the two sub-clusters under the final machine cluster with the biggest distance are
compared to gain the bottleneck cluster and non-bottleneck cluster. Four, the sub-clusters
corresponding to different order under the bottleneck cluster were gradually compared to gain the
set of primary bottleneck clusters under different orders. Finally, 24 benchmarks of job shop
scheduling are selected and compared between this proposed approach with the existing approach,
such as Shifting Bottleneck Detection Method and Bottleneck Detection Method based on
Orthogonal Experiment. The results show that this approach is feasible and prominent.
Keywords: bottleneck identification; bottleneck cluster; clustering algorithm; Job Shop
Scheduling Problem; multiple attribute decision making
0 引言
制造资源的有限性以及生产系统本身具有统计波动性和加工相依性,必然造成限制系
统有效产出最大化输出的“瓶颈”现象 [1]。约束理论(Theory of Constraints,TOC)认为瓶颈
(Bottleneck)是制约整个系统有效产出(Throughput)的控制点,瓶颈的时间损失就是整
个系统的时间损失,只有立足瓶颈并使瓶颈利用率最大化,才能使系统整体产出最优。显
见,瓶颈识别不仅成为瓶颈管理的基础,更是生产管理与过程控制的关键。
目前瓶颈识别方面的研究主要集中在单瓶颈识别上,所采用的方法主要是指标法,本
文总结为以下四类指标。①设备类:文献[2]定义系统加工能力最差的机器为系统的瓶颈,
文献[3]定义负荷最大的机器为系统的瓶颈。然而负荷最大或者机器加工能力最差的机器并
非真正的瓶颈,充其量,负荷和机器加工能力只能作为瓶颈识别的先验信息。②在制品类
文献[4]定义具有最长平均等待时间的机器为系统的瓶颈,文献[5]定义具有最长队列长度的
机器为系统瓶颈机器。当多个机器缓冲区待加工工件队列长度相同或缓冲区队列同时溢出
时,此方法不能准确识别系统的瓶颈。③有效产出类:文献[6-9]提出“敏感度”(Sensitivity)
指标,认为对系统有效产出影响最敏感的机器为瓶颈。文献[10]基于在线数据驱动方法,
1