一种考虑机器多维特征属性的作业车间瓶颈识别方法

摘要

本发明提出了一种考虑机器多维特征属性的作业车间瓶颈识别方法。首先采用优化算法进行作业调度优化求解，其次改变传统依据机器单方面因素识别瓶颈的做法，综合考虑瓶颈的多方面特征属性，提出多属性瓶颈识别方法，综合全面评价机器性能进行瓶颈识别。本发明将瓶颈利用和瓶颈识别问题放在统一框架下进行集成求解，解决了传统瓶颈识别与优化方案相割离而导致瓶颈识别不准、优化方案不优等不足；得到调度优化方案后，综合考虑机器的不同特征属性，采用TOPSIS多属性瓶颈识别方法进行瓶颈识别，克服了传统瓶颈识别指标片面、识别结果偏颇的缺陷。

说明书

技术领域

本发明涉及作业车间瓶颈识别技术领域，具体为一种考虑机器多维特征属性的作 业车间瓶颈识别方法。

背景技术

制造资源的有限性以及生产系统本身具有统计波动性和加工相依性，必然造成限 制系统有效产出最大化输出的“瓶颈”现象。约束理论(Theory of Constraints,TOC)认 为瓶颈（Bottleneck）是真正制约整个系统有效产出和库存水平的控制点，瓶颈上的损 失意味着整个生产系统的损失，只有立足瓶颈并使瓶颈利用率最大化，才能使系统整 体产出最优。因此，生产管理与控制的依赖点和基点应放在瓶颈上。

现有瓶颈识别研究集中在瓶颈识别指标与瓶颈识别方法，现有瓶颈识别指标分为 在制品类(Work-in-process Orientation)、设备能力类(Equipment Capacity Orientation)两 类；将瓶颈识别方法分为指标直接识别法、数学分析法与数据分析法三类。瓶颈识别 方法与瓶颈识别指标相互对应，通过瓶颈指标进行识别：

(1)指标直接识别法，通过生产现场机器加工状况或在制品指标直接进行瓶颈识 别。文献中定义的瓶颈包括：具有最长平均等待时间的机器；具有最长队列长度的机 器；系统加工能力最差的机器；负荷最大的机器；设备综合效率(Overall Equipment  Effectiveness,OEE)最大的机器。

(2)数学分析法，在假设机器的性能参数，如故障率、加工周期、MTTR等，皆 满足一定概率分布的基础上，建立生产线的数学模型，通过分析机器的产出对系统产 出的影响识别系统的瓶颈机器。

(3)数据分析法，基于仿真或在线数据实时监控，对于仿真数据、实时数据等进 行分析和处理，辨别系统的瓶颈机器。

传统作业车间瓶颈识别考虑单方面因素，综合考虑多因素少。大多文献考虑瓶颈 的某一方面，基于单因素特征建立瓶颈识别指标进行瓶颈识别，少数文献考虑多个指 标，但是都是基于简单的规则，不能挖掘机器特征属性的信息量，无法实现综合评价 机器的目的。

发明内容

要解决的技术问题

为解决现有技术存在的问题，本发明提出了一种考虑机器多维特征属性的作业车 间瓶颈识别方法。

技术方案

本发明运用TOC新型优化运作逻辑，提出将瓶颈利用和瓶颈识别问题放在统一框 架下进行集成求解，第一层级为瓶颈利用，采用优化算法进行作业调度优化求解，保 证作业调度方案整体性能最优和瓶颈机器能力充分利用程度最高；第二层级为瓶颈识 别，改变传统依据机器单方面因素识别瓶颈的做法，综合考虑瓶颈的多方面特征属性， 提出多属性瓶颈识别方法，综合全面评价机器性能进行瓶颈识别。此框架改变了传统 瓶颈识别独立于调度优化方案的做法，将作业车间调度优化与瓶颈识别相结合，先进 行瓶颈充分利用再进行系统瓶颈的辨识，既保证了瓶颈设备的充分利用，又保证了调 度优化方案的整体最优。

本发明所指的瓶颈利用层的核心任务是进行Job Shop调度问题的优化求解。

本发明所指的瓶颈识别层的核心任务是辨识瓶颈机器。

