浙江大学学报(工学版), 2019, 53(5): 852-861 doi: 10.3785/j.issn.1008-973X.2019.05.005

计算机与控制工程

不确定环境下复杂产品维护、维修和大修服务资源调度优化

杨新宇,, 胡业发,

Maintenance, repair and overhaul/operations service resource scheduling optimization for complex products in uncertain environment

YANG Xin-yu,, HU Ye-fa,

通讯作者: 胡业发,男,教授,博导. orcid.org/0000-0003-0704-9934. E-mail: huyefa@whut.edu.cn

收稿日期: 2018-04-15  

Received: 2018-04-15  

作者简介 About authors

杨新宇(1971—),男,副教授,博士,从事制造服务、网络化协同制造等研究.orcid.org/0000-0003-0215-3791.E-mail:yangxy@zzuli.edu.cn , E-mail:yangxy@zzuli.edu.cn

摘要

基于对复杂产品维护、维修和大修(MRO)协同服务资源调度的需求分析,从现实角度出发,建立资源调度时间和服务执行时间参数不确定条件下的随机机会约束规划数学模型. 提出由随机模拟、神经网络和离散粒子群优化算法组合成的混合智能算法,求解所提出的优化问题. 随机模拟方法为所建立的神经网络模型提供训练样本集,得到的训练样本集被用于训练神经网络模型以逼近优化目标函数,训练后的神经网络模型被用于代替优化目标函数来执行粒子群算法优化迭代. 该混合算法能有效提升时间参数不确定条件下的复杂产品MRO协同服务资源调度双目标优化问题的求解速度. 案例分析表明,相比于确定性条件下的优化算法,所提出的随机机会约束规划模型和混合算法更适用于求解现实中不确定条件下的MRO服务资源调度问题,所求得的调度方案在实际执行中具有更好的鲁棒性.

关键词: 维护、维修和大修(MRO)服务 ; 参数不确定性 ; 随机模拟 ; 神经网络 ; 离散粒子群优化算法

Abstract

A stochastic chance-constrained programming mathematical model under uncertain resource scheduling time and uncertain service execution time was built from a realistic perspective, based on the requirement analysis of the collaborative maintenance, repair and overhaul/operations (MRO) service resource scheduling of complex products. A hybrid intelligent algorithm composed of the stochastic simulation, the neural network and the discrete particle swarm optimization algorithm was proposed to solve the proposed optimization problem. The training sample set produced by stochastic simulation was used to train the neural network for the approximation of the optimization objective function. The trained neural network model was used to replace the optimization objective function to perform the optimization iterations of particle swarm algorithm. This hybrid intelligent algorithm can effectively improve the solving rate of bi-objective problem of collaborative MRO service resource scheduling of complex products under uncertain time variables. The results of case study showed that the proposed stochastic chance-constrained programming model and the hybrid intelligent algorithm were more suitable for solving the MRO service resource scheduling problem under uncertainty in the reality, compared with the optimization algorithm under certainty. The proposed scheduling scheme was more robust in practical implementation.

Keywords: maintenance, repair and overhaul/operations (MRO) service ; parameter uncertainty ; stochastic simulation ; neural network ; discrete particle swarm optimization algorithm

PDF (1108KB) 元数据 多维度评价 相关文章 导出 EndNote| Ris| Bibtex  收藏本文

本文引用格式

杨新宇, 胡业发. 不确定环境下复杂产品维护、维修和大修服务资源调度优化. 浙江大学学报(工学版)[J], 2019, 53(5): 852-861 doi:10.3785/j.issn.1008-973X.2019.05.005

YANG Xin-yu, HU Ye-fa. Maintenance, repair and overhaul/operations service resource scheduling optimization for complex products in uncertain environment. Journal of Zhejiang University(Engineering Science)[J], 2019, 53(5): 852-861 doi:10.3785/j.issn.1008-973X.2019.05.005

维护、维修和大修(maintenance,repair and overhaul/operations,MRO)是产品在使用和维护阶段所进行的各种维护、修理、大修和操作等工业产品服务活动的总称. 随着行业竞争日益加剧、技术创新保值期缩短、客户需求个性化和制造销售链后端服务业务盈利比重提升等环境变化,复杂产品制造企业越来越重视提升自身产品的MRO服务品质,以吸引和保有客户,同时为企业创造经济效益[1]. 复杂产品技术含量高、结构复杂,运行集成多种技术且零部件多源化,因而客户自身难以高效率地判断和解决设备运行中出现的所有问题,须制造商及时的技术服务支持. 对于复杂产品,传统的制造商-用户单一对接的MRO服务模式所面临的问题如下:设备结构复杂和零部件多源化导致大量资源和库存占用;客户离散分布导致技术服务成本高、服务效率难以提升;要求制造商设备维修技术人员具备过高的技能水平和过宽泛的技能范围. 目前,物联网、云计算及大数据等新技术手段在制造行业的应用研究和实验在不断展开,为打破壁垒和实现制造业运作模式变革提供了可能[2-3]. 在复杂产品MRO多方协同模式下执行一项MRO服务任务必然会在协同执行网络的诸多环节产生众多不确定性,包括服务描述不确定性、服务执行时间不确定性、服务资源质量不确定性等,进而最终体现在服务完成时的服务时间、服务质量、服务成本的不确定性上. 对这些不确定性因素的忽略将严重影响产品协同MRO服务的调度执行效果,甚至抵消协同服务模式带来的优势.

