一种基于指标补偿的平均流经时间快速预测方法

摘要

平均流经时间是企业关注的一个重要调度性能指标。利用基于软计算等的调度方法进行优化调度过程中，需要对调度策略进行全局仿真以获得对应的平均流经时间指标，且上述过程需多次进行，若对整个较大规模生产线建立精确仿真模型并对调度策略进行全局仿真，其耗时较长，因而，对平均流经时间指标进行快速预测，对提高调度算法的性能具有重要意义。本发明公开了一种基于指标补偿的平均流经时间快速预测方法，该方法通过将机器组划分为瓶颈和非瓶颈机器组，进而松弛非瓶颈机器组加工能力建立简化调度模型，然后利用SVM(支持向量机)获得简化调度模型和非简化调度模型对应的平均流经时间指标之间的补偿关系，从而实现对平均流经时间指标的快速预测。

主权项

1.一种基于指标补偿的平均流经时间快速预测方法，其特征在于，所述方法是在计算机上依次按以下步骤实现的：步骤(1)：初始化：基于从实际生产过程中得到的如下信息：整个生产线中机器组数量、每个机器组对应的机器数量、待调度的工件种类及各类的数量、各类工件的工艺路径、各工件每个操作的加工时间，形成原调度问题；步骤(2)：初始化完成后，将各机器组的调度规则设为SRPT规则(剩余加工时间最小者优先规则)，按以下步骤进行瓶颈机器组的识别：步骤(2.1)：进行原调度问题的仿真，获得各操作到达机器组缓冲区的时间和该操作加工完成时间的仿真结果数据；步骤(2.2)：按下式确定各个操作流经机器组的时间${\delta }_{j_{k}l}=b_{j_{k}l}-a_{j_{k}l},j=\mathrm{1,2},...,n;l=\mathrm{1,2},...,m$其中，分别为第j个工件在机器组l上加工的第k个操作到达机器组缓冲区的时间和该操作加工完成时间；m为机器组的数量；n为工件的数量；步骤(2.3)：按下式计算流经机器组l对应的所有操作的平均流经时间为δ_l：${\bar{\delta }}_l=\frac{\underset{j=1}{\overset{n}{\Sigma }}\underset{k=1}{\overset{l_j}{\Sigma }}{\delta }_{j_{k}l}}{\underset{j=1}{\overset{n}{\Sigma }}{l}_j}$式中n为工件数量，l_j表示第j个工件在机器组l上加工的操作数量；步骤(2.4)：按下式计算所有工件的平均流经时间f：$\bar{f}=\frac{\underset{l=1}{\overset{m}{\Sigma }}\underset{j=1}{\overset{n}{\Sigma }}{l}_j{\bar{\delta }}_l}{n}$步骤(2.5)：按照δ_l从大到小的顺序进行机器组瓶颈程度排序，记排序后的各机器组δ_l值序列为{β₁，β₂，…，β_m}，按下式确定瓶颈机器组数量b：$\underset{b}{\min }\frac{\underset{i=1}{\overset{b}{\Sigma }}{\beta }_i}{\underset{i=1}{\overset{m}{\Sigma }}{\beta }_i}\ge 80\%$选取{β₁，β₂，…，β_m}中前b个值所对应的机器组为瓶颈机器组；步骤(3)：在瓶颈机器组识别基础上，按如下步骤进行调度模型简化：步骤(3.1)：保持瓶颈机器组对应的相关调度约束不变，包括保持不可中断约束、机器唯一性约束和工件唯一性约束不变；步骤(3.2)：松弛非瓶颈机器组加工能力为无穷大，即不考虑操作在非瓶颈机器组上的等待时间，直接用相应操作的加工时间作为其在该机器组上的流经时间；步骤(4)：在瓶颈机器组识别和调度模型简化基础上，按照如下步骤提取训练SVM(支持向量机)需要的输入特征属性向量和输出目标属性数据，并对SVM相关参数进行训练：步骤(4.1)：对各机器组对应的待调度的所有操作分别随机产生一个排序，将排序结果作为一条调度策略，基于上述简化调度模型对生产线进行仿真，获得各工件完工时间序列{sf₁，sf₂，…，sf_n}(满足sf₁≤sf₂≤…≤sf_n)，并计算其对应的平均流经时间如下：$\overline{\mathrm{sf}}=\frac{\underset{i=1}{\overset{n}{\Sigma }}{\mathrm{sf}}_i}{n}$步骤(4.2)：基于上述获得的工件完工时间序列，按如下步骤提取SVM输入特征属性向量：步骤(4.2.1)：按下式确定工件完工时间序列中相邻工件的完工时间间隔，形成工件完工时间间隔数据序列t₁，t₂，…，t_n-1：t_i＝sf_i+1-sf_i，i＝1，2，…，n-1步骤(4.2.2)：按照下式将上述工件完工时间间隔数据序列依次分成K组，记N＝n-1，每组的个数为：$b_k=\left\{\begin{array}{c}[N/K],k=\mathrm{1,2},...,K-1\\ N-[N/K]\times (K-1),k=K\end{array}\right.$步骤(4.2.3)：按下式提取工件完工时间间隔数据序列的特征属性向量：X＝[m_m，m_σ，σ_m，σ_σ]^T其中：X表示当前训练样本的输入特征属性向量$m_{\mathrm{tk}}=\left\{\begin{array}{cc}\frac{\underset{i=(k-1)\times b_k+1}{\overset{k\times b_k}{\Sigma }}{t}_i}{b_k},& k=\mathrm{1,2},...,K-1\\ \frac{\underset{i=(K-1)\times b_k+1}{\overset{N}{\Sigma }}{t}_i}{b_k},& k=K\end{array}\right.$${\sigma }_{\mathrm{tk}}=\left\{\begin{array}{cc}\frac{1}{b_k}\underset{i=(k-1)\times b_k+1}{\overset{b\times b_k}{\Sigma }}{(t_i-m_{\mathrm{tk}})}^2,& k=\mathrm{1,2},...,K-1\\ \frac{1}{b_k}\underset{i=(K-1)\times b_k+1}{\overset{N}{\Sigma }}{(t_i-m_{\mathrm{tk}})}^2,& k=K\end{array}\right.$$m_m=\frac{\underset{k=1}{\overset{K}{\Sigma }}{m}_{\mathrm{tk}}}{K},$$m_{\sigma }=\frac{1}{K}\underset{k=1}{\overset{K}{\Sigma }}{(m_{\mathrm{tk}}-m_m)}^2$${\sigma }_m=\frac{\underset{k=1}{\overset{K}{\Sigma }}{\sigma }_{\mathrm{tk}}}{K},$${\sigma }_{\sigma }=\frac{1}{K}\underset{k=1}{\overset{K}{\Sigma }}{({\sigma }_{\mathrm{tk}}-{\sigma }_m)}^2$步骤(4.3)：基于步骤(4.1)中所得到的调度策略，对原调度问题基于非简化模型进行仿真，利用步骤(2.4)的计算公式，得到所有工件的平均流经时间f，按照下式确定当前训练样本中的目标属性值：Δf＝f-sf步骤(4.4)：重复步骤(4.1)～步骤(4.3)直至满足设定的训练样本数量S要求，按下式形成训练样本集：输入特征属性向量集：XX＝[X₁，X₂，…，X_S]输出目标属性集：ff＝[Δf₁，Δf₂，…，Δf_S]步骤(4.5)：利用训练样本集给出的输入特征属性向量集和输出目标属性集，对SVM进行训练；训练完成后，建立SVM回归函数为：$\Delta f_y\left(X\right)=\underset{i=1}{\overset{S}{\Sigma }}({{\alpha }_i}^{*}-{\alpha }_i)K(X_i,X)+b$其中：为高斯核函数，γ为高斯核函数宽度参数，b为训练得到的阈值，Δf_y(X)为对输入特征属性向量X的预测值，即平均流经时间的补偿量，α_i^*、α_i为训练完成后得到的参数；步骤(5)：在得到原调度问题的简化调度模型及用于计算平均流经时间补偿值的SVM后，在调度算法的优化过程中，对给定的调度策略，按照如下步骤确定平均流经时间指标预测值：步骤(5.1)：根据优化调度过程中给定的调度策略，提取SVM需要的输入特征属性向量X；步骤(5.2)：利用训练得到的SVM回归函数，计算平均流经时间补偿值：$\Delta f_y=\underset{i=1}{\overset{S}{\Sigma }}({{\alpha }_i}^{*}-{\alpha }_i)K(X_i,X)+b$步骤(5.3)：按下式计算上述调度策略对应的平均流经时间指标预测值：${\bar{f}}_y=\overline{\mathrm{sf}}+\Delta f_y=\frac{\underset{i=1}{\overset{n}{\Sigma }}{\mathrm{sf}}_i}{n}+\Delta f_y$其中：f_y为平均流经时间指标预测值。