本发明所识别的瓶颈为通过多属性决策方法求得的评价值最大的机器。

本发明的技术方案为：

所述一种考虑机器多维特征属性的作业车间瓶颈识别方法，其特征在于：包括以 下步骤：

步骤1：采用优化算法确定作业车间的最优调度方案Ω：

Ω＝{{B₁₁,…,B_v1,…,B_e1;C₁₁,…,C_vl,…,C_e1;Z_l1,…,Z_v1,…,Z_e1},…,{B_li,…,B_vi,…,B_ei;C_li, …,C_vi,…,C_ei;Z_1i,…,Z_vi,…,Z_ei},…,{B_1m,…,B_vm,…,B_em;C_1m,…,C_vm,…,C_em;Z_1m,…,Z_vm,…,Z_em}}

其中，B_vi表示第v∈E＝{1,2,…,e}个工件在第i∈M＝{1,2,...,m}台机器上的开始加工时 间，C_vi表示第v个工件在第i台机器上的加工完成时间，Z_vi表示第v个工件在第i台机 器上的工装准备时间；

步骤2：建立机器集为A＝{A₁,A₂,...,A_m}，评价属性集为X＝{X₁,X₂,...,X_n}；根据步 骤1得到的最优调度方案Ω，计算每个机器各评价属性值，得到用于瓶颈识别的决策 矩阵D＝(x_ij)_m×n，x_ij是第i个的机器的第j个评价属性值；

步骤3：采用向量标准化方法将步骤2的决策矩阵D＝(x_ij)_m×n转换成标准决策矩阵 R＝(r_ij)_m×n：

$r_{\mathrm{ij}}=x_{\mathrm{ij}}/\sqrt{\underset{i=1}{\overset{m}{\Sigma }}{x}_{\mathrm{ij}}^2}$

步骤4：采用熵权法确定评价属性权重，评价属性权重向量W＝(ω₁,ω₂,...,ω_j,...,ω_n)：

步骤4.1：将各评价属性值标准化，其中第j个属性下第i台机器的无量纲化属 性值p_ij为：

$p_{\mathrm{ij}}=x_{\mathrm{ij}}/\underset{i=1}{\overset{m}{\Sigma }}{x}_{\mathrm{ij}}$

步骤4.2：计算第j个评价属性的熵值E_j：

$E_j=-\delta \underset{i=1}{\overset{m}{\Sigma }}{p}_{\mathrm{ij}}\ln p_{\mathrm{ij}}$

其中δ＝1/lnm，保证了0≤E_j≤1；

步骤4.3：计算第j个属性的信息偏差度d_j：

d_j＝1-E_j

步骤4.4：对信息偏差度进行归一化计算权重：

当决策者没有评价属性间的偏好时：

${\omega }_j=d_j/\underset{j=1}{\overset{n}{\Sigma }}{d}_j$

当决策者有评价属性间的偏好时：

${\omega }_j={\lambda }_j{d}_j/\underset{j=1}{\overset{n}{\Sigma }}{\lambda }_j{d}_j$

其中λ_j为决策者的主观权重；

步骤5：将步骤4得到的评价属性权重纳入标准决策矩阵R＝(r_ij)_m×n中，得到加权 标准化决策矩阵V＝(v_ij)_m×n＝(ω_jr_ij)_m×n；

步骤6：确定评价属性的正、负理想解A⁺和A^-：

$A^{+}=\{\left(\underset{i}{\max }{v}_{\mathrm{ij}}\right|j\in J),\left(\underset{i}{\min }{v}_{\mathrm{ij}}\right|j\in J^{\prime })|i=M\}=\{v_1^{+},v_2^{+},...,v_j^{+},...,v_n^{+}\}$

$A^{-}=\{\left(\underset{i}{\min }{v}_{\mathrm{ij}}\right|j\in J),\left(\underset{i}{\max }{v}_{\mathrm{ij}}\right|j\in J^{\prime })|i\in M\}=\{v_1^{-},v_2^{-},...,v_j^{-},...,v_n^{-}\}$

其中J为效益型评价属性集合，J′为成本型评价属性集合；

步骤7：通过n维Euclid距离计算各机器与正理想解以及负理想解之间的距离： 每台机器到正理想解的距离为：