一方面,MRO服务调度可以视作特殊的多资源约束作业车间生产调度问题,可以从现有生产调度研究中借鉴经验. 另一方面,复杂装备MRO服务资源调度问题又具有自身的特点:任务执行顺序的强逻辑约束性;资源调度和任务执行时间的高模糊性;资源调度执行时间和成本的不可忽略性;子任务对应需求资源组合方案的多选择性等. 当前,关于不确定性条件下生产调度问题的相关研究较多. Sakawa等[4]首次提出不确定因素为模糊处理时间的生产调度问题,并定义了2种用于模糊调度问题的模糊运算;Sahinidis[5]评述不确定条件下生产计划和调度优化问题的各种建模方法及适用领域;顾幸生等[6-7]分析实际生产调度中各种不确定性因素,并针对JobShop和FlowShop问题开展基于模糊规划理论和启发式算法的优化求解方法研究;张国军等[8]基于不确定规划理论建立生产调度问题的不确定性调度模型,并研究解决该类问题的混合智能算法;潘全科等[9]针对兼具模糊加工时间和模糊交货期的多工艺路线的作业车间调度问题提出基于遗传算法的全局优化调度算法;Adhitya等[10]首次采用启发式调度方法对不确定条件下原油调度问题进行优化. 关于复杂产品MRO服务资源调度优化的相关研究主要在确定性条件下展开. Jha等[11-13]从维修资源有效性的角度分析不同领域维修资源的优化配置问题;郑小强等[14]运用云遗传算法求解所建立的在一定维修成本下以最短时间实现维修任务为优化目标的数学模型;李旭[15]提出基于遗传算法和团队评价的MRO派工调度技术;密尚华[16]针对大型矿渣立磨类复杂产品MRO服务资源调度组合优化问题建立多目标优化模型并应用多目标算法进行求解. 现有针对复杂产品且考虑不确定条件下MRO服务资源调度的研究较少. 多方协同的复杂产品MRO服务新模式进一步加大了调度执行过程的不确定性,研究基于更贴合实际应用的不确定性条件下的复杂产品MRO协同服务资源调度优化方法具有重要意义.

为了进一步提升服务效率和质量,同时缓解复杂产品MRO协同服务过程中由协同性特征带来的不确定性因素影响加剧效应,针对不确定条件下的复杂产品MRO协同服务资源调度问题,开展能够产生具有一定鲁棒性的资源调度方案的优化方法.

1. 不确定条件下的复杂产品MRO服务资源调度建模

1.1. MRO服务资源调度问题分析

从企业的实施目标来分析,复杂产品MRO协同服务输出的服务一方面要最大化客户满意度(体现在客户对服务质量、服务响应效率、客户服务成本的评价上),从而增强企业产品竞争力以及吸引和保有客户的能力;同时还要维护企业自身利益,如控制资源占用比、控制服务成本、最大化利润等. 这些目标都须通过定制和控制服务执行过程,特别是服务资源调度过程来实现. 因此,复杂产品MRO协同服务资源调度优化问题是多目标优化问题,如图1所示. 依据不同服务任务的实际要求,所选择的调度方案应该向不同的目标倾斜.

图 1

图 1   多目标优化过程分析

Fig.1   Multi-objective optimization process analysis


复杂产品MRO协同服务过程的参与单元在企业级上包括服务主导单元(复杂产品制造企业)、服务协同单元(第三方组织)和客户单元3类. 这些单元个体在服务执行过程中执行各自负责的服务构件,最终向其服务执行逻辑上的下游单元输出资源. 资源就位后发挥功效,从而驱动协同服务执行过程,最终向客户单元输出完整的一次服务. 各单元输出资源分为物理资源和虚拟资源,物理资源包括相关设备、人员、零部件等. 本研究所涉及的复杂产品MRO协同服务资源指的是各类物理资源.

复杂产品MRO协同服务模式的优势是为服务调度提供更多更优的资源选择项,从而允许产生更加优化的资源调度方案. 提供资源的各协同服务单元地理位置、实时状态等属性不同,可提供的各类资源属性和实时状态也不同,依据服务需求可以从众多资源选项中组合出多种资源调度选择方案,如图2所示. 不同的方案具有不同的属性,可能产生的调度执行结果也不同. 因此复杂产品MRO协同服务资源调度优化问题,就是基于MRO服务资源调度的优化目标,实现对资源调度路径组合方案的优选. 基于对复杂产品MRO服务客户和企业双方实际需求的调研,本研究选择调度时间、性能成本比2个优化目标,开展在调度过程时间参数不确定条件下的针对复杂产品MRO服务资源调度问题的建模和优化方法研究.

图 2

图 2   服务资源调度方案提取组合

Fig.2   Extraction combination of service resource scheduling scheme


1.2. 不确定条件下的MRO协同服务资源调度优化数学模型

在实际调研中发现,复杂装备一般是客户企业生产链条中的关键节点,在其产生MRO服务需求后,若不能及时处理,将给客户生产带来极大的影响和损失. 例如,江苏常州某建材生产企业在用的一台大型立磨轴承发生故障后,企业该条产线处于停产状态,等待零部件、检测设备和吊装设备调度以及资源到达后的维修维护作业,期间每日损失达数十万元. 因此,第1个优化目标是在资源调度时间和任务执行时间不确定的条件下,最小化服务执行总时间.

