-
摘要: 针对传统多变量时间序列预测方法未考虑变量间依赖关系从而影响预测效果的问题，提出了一种基于异常序列剔除的多变量时间序列预测算法.该算法旨在利用多维支持向量回归机（Multi-dimensional support vector regression，M-SVR）内在的结构化输出特性，对选取到具有相似性的多个变量序列进行联合预测.首先，对已知序列进行基于模糊熵的层次聚类，实现对相似序列的初步划分；其次，求出类中所有序列的主曲线，根据序列到主曲线的距离计算各个序列的异常因子，从而进一步剔除聚类结果中的异常序列；最后，将选取到的相似变量序列作为输入，利用M-SVR进行预测.通过理论分析，证明本文算法在理论上存在信息损失上界与可靠度下界，从而说明本文算法的合理性与可行性.采用混沌时间序列数据与多个实际数据集进行对比实验，结果表明，与现有多个代表性方法相比，本文算法可有效挖掘多变量时间序列的内在结构信息，预测精度更高，数值稳定性更好.Abstract: To solve the problem that the traditional multivariate time series prediction generally ignores the dependency among all variables, a new multivariate time series structural prediction method through outlier elimination is proposed. This algorithm predicts on the selected multivariate time series by using the structural output characteristic. Firstly, to recognize the relatedness among the sequences, the variable sequences are initially divided by hierarchical clustering according to fuzzy entropy. Secondly, to further evaluate the similarity of the sequences in the obtained cluster, the principal curve is introduced to calculate the abnormality degree of each sequence, and then the outlier sequence can be eliminated in terms of the value of abnormality degree. As a result, similar sequences can be distinguished. Finally, for the similar series, multi-dimensional support vector regression (M-SVR) is used to construct the prediction model, and then the structural prediction for multivariate time series is conducted. Moreover, a theoretical proof is provided to show the proposed method has an upper bound of the loss of information and a lower bound of reliability and that the proposed method is reasonable and feasible from the perspective of information entropy. Experiments are conducted on three chaotic time series datasets and five real-life datasets. The results show that the proposed method can effectively recognize the inner group structure among multivariable sequences, so as to obtain a better forecasting accuracy and numerical stability than those widely used methods in terms of two different error measurements.
-
当前, 我国的制造业成本已达美国的90 %以上, 传统的劳动密集型制造业竞争力已逐渐消失[1], 产品多样性和定制化急剧增加, 产品生命周期显著缩短, 导致市场需求的波动性和不确定性随之加剧.日趋多变的市场环境要求企业具有更为强大和迅速的应变能力, 这种能力已经很难通过传统生产模式得到满足.
以索尼(Sony)和佳能(Canon)为例, 由于它们的生产具有多品种、小批量、高附加值的特点, 且产品频繁进行设计升级与更新换代, 因此在生产技术和配置上要求生产系统能够根据生产需要进行快速调整, 而传统的基于精益思想构建的同步式、集成式的流水线已不能满足这样的需求.因此索尼和佳能通过构建一种新型生产系统, 即Seru (单元)生产系统, 在多变的市场环境中脱颖而出[2-4].佳能与索尼对Seru单元的实践转化遵循以下步骤: 1)当顾客需求产生波动, 组装流水线的不足凸现出来, 为了获得响应能力, 可以采取战略上的重新选择; 2)拆除流水线, 通过资源集中放置和去除/替换、多能工培训, 获得独立性和自治性, 构建分割式Seru单元来取代流水线; 3)随着Seru单元系统的成熟, 构建起Seru生产系统来达到供需平衡.基于以上步骤, Seru生产系统在实践中取得了令人瞩目的成效.索尼在构建了Seru生产系统后, 累计拆除了35 000米的传送带流水线, 节约了71万平方米的场地空间, 节省了36 846个工作岗位(相当于其之前劳动力总数的1/4).佳能的54家工厂在应用Seru生产系统后的5年间拆除了20 000米的组装流水线, 释放出72万平方米的厂房(相当于12家大型工厂), 节省了35 976个岗位, 总计降低成本2亿3 000万日元, 平均生产效率甚至超过了丰田[5].
继索尼和佳能之后, Seru生产系统在电子(如三星、松下、富士通等)、汽车零部件(如通用、丰田、本田等)以及食品行业得到推广并获得成功[2-8].在我国, 随着外资企业大量建厂, 带动了Seru生产系统这一新型生产模式的传播和推广.目前, 海尔、美的以及许多东部沿海的生活家电企业已经推行了Seru生产系统进行生产, 此外, 内蒙一机等企业在其小型零部件的装配中也开始实施Seru生产系统.这些令人瞩目的现象引起了研究领域的浓厚兴趣--为什么Seru生产系统不仅节约了资源, 还能够获得更快的响应速度、更高的效率和更大的利润？许多学者(包括INFORMS会士Stecke、Decision Sciences Institute (DSI)主席Swink、顶级期刊Production and Operations Management (POM)创始人Singhal、顶级期刊Manufacturing & Service Operations Management (M & SOM)主编Tang等)先后围绕Seru生产系统开展研究或将其作为一个新兴研究领域进行介绍[2, 9], 认为Seru生产系统代表了"下一代生产系统"的发展趋势[7].
目前的研究主要集中于两方面:
一方面是通过与传统生产方式的对比论证Seru生产系统的优势. Yin等[5]通过研究佳能企业的生产转型过程, 指出了将传统流水线改造为Seru生产系统的重要性. De Treville等[7]指出Seru生产系统在不确定市场环境下, 可使生产系统具备比现有的装配流水线更加强大的应变能力, Liu等[10-12]也提出了相同的观点. Manupati等[4]将Seru生产系统与传统流水线对比, 认为Seru生产系统更加节省人力资源, 并且更加规范和灵活. Liu等[13-14]认为, Seru生产系统是一种更为先进的生产模式, 其潜力远大于传统流水线, 同时也论证了Seru生产系统具有缩短提前期、降低库存的效果. Stecke等[2]在探索可以适应市场需求多变的生产模式时指出, Seru生产系统具有长期学习和进化的能力. Zhang等[15]指出, Seru生产系统可以节约大量的环境资源, 减少费用支出, 具有可持续发展性.
另一方面集中于如何将传统流水线改造为Seru生产系统. Luo等[16]研究了将传统流水线转为Seru生产系统过程中的人员分配问题. Yu等[17-19]在研究传统流水线向Seru生产系统转化的过程中, 提出了一种流水线分割与重组的数学模型, 他们还研究了转化过程中考虑时间成本、劳动力等多目标优化问题, 以及如何减少劳动力的问题. Liu等[10-12, 14, 18]提出传统流水线转化为Seru生产系统的框架与原则, 并且研究了多能工的培训分配问题. Zhang等[15]也研究了多能工对传统流水线转化为Seru生产系统的作用. Yu等[20]研究了Seru生产系统的形成与分配问题.
在对流水线向Seru系统转化(Line-seru conversion)这个问题的研究中, 可将问题简化为两个决策过程: Seru构建和Seru调度.将Seru生产系统投入实际生产的首要步骤是如何将现有流水线拆分为若干Seru, 以完成Seru生产系统的构建, 即Seru构建. Seru调度决策批次如何分配到Seru中.目前的研究都是对Seru调度阶段采用了例如FCFS (First come first served)等简单的启发式规则进行规划, 然后再设计算法来求解Seru构建的精确解或较优解.例如Yu等[21]通过修改原始NSGA (Non-dominated sorting genetic algorithm)-Ⅱ交叉、变异操作符的具体实现方式, 以适应Seru构建的特点, 从而将其运用在解决Seru构建问题上. Yu等[19]为了提高算法的知识利用能力, 将局部搜索算法与NSGA-Ⅱ相结合, 以提高Seru构建的质量. Liu等[18]提出了一种三阶段启发式算法, 解决了Seru生产系统构建阶段中工人分配的问题.
但是, 上述研究并没有联合决策过程进行全局寻优, 因此通过这类方法规划出的Seru生产系统无法充分发挥系统的灵活性与均衡能力较强的优势.实际上, 求解流水线向Seru转化问题的最优解应该是联合考虑Seru构造和Seru调度两个问题, 但如果同时对Seru构建与Seru调度两个方面联合进行寻优, 那么问题的解空间就会变得过于巨大, 现有方法难以在可接受的时间内得到Seru系统的最优规划方案.所以, 如何在合理的算法运行时间内, 同时对两个方面进行规划以获得较优的规划方案, 是解决该问题的关键.
本文参考Kaku等[22]研究, 引入了两项评估指标对Seru生产系统的性能进行评估, 即产品流通时间(Total throughput time, TTPT)和总劳动时间(Total labor hours, TLH)作为优化目标. TTPT即为系统中所有产品批次加工完成所花费的时间, 用来评估系统的生产率. TLH即为系统中所有工人的累计劳动时间, 用来评估系统的人员劳动效率.
基于以上分析, 本文提出一种多目标协同进化算法(Multi-objective cooperative coevolution, MOCC), 用以解决流水线向Seru转化的联合优化问题.本文方法在传统进化算法思想的基础上, 加入了子种群间的协同机制.算法针对流水线向Seru转化问题的特点, 建立两个子种群分别对应Seru构建与Seru调度两个子问题.通过协同机制, 两个子种群便可相互协同进化, 即在进化过程中同时考虑Seru构建与Seru调度且不增加算法运行时间, 以此解决现有方法存在的不足, 获得更优的转化结果.另外, 本文在解的基因编码中引入了冗余码, 以期在规划过程中获得更优的均衡性能.通过应用MOCC, 转化后的Seru生产系统在灵活性与生产能力上都会获得较大的提升.
本文其余部分组织如下:第1节介绍了在进化算法中引入协同机制的相关研究; 第2节给出了流水线向Seru生产系统转换问题抽象出的问题模型; 第3节提出了一种带有协同机制的进化算法; 第4节通过仿真实验验证该算法的性能; 第5节给出结论并展望下一步工作.
1. 相关工作
本节针对调度问题, 介绍了在进化算法中引入协同机制的相关研究.
进化算法在解决复杂调度问题上有着良好的应用效果[23-24].但是一些调度问题, 例如流水线向Seru系统转化往往涉及到一个完整的解由若干个子问题的解组成的情况(在流水线向Seru系统转化问题中, 子问题即为Seru构建与Seru调度), 这些子问题往往耦合度较高.但传统的进化算法只能够针对一个独立的问题进行调度规划, 对于上述这类问题, 只能够将每个子问题单独进化, 再将解进行组合.如贾凌云等[25]针对运输能力受限条件下的跨单元问题, 提出了一种基于混合蛙跳与遗传规划的超启发式算法, 该算法首先对工序分派、工序排序、运输组批和路径决策等4个子问题分别求解, 最后再将4个子问题的解进行组合.田云娜等[26]提出一种基于动态决策块和蚁群优化的超启发式方法, 利用决策块分别解决跨单元生产调度和运输调度问题, 并最终生成调度解.这样的方式虽然可以得到一个完整的解, 但子问题之间的依赖关系在进化过程中被忽略, 多个子问题的解组合后协作效果往往难以满足生产需要.因此传统的进化算法并不适用于解决这类问题.
为了充分利用进化算法对于解决调度问题的优势, 一种多阶段协作的方法被应用到求解的过程中. Cheng[27]提出了一种分阶段:先使用作业调度(Job dispatching)再进行交货期安排决定(Due-date assignment decisions)的方法来解决作业车间调度问题. Baker[28]使用了调度规则和交货期安排两种方式分别解决两个阶段的问题并分析了影响分派规则的各类参数. Miyazaki[29]给出了一种在调度系统中加入顺序方式的分配方法用来降低作业延迟.这样的方法在子问题之间耦合关系较弱时, 可以取得很好的应用效果, 但如果子问题间相互依赖, 由于前序子种群的解已被确定, 当前阶段的子种群的知识探索便会被严重的制约, 无法跳出已有的约束搜索到更优的解.而实际生产环境中, 子问题间往往耦合度较高, 因此, 这样的方法依然不能很好地求解多个子问题.
为了充分考虑子种群之间依赖关系, 并将其在调度过程中加以体现, Cochran等[30]提出了一种基于代表机制的种群协同方式, 从而实现多个子种群同时进化. Goh等[31]使用的方法在进化初期允许分解优化问题, 并在各个种群中加入合作与竞争的机制.通过这样的方式, 子种群间的依赖关系就可以被充分考虑并且算法的计算效率也可以得到大幅度的提高.
基于以上分析, 为了保证算法在实际生产环境中的成功应用, 本文结合以上思路, 针对流水线向Seru生产系统转换问题的特点, 考虑了子种群之间的相互作用与影响, 设计了一种带有协同机制的进化算法.本文的主要贡献在于以下两点: 1)提出了充分考虑子种群间依赖关系的协同机制, 并将其应用在流水线向Seru生产系统转化的问题上; 2)对于协同机制两个子种群间个体相互依赖的特点, 设计了具有针对性的个体基因编码方式, 使协同机制能够被应用到进化算法中去.
2. 问题模型
流水线向Seru系统转化问题已受到广泛的关注, 本文参考Yu等[21]提出的问题模型, 以最小化TTPT和TLH作为优化调度目标, 同时考虑了Seru构建和Seru调度两个子问题的协同.
2.1 问题描述
带有装配流水线和装配Seru的装配系统主要有以下三种:纯Seru系统、纯装配线系统、混合装配系统[22].为了保留Seru生产系统基本特点并简化问题模型, 本文讨论的流水线向Seru转化问题是将流水线转换为纯Seru系统.
纯Seru生产中, Seru间生产的平衡极为重要.实际生产中, 生产批次的大小差异很大, 这使得在Seru构建和Seru调度的过程中极易出现Seru间生产不平衡的情况. Yu等[21]在研究中, 将生产批次的大小差异设计为正态分布.而本文的问题模型中, 生产批次的大小分布为均匀分布, 更贴合实际生产状况.
本文中对流水线向Seru转换方法的评估是基于帕累托(Pareto)多目标最优, 对TTPT和TLH两个指标进行评价.
2.2 问题假设
本文的基本假设条件如下:
1) 有N个产品类型, M个产品批次(每个批次只有一种产品类型), 且批次大小已知;
2) Seru中的大多数工序是用简单低价的设备完成的, 复制它们通常成本较小[6], 故复制设备的成本可忽略不计;
3) 一个产品批次只能在一个Seru中完成, 不考虑拆分;
4) 每一个工序都在其给定的设备中完成, 若某类型产品无需某种工序, 则跳过该工序的设备;
5) 在Seru中的工序与流水线中的工序一致, 共有W种不同的工序, 与工人人数相同;
6) 在Seru中, 每个工人能执行Seru的所有工序, 且忽略相邻工序之间的延时;
7) 在流水线生产方式中, 每个工人只执行一个工序, 工人数与工序数相等;
8) 不同Seru中的工人数可以不同, 但不超过工人总人数;
9) 两种不同类型产品相邻加工时, 考虑设备的准备时间, 否则忽略准备时间.
2.3 符号列表
与本文问题相关的符号变量定义如下所示.
索引:
i为工人的索引集(i = 1, 2, $\cdots, $ W), W为工人总数;
j为Seru序号的索引集(j = 1, 2, $\cdots, $ J);
n为产品型号的索引集(n = 1, 2, $\cdots, $ N);
m为产品批次的索引集(m = 1, 2, $\cdots, $ M);
k为产品批次在一个Seru中加工顺序的索引集(k = 1, 2, $\cdots, $ M).
参数:
$ V_{mn} = \begin{cases} 1,&{\text 表示批次的产品类型是n}\\ 0,&{\text 其他} \end{cases} $
$B_m$:批次m的大小;
$T_n$:为产品类型n在流水线的平衡时间;
${SL}_n$:为在流水线中加工产品类型n的准备时间;
${SCP}_n$:为在Seru中加工产品类型n的准备时间;
${\eta }_i$:为工人i在Seru中有效操作工序个数的上界, 当工人在Seru中操作工序的个数超过这个上界时, 其工序加工时间将变长;
${CW}_i$:工人$i$在Seru中操作多个工序的能力系数;
${\epsilon }_i$:为多能工系数;
${\beta }_{ni}$:为工人i加工产品类型n的技术系数, 值越小表示能力越高.
决策变量:
$ X_{ij} = \begin{cases} 1,&{\text 工人i配到了Seru j}\\ 0,&{\text 其他} \end{cases} $
$ Z_{mjk} = \begin{cases} 1,&{\text 批次m被分配到了 Seru ~j中}\\ &{\text 并被第k个生产}\\ 0,&{\text 其他} \end{cases} $
变量:
$ \begin{equation} \label{GrindEQ__1_} {CW}_i{\rm{=}}\begin{cases} {\rm{1+}}{\varepsilon }_i(W-{\eta }_i),&W>{\eta }_i \\ {\rm{1, }}&W{\rm{\le }}{\eta }_i \end{cases} , \forall i \end{equation} $
(1) ${TC}_m:\ $批次m的一个产品在Seru中一个工序的加工时间, 等于Seru中所有工人对批次m加工时间的平均值, 如式(2)所示:
$ \begin{equation} \label{GrindEQ__2_} {TC}_m=\frac{\sum\limits_{n=1}^N{\sum\limits_{i=1}^W{\sum\limits_{j=1}^J{\sum\limits_{k=1}^M{V_{mn}T_n{\beta }_{ni}{CW}_iX_{ij}Z_{mjk}}}}}}{\sum\limits_{i=1}^W{\sum\limits_{j=1}^J{\sum\limits_{k=1}^M{X_{ij}Z_{mjk}}}}} \end{equation} $
(2) ${SC}_m$:批次m在Seru中的准备时间, 如果批次m与Seru中上一批次的产品类型相同, 则其准备时间为0;否则为${SCP}_nV_{mn}$, 如式(3)所示:
$ \begin{equation} \label{GrindEQ__3_} {SC}_m{\rm{=}}\left\{ \begin{array}{l} {SCP}_nV_{mn}, \quad~ V_{mn}=1, V_{m'n}=0 \\ 0, \quad\qquad\qquad\ V_{mn}=\ V_{m'n}=1 \end{array} \right. \end{equation} $
(3) $(m'j Z_{mjk}=1, \ $ $Z_{m'j(k-1)}=1, \ \ {\rm{\forall }}j, k$)
${FC}_m$:批次m在Seru中的流通时间, 与批次大小、${TC}_m$、工序个数和Seru中的工人个数相关, 如式(4)所示:
$ \begin{equation} \label{GrindEQ__4_} {FC}_m{\rm{=}}\frac{B_m{TC}_mW}{\sum\limits_{i=1}^W{\sum\limits_{j=1}^J{\sum\limits_{k=1}^M{X_{ij}Z_{mjk}}}}} \end{equation} $
(4) ${FCB}_m$:批次m在Seru中的开始时间, 等于该Seru中前序批次流通时间和准备时间的总和, 如式(5)所示:
$ \begin{equation} \label{GrindEQ__5_} {FCB}_m{\rm{=}}\sum\limits^{m-1}_{s=1}{\sum\limits^J_{j=1}{\sum\limits^m_{k=1}{{(FS}_s+{SC}_s)Z_{mjk}Z_{sj(k-1)}}}} \end{equation} $
(5) 2.4 问题形式化描述
Seru系统的产品流通时间TTPT和总劳动时间TLH表示如下:
$ \begin{equation} \label{GrindEQ__6_} {\rm{TTPT=}} {\mathop{{\rm{min}}}_{} \left\{{\max\limits_{m} ({FCB}_m{\rm{+}}{FC}_m{\rm{+}}{SC}_m)}\right\}\ } \end{equation} $
(6) $ \begin{equation} \label{GrindEQ__7_} {\rm{TLH=}} {\mathop{{\rm{min}}}_{} \sum\limits^M_{m=1}{\sum\limits^W_{i=1}{\left(\sum\limits^J_{j=1}{\sum\limits^M_{k=1}{{FC}_mX_{ij}Z_{mjk}}}\right)}}\ } \end{equation} $
(7) 根据实际生产中的问题特性和约束, 本文的约束条件描述如下:
$ \begin{equation} \label{GrindEQ__8_} {\rm{1}}{\rm{\le }}\sum\limits^W_{i=1}{X_{ij}}{\rm{\le }}{\rm{W, \ \ }}{\rm{\forall }}j \end{equation} $
(8) $ \begin{equation} \label{GrindEQ__9_} \sum\limits^J_{j=1}{X_{ij}}=1, \ \ \forall i \end{equation} $
(9) $ \begin{equation} \label{GrindEQ__10_} \sum\limits^J_{j=1}{\sum\limits^M_{k=1}{Z_{mjk}}}={\rm{1, \ \ }}{\rm{\forall }}m \end{equation} $
(10) $ \begin{equation} \label{GrindEQ__11_} \sum\limits^M_{m=1}{\sum\limits^M_{k=1}{Z_{mjk}}}={\rm{0, \ }}{\rm{\forall }}j{\rm{\ |\ }}\sum\limits^W_{i=1}{X_{ij}}=0 \end{equation} $
(11) $ \begin{equation} \label{GrindEQ__12_} \sum\limits^J_{j=1}{\sum\limits^M_{k=1}{Z_{mjk}}}\le \sum\limits^J_{j' =1}{\sum\limits^M_{k'=1}{Z_{(m-1)j'k'}}} , m = 2, 3, {\cdots}, M \end{equation} $
(12) 其中, 式(8)表示每个Seru中的工人数不可超过工人总数; 式(9)表示每个工人必须且仅可被分配至一个Seru; 式(10)表示每个批次被且仅被一个Seru加工; 式(11)表示一个产品批次不可以被分配至没有工人的Seru; 式(12)表示产品批次必须按顺序被分配.
2.5 问题性质分析
流水线向Seru系统转化包含Seru构建和Seru调度两个决策过程. Yu等[20]已证明将现有流水线拆分为若干Seru的Seru构建问题是一个NP难问题.对于决策批次如何分配到Seru中的Seru调度问题的复杂度, 下面将给出简要说明.
已知多处理机调度问题是一个NP难问题, 描述如下:设有n个独立的作业$\{1, 2, {\cdots}, $ n}, 由m台相同的机器$\{1, 2, {\cdots}, $ m}, 进行加工处理.作业i所需时间为t${}_{i}$.任何作业可以在任何一台机器上加工处理, 但未完工前不允许中断处理, 任何作业不能拆分成更小的子作业.在满足以上约束下, 要求给出一种作业调度方案, 使所给的n个作业在尽可能短的时间内由m台机器加工处理完成.
在Seru调度问题中, 可将每一个已经被构建的Seru j, 对应于多机器调度问题中的一个机器, 每个加工批次m, 对应于作业.此处, 不同于多处理机问题中的机器, 各个Seru之间存在加工能力差异. Seru调度问题所求解的帕累托最优结果, 相较于多处理机调度问题也更为复杂.由此可见, 对于更为复杂的Seru调度问题, 其在多项式时间内也无法得到最优解.
3. MOCC算法
为解决流水线向Seru转化的问题, 本文提出了一种基于个体编码内部交换的进化算法.
由于所考虑的问题可分为Seru构建和Seru调度两个子问题, 并且子问题之间存在着交互作用, 本方法采用了协同进化的策略, 即形成两个子种群分别对应两个子问题.两个子种群互相协作共同进化, 最后进化出协同效果较好的完整解.
针对两个子种群的特点, 本方法设计了一种增加了冗余编码的编码方案, 以更好地进行Seru之间的平衡.
算法流程:
步骤1. 初始种群, 随机产生个体编码, 形成两个子种群;
步骤2. 使用个体编码内部交换操作对其中个体进行进化;
步骤3. 每个子种群在其他子种群代表的协助下评估种群内部个体适应度并更新代表;
步骤4. 每代种群进化后采用精英策略生成下一代种群;
步骤5. 若未达到迭代次数, 返回步骤2;若达到最终迭代次数, 停止.
3.1 编码方案
Seru生产系统的出现, 能够实现各个生产Seru间的平衡, 非常好地适应了当今加工周期短、多品种、小批量的生产模式.为了更好地实现Seru生产系统的平衡特性, 针对前文中提出的流水线向Seru转化问题所包含的Seru构建和Seru调度两个子问题, 我们分析了其各自的特点, 设计出了一种加入冗余码的编码方案.这种加入冗余码的编码方式可以更好地引导进化方向, 通过使Seru间的生产状态达到平衡, 更好地进行Seru构建和Seru调度.
针对Seru构建问题中可能出现的Seru个数及Seru内工人数量与加工货物批次大小间不能互相平衡协调的问题, 在Seru构建的编码中加入的冗余码用于对工人编码的分隔, 使各个Seru内包含的工人数量有所区别, 构成规模不同的Seru.
针对Seru调度问题中可能出现的货物批次大小与Seru规模不匹配造成的不平衡问题, 在Seru调度的编码中加入用于占位的冗余码, 使规模不同的Seru有机会被分配到不同个数的货物.
3.1.1 Seru构建
Seru构建是流水线向Seru转化问题中首要决策步骤, 它决定了Seru生产系统中Seru的个数以及每个Seru内的工人. Seru构建的结果将影响Seru生产系统的性能, 为了使构建好的Seru生产系统具有良好的平衡特性, 我们采用文献[21]中编码方式解决Seru构建子问题, 即一种通过加入冗余码对工人编码进行分隔的编码方式.
工人编码表示了构成当前Seru生产系统中所有的工人, 工人的不同组合可以构成不同的Seru, 所以Seru构建的过程就是将工人进行组合的过程.因此用一条编码表示一种全部工人的组合方式, 不同的编码组成一个种群在进化算法中进行进化.编码中不仅有全部工人的信息, 还加入了用于分隔的冗余码, 可将表示工人的编码进行划分.被冗余码分隔开的(在两个不相邻的冗余码之间的)工人编码同属于一个Seru, 这样不仅确定了Seru的个数, 也同时确定了Seru内工人的分配.
在进化过程中, 用于分隔的冗余码可能进化出不同的位置, 这样会使得每个Seru内包含的工人有所变化, 使Seru的规模出现变化, 更能适应变批量的生产情况, 有更强的平衡能力.
下面举例说明该编码方式:
考虑有5个工人编号为1 $\sim$ 5, 冗余码为6 $\sim$ 9的情况.
若编码为:
则Seru构建情况为:工人1为一个Seru, 工人2、5为一个Seru, 工人3、4为一个Seru.
若编码为:
则Seru构建情况为:工人5、3、2为一个Seru, 工人1、4为一个Seru.
3.1.2 Seru调度
Seru调度是指给各个Seru安排需要加工的批次.在解决流水线向Seru转化问题时, Seru调度往往在Seru构建好之后由简单的启发式规则来完成.而本文提出的方法将Seru调度也作为一个子问题通过进化算法给出调度方案.在解决Seru调度子问题时, 为了使所有的批次都能够被分配至构建的Seru中, 我们设计了一种基于求模运算的"批次－Seru"映射机制; 为了能使各个Seru更好地平衡对变批量批次的加工, 我们在批次的编码内设计了带有用于占位的冗余码的编码方式.
通过对批次编码的操作可以实现Seru的调度.在批次的编码中加入冗余码, 在每次进化后, 根据Seru构建的结果对每个编码的位置进行求模运算, 将每个编码安排入对应的Seru.若为冗余码, 则该位置空闲, 若为批次编码则将该批次放入该Seru进行加工.
在进行Seru调度的过程中, 不同的调度结果有可能导致Seru间的不平衡, 为使各个Seru保持平衡, 批次编码中增加了冗余编码.在添加冗余编码后, 批次编码分配入不同Seru的个数会产生变化, Seru的加工能力将通过这一方式再次平衡.
下面举例说明该编码方式:考虑有3个Seru, 5个批次编号为1 $\sim$ 5, 冗余码为6 $\sim$ 15的情况.
若编码为:
则Seru调度情况为:第一个Seru中有位置模3为0的编码: 11, 15, 14, 4, 8.去除冗余码后, 第一个Seru加工的批次为: 4.
第二个Seru中有位置模3为1的编码: 1, 6, 13, 9, 11.去除冗余码后, 第二个Seru加工的批次为: 1.
第三个Seru中有位置模3为2的编码: 7, 2, 5, 3, 10.去除冗余码后, 第三个Seru加工的批次为: 2, 5, 3.
若编码为:
则Seru调度情况为:第一个Seru中有位置模3为0的编码: 5, 15, 8, 4, 9.去除冗余码后, 第一个Seru加工的批次为: 5, 4.
第二个Seru中有位置模3为1的编码: 12, 13, 2, 11, 6.去除冗余码后, 第一个Seru加工的批次为: 2.
第三个Seru中有位置模3为2的编码: 14, 3, 7, 1, 10.去除冗余码后第一个Seru加工的批次为: 3, 1.
3.2 种群进化
种群的进化是根据问题模型设计基于个体编码的一种简单的进化算法.该方法针对一个种群, 通过对个体编码的内部操作, 经过种群内的进化淘汰迭代, 不断地优化个体结构, 产生更优解.
3.2.1 交换操作
内部交换是种群进化的最基本的方法, 它可以使种群内部产生新的个体, 使种群保持进化.交换个体内部编码可使新个体依据亲代的编码产生变化, 在一个种群内部, 可保持种群多样性.具体的做法是, 对于一个父代个体, 随机选取其自身编码两位进行交换产生新个体.
交换前:
如图, 深色的两位即是随机选取的两位编码, 交换后的个体编码如下:
交换后:
3.2.2 精英策略
精英策略指的是种群在进化过程中不断保存下部分性能最优个体的做法.在种群内部每一代进化过程中, 筛选出部分性能最优的个体, 这部分个体会进行保留, 不对其进行内部交换.用这些最优个体替换掉经过内部交换后较差的部分个体, 形成新的种群, 再进行下一次进化.
下面给出精英策略的形式化描述:
Parent = {p |亲代全部个体编码}
Elitist = {elite | elite ${\rm{\in }}$ Parent $\cap$ nondominated rankelite =1}
Offspring'= {p' | p'进化后个体编码}
Eliminated = {elim | elim ${\rm{\in }}$ Offspring' $\cap$ nondominated rankelim} = Max(nondominated rank)}
Offspring = Offspring'- Eliminated ${\rm{\cup }}{\rm{\ }}$Elitist其中, Parent为亲代种群, Elitist为精英个体集合, Eliminated为被淘汰个体种群, Offspring'为过渡子代种群, Offspring为最终子代种群.
3.3 种群协同
本文所考虑的问题可分为Seru的构建和Seru的调度两个子问题, 并且子问题之间存在着交互作用.由于以上所述的编码和进化过程中, 单个种群只针对两种子问题中的一个进行进化, 但是单个子种群中的个体无法构成一个完整的解, 所以在对一个子种群中个体的进化进行评价时, 需要加上其他子种群的个体形成一个完整的解.
本方法采用了协同进化的策略, 在本问题的两个子问题间建立协同机制, 使得对应的两个子种群互相协作共同进化, 最后进化出协同效果较好的完整解.在进化过程中, 在对每一个个体进行评估时, 都先将该个体与来自另一种群的代表个体组成对于问题的完整解, 再对该完整解进行评估, 即评估将由该个体和另一种群的代表个体协同完成.在本方法中, 子种群代表个体由二进制锦标赛算法, 根据非支配等级(Nondominated rank)从子种群中进行选择.
如图 7所示, 两个子种群A和B分别对应Seru构建和Seru调度两个子问题, 子种群之间为协同进化关系. a和b分别为子种群A和B中评价出的当前最优个体, a和b共同组成一个当前最优解.黑色实线箭头表示更新, 当子种群中有评价值更好的个体则对当前最优解的该部分进行替换.黑色虚线箭头代表子种群之间的协作, 表示在评估时使用另一个子种群的最优个体.例如, 当前最优解为ab, 当子种群A在评估种群内的某个个体a'时, 则使用b与a'组成一个完整解进行调度, 进而得到适应度赋给a'.如果此时a'的适应度比a高, 说明出现了一组协同更优的解, 我们把a替换成a', 当前的最优解为a'b.根据此种方式, 子种群在进化中互相影响, 最终得到一个可使种群间协作较好的解.
4. 对比实验
为了验证本方法的优化性能和计算效率, 本文进行了多组对比实验, 仿真实验采用C#语言实现, 运行在3.10 GHz Core i5-2400 CPU, 4 GB RAM的PC机上.
4.1 实验设计
本文实验设计的工人数为20, 多能工系数$\varepsilon{_{i}}$按N (0.2, 0.05)分布, 具体如表 1所示.工人对不同类型产品熟练度数据的分布、工人对不同产品的熟练度以及30批产品的信息数据, 如表A1, A2, A3, A4所示.进化算法交叉率P${_{c}}$为0.5, 精英策略中精英数量N${_{elite}}$为10.
表 1 算例产生的参数表Table 1 Parameters of test problems算例产生参数 取值 产品类型 5 批次大小 $\sim$ U[10, 110] $\varepsilon$${}_{i}$ $\sim$ N[0.2, 0.05] SL${}_{n}$ 2.2 SCP${}_{n}$ 1.0 $T{}_{n}$ 1.8 $\eta$${}_{i}$ 10 4.2 协同策略的影响
本文在进化算法中加入了协同机制, 在考虑两个子问题间交互关系的前提下, 同时对两个子问题进行规划以求获得性能更优的规划结果.
为了检验协同机制的有效性, 实验与没有加入协同机制的方法(Multi-objective evolution, MOE)进行了对比.
在这里, 我们引入了参考集(由于问题规模较为庞大, 无法求得精确解, 故将算法迭代100次后获得的非支配集作为参考集), 并使用了RNI (Ratio of non-dominated individuals)[32]与$D$[34-35]两个指标对算法性能进行评估.
其中RNI定义了非支配集中解的个数与参考集中解个数的比值, RNI越高即代表所得出非支配集的有效解越多; $D$即为非支配集中的解与参考集中解的距离, $D$越小即代表非支配集越接近参考集.
在没有加入协同机制的方法中, 先用本文方法解决Seru构建子问题; 再根据其结果用经典规则FCFS解决Seru调度子问题; 最后将对两个子问题的结果合成一个完整的解, 与本文中使用协同进化的算法结果进行比较.
在5个工人的情况下, 其两个评价指标TLH和TTPT的帕累托前沿结果对比如图 8所示.
图 8 工人数量为5时, MOCC与未加入协同算法的非支配集间的比较Fig. 8 The non-dominated solutions of MOCC and the one without cooperation strategy with 5 workers其余对比结果如表 2所示, MOCC与未加入协同机制的算法之间的Gap值计算方法均参考公式(13)、(14), $Av$为Average的缩写:
表 2 与未使用协同策略的性能对比Table 2 Comparison proposed approach and the one without cooperation strategy$W$ ${R}$ Proposed algorithm MOE ${\rm Gap}_{{\rm RNI}\_AV}$(%) ${\rm Gap}_{D\_AV}$(%) $Av$ RNI Min RNI $Av$ $D_{av}$ $Av$ $D_{\max}$ $Av$ RNI Min RNI $Av$ $D_{av}$ $Av$ $D_{\max}$ 5 20 0.66 0.50 0.04 0.09 0.42 0.35 0.13 0.37 57.14 256.83 10 43 0.50 0.33 0.12 0.68 0.45 0.35 0.16 0.81 10.00 36.63 15 62 0.51 0.32 0.03 0.22 0.40 0.45 0.06 0.48 27.50 117.42 20 57 0.65 0.47 0.02 0.13 0.41 0.35 0.05 0.36 56.89 169.32 25 31 0.64 0.54 0.11 0.26 0.52 0.44 0.16 0.21 22.96 49.06 30 39 0.69 0.56 0.09 0.28 0.41 0.46 0.18 0.32 45.57 87.23 Average 36.68 119.42 注: $W$表示工人数量, $R$表示参考集中解的数量 $ \begin{equation} \label{GrindEQ__13_} {\rm Gap}_{{\rm RNI}\_AV}=\frac{{Av\ {\rm RNI}}_{\rm MOCC}-{Av\ {\rm RNI}}_{\ {\rm MOE}}}{{Av\ {\rm RNI}}_{{\rm{\rm MOCC}}\ }} \end{equation} $
(13) $ \begin{equation} \label{GrindEQ__14_} {\rm Gap}_{D\_AV}{\rm{=}}\frac{{Av\ D}_{{\rm{\rm MOCC}}\ }{\rm{-}}{Av\ D}_{\rm MOE}}{{Av\ D}_{{\rm{\rm MOCC}}\ }} \end{equation} $
(14) 由实验结果可知, 在不同规模的测试问题下, 加入协同机制的方法均优于未加入协同机制方法的优化性能, Gap${}_{{\rm RNI}\_AV}$平均值为36.68 %, Gap${}_{D\_AV}$平均值为119.42 %.这组实验表明, 由加入协同机制的算法产生的解不仅有效解更多, 而且也更靠近参考集, 优化性能较未加入协同机制的算法有明显的提升.
产生这样结果的原因在于, 加入协同机制之后, 问题的两个子问题(即Seru构建与Seru调度)协同进化, 算法生成的解在解决对应子问题时, 考虑了子问题间的耦合关系, 因此与单独对子问题进化所产生的解相比, MOCC所产生解的协同性能较为理想的.而Seru生产系统能够发挥其优势的关键正是在于两阶段能够同时进行调整所产生的柔性与灵活性, 因此协同性能更好的解往往会为Seru系统带来更佳的应用效果.由此可见, 未加入协同机制的方法虽然能够在单个子问题上获得较好的应用效果, 但当两个子问题的解组合为完整的解时, 由于其进化时模拟的场景不尽相同, 综合求解能力也就与加入协同机制的方法相比较差.
4.3 与其他方法对比
本文选择了2种解决流水线向Seru生产系统转化问题的方法对比我们的方法进行实验, 分别为: NSGA-Ⅱ和加入局部搜索的NSGA-Ⅱ.除了引入RNI及D等指标进行性能对比, 为了更好地验证本方法对Seru生产系统进行均衡的能力, 我们还引入了STDEV (Standard deviation)${}_{\rm TTPT}$作为衡量算法均衡性能的指标. STDEV${}_{\rm TTPT}$定义了方案中不同Seru间TTPT的标准差, STDEV${}_{\rm TTPT}$越小, 即代表不同$Seru$间加工流通时间差距越小、$Seru$系统加工能力的浪费越少, 算法的均衡性能也就越好.
4.3.1 与NSGA-Ⅱ方法的对比
NSGA-Ⅱ[36]是一种基于GA (Genetic algorithm)的进化方法. Yu等[21]采用NSGA-Ⅱ, 以解决流水线向Seru系统转化问题.本节将进行MOCC与NSGA-Ⅱ的对比实验.为了保证实验的公平性, 对比实验采用了与文献[21]相同的问题模型以及实验参数.
与本文中使用协同进化的算法结果进行比较, 其两个评价指标TLH和TTPT的帕累托前沿结果如图 9所示.其余对比结果如表 3所示, MOCC与NSGA-Ⅱ之间的Gap值计算方法均参考公式(15) $\sim$ (17):
图 9 工人数量为5时, MOCC与NSGA-Ⅱ算法的非支配集间的比较Fig. 9 The non-dominated solutions of MOCC and NSGA-Ⅱ with 5 workers表 3 与NSGA-Ⅱ方法的性能对比Table 3 Comparison of proposed approach and NSGA-Ⅱ${W}$ ${R}$ Proposed algorithm NSGA-Ⅱ ${\rm Gap}_{{\rm RNI}\_AV}$(%) ${\rm Gap}_{D\_AV}$(%) ${{\rm Gap}_{\rm STDEV}}$ $Av$ RNI $Av$ $D_{av}$ $Av$ $D_{\max}$ STDEV TTPT $Av$ RNI $Av$ $D_{av}$ $Av$ $D_{\max}$ STDEV TTPT 5 20 0.66 0.04 0.09 134.91 0.37 0.14 0.40 390.95 78.38 281.42 189.79 10 43 0.45 0.12 0.68 330.33 0.35 0.14 0.69 1 101.28 25.71 20.61 233.39 15 62 0.40 0.03 0.22 552.93 0.27 0.06 0.45 2 518.01 48.71 142.42 355.39 20 57 0.65 0.02 0.13 1 672.87 0.23 0.06 0.38 5 443.23 176.02 263.64 225.38 25 31 0.64 0.11 0.26 1 551.91 0.49 0.18 0.31 7 613.63 31.52 73.58 390.60 30 39 0.69 0.09 0.28 1 286.32 0.41 0.19 0.27 6 156.87 66.68 97.87 378.64 Average 71.17 146.59 295.53 $ \begin{equation} \label{GrindEQ__15_} {\rm Gap}_{{\rm RNI}\_AV}=\frac{{Av\ {\rm RNI}}_{{\rm{MOCC}}\ }-{Av\ {\rm RNI}}_{\rm NSGA-Ⅱ\ }}{{Av\ {\rm RNI}}_{{\rm{MOCC}}\ }} \end{equation} $
(15) $ \begin{equation} \label{GrindEQ__16_} {\rm Gap}_{D\_AV}=\frac{{Av\ D}_{{\rm{MOCC}}\ }-{Av\ D}_{\rm NSGA-Ⅱ\ }}{{Av\ D}_{{\rm{MOCC}}\ }} \end{equation} $
(16) $ \begin{equation} \label{GrindEQ__17_} {\rm Gap}_{\rm STDEV}=\frac{{Av\ {\rm STDEV}}_{{\rm{MOCC}}\ }-{Av\ \rm STDEV}_{\rm NSGA-Ⅱ\ }}{{Av\ {\rm STDEV}}_{{\rm{MOCC}}\ }} \end{equation} $
(17) 由实验结果可知, MOCC与NSGA-Ⅱ相比, RNI平均提升了71.17 %, $D$平均提升了146.59 %, STDEV TTPT平均提升了295.53 %.这组实验表明, 本方法产生的规划方案不仅在生产性能指标上较NSGA-Ⅱ有所提升, 均衡性能也有较为明显的改善.
分析实验结果, MOCC较NSGA-Ⅱ的优势主要有两个方面.一方面, 协同机制的加入, 使得MOCC更能适应流水线向Seru生产系统转化问题的特点, 即两阶段子问题相互依赖、耦合度高, 避免了NSGA-Ⅱ子问题单独进化时, 过度缩小搜索空间所导致解的多样性受到限制的问题.另一方面, 由于引入了冗余码, MOCC所产生的解不仅在均衡性上具有优势, 而且能够充分体现Seru生产系统的柔性, 避免了Seru在进行构建及调度时受到不必要约束, 从而提高了解的质量.因此, 与传统方法相比, MOCC在解决流水线向Seru生产系统转化的问题上具有一定优势.
4.3.2 与加入局部搜索的NSGA-Ⅱ方法对比
加入局部搜索(Local search)的NSGA-Ⅱ可以增强NSGA-Ⅱ的寻优能力. Yu等[19]将局部搜索加入NSGA-Ⅱ, 以获得更佳的流水线向Seru系统转化方案.本节将进行MOCC与加入局部搜索的NSGA-Ⅱ的对比实验.为了保证实验的公平性, 对比实验采用了与文献[19]相同的问题模型以及实验参数.
与本文中使用协同进化的算法结果进行比较, 其两个评价指标TLH和TTPT的帕累托前沿结果如图 10所示.其余对比结果如表 4所示, MOCC与加入局部搜索的NSGA-Ⅱ之间的Gap值计算方法均参考公式(18) $\sim$ (20):
图 10 工人数量为5时, MOCC与加入局部搜索的NSGA-Ⅱ算法的非支配集间的比较Fig. 10 The non-dominated solutions of MOCC and NSGA-Ⅱ combining local search with 5 workers表 4 与加入local search的NSGA-Ⅱ方法的性能对比Table 4 Comparison of proposed approach and NSGA-Ⅱ combining local search${W}$ ${R}$ Proposed algorithm NSGA-Ⅱ combining local search ${\rm Gap}_{{\rm RNI}\_AV}$(%) ${\rm Gap}_{D\_AV}$(%) ${{\rm Gap}_{\rm STDEV}}$ $Av$ RNI $Av$ $D_{av}$ $Av$ $D_{\max}$ STDEV TTPT $Av$ RNI $Av$ $D_{av}$ $Av$ $D_{\max}$ STDEV TTPT 5 20 0.66 0.04 0.09 134.91 0.40 0.13 0.42 377.08 65.00 262.84 179.51 10 43 0.45 0.12 0.68 330.33 0.39 0.15 0.68 1 010.48 15.68 26.75 205.90 15 62 0.40 0.03 0.22 552.93 0.26 0.07 0.52 3 122.81 53.92 159.85 464.78 20 57 0.65 0.02 0.13 1 672.87 0.29 0.06 0.39 5 275.38 122.79 263.64 215.35 25 31 0.64 0.11 0.26 1 551.91 0.51 0.17 0.26 6 962.83 26.35 64.15 348.66 30 39 0.69 0.09 0.28 1 286.32 0.47 0.16 0.34 6 261.26 47.44 74.47 386.76 Average 55.20 141.95 300.16 $ \begin{equation} \label{GrindEQ__18_} {\rm Gap}_{{\rm RNI}\_AV}=\frac{{Av\ {\rm RNI}}_{{\rm{\rm MOCC}}\ }-{Av\ \rm RNI}_{\rm NSGA\mbox{-}II\_local\ search\ }}{{Av\ {\rm RNI}}_{{\rm{\rm MOCC}}\ }} \end{equation} $
(18) $ \begin{equation} \label{GrindEQ__19_} {\rm Gap}_{D\_AV}=\frac{{Av\ D}_{{\rm{MOCC}}\ }-{Av\ D}_{\rm NSGA\mbox{-}II\_local\ search\ }}{{Av\ D}_{{\rm{\rm MOCC}}\ }} \end{equation} $
(19) $ \begin{equation} \label{GrindEQ__20_} { {\rm Gap}_{\rm STDEV}=\frac{{Av\ {\rm STDEV}}_{{\rm{MOCC}}\ }-{Av\ {\rm STDEV}}_{\rm NSGA\mbox{-}II\_\ local\ search\ }}{{Av\ {\rm STDEV}}_{{\rm{\rm MOCC}}\ }}} \end{equation} $
(20) 由实验结果可知, MOCC与加入局部搜索的NSGA-Ⅱ方法相比, RNI平均提升了55.20 %, D平均提升了141.95 %, STDEV TTPT平均提升了300.16 %.实验结果表明, 虽然加入了局部搜索使得NSGA-Ⅱ的寻优性能有所提升, 产生的有效解数量较NSGA-Ⅱ有一定程度上的增加, 但由于Seru系统转化问题的特点, 两个子问题解的协同性能也是影响完整解性能的一个重要因素, 因此本文加入了协同机制的方法依然体现出了能够同时考虑子问题间相互作用的优势.在均衡性能上, 由于引入了冗余码, MOCC的优势也较为明显.
4.4 在实际生产中的应用
为了进一步评估MOCC的性能, 本文构建了一个基于内蒙古第一机械集团(内蒙一机)实际生产环境的Seru生产系统, 并将MOCC应用到该系统的生产调度中.部分在实际生产中常用的经典的生产调度规则也在本节中与MOCC进行对比.
内蒙一机在传动装置的生产中, 操纵电控部件、液力变矩器、行星变速装置等小型零部件装配中已经初步实施了Seru生产系统.本文将内蒙一机构建的一处Seru生产系统用于对比实验, 该系统包含有10个工人.在本文构建的Seru生产系统在内蒙一机应用前, 内蒙一机的Seru调度是由调度人员根据经典的生产调度规则进行的, 例如, 先到先服务(FCFS)、最短加工时间(Shortest processing time, SPT)、最短劳动时间(Shortest total labor hour, STLH)、最短等待时间(Shortest waiting time, SWT).内蒙一机的Seru生产系统中有两到三名调度员专门负责生产过程中的Seru调度.虽然有上述调度规则的协助, 但由于Seru生产系统的复杂性, 人工调度的结果往往难以满足实际生产的需求, 使得Seru系统成为整个企业生产系统中的瓶颈.
本文采用了采集自内蒙一机Seru生产系统的实际生产数据, 将MOCC与上述4条经典的生产调度规则进行对比.实验结果表明利用MOCC构建的Seru生产系统性能优于经典调度规则, RNI平均提升了79.65 %, $D$平均提升了274.61 %, STDEV TTPT平均提升了226.36 %.
由实验结果可以看出, MOCC相较于经典调度规则, 规划结果更具有针对性, 因此具有更强的优化能力, 规划出的Seru生产系统也具有更优的均衡性能, 能够更好地发挥出Seru生产系统在实际生产中的潜力与优势.
5. 结论
本文针对流水线向Seru生产系统转化问题的特点, 从实际应用的要求出发, 提出一种基于个体编码内部交换的MOCC算法, 并针对问题特点, 加入了种群间协同机制, 解决流水线向Seru生产系统转化问题.由于所考虑的问题可分为Seru的构建和Seru的调度两个子问题, 并且子问题之间存在着交互作用, 所以该方法使用了两个子种群互相协作共同进化, 最后进化出协同效果较好的完整解.通过这样的方式, 该方法可以在兼顾计算效率的前提下, 获得良好的优化能力.实验结果表明, 与子问题单独进化相比, 协同进化能够有效扩大算法搜索范围, 充分发挥Seru生产系统的柔性与灵活性, 最终生成的规划方案也能够在实际生产中取得更好的应用效果.与应用NSGA-Ⅱ等传统算法求解该问题的方法相比, MOCC不仅在生产指标(如TTPT等)上优于传统算法, 所产生规划方案的均衡性能也有较为突出的表现.这种差异的原因在于, 通过子种群间的协同机制, 本方法同时考虑了Seru构建与Seru调度两个方面, 而传统方法往往将关注点置于Seru构建的规划上, 仅使用例如FCFS的启发式规则对Seru调度阶段进行规划, 虽然降低了问题的复杂性, 但也忽视了Seru调度阶段的重要性.并且, 我们在编码方案中引入冗余码, 增加了解的多样性, 从而提高了算法的优化性能.由此可见, MOCC同时兼备计算效率和优化性能的优势, 可以在实际应用中高效地解决复杂性高, 产品批次大小波动较大的流水线向Seru生产系统转化问题.
附录A
表 A1 工人i的多能工系数Table A1 Worker i's coefficient of influencing level of doing multiple assembly task工人 1 2 3 4 5 $\varepsilon{}_{i}$ 0.18 0.19 0.2 0.21 0.2 工人 6 7 8 9 10 $\varepsilon{}_{i}$ 0.2 0.2 0.22 0.19 0.19 工人 11 12 13 14 15 $\varepsilon{}_{i}$ 0.18 0.23 0.24 0.22 0.16 工人 16 17 18 19 20 $\varepsilon{}_{i}$ 0.24 0.18 0.18 0.21 0.18 表 A2 工人对不同类型产品熟练度数据的分布Table A2 The data distribution of worker's level of skill for each product type产品类型 1 2 3 4 5 N(1, 0.05) N(1.05, 0.05) N(1.1, 0.05) N(1.15, 0.05) N(1.2, 0.05) 表 A3 工人对不同产品的熟练度Table A3 The data of worker's level of skill工人/产品 1 2 3 4 5 1 0.92 0.96 1.04 1.09 1.20 2 0.95 0.97 1.09 1.12 1.18 3 0.99 1.01 1.05 1.09 1.21 4 1.03 1.07 1.09 1.12 1.25 5 0.96 1.02 1.05 1.10 1.18 6 1.01 1.10 1.10 1.15 1.23 7 1.04 1.07 1.09 1.17 1.24 8 0.98 1.02 1.10 1.11 1.20 9 0.97 1.03 1.12 1.19 1.26 10 0.98 1.06 1.13 1.18 1.28 11 0.95 1.04 1.03 1.14 1.19 12 0.98 1.07 1.07 1.15 1.15 13 0.99 0.95 1.11 1.17 1.10 14 1.01 1.10 1.05 1.13 1.18 15 1.04 1.10 1.05 1.15 1.11 16 0.99 0.97 1.08 1.11 1.22 17 1.04 1.01 1.11 1.15 1.24 18 0.93 1.06 1.07 1.13 1.14 19 0.96 0.98 1.12 1.14 1.21 20 1.08 1.04 1.09 1.11 1.13 表 A4 30批产品的信息数据Table A4 The data of 30 batches批次编号 产品类型 批次大小 1 3 46 2 5 68 3 3 45 4 4 19 5 1 36 6 4 45 7 1 62 8 2 30 9 2 60 10 3 67 11 2 9 12 4 24 13 3 38 14 4 32 15 5 52 16 5 48 17 1 68 18 4 71 19 2 46 20 5 25 21 1 26 22 3 52 23 4 46 24 5 44 25 2 32 26 3 75 27 1 33 28 4 103 29 2 74 30 3 53
-
图 9 序列3的OE-MSVR预测效果图
Fig. 9 The prediction of the third sequence with OE-MSVR algorithm
表 1 各个阶段预测结果性能指标对比
Table 1 Prediction performance parameters of capillary of three stages
序列 RMSE MAE 初始序列 聚类后 异常序列剔除后 初始序列 聚类后 异常序列剔除后 序列3 0.0589 0.0511 0.0319 0.0405 0.0357 0.0248 序列4 0.0843 0.0814 0.0364 0.0638 0.0603 0.0270 序列5 0.0559 0.0508 0.0379 0.0435 0.0387 0.0292 序列6 0.0675 0.0585 0.0350 0.0494 0.0435 0.0269 
下载: 导出CSV
表 2 实际数据集信息
Table 2 Real datasets
数据集 样本数目 属性数目 训练样本 测试样本 澳门气象数据 1 276 547 11 Monitor system 1 260 540 19 Istanbul stock exchange 375 161 9 Air quality 1 680 720 13 Gas sensor array drift 310 133 30
下载: 导出CSV
表 3 A monitorsystem数据集预测结果性能指标对比
Table 3 Prediction performance parameters of capillary of A monitor system dataset
序列 RMSE MAE OE-MSVR Fol-BP SVR ELM AR OE-MSVR Fol-BP SVR ELM AR 序列1 0.1318 0.4561 0.8583 0.2388 0.1628 0.0949 0.3288 0.4115 0.1115 0.1628 序列2 0.1006 0.5843 0.4862 0.1926 0.1514 0.0835 0.4236 0.3271 0.1249 0.1514 序列5 4.7365 9.1443 14.5330 6.8052 4.0215 3.0607 6.4887 14.2472 2.4689 4.0215 序列6 0.5226 1.6900 0.7693 0.4723 0.4642 0.3459 1.1693 0.6508 0.3407 0.4642 序列7 0.3767 1.2893 0.5828 0.3817 0.2548 0.2730 0.9145 0.4679 0.2784 0.2548 序列17 0.2112 0.9896 1.6971 0.4789 0.2820 0.1642 0.7497 0.7099 0.2239 0.2820 序列18 0.7122 2.2701 0.9597 0.8947 0.6812 0.5146 1.7620 0.7590 0.6643 0.6812 序列19 0.1244 0.7442 0.2993 0.0434 0.0994 0.0613 0.4913 0.2992 0.0038 0.0994
下载: 导出CSV
表 4 Italian airquality数据集预测结果性能指标对比
Table 4 Prediction performance parameters of capillary of Italian air quality
序列 RMSE MAE OE-MSVR Fol-BP SVR ELM AR OE-MSVR Fol-BP SVR ELM AR 序列2 121.9587 122.2608 123.6130 122.9571 123.4309 75.7143 70.2002 75.4696 76.6154 69.6428 序列5 146.4420 148.3487 146.5258 146.3931 168.6011 89.7674 89.3968 88.6896 92.8062 100.1906 序列7 113.6631 113.6741 117.6938 122.5415 123.6603 76.7395 77.8434 81.9074 85.8995 85.7884 序列9 165.8359 167.1297 167.6215 174.2383 184.5600 100.3676 100.1063 101.4094 106.4807 108.7986 序列10 178.1549 180.5234 186.9799 190.4919 200.0233 120.5245 118.7809 125.6156 129.6792 131.0641
下载: 导出CSV
表 5 Istanbul stockexchange数据集预测结果性能指标对比
Table 5 Prediction performance parameters of capillary of Istanbul stock exchange
序列 RMSE MAE OE-MSVR Fol-BP SVR ELM AR OE-MSVR Fol-BP SVR ELM AR 序列1 0.0119 0.0192 0.0121 0.0133 0.0119 0.0090 0.0140 0.0092 0.0101 0.0092 序列2 0.0151 0.0217 0.0153 0.0167 0.0151 0.0116 0.0167 0.0117 0.0128 0.0117 序列5 0.0097 0.0170 0.0095 0.0110 0.0098 0.0072 0.0123 0.0073 0.0083 0.0073
下载: 导出CSV
表 6 Gas sensor arraydrift数据集预测结果性能指标对比
Table 6 Prediction performance parameters of capillary of Gas sensor array drift dataset
序列 RMSE MAE OE-MSVR Fol-BP SVR ELM AR OE-MSVR Fol-BP SVR ELM AR 序列2 9.08E + 04 2.58E + 05 9.17E + 04 1.17E + 05 9.27E + 04 5.20E + 04 1.58E + 05 5.73E + 04 7.48E + 04 5.30E + 04 序列4 22.7062 74.2977 27.8097 26.3881 25.4101 10.9343 39.8237 17.5229 17.1492 15.2092 序列5 31.5850 111.9757 34.3149 39.0925 34.9793 16.1337 73.2789 20.6630 25.5340 21.5229 序列6 45.5174 221.2905 52.0124 59.9806 52.5336 22.6310 118.2681 27.9837 36.8887 30.6452 序列12 18.0458 80.8880 24.1219 28.6046 20.4600 9.0439 45.7426 16.7021 16.8084 12.8685 序列13 26.9213 79.6147 26.4391 34.9546 30.0822 13.2553 49.2278 16.5452 24.2313 19.3481 序列14 36.5061 241.8456 38.7079 49.0467 43.4256 15.8653 138.9438 20.7230 27.4320 24.8211 序列22 3.2263 5.0164 3.4150 2.7369 2.3271 2.7023 2.9809 2.9791 1.8935 1.4541 序列30 3.1137 6.3610 3.4056 2.7941 2.2838 2.5935 4.2371 3.0138 1.8682 1.3841
下载: 导出CSV
-
[1] Schölkopf B B, Smola A J. Learning with Kernels. Cambridge, Britain:MIT Press, 2002, 3:2165-2176 https://www.cs.utah.edu/~piyush/teaching/learning-with-kernels.pdf [2] 张勇, 关伟.基于最大Lyapunov指数的多变量混沌时间序列预测.物理学报, 2009, 58(2):756-763 doi: 10.7498/aps.58.756Zhang Yong, Guan Wei. Predication of multivariable chaotic time series based on maximal Lyapunov exponent. Acta Physica Sinica, 2009, 58(2):756-763 doi: 10.7498/aps.58.756 [3] Sun B Q, Guo H F, Karimi H R, Ge Y J, Xiong S. Prediction of stock index futures prices based on fuzzy sets and multivariate fuzzy time series. Neurocomputing, 2015, 151:1528-1536 doi: 10.1016/j.neucom.2014.09.018 [4] 韩敏, 许美玲, 任伟杰.多元混沌时间序列的相关状态机预测模型研究.自动化学报, 2014, 40(5):822-829 http://www.aas.net.cn/CN/abstract/abstract18350.shtmlHan Min, Xu Mei-Ling, Ren Wei-Jie. Research on multivariate chaotic time series prediction using mRSM model. Acta Automatica Sinica, 2014, 40(5):822-829 http://www.aas.net.cn/CN/abstract/abstract18350.shtml [5] Wang X Y, Han M. Improved extreme learning machine for multivariate time series online sequential prediction. Engineering Applications of Artificial Intelligence, 2015, 40:28-36 doi: 10.1016/j.engappai.2014.12.013 [6] Han M, Xu M L, Liu X X, Wang X Y. Online multivariate time series prediction using SCKF-γ ESN model. Neurocomputing, 2015, 147:315-323 doi: 10.1016/j.neucom.2014.06.057 [7] Chen T T, Lee S J. A weighted LS-SVM based learning system for time series forecasting. Information Sciences, 2015, 299:99-116 doi: 10.1016/j.ins.2014.12.031 [8] Sanchez-Fernandez M, de-Prado-Cumplido M, Arenas-Garcia J, Perez-Cruz F. SVM multiregression for nonlinear channel estimation in multiple-input multiple-output systems. IEEE Transactions on Signal Processing, 2005, 52(8):2298-2307 http://ieeexplore.ieee.org/xpls/icp.jsp?arnumber=1315948 [9] Bao Y K, Xiong T, Hu Z Y. Multi-step-ahead time series prediction using multiple-output support vector regression. Neurocomputing, 2014, 129:482-493 doi: 10.1016/j.neucom.2013.09.010 [10] Han J W, Kamber M, Pei J[著], 范明, 孟小峰[译]. 数据挖掘概念与技术(第3版) (计算机科学丛书). 北京: 机械工业出版社, 2012. 297-301Han J W, Kamber M, Pei J[Author], Fan Ming, Meng Xiao-Feng[Translator]. Data Mining Concepts and Techniques (3rd edition) (Computer Science Series). Beijing: China Machine Press, 2012. 297-301 [11] 韩忠明, 陈妮, 乐嘉锦, 段大高, 孙践知.面向热点话题时间序列的有效聚类算法研究.计算机学报, 2012, 35(11):2337-2347 http://kns.cnki.net/KCMS/detail/detail.aspx?filename=jsjx201211012&dbname=CJFD&dbcode=CJFQHan Zhong-Ming, Chen Ni, Le Jia-Jin, Duan Da-Gao, Sun Jian-Zhi. An efficient and effective clustering algorithm for time series of hot topics. Chinese Journal of Computers, 2012, 35(11):2337-2347 http://kns.cnki.net/KCMS/detail/detail.aspx?filename=jsjx201211012&dbname=CJFD&dbcode=CJFQ [12] Lee H. The Euclidean distance degree of Fermat hypersurfaces. Journal of Symbolic Computation, 2017, 80:502-510 doi: 10.1016/j.jsc.2016.07.006 [13] Hautamaki V, Nykanen P, Franti P. Time-series clustering by approximate prototypes. In: Proceedings of the 19th International Conference on Pattern Recognition. Tampa, FL, USA: IEEE, 2008. 1-4 [14] 杨一鸣, 潘嵘, 潘嘉林, 杨强, 李磊.时间序列分类问题的算法比较.计算机学报, 2007, 30(8):1259-1266 http://kns.cnki.net/KCMS/detail/detail.aspx?filename=jsjx200708010&dbname=CJFD&dbcode=CJFQYang Yi-Ming, Pan Rong, Pan Jia-Lin, Yang Qiang, Li Lei. A comparative study on time series classification. Chinese Journal of Computers, 2007, 30(8):1259-1266 http://kns.cnki.net/KCMS/detail/detail.aspx?filename=jsjx200708010&dbname=CJFD&dbcode=CJFQ [15] 张军平, 王珏.主曲线研究综述.计算机学报, 2003, 26(2):129-146 http://kns.cnki.net/KCMS/detail/detail.aspx?filename=jsjx200302000&dbname=CJFD&dbcode=CJFQZhang Jun-Ping, Wang Yu. An overview of principal curves. Chinese Journal of Computers, 2003, 26(2):129-146 http://kns.cnki.net/KCMS/detail/detail.aspx?filename=jsjx200302000&dbname=CJFD&dbcode=CJFQ [16] 毛文涛, 王金婉, 何玲, 袁培燕.面向贯序不均衡数据的混合采样极限学习机.计算机应用, 2015, 35(8):2221-2226 doi: 10.11772/j.issn.1001-9081.2015.08.2221Mao Wen-Tao, Wang Jin-Wan, He Ling, Yuan Pei-Yan. Hybrid sampling extreme learning machine for sequential imbalanced data. Journal of Computer Application, 2015, 35(8):2221-2226 doi: 10.11772/j.issn.1001-9081.2015.08.2221 [17] 孙克辉, 贺少波, 尹林子, 阿地力·多力坤.模糊熵算法在混沌序列复杂度分析中的应用.物理学报, 2012, 61(13):130507 doi: 10.7498/aps.61.130507Sun Ke-Hui, He Shao-Bo, Yin Lin-Zi, A Di-Li·Duo Li-Kun. Application of fuzzyen algorithm to the analysis of complexity of chaotic sequence. Acta Physica Sinica, 2012, 61(13):130507 doi: 10.7498/aps.61.130507 [18] 毛文涛, 赵胜杰, 张俊娜.基于主曲线的多输入多输出支持向量机算法.计算机应用, 2013, 33(5):1281-1284, 1293 http://kns.cnki.net/KCMS/detail/detail.aspx?filename=jsjy201305022&dbname=CJFD&dbcode=CJFQMao Wen-Tao, Zhao Sheng-Jie, Zhang Jun-Na. Multi-input-multi-output support vector machine based on principal curve. Journal of Computer Application, 2013, 33(5):1281 -1284, 1293 http://kns.cnki.net/KCMS/detail/detail.aspx?filename=jsjy201305022&dbname=CJFD&dbcode=CJFQ [19] Yuan P Y, Ma H D, Fu H Y. Hotspot-entropy based data forwarding in opportunistic social networks. Pervasive and Mobile Computing, 2015, 16:136-154 doi: 10.1016/j.pmcj.2014.06.003 [20] 汤礼东, 宋保维, 李正, 郑珂.基于信息熵理论的小子样模糊可靠性评定方法.弹箭与制导学报, 2005, 25(S1):214-216 http://kns.cnki.net/KCMS/detail/detail.aspx?filename=djzd2005s1040&dbname=CJFD&dbcode=CJFQTang Li-Dong, Song Bao-Wei, Li Zheng, Zheng Ke. A fuzzy reliability evaluation method for sub-sample products based on information entropy theory. Journal of Projectiles, Rockets, Missiles and Guidance, 2005, 25(S1):214-216 http://kns.cnki.net/KCMS/detail/detail.aspx?filename=djzd2005s1040&dbname=CJFD&dbcode=CJFQ [21] Mao W T, Zhao S J, Mu X X, Wang H C. Multi-dimensional extreme learning machine. Neurocomputing, 2015, 149:160 -170 doi: 10.1016/j.neucom.2014.02.073 [22] Chang C C, Lin C J. LIBSVM: a library for support vector machines[Online], available: http://www.csie.ntu.edu.tw/~cjlin/libsvm/index.html. February 1, 2016 [23] 许美玲, 韩敏.多元混沌时间序列的因子回声状态网络预测模型.自动化学报, 2015, 41(5):1042-1046 http://www.aas.net.cn/CN/abstract/abstract18678.shtmlXu Mei-Ling, Han Min. Factor echo state network for multivariate chaotic time series prediction. Acta Automatica Sinica, 2015, 41(5):1042-1046 http://www.aas.net.cn/CN/abstract/abstract18678.shtml [24] 李军, 李大超.基于优化核极限学习机的风电功率时间序列预测.物理学报, 2016, 65(13):33-42 http://kns.cnki.net/KCMS/detail/detail.aspx?filename=wlxb201613005&dbname=CJFD&dbcode=CJFQLi Jun, Li Da-Chao. Wind power time series prediction using optimized kernel extreme learning machine method. Acta Physica Sinica, 2016, 65(13):33-42 http://kns.cnki.net/KCMS/detail/detail.aspx?filename=wlxb201613005&dbname=CJFD&dbcode=CJFQ [25] 马千里, 郑启伦, 彭宏, 覃姜维.基于模糊边界模块化神经网络的混沌时间序列预测.物理学报, 2009, 58(3):1410-1419 doi: 10.7498/aps.58.1410Ma Qian-Li, Zheng Qi-Lun, Peng Hong, Qin Jiang-Wei. Chaotic time series prediction based on fuzzy boundary modular neural networks. Acta Physica Sinica, 2009, 58(3):1410-1419 doi: 10.7498/aps.58.1410 [26] 侯公羽, 梁荣, 孙磊, 刘琳, 龚砚芬.基于多变量混沌时间序列的煤矿斜井TBM施工动态风险预测.物理学报, 2014, 63(9):90505 doi: 10.7498/aps.63.090505Hou Gong-Yu, Liang Rong, Sun Lei, Liu Lin, Gong Yan-Fen. Risk analysis on long inclined-shaft construction in coalmine by TBM techniques based on multiple variables chaotic time series. Acta Physica Sinica, 2014, 63(9):90505 doi: 10.7498/aps.63.090505 [27] Liu C H, Shang Y L, Duan L, Chen S P, Liu C C, Chen J. Optimizing workload category for adaptive workload prediction in service clouds. Service-Oriented Computing. Lecture Notes in Computer Science. Berlin, Heidelberg, Germany: Springer, 2015. 87-104 期刊类型引用(7)
1. 王凌，吴玉婷，陈靖方，潘子肖. Seru系统调度优化的知识引导协同进化算法. 控制理论与应用. 2024(06): 959-966 . 
百度学术2. 李斌，谢乃明. 考虑团队交互学习效应的单工作组可中断任务调度模型. 计算机集成制造系统. 2022(01): 161-174 . 百度学术3. 江煜舟，李冬妮，靳洪博，殷勇. 带有资源冲突的Seru在线并行调度算法. 自动化学报. 2022(02): 444-459 . 本站查看4. 湛荣鑫，李冬妮，马涛，李俊杰，吴延昭，殷勇. 面向快速响应的赛汝生产系统构建模型与方法. 自动化学报. 2022(12): 2922-2930 . 本站查看5. 于洋，李晓龙，崔思国. 赛汝生产系统构建与调度的研究进展. 系统工程理论与实践. 2021(02): 465-474 . 百度学术6. 白朝阳，王浩，和莉. 考虑批量分割的单元装配系统工作量平衡联合决策模型. 控制与决策. 2021(10): 2517-2527 . 百度学术7. 韩毅，沈杨科，张亮，林华珍，邓丽丽，朱晨波. 考虑E/T惩罚的产品SERU数量优化. 浙江工业大学学报. 2020(02): 188-194 . 百度学术其他类型引用(18)
-
下载:
计量
- 文章访问数: 3471
- HTML全文浏览量: 456
- PDF下载量: 980
- 被引次数: 25