$S_{i^{+}}=\sqrt{\underset{j=1}{\overset{n}{\Sigma }}{(v_{\mathrm{ij}}-v_j^{+})}^2}$

每台机器到负理想解的距离为：

$S_{i^{-}}=\sqrt{\underset{j=1}{\overset{n}{\Sigma }}{(v_{\mathrm{ij}}-v_j^{-})}^2}$

步骤8：计算每台机器与正理想解A⁺的贴近度C_i：

$C_i=S_{i^{-}}/(S_{i^{+}}+S_{i^{-}}),0<C_i<1$

得到贴近度C_i最大的机器为作业车间的瓶颈。

所述一种考虑机器多维特征属性的作业车间瓶颈识别方法，其特征在于：评价属 性包括机器负荷，机器利用率，活跃时间，活跃偏差，敏感度，单位有效产出，在制 品队列长度和设备综合效率。

有益效果

本发明综合考虑机器多个特征属性进行瓶颈识别，建立多属性瓶颈识别模型，给 出了瓶颈的数学化定义，采用瓶颈识别与瓶颈利用统一框架，瓶颈利用层进行优化调 度，瓶颈识别层基于TOPSIS多属性决策方法，综合评价机器，从而识别作业车间瓶 颈机器，其优点在于：

(1)将瓶颈利用和瓶颈识别问题放在统一框架下进行集成求解，解决了传统瓶颈识 别与优化方案相割离而导致瓶颈识别不准、优化方案不优等不足，在生成调度优化方 案的同时确定相对应的瓶颈，得到的最优调度方案更具指导意义。

(2)得到调度优化方案后，综合考虑机器的不同特征属性，采用TOPSIS多属性瓶 颈识别方法进行瓶颈识别，克服了传统瓶颈识别指标片面、识别结果偏颇的缺陷。另 外，引入熵权法使得确定机器评价属性的权重方法更为科学。

(3)瓶颈识别的多属性决策除了给出系统瓶颈外，还给出了预测成为瓶颈可能性的 评判指标——贴近度C_i。依据贴近度指标可预测机器成为可能瓶颈的优先顺序，为保 护瓶颈作业、次瓶颈能力以及预防瓶颈漂移提供重要的信息。

附图说明

图1：本发明瓶颈识别过程简图；

图2：本发明瓶颈识别过程图；

具体实施方式

本发明可以用于作业车间生产控制过程中。通过本发明的方法识别出瓶颈，使调 度人员合理关注瓶颈资源和非瓶颈资源，提高生产组织的效率，使车间的产能得到最 大化的利用，提高经济效益。

本实施例中选择JSSP问题LA类的24个标准算例作为比较测试算例，分别为10 ×5、15×5、10×10、15×10、20×10、30×10的6种不同规模的典型问题，每种规 模选取4个算例，共24个算例。并将本发明的方法与移动瓶颈识别法(Shifting bottleneck  detection method,SBD)和正交试验瓶颈识别法进行比较。

本实施例中的考虑机器多维特征属性的作业车间瓶颈识别方法，包括以下步骤：

步骤1：采用免疫进化算法CHIEA(Clonal Selection and Hyper Mutations Based  Immune Evolution Algorithm)确定作业车间的最优调度方案Ω，目标是充分利用瓶颈的 能力，实现调度方案整体性能指标的最优。免疫进化算法见文献《免疫进化算法求解静 态Job shop调度》（牛刚刚,孙树栋,余建军,机械工程学报,2006,42(05):87-91.）：

免疫进化算法CHIEA求解最优调度方案步骤如下：

步骤a构造抗原和初始抗体。根据输入作业调度问题和相关约束信息随机生成具 有机器偏好的基于工序编码的抗原，该编码方式相比传统基于工序编码方式，在编码 效率上具有很大优势；抗原生成以后，对其进行复制产生初始抗体。

步骤b抗体克隆。增大初始抗体或者对抗原反应激烈的抗体(即优秀抗体)的规模， 以期获得更优秀的抗体。