一次完整的MRO服务任务可以划分为按逻辑顺序执行的多个服务子任务. 每个服务子任务由相关协同单元通过输出相应资源,完成各自责任服务构件的执行,相互配合完成. 每个子任务的执行驱动整体服务任务进入某个状态,为下一个子任务执行创造条件. 一次完整的MRO服务任务可以使用子任务集向量[t1t2,···,tn]表示. 各子任务间遵循并行、顺序等逻辑执行关系. 为了方便模型描述,认为每个子任务只有在其前序条件子任务集执行完毕,且每个子任务执行所需的3类资源集(设备工具集A、相关人员集B和零部件集C)全部就位后才能开始执行. 执行子任务ti所需的设备工具、相关人员、零部件3类资源集的调度就位时间分别取对应集合中资源的最晚就位时间,分别记为 $T_{A_i}$$T_{B_i}$$T_{C_i}$,子任务执行时间记为 $T_{{\rm{r}}_i} $,如图3所示. 可以看出,服务调度时间优化目标可以描述为通过保证子任务执行衔接性,减少资源等待时间和子任务执行等待时间,进而缩短完整服务任务执行总时间的优化目标. 须注意的是,在现实调度执行中,受协同单元内部和外部各类不确定性因素影响,各类资源调度就位时间不确定,各子任务对应的 $T_{A_i} $$T_{B_i}$$T_{C_i}$ 也是不确定的. 资源实时状态的不确定性使得子任务执行时间不确定. $T_{A_i}$$T_{B_i}$$T_{C_i}$$T_{{\rm{r}}_i}$ 均可近似视作临近某个已知预期固定值,且服从于一定已知概率分布函数[17]. 为了尽可能缩短服务任务执行时间,在选择资源调度方案时,须正确对待调度时间和执行成功概率. 承担适当的概率风险,有助于在保证一定可靠性的前提下,获得子任务实际执行衔接性更好,服务总时间更短的资源调度方案.

图 3

图 3   子任务划分及逻辑执行顺序

Fig.3   Subtask division and logic execution sequence


使用随机变量描述相关资源调度时间和各子任务执行时间变量,建立服务时间优化的随机机会约束规划模型[18]. 通过对随机机会约束取一定置信水平反映对调度方案所存在的适当风险的承担. 依据随机机会约束规划的标准形式,建立以服务总时间最小化为目标的数学模型:

$\left. \begin{aligned} & \min \; \overline {{T_{\rm{T}}}} {\text{或}}\max \;( - \overline {{T_{\rm{T}}}} ).\\ {\rm{s}}{\rm{.t}}.\quad & \Pr \left\{ {{T_{\rm{T}}} \leqslant \overline {{T_{\rm{T}}}} } \right\} \geqslant {\beta _1}; \\ & {T_{\rm{T}}} = T_{{\rm{E}}_n} - T_{{\rm{S}}_1}; \\ & T_{{\rm{E}}_i} = T_{{\rm{S}}_i} + T_{{\rm{r}}_i}; \\ & T_{S_i} = \max \;(T_{A_i},\, T_{B_i},\, T_{C_i},\, {M_i}); \\ & {M_i} = {\rm{max}}\;\left( {T_{{\rm{E}}_1}{Q_{1i}},\, T_{{\rm{E}}_2}{Q_{2i}},\, \cdot \cdot \cdot ,\, T_{{\rm{E}}_n}{Q_{ni}}} \right); \\ & {Q_{ij}} = \left\{ {\begin{aligned} & {1,\, {t_i}{\text{是}}{t_j}{\text{的前序条件子任务}};}\\ & {0,\, {t_i}{\text{不是}}{t_j}{\text{的前序条件子任务}}; } \end{aligned}} \right.\\ & \sum\limits_{i = 1,\;i \ne j}^n {{Q_{ij}}} \geqslant 1. \end{aligned} \right\}$

式中: $T_{{\rm{S}}_i}$$T_{{\rm{E}}_i}$分别为子任务ti的开始执行时间和执行完成时间;TT为完整服务执行总时间,等于子任务tn执行完成时间 $T_{{\rm{E}}_n}$和子任务t1开始执行完成时间 $T_{{\rm{S}}_1}$的差值;Tri为子任务ti执行时间,是服从某一概率分布的随机变量;子任务ti执行完成时间 $T_{{\rm{E}}_i}$等于开始执行时间 $T_{{\rm{S}}_i}$与任务执行时间Tri的和;Mi为子任务ti所有前序条件子任务完成时间中的最大值;子任务ti开始执行时间 $T_{{\rm{S}}_i}$等于该任务所需资源就位时间Ti(该子任务所需3种类型资源调度就位时间 $T_{A_i}$$T_{B_i}$$T_{C_i} $中的最大值)和Mi中的最大值;Qij为子任务titj间逻辑关系判断参数;Pr{·}表示{·}中事件成立的概率;β1为事先给定的约束函数的置信水平; $\overline {{T_{\rm{T}}}} $为目标函数的β1乐观值. 该模型表示在约束成立条件下,求使得服务完整执行时间的置信水平不小于β1的乐观值 $\overline {{T_{\rm{T}}}} $,该值既是判别值,也是优化目标.

提升资源调度方案的性能成本比为第2个优化目标. 对客户方来说,可以在同样的资金成本支出下获取较好的MRO服务质量和效果;对企业方来说,可以控制企业支出的MRO服务过程资金成本,提升利润率. 假设开展一次由子任务集[t1t2,···,tn]组成的MRO服务任务共需h种资源,集合向量为[re1,re2,···,reh]. 子任务和资源间是多对多的关系,同一个资源可以被不同子任务使用. 如图2所示,每一种资源分别有不同数量的可选供给路径,不同路径的资源其资源就位时间、资源性能、资源调度成本均不相同. 建立以资源性能成本比为目标的数学模型如下.