步骤c细胞超变异。CHIEA构造了一种随机混排变异：首先随机选择i个机器对 应的基因片段(i为一随机数，1≤i≤m，m表示机器总数)；然后对每个基因片段上的随 机两个基因位进行随机排列，随机排列的结果为下面两种方案之一：①交换变异(Swap  mutation)，②基因片段保存不变。

步骤d自识别解码。在对初始抗体进行超变异后，抗体可能转变成非可行解，在 解码的时就会发生死锁，自识别解码对每个加工工件识别并插入到机器的可加工间隙 中，实现非可行解向可行解的动态调整。

步骤e记忆库更新。据抗体的适合度值(抗体解码后的Makespan)对新产生的抗体 以及父代抗体进行排序，然后保存优秀的新生抗体，淘汰较差的抗体。

步骤f抗体选择。抗体选择是在记忆库中选取一定数量的优秀抗体以进行抗体克 隆操作。考虑到算法的计算效率以及避免算法陷入局部最优，CHIEA的抗体选择是基 于抗体适合度的选择，而不是其他文献中基于抗体信息熵和抗体浓度的选择。

步骤g循环步骤b至步骤f所有的免疫进化操作，直到得到最优抗体即Job Shop 问题的最优调度方案Ω：

Ω＝{{B_1l,…,B_vl,…,B_e1;C_ll,…,C_v1,…,C_e1;Z_1l,…,Z_v1,…,Z_e1},…,{B_1i,…,B_vi,…,B_ei;C_1i, …,C_vi,…,C_ei;Z_li,…,Z_vi,…,Z_ei},…,{B_1m,…,B_vm,…,B_em;C_lm,…,C_vm,…,C_em;Z_lm,…,Z_vm,…,Z_em}}

其中，B_vi表示第v∈E＝{1,2,…,e}个工件在第i∈M＝{1,2,...,m}台机器上的开始加工时 间，C_vi表示第v个工件在第i台机器上的加工完成时间，Z_vi表示第v个工件在第i台机 器上的工装准备时间；

步骤2：建立机器集为A＝{A₁,A₂,...,A_m}，评价属性集为X＝{X₁,X₂,...,X_n}；根据步 骤1得到的最优调度方案Ω，计算每个机器各评价属性值，得到用于瓶颈识别的决策 矩阵D＝(x_ij)_m×n，x_ij是第i个的机器的第j个评价属性值；评价属性可以在机器负荷， 机器利用率，活跃时间，活跃偏差，敏感度，单位有效产出，在制品队列长度和设备 综合效率中进行组合选择，本实施例中选取机器负荷，机器利用率，活跃时间作为评 价属性。

步骤3：采用向量标准化方法将步骤2的决策矩阵D＝(x_ij)_m×n转换成标准决策矩阵 R＝(r_ij)_m×n：

$r_{\mathrm{ij}}=x_{\mathrm{ij}}/\sqrt{\underset{i=1}{\overset{m}{\Sigma }}{x}_{\mathrm{ij}}^2}$

其目的是将各种类型的评价属性值转换为无量纲的属性，使属性可以进行相互比较。

步骤4：在决策矩阵D＝(x_ij)_m×n中，对于某个属性X_j的属性值x_ij的差距越大，则 该属性在综合决策中所起的作用越大，反之则越小。信息熵是信息无序度的度量，信 息熵越大，信息的无序度越高，其值越小，系统无序程度越小，故采用信息熵评价系 统信息的有序度及其效用。本步骤采用熵权法确定评价属性权重，求解评价属性权重 向量W＝(ω₁,ω₂,...,ω_j,...,ω_n)，熵权法能尽量消除各指标权重计算的人为干扰，使评价结 果更符合实际。其计算步骤如下：

步骤4.1：将各评价属性值标准化，其中第j个属性下第i台机器的无量纲化属 性值p_ij为：

$p_{\mathrm{ij}}=x_{\mathrm{ij}}/\underset{i=1}{\overset{m}{\Sigma }}{x}_{\mathrm{ij}}$

步骤4.2：计算第j个评价属性的熵值E_j：

$E_j=-\delta \underset{i=1}{\overset{m}{\Sigma }}{p}_{\mathrm{ij}}\ln p_{\mathrm{ij}}$

其中δ表示一个常量，δ＝1/lnm(ln为自然对数)，保证了0≤E_j≤1；

步骤4.3：计算第j个属性的信息偏差度d_j：

d_j＝1-E_j

当d_j越大时，属性越重要。

步骤4.4：对信息偏差度进行归一化计算权重：

当决策者没有评价属性间的偏好时，根据不确定理论可以认为这n个评价属性具有相 同的偏好，则：

${\omega }_j=d_j/\underset{j=1}{\overset{n}{\Sigma }}{d}_j$

当决策者有评价属性间的偏好时：

${\omega }_j={\lambda }_j{d}_j/\underset{j=1}{\overset{n}{\Sigma }}{\lambda }_j{d}_j$

其中λ_j为决策者的主观权重；

本实施例中，认为决策者没有属性的偏好。

步骤5：将步骤4得到的评价属性权重纳入标准决策矩阵R＝(r_ij)_m×n中，得到加权 标准化决策矩阵V＝(v_ij)_m×n＝(ω_jr_ij)_m×n；

步骤6：确定评价属性的正、负理想解A⁺和A^-：

$A^{+}=\{\left(\underset{i}{\max }{v}_{\mathrm{ij}}\right|j\in J),\left(\underset{i}{\min }{v}_{\mathrm{ij}}\right|j\in J^{\prime })|i=M\}=\{v_1^{+},v_2^{+},...,v_j^{+},...,v_n^{+}\}$

$A^{-}=\{\left(\underset{i}{\min }{v}_{\mathrm{ij}}\right|j\in J),\left(\underset{i}{\max }{v}_{\mathrm{ij}}\right|j\in J^{\prime })|i\in M\}=\{v_1^{-},v_2^{-},...,v_j^{-},...,v_n^{-}\}$

其中J为效益型评价属性集合，J′为成本型评价属性集合；对于效益型评价属性，属 性值越大越好，对于成本型评价属性，属性值越小越好。

步骤7：通过n维Euclid距离计算各机器与正理想解以及负理想解之间的距离： 每台机器到正理想解的距离为：

$S_{i^{+}}=\sqrt{\underset{j=1}{\overset{n}{\Sigma }}{(v_{\mathrm{ij}}-v_j^{+})}^2}$

每台机器到负理想解的距离为：

$S_{i^{-}}=\sqrt{\underset{j=1}{\overset{n}{\Sigma }}{(v_{\mathrm{ij}}-v_j^{-})}^2}$

步骤8：计算每台机器与正理想解A⁺的贴近度C_i：

$C_i=S_{i^{-}}/(S_{i^{+}}+S_{i^{-}}),0<C_i<1$

得到贴近度C_i最大的机器为作业车间的瓶颈。

瓶颈识别结果比较见表1。

表1多属性瓶颈识别方法(MABI)与SBD法和正交试验瓶颈识别法的结果比较

注：加*表示本文瓶颈识别方法与移动瓶颈法识别结果不相同；加**表示本文瓶颈识别方法与正交试验法 识别结果不相同；

从表1的算例结果可以看出本文提出的瓶颈识别方法与移动瓶颈识别法的瓶颈识 别结果吻合率高达到95.8%，与正交试验法识别结果吻合率也达到75%。本方法在算 例中采用了机器平均持续活跃时间作为指标之一，而移动瓶颈识别法是基于平均活跃 时间指标并进行了改进而提出的瓶颈识别方法。考虑到两种方法都相关于平均持续活 跃时间因素，本方法与移动瓶颈识别法识别结果相似度相对较高。另外，算例结果证 明了负荷高的机器并不一定是系统瓶颈，如算例LA21、LA22、LA27。

三种瓶颈识别方法识别出了不同的瓶颈，识别结果的不尽相同说明了瓶颈定义对 瓶颈识别结果的影响。移动瓶颈识别法将瓶颈活跃持续时间最长的机器定义为系统的 瓶颈机器，正交试验法考虑了机器对系统有效产出的影响，将对于试验指标影响最大 的因素定义为系统的瓶颈机器。本发明考虑多个瓶颈特征属性的瓶颈综合决策方法， 区别于根据机器单一因素的定义识别瓶颈的传统方法，是一种综合评价机器的方法。