$\left. \begin{split} & \max \;\overline {{P_{\rm{T}}}}. \\ {\rm{s}}{\rm{.t}}.\quad & \Pr \left\{ {{P_{\rm{T}}} \geqslant \overline {{P_{\rm{T}}}} } \right\} \geqslant {\beta _2};\\ & {P_{\rm{T}}} = \sum\limits_{i = 1}^h {\left( {{w_i}{P_i}} \right)}; \\ & {P_i} = {{{H_i}} / {{C_i}}};\\ & {C_i} = {C_{i{\rm{g}}}} + {C_{i{\rm{h}}}}\left( {T_{{\rm{K}}_i} - T_{{\rm{D}}_i}} \right);\\ & T_{{\rm{K}}_i} = \max \;\left[ {T_{{\rm{E}}_1}{O_{1i}},T_{{\rm{E}}_2}{O_{2i}}, \cdot \cdot \cdot ,T_{{\rm{E}}_n}{O_{ni}}} \right];\\ & {O_{ij}} = \left\{ {\begin{aligned} & {1,{\text{子任务}}{t_i}{\text{需要资源}}{\rm{r}}{{\rm{e}}_j};}\\ & {0,{\text{子任务}}{t_i}{\text{不需要资源}}{\rm{r}}{{\rm{e}}_j}; } \end{aligned}} \right.\\ & \sum\limits_{i = 1}^n {{O_{ij}}} \geqslant 1,\;j = 1,2 ,\cdot \cdot \cdot , h;\\ & \sum\limits_{j = 1}^h {{O_{ij}}} \geqslant 0,\;i = 1,2 ,\cdot \cdot \cdot , n. \end{split} \right\}$

式中:PT为资源调度方案的总性能成本比;HiCiPi分别为资源rei的性能、成本和性能成本比;wi为资源重要度权值;CigCih分别为资源rei的固定调度成本和单位时间的消耗成本; $ T_{{\rm{K}}_i}$为需求资源rei的子任务集的最晚执行完成时间; $T_{{\rm{D}}_i}$为资源rei的就位时间,认为等于逻辑上最先使用该资源的某子任务j的开始执行时间 $T_{{\rm{S}}_j} $β2为事先给定的约束函数的置信水平; $\overline {{P_{\rm{T}}}} $为目标函数的β2乐观值.

2. 基于混合算法的MRO协同服务资源调度优化方法

2.1. 智能混合算法及应用

传统求解机会约束规划的方法是将其转化为确定等价形式求解,但只适合一些特殊形式[19-20]. 张国军等[8]对随机机会约束规划问题开展研究,并针对含有不确定变量的相关领域问题,建立了随机机会约束规划模型,应用随机模拟、神经网络、启发式算法等相结合的混合算法进行求解,取得了较好的应用效果. 本研究应用随机模拟、BP神经网络、离散多目标粒子群优化算法相结合求解所建立的资源调度时间和任务执行时间不确定条件下的复杂产品MRO协同服务资源调度优化问题的双目标随机机会约束规划数学模型. 混合算法流程框架如图4所示.

图 4

图 4   本研究所提出的混合算法流程图

Fig.4   Flow chart of proposed hybrid algorithm


2.2. 随机模拟

随机模拟主要是依据概率分布对随机变量进行抽样,从而为系统决策提供依据或对系统决策进行检验. 虽然它只给出统计估计而非精确结果,且应用其研究问题须花费大量的计算时间,但是它确实是处理无法应用解析方法的复杂问题的有效工具,已被应用到许多领域中[21-22]. 本研究使用随机模拟方法中的乐观值估计算法计算优化目标函数 $\overline {{P_{\rm{T}}}} $$ - \overline {{T_{\rm{T}}}} $.$\overline {{P_{\rm{T}}}} $计算为例,计算步骤如下:1)取 ${\overline {{P_{\rm{T}}}} _0} = - \infty $,依据随机变量参数( $T_{A_i}$$T_{B_i}$$T_{{\rm{C}}_i}$$T_{{\rm{r}}_i} $)的概率分布随机选取产生N组随机参数;2)计算 ${P_{\rm{T}}}$得到序列 $\left\{ {{P_{\rm{T}}}_1, {P_{\rm{T}}}_2, \cdots, {P_{\rm{T}}}_N} \right\}$,计算 $N' = \beta $N,取序列 $\left\{ {P_{\rm{T}}}_1, {P_{\rm{T}}}_2, \right.$ $\left. \cdots, {P_{\rm{T}}}_N \right\}$中第 $N'$个最大元素为 ${P_{\rm{T}}}_0$,若 ${P_{\rm{T}}}_0 > {\overline {{P_{\rm{T}}}} _0}$,则令 ${\overline {{P_{\rm{T}}}} _0} = {P_{\rm{T}}}_0$;3)重复步骤1)、2)K次后,可认为 $\overline {{P_{\rm{T}}}} = {\overline {{P_{\rm{T}}}} _0}$为优化目标函数值.

2.3. BP神经网络

误差反向传播(back propagation,BP)算法是人工神经网络中的监督式学习算法. BP神经网络算法在理论上可以逼近任意函数,基本结构由非线性变化单元组成,具有较强的非线性映射能力[23-24]. 使用随机模拟方法估计目标值,要使估计值尽量精确,仿真次数(NK)就必须加大,这使得求解过程十分费时,从而影响算法的效率. 本研究使用3层BP神经元网络来逼近不确定函数:

$U:x \to ({U_1}(x), {U_2}(x)).$

式中:

假设所建立数学模型中随机变量参数均服从正态分布Nμ,σ2[17],则所训练的3层BP网络包含5n个输入神经元(n为资源种类数,包含每种资源reii=1,···,n)的调度时间参数TμTσ;调度成本CgCh和性价比参数H);y个隐藏神经元(y依据输入输出神经元个数和训练效果调节选择);2个输出神经元( $ - \overline {{T_{\rm{T}}}} $$\overline {{P_{\rm{T}}}} $).

依据实际案例数据生成输入参数,通过随机模拟方法计算对应输出参数,为所建立的BP神经网络产生训练样本. 应用训练样本训练BP网络,在后续优化算法中使用训练好的BP网络计算适应度,以缩短算法运行时间.

2.4. 离散多目标优化粒子群算法

近年来,多目标进化算法(multiobjective evolutionary algoritnm,MOEA)中基于Pareto的方法在解决多目标优化问题上得到广泛应用和研究[25]. 国内外学者在这方面做了大量的研究,提出了许多基于Pareto最优解的优秀多目标进化算法,如NSGA-II、PESA等[26]. 粒子群优化算法(particle swarm optimization,PSO)是由Kennedy[27]提出的基于群智能的演化计算技术,是后启发式算法. PSO算法的优点在于收敛速度快、鲁棒性好、设置参数少、简单易实现[28]. 标准粒子群算法流程如图5所示.

图 5

图 5   标准粒子群优化算法流程图

Fig.5   Flow chart of standard PSO algorithm


在利用PSO算法求解离散多目标优化问题研究方面,Krause等[29]给出离散粒子群算法问题研究现状最新综述,Clerc[30]应用离散粒子群算法求解旅行商问题(traveling salesman problem,TSP). 本研究应用离散粒子群算法求解所提出的双目标优化问题,该过程与利用PSO算法求解连续单目标问题过程的不同之处有2点. 1)在多目标优化条件下,个体历史最优位置Pi和全局最优位置Pg选择方法不同. 在单目标优化条件下是通过比较适应度来更新位置. 在多目标情况下,Pi的更新是通过判别粒子当前位置和历史最优位置的适应度向量的支配关系;对于Pg(在多目标优化条件下,全局最优位置为非支配解集合)的更新,是先将当前粒子群中属于非支配解的适应度向量的粒子位置加入全局最优位置集合中,然后对该集合中的元素进行快速非支配排序,只留下非支配解,并应用网格法依据粒子位置密集度筛选控制全局最优位置集合中的元素数量. 2)离散整数变量和连续实数变量间的转换. 粒子位置编码串由离散整数型变量构成,每次迭代更新速度和位置后,粒子位置编码串中整数将会变为实数,为此,采用的粒子位置编码方法为整数值编码,例如,某任务需求5种资源,则粒子位置编码[2,3,1,4,3]代表资源组合方案中1到5号资源所选用的路径分别为2、3、1、4、3. 实数值编码转化为整数值编码的方法如图6所示.

图 6

图 6   粒子位置数值转化方法

Fig.6   Numerical conversion method of particle position


3. 算例及比较分析

3.1. 实际案例

为了验证提出的优化方法,给出实际的服务调度优化问题算例. 服务参数如下:服务包括5个子任务,需求2类设备工具、2类相关人员、3类相关零部件,各类资源均有3个可选来源,该服务资源调度问题相关基础参数如表1所示. 其中,T为资源-路径运抵时间参数矩阵,H为资源-路径性能参数矩阵,Cg为资源-路径固定成本参数矩阵,Ch为资源-路径单位时间消耗成本参数矩阵,均具有相同的行列数. 矩阵行号代表资源来源路径(资源供货方)代号,矩阵列号代表资源类别代号,其中第1、2列为设备工具类,第3、4、5列为相关零部件类,第6、7列为相关人员类. 矩阵T的第i行、第j列的参数为来源于第i路径、第j类资源的资源调运至现场的时间,服从对应的正态分布Nμσ2);矩阵H的第i行、第j列的参数为源于第i路径、第j类资源的资源性能状态评价值,取值为[0,1.0],1.0代表最优性能;矩阵Cg中第i行、第j列的参数为源于第i路径、第j类资源的固定调度成本;矩阵Ch中第i行、第j列的参数表示源于第i路径、第j类资源的在调度使用中的单位时间使用成本. Tr为子任务执行时间参数矩阵,列号代表子任务序号,数值代表该子任务的执行时间,取值服从对应的正分布Nμσ2);w为资源重要度权值矩阵;O为子任务-需求资源关联参数矩阵,表示子任务执行对资源的需求关系,矩阵行号代表子任务号,矩阵列号代表资源号,取值为0代表该子任务不需求该资源,取1代表需求;Q为子任务间逻辑关联参数矩阵,表示子任务间逻辑执行关系,矩阵行列号均代表子任务号,第i行、第j列参数取值为1表示第i号子任务是第j号子任务的直接前序关联任务,0表示无直接关联.

表 1   服务任务调度优化关键参数

Tab.1  Key parameters of service task scheduling optimization

参数 取值
T3×7/h $\left[ {\begin{array}{*{20}{c}} {N(45, 64)}&{N(20, 64)}&{N(30, 16)}&{N(50, 64)}&{N(12, 16)}&{N(10, 25)}&{N(24, 25)} \\ {N(30, 100)}&{N(10, 25)}&{N(12, 16)}&{N(25, 25)}&{N(24, 64)}&{N(15, 64)}&{N(40, 25)} \\ {N(25, 64)}&{N(40, 49)}&{N(20, 25)}&{N(30, 64)}&{N(40, 25)}&{N(30, 25)}&{N(25, 64)} \end{array}} \right]$
H3×7 $\left[ {\begin{array}{*{20}{c}} {0.8}&{0.8}&{0.7}&{0.7}&{0.6}&{0.6}&{0.8} \\ {0.7}&{0.6}&{0.5}&{0.8}&{0.9}&{0.8}&{0.8} \\ {0.6}&{0.8}&{0.6}&{0.8}&{0.8}&{0.8}&{0.7} \end{array}} \right]$
Cg3×7/元 $\left[ {\begin{array}{*{20}{c}} {425}&{385}&{645}&{880}&{1200}&{130}&{250} \\ {350}&{350}&{570}&{980}&{1600}&{220}&{150} \\ {250}&{410}&{780}&{870}&{1300}&{330}&{240} \end{array}} \right]$
Ch3×7/(元/h) $\left[ {\begin{array}{*{20}{c}} {30}&{20}&{55}&{60}&{60}&{15}&{10} \\ {25}&{25}&{60}&{55}&{50}&{10}&{15} \\ {20}&{35}&{50}&{50}&{55}&{10}&{15} \end{array}} \right]$
w1×7 $[ {\begin{array}{*{20}{c}} 4,&\!\!3,&\!\!5,&\!\!6,&\!\!8,&\!\!3,&\!\!4 \end{array}}]$
Tr1×5/h $[ {\begin{array}{*{20}{c}} {N(12, 16)},&{N(30, 64)},&{N(12, 25)},&{N(20, 64)},&{N(12, 64)} \end{array}}]$
O5×7 $\left[ {\begin{array}{*{20}{c}} 0&1&0&0&0&1&0 \\ 1&0&1&0&0&0&1 \\ 1&0&0&0&1&0&1 \\ 0&0&0&1&0&0&1 \\ 0&1&0&0&0&1&1 \end{array}} \right]$
Q5×5 $\left[ {\begin{array}{*{20}{c}} 0&1&1&0&0 \\ 0&0&0&0&1 \\ 0&0&0&1&0 \\ 0&0&0&0&1 \\ 0&0&0&0&0 \end{array}} \right]$


新窗口打开| 下载CSV


3.2. 案例仿真分析

应用Matlab工具实现对混合算法的编码实现和案例应用验证. 案例应用验证过程如下:1)随机选出1 000种无重复且可行的资源调度路径组合方案,并应用本研究所提出的随机模拟方法计算数学模型的目标值,产生1 000个训练样本;2)经多次运行调整后,3层BP网络参数选定为35个输入神经元、13个隐藏神经元、2个输出神经元结构. 使用Matlab神经网络工具箱进行训练,训练前对训练样本进行归一化操作. 如图7(a)(b)所示分别为工具箱运行结果和BP训练过程中误差变化. 图中,E为训练过程中的均方误差,T为训练次数. 当样本训练27次时,资源调度路径组合方案达到最优值,最佳验证性能为0.000 659 07. 3)应用离散粒子群多目标优化算法求解案例的资源调度路径组合方案优化问题,设置迭代次数为500次,初始种群规模为300,学习因子为1、2,惯性权重及其衰减率为0.5、0.99,取两优化目标中的置信水平β1=0.85、β2=0.80,在迭代过程中粒子位置的适应度使用训练好的BP网络进行计算. 优化所得Pareto最优解集结果如表2图8(b)所示,图中,F1F2分别为目标一、二的适应度.

图 7

图 7   MRO服务调度优化BP网络训练结果

Fig.7   BP network training result of MRO service scheduling optimization


图 8

图 8   不同条件下优化所得Pareto最优解集对比

Fig.8   Comparison of Pareto optimal solutions under different conditions


表 2   确定条件下优化所得资源组合方案及适应度

Tab.2  Optimized resource combination scheme and fitness value under certain conditions

序号 资源组合方案编码 确定条件下适应度 不确定条件下适应度
1 [1,1,1,3,2,2,3] [−17,44.238 6] [−26.299 7,22.476 3]
2 [1,1,1,3,2,2,1] [−16,41.161 1] [−24.081 6,31.819 9]
3 [1,1,1,3,2,3,1] [−12,35.159 9] [−19.129 4,29.524 7]

新窗口打开| 下载CSV


为了对比分析所建立的随机机会约束数学模型的有效性,将案例数据中随机变量变换为常数变量(即对于服从正态分布Nμσ2)的随机变量参数值取μ,数学模型的两优化目标变为max (−TT)和max PT,其余计算过程和参数关系不变),应用多目标粒子群算法进行优化,优化所得Pareto最优解集结果如图8(a)表2所示. 对比图8(a)8(b),发现图8(a)中在理想确定性条件下优化所得的Pareto最优解集相比图8(b)中两目标的适应度更优,但图8(a)同时给出了将在确定条件下优化得到的最优组合方案放在不确定条件下求解得出的两目标适应度(见表3),发现这些方案的目标适应度均被图8(b)中Pareto最优解方案集对应目标适应度所支配. 因此,针对不确定条件下MRO服务资源调度优化问题所建立的含有随机变量的随机机会约束数学模型和提出的混合算法更适用于求解现实中不确定条件下的调度需求问题.

表 3   不确定条件下优化所得资源组合方案及适应度(部分举例)

Tab.3  Optimized resource combination scheme and fitness value under uncertain conditions (partial examples)

序号 资源组合方案编码 不确定条件下适应度
1 [1,3,1,3,2,2,1] [−18.775 9,29.160 2]
2 [1,3,1,2,2,2,1] [−18.525 4,28.799 0]
3 [1,1,2,2,2,2,1] [−23.778 4,30.360 0]
4 [1,3,2,2,2,2,1] [−18.497 5,27.935 0]
5 [1,1,1,3,2,2,1] [−24.081 6,31.819 9]
6 [1,3,1,2,2,3,1] [−18.202 6,27.3827 0]

新窗口打开| 下载CSV


在实际应用中,首先使用提出的模型和算法计算得到如图8(b)所示的两优化目标的Pareto最优解方案适应度分布状况,然后依据实际情况对两目标的不同侧重需求在Pareto最优解方案集中选取适合的资源调度组合方案,在承担一定风险的情况下,获得更好的资源调度效果.

4. 结 语

针对复杂产品MRO协同服务开展更贴近实际情况的多参数不确定条件下资源调度优化方法研究具有重要应用价值. 分析复杂产品MRO协同服务资源调度的资源要素、过程以及优化目标;建立资源调度时间和任务执行时间参数不确定条件下的复杂产品MRO协同服务资源调度优化问题数学模型;针对优化问题的求解,提出包含随机模拟、BP神经网络和离散多目标粒子群算法的智能混合算法,并应用案例验证分析算法的有效性. 所提出的模型和算法能够有效求解执行过程时间参数不确定条件下复杂产品MRO服务资源调度优化策略,使得优化得到的调度方案在实际执行过程中表现出更强的鲁棒性. 基于本研究的内容和思路,后续的研究工作将在算法过程、效率优化以及算法评价层面展开.

参考文献

李浩, 纪杨建, 祁国宁, 等

面向全生命周期的复杂装备MRO集成模型研究

[J]. 计算机集成制造系统, 2010, 16 (10): 2064- 2072

[本文引用: 1]

LI Hao, JI Yang-jian, QI Guo-ning, et al

Integration model of complex equipment MRO based on lifecycle management

[J]. Computer Integrated Manufacturing Systems, 2010, 16 (10): 2064- 2072

[本文引用: 1]

LI H, MI S H, LI Q F, et al. A scheduling optimization method for MRO service resources for complex products [J/OL]. Journal of Intelligent Manufacturing [2018-06-10]. https://doi.org/10.1007/s10845-018-1400-4.

[本文引用: 1]

LI H, JI Y J, GU X J, et al

A universal enterprise manufacturing services maturity model: a case study in a Chinese company

[J]. International Journal of Computer Integrated Manufacturing, 2014, 27 (5): 434- 449

DOI:10.1080/0951192X.2013.814164      [本文引用: 1]

SAKAWA M, MORI T

An efficient genetic algorithm for job-shop scheduling problems with fuzzy processing time and fuzzy duedate

[J]. Computers and Industrial Engineering, 1999, 36 (2): 325- 341

DOI:10.1016/S0360-8352(99)00135-7      [本文引用: 1]

SAHINIDIS N V

Optimization under uncertainty: state-of-the-art and opportunities

[J]. Computers and Chemical Engineering, 2004, 28 (6): 971- 983

[本文引用: 1]

顾幸生

不确定性条件下的生产调度

[J]. 华东理工大学学报, 2000, 26 (5): 441- 446

DOI:10.3969/j.issn.1006-3080.2000.05.001      [本文引用: 1]

GU Xing-sheng

A survey of production scheduling under uncertainty

[J]. Journal of East China University of Science and Technology, 2000, 26 (5): 441- 446

DOI:10.3969/j.issn.1006-3080.2000.05.001      [本文引用: 1]

徐震浩, 顾幸生

不确定条件下的flow shop问题的免疫调度算法

[J]. 系统工程学报, 2005, 20 (4): 374- 380

DOI:10.3969/j.issn.1000-5781.2005.04.006      [本文引用: 1]

XU Zhen-hao, GU Xing-sheng

Immune scheduling algorithm for flow shop problems under uncertainty

[J]. Journal of Systems Engineering, 2005, 20 (4): 374- 380

DOI:10.3969/j.issn.1000-5781.2005.04.006      [本文引用: 1]

张国军, 李婵娟, 朱海平, 等

不确定信息条件下Job-shop调度的混合智能算法

[J]. 中国机械工程, 2007, 18 (16): 1939- 1942

DOI:10.3321/j.issn:1004-132x.2007.16.012      [本文引用: 2]

ZHANG Guo-jun, LI Chan-juan, ZHU Hai-ping, et al

A hybrid intelligent algorithm for Job-shop scheduling under uncertain information environment

[J]. China Mechanical Engineering, 2007, 18 (16): 1939- 1942

DOI:10.3321/j.issn:1004-132x.2007.16.012      [本文引用: 2]

潘全科, 朱剑英

多工艺路线的作业车间模糊调度优化

[J]. 中国机械工程, 2004, 15 (24): 2199- 2202

DOI:10.3321/j.issn:1004-132X.2004.24.010      [本文引用: 1]

PAN Quan-ke, ZHU Jian-ying

An efficient algorithm for job shop scheduling problems with fuzzy processing time, fuzzy duedate and alternative machines

[J]. China Mechanical Engineering, 2004, 15 (24): 2199- 2202

DOI:10.3321/j.issn:1004-132X.2004.24.010      [本文引用: 1]

ADHITYA A, SRINIVASAN R, KARIMI I A

Heuristic rescheduling of crude oil operations to manage abnormal supply chain events

[J]. AICHE Journal, 2007, 53 (2): 397- 422

DOI:10.1002/(ISSN)1547-5905      [本文引用: 1]

JHA M K, SHARIAT S, ABDULLAH J, et al

Maximizing resource effectiveness of highway infrastructure maintenance inspection and scheduling for efficient city logistics operations

[J]. Procedia-Social and Behavioral Sciences, 2012, 39: 831- 844

DOI:10.1016/j.sbspro.2012.03.151      [本文引用: 1]

MARTORELL S, VILLAMIZAR M, CARLOS S, et al

Maintenance modeling and optimization integrating human and material resources

[J]. Reliability Engineering and System Safety, 2010, 95 (12): 1293- 1299

DOI:10.1016/j.ress.2010.06.006     

DE CASTRO F, CAVALCA K L

Maintenance resources optimization applied to a manufacturing system

[J]. Reliability Engineering and System Safety, 2006, 91 (4): 413- 420

DOI:10.1016/j.ress.2005.02.004      [本文引用: 1]

郑小强, 刘敏, 孔繁荣, 等

基于云遗传算法的MRO服务调度

[J]. 计算机集成制造系统, 2013, 19 (9): 2348- 2354

[本文引用: 1]

ZHENG Xiao-qiang, LIU Min, KONG Fan-rong, et al

Cloud genetic algorithm based MRO services scheduling model

[J]. Computer Integrated Manufacturing Systems, 2013, 19 (9): 2348- 2354

[本文引用: 1]

李旭. 复杂装备MRO服务的若干关键技术研究[D]. 杭州: 浙江大学, 2012.

[本文引用: 1]

LI Xu. Research on some key technologies of MRO service for complex equipment [D]. Hangzhou: Zhejiang University, 2012.

[本文引用: 1]

密尚华. 复杂产品服务业务建模与资源调度优化方法研究[D]. 郑州: 郑州轻工业学院, 2016.

[本文引用: 1]

MI Shang-hua. Modeling and resources scheduling optimization method for the service business process of complex product [D]. Zhengzhou: Zhengzhou University of Light Industry, 2016.

[本文引用: 1]

李培根. 制造系统性能分析建模:理论与方法[M]. 武汉:华中理工大学出版社, 1998: 25-30.

[本文引用: 2]

刘宝碇, 赵瑞清, 王纲. 不确定规划及应用[M]. 北京:清华大学出版社, 2003: 24-29.

[本文引用: 1]

方述成, 汪定伟. 模糊数学与模糊优化[M]. 北京: 科学出版社, 1997: 60-63.

[本文引用: 1]

KALL P, STEIN W W, PETER K. Stochastic programming [M]. Chichester: Wiley, 1994: 46-49.

[本文引用: 1]

肖宁

求解随机机会约束规划的混合智能算法

[J]. 计算机工程与应用, 2010, 46 (22): 43- 46

DOI:10.3778/j.issn.1002-8331.2010.22.015      [本文引用: 1]

XIAO Ning

Solving stochastic chance-constrained programming problems with hybrid intelligent algorithm

[J]. Computer Engineering and Applications, 2010, 46 (22): 43- 46

DOI:10.3778/j.issn.1002-8331.2010.22.015      [本文引用: 1]

丁晓东, 吴让泉

含有模糊和随机参数的混合机会约束规划模型

[J]. 控制与决策, 2002, 17 (5): 587- 590

DOI:10.3321/j.issn:1001-0920.2002.05.018      [本文引用: 1]

DING Xiao-dong, WU Rang-quan

Hybrid programming model with fuzzy and stochastic parameters

[J]. Control and Decision, 2002, 17 (5): 587- 590

DOI:10.3321/j.issn:1001-0920.2002.05.018      [本文引用: 1]

焦李成. 神经网络系统理论[M]. 西安:西安电子科技大学出版社, 1992: 55-59.

[本文引用: 1]

周志华. 机器学习[M]. 北京: 清华大学出版社, 2016: 70-78.

[本文引用: 1]

郑金华. 多目标进化算法及其应用[M]. 北京: 科学出版社, 2007: 62-68.

[本文引用: 1]

DEB K, PRATAP A, AGARWAL S, et al

A fast and elitist multiobjective genetic algorithm: NSGA-II

[J]. IEEE Transactions on Evolutionary Computation, 2002, 6 (2): 182- 197

DOI:10.1109/4235.996017      [本文引用: 1]

KENNEDY J. Particle swarm optimization [M]// Encyclopedia of machine learning. New York: Springer, 2011: 760-766.

[本文引用: 1]

曾建潮, 介婧, 崔志华. 微粒群算法[M]. 北京: 科学出版社, 2004: 56-59.

[本文引用: 1]

KRAUSE J, CORDEIRO J, PARPINELLI R S, et al. A survey of swarm algorithms applied to discrete optimization problems [M]// Swarm intelligence and bio-inspired computation: theory and applications. London: Elsevier, 2013: 169-191.

[本文引用: 1]

CLERC M. Discrete particle swarm optimization, illustrated by the traveling salesman problem [M]// New optimization techniques in engineering. New York: Springer, 2004: 67-72.

[本文引用: 1]

/