logo资料库

云制造环境下虚拟制造单元调度优化方法研究.pdf

发布时间：2022-05-29 发布人：admin 分类：说明书 资料大小：0.30M 资料格式：pdf 举报 版权申诉
第1页 / 共11页
第2页 / 共11页
第3页 / 共11页
第4页 / 共11页
第5页 / 共11页
第6页 / 共11页
第7页 / 共11页
第8页 / 共11页
资料共11页，剩余部分请下载后查看
    5 10 15 20 25 30 35 中国科技论文在线 http://www.paper.edu.cn 云制造环境下虚拟制造单元调度优化方法 研究 刘明周，彭金成，费凡，张楠* （合肥工业大学机械工程学院，合肥 230009） 摘要：将虚拟制造单元在云制造环境下的调度优化问题划分为单元构建和单元调度两个阶 段，建立了调度优化问题模型。针对虚拟制造单元的构建问题，从距离函数和有效性评价指 标两个方面对模糊 C 均值算法进行改进；针对构建完成的虚拟制造单元调度问题，采用改 进的粒子群算法进行求解。最后通过实例验证了上述所提算法的有效性。 关键词：云制造；虚拟制造单元；调度；模糊 C 均值；粒子群算法 中图分类号：TH186 Research on Optimization of Virtual Manufacturing Cell Scheduling in Cloud Manufacturing Environment LIU Mingzhou, PENG Jincheng, FEI Fan, ZHANG Nan (School of Mechanical Engineering, Hefei University of Technology, Hefei 230009) Abstract: The scheduling optimization problem of the virtual manufacturing cell in the cloud manufacturing environment is divided into two phases: cell construction and cell scheduling. The scheduling optimization problem model is established. For the problem of virtual manufacturing cell construction, the fuzzy C-means algorithm is improved from two aspects of distance function and effectiveness evaluation index. For the constructed virtual manufacturing cell scheduling problem, an improved particle swarm algorithm is used to solve. Finally, an example is given to verify the effectiveness of the proposed algorithm. Key words: Cloud Manufacturing; Virtual Manufacturing Cell; Scheduling; Fuzzy C-Means; Particle Swarm Optimization 0 引言 进入 21 世纪后，世界制造业正在孕育着新一轮的科技革命和产业革命，全球各个主要 国家都采取了积极的应对手段。云制造作为实现“中国制造 2025”战略计划的重要手段之 一，自提出以来就得到了我国相关学术界和产业界的认同与关注。虚拟制造单元是在传统制 造单元的基础上发展而来，它是根据生产制造任务从备选资源集中选出所需资源，组成逻辑 上的制造单元，即为虚拟制造单元。虚拟制造单元能够动态响应变化的市场需求，在一定程 度上实现柔性生产，同时可以提高资源利用率、有效降低生产制造成本。在云制造环境下引 入虚拟制造单元的概念，生成云制造环境下的虚拟制造单元，有利于降低云制造服务平台制 造任务调度问题的复杂性、充分利用平台内各种制造资源、充分发挥云制造这一生产模式的 优势。云制造环境下虚拟制造单元概念如图 1 所示，与传统的虚拟制造单元相比：资源内容 从设备转换为制造能力；各个资源提供者分布于异地，因此必须考虑其间的流转时间；云制 造资源是由资源提供者提供的空闲资源，云制造服务平台的运行不能妨碍其自身对资源的使 作者简介：刘明周（1968.03-），男，教授、博导，主要研究方向：制造过程检测、控制与管理，数字化管 理与管理可视化. E-mail: liumingzhou0551@163.com - 1 -
    中国科技论文在线 用，因此资源的占用是不得不考虑的问题。 http://www.paper.edu.cn VMC2 Service4 Service8 Service9 …… VMC1 Service5 Service7 … VMC4 Service1 Service6 Service9 VMC3 Service2 Service5 Service1 Service2 Service3 Service4 Service5 …… …… 企业C C2 C3 … C1 企业A A2 A1 企业B A3 B1 B2 虚拟制造单元 云制造服务平台 制造资源 40 45 50 Fig. 1 Virtual Manufacturing Cell Concept Diagram in Cloud Manufacturing Environment 图 1 云制造环境下虚拟制造单元概念图 在云制造相关研究方面，李伯虎院士[1]首先提出了云制造的概念，将云制造定义为“一 种利用网络和云制造服务平台，按用户需求组织网上制造资源（制造云），为用户提供各类 按需制造服务的一种网络化制造新模式”；刘万军等[2]设计了一种基于群体协作以及变异粒 子反向移动的改进粒子群优化算法，从而解决云制造资源调度和负载平衡的优化问题；Guo 等[3]研究了云制造环境下的资源服务组合的柔性度量方法，建立了基于云制造的柔性管理框 架。在虚拟制造单元相关研究方面，Mclean 等[4]首次提出虚拟制造单元的概念；Abdulkader[5] 设计了虚拟单元制造系统的整数规划模型，并选择成本为目标；Kesen 等[6]针对具有多种加 工工艺路线的虚拟制造单元调度问题，设计了一种基于遗传算法的虚拟制造单元调度的启发 式算法，完成对工件的机器分配和工件加工时间的排序；来庆蕾等[7]将学习曲线函数引入到 制造单元构建问题中，利用遗传算法处理虚拟单元构建过程中的人员派工问题。而关于虚拟 制造单元在云制造环境下的研究相当匮乏，因此本文针对虚拟制造单元在云制造环境下的调 度优化问题，从单元构建和单元调度两个方面进行研究。 55 1 问题描述 云制造服务平台中有 a 个制造任务需要完成，通过云制造资源的选择与匹配选出了 b 个 资源来完成制造任务，则每个任务至少选择一个资源完成，每个资源至少完成一个任务。为 了达到提高生产制造效率的目标，将 a 个任务拆分成 c 个任务族，同时也将 b 个资源分配到 c 个资源族，再将 c 个任务族和 c 个资源族关联起来，组成 c 个虚拟制造单元，即云制造环 - 2 -
    60 65 70 75 80 85 90 中国科技论文在线 http://www.paper.edu.cn 境下的虚拟制造单元。使不同虚拟制造单元之间跨单元行为最少，同时使单元内以及单元间 负载平衡。一个构建后的虚拟制造单元由包含 n 个任务的任务集{J1, J2, ···, Jn}和包含 m 个制 造资源的资源集{R1, R2, ···, Rm}组成。任务集中各个任务的制造需要至少一个到多个制造资 源的参与，各个任务在相应的制造资源下完成需要一定的时间，且在云制造环境下必须考虑 任务在制造资源间的流转所需的时间，可简化为运输时间，任务在各个制造资源上的制造顺 序是预先确定的，同时考虑资源占用。单元调度目标是在考虑资源间流转所需时间和资源占 用的情况下，确定每一个任务在相应制造资源上的开始制造时间和结束时间，使得调度优化 目标最优。本文选择最小化单元内的任务平均完工时间作为单元调度目标。 2 虚拟制造单元构建 模糊 C 均值（Fuzzy C-Means，FCM）算法是一种模糊划分方法，其基本原理是使得聚 类后形成的不同组之间的相似性最小，而同一组内的相似性要尽可能的大[8]。针对云制造环 境下虚拟制造单元的构建问题，本文设计了改进的模糊 C 均值算法进行求解：开发新的更 能 代表实 际问题 的距离 函数取 代了传 统的欧 式距离 、采用 单元构 建效 率 CCE（Cell Construction Efficiency）作为有效性评价指标。 1）距离函数 传统模糊 C 均值算法一般使用欧式距离。在制造单元构建过程中数值为 0 或 1（0 表示 不使用该资源，1 表示使用该资源），本文依据虚拟制造单元构建问题具体特征提出了一种 更加适用的距离函数公式如下： = d ki 5.0 + b  j 5.0 1 = + − 1(  j b x ij 1)( − v kj ) vx ij kj = 1 （1） 式中，分子表示任务 i 所需要的资源不是由聚类中心 k 分配的数量；分母表示任务 i 所 需要的资源由聚类中心 k 分配的数量。为了防止分母为“0”的极端情况出现，使用“0.5” 对公式进行修正。 2）有效性评价指标 对于不同的单元构建结果来说，应当使尽量减少单元外“1”元素（EE）个数和单元内 “0”元素（DE）个数，以减少跨单元任务出现，而且有利于平衡各单元负载。因此本文采 用单元构建效率 CCE 作为有效性评价指标，公式如下： CCE = 5.0 5.0 + + c  = 1 k EE 2 NM kk + DE （2） 式中 Mk 表示第 k 个虚拟制造单元中任务的数量，Nk 表示第 k 个虚拟制造单元中资源的 k 1 c kkNM 表示虚拟制造单元中所有元素的总数量；0.5 是公式的修正，防止分 数量，则 = 母为“0”的极端情况出现，此时为完全理想情况，即例外元素和相异元素的数量均为 0， 但一般情况下很少出现。 - 3 -
    中国科技论文在线 http://www.paper.edu.cn 总结改进模糊 C 均值算法用于云制造环境下虚拟制造单元构建问题步骤。步骤一：初 始化聚类参数，包括最大迭代次数、停止误差、平滑指数；步骤二：根据式（1）计算距离 矩阵；步骤三：重新计算隶属度矩阵；步骤四：判断是否满足停止条件，若不满足，则进入 步骤二；步骤五：比较各次结果的有效性评价指标 CCE，选取评价值最优的结果作为最终 的单元构建结果。 95 3 虚拟制造单元调度 3.1 调度数学模型 本文云制造环境下虚拟制造单元的调度优化模型可以表示为： min f = AFT = min( AFT ) i = C n i 1 n （3） （4） 100 105 110 115 120 约束条件为：  = m ( x MST ijk x k 1  n i = j 1 ijk ijk = + (,1 i = MT ) ijk  n h = j 1 x MST ( hjk hjk + ≤ ,2,1  ≤ ⋅⋅⋅ jn ;, = ⋅⋅⋅ ,2,1 n ), i （5） n h = j 1 x hjk MST hjk + Q 1( − y （6） ) ihk n i = j MSTx ijk ijk 1 + Qy ihk （7） ( − jji )1 （8） （9） )1 MT ijk （10） MT hjk  ijk TFT ) ≥ = ijk TST = = MST ( + jij + + ijk MST MFT MFT ijk ijh ijh ijh TT TFT TST （11） 在上述数学模型中，Q 表示无穷大的整数；Ci 表示任务 i 的制造完工时间；xijk 为决策 变量，取值 0 或 1，表示任务 i 的第 j 个工序是否在第 k 个制造资源处加工制造；MSTijk 和 MFTijk 分别表示任务 i 的第 j 个工序在第 k 个制造资源处的制造开始时间和制造结束时间； MTijk 表示任务 i 的第 j 个工序在第 k 个制造资源处的制造时间；TSTijh 和 TFTijh 分别表示任 务 i 的第 j 个工序到第 h 个工序的运输开始时间和运输结束时间；TTijh 任务 i 的第 j 个工序 到第 h 个工序运输总时间。式（5）表示工序资源唯一性约束；式（6）和式（7）表示同一 任务的工艺顺序约束；式（8）和式（9）表示任务到达才能开始加工制造以及加工制造完成 后立即运输至下一个制造资源处；式（10）和式（11）表示制造过程和运输过程不可中断。 3.2 改进粒子群调度算法设计 粒子群优化算法又称为微粒群优化算法，是一种全新的优化方法，它具有收敛速度快、 参数设置少、流程清晰的特点。在算法运算的循环迭代过程中，使用式（12）和式（13）对 粒子的速度和位置进行更新。 =+ ω t v id （12） ) t xrc idbest t xrc gdbest ( 22 t v id t x id t x id ( 11 + − + − ) 1 - 4 -
    125 130 135 140 145 中国科技论文在线 http://www.paper.edu.cn + t x id 1 = t x id + + t v id 1 （13） 式中，ω 表示惯性系数，c1 和 c2 分别表示个体学习因子和群体学习因子，r1 和 r2 均为区 间[0,1]内的随机数。将粒子群优化算法应用于云制造环境下的虚拟制造单元调度问题，需要 对其在多个方面进行改进。 1）惯性系数线性递减 惯性系数取值较小时算法收敛速度快，但容易陷入局部最优解，因此在算法前期取较大 的惯性系数有利于加快收敛速度，在算法后期取较小的惯性系数有利于防止算法陷入局部最 优解。本文采用惯性系数线性递减的方法[9]，如下： − ωωωω g （14） − × g max min = max max 式中，ωmax 和 ωmin 分别表示惯性系数的最大值和最小值，g 表示当前运算次数，gmax 表示允 许的最大运算次数。 2）离散化处理 粒子群优化算法一般用于连续函数或空间的数值求解问题，因此针对虚拟制造单元调度 这一典型的组合排序问题，需要对其进行离散化处理。离散化要求通过确定粒子的表示方式 以映射问题的解空间，即该问题的可行解域可以用粒子表示的同时，任一个粒子也处于可行 解域内。本文采用基于次序的粒子表示方法，该方法满足上述离散化要求，如图 2 所示。 任务 维度值 1 x1 ··· ··· 1 xN1 ··· ··· i ··· i ··· i ··· ··· ··· n ··· n ··· n xNn 图 2 基于次序的粒子表示方法 Fig. 2 Order-Based Particle Representation 3）编码与解码 本文采用基于操作的粒子编码方式。每个任务需要一个或多个制造资源，且在各个工序 之间存在前后顺序约束。在基于操作的粒子编码方式中，用自然数表示任务，相同任务的不 同操作用同一个任务号表示。粒子解码的过程是先由粒子获取一个具有先后顺序的操作表， 再根据工艺约束条件，确定各操作的最早允许加工时间，再进行加工制造。如图 3 和图 4 所示。 - 5 -
    中国科技论文在线 任务Ji 1 1 http://www.paper.edu.cn 2 2 3 3 3 维度值 0.143 0.871 0.640 0.538 0.424 0.962 0.163 升序 排序 任务Ji 1 3 3 2 2 1 3 维度值 0.143 0.163 0.424 0.538 0.640 0.871 0.962 图 3 粒子生成与编码示意图 Fig. 3 Particle Generation and Coding Diagram 粒子 1 3 3 2 2 1 3 调度排序 O112 O311 O323 O213 O222 O121 O332 任务 工序序号 制造资源 J1 J1 1 R2 J3 1 R1 J3 2 R3 J2 1 R3 J2 2 R2 J1 2 R1 J3 3 R2 150 155 160 Fig. 4 The Relationship between Task Processes and Manufacturing Resources in Particles 图 4 粒子中任务工序与制造资源对应关系 4）调度方案生成方法 在生成调度方案时需要考虑运输时间，本文假定在前一个制造任务工序后，若需要将任 务运输至下一资源节点，则立即进行运输。首先获取解码后的有序操作序列，并将全部任务 的首工序的开始加工时间置为零；再依照顺序，依次将有序操作表中的操作列入其所需制造 资源的加工队列中，在插入过程中需要满足制造和运输不可分割的原则，同时若插入操作可 以在前序操作的空闲时间完成，则可置于该操作之前；最后根据调度结果生成调度方案甘特 图，如图 5 所示，图中黑色表示资源占用、灰色表示任务运输、其余各颜色分别代表不同任 务。 - 6 -
    中国科技论文在线 http://www.paper.edu.cn 图 5 虚拟制造单元调度方案甘特图示意 Fig. 5 Gantt Diagram of Virtual Manufacturing Cell Scheduling Scheme 3.3 算法流程 165 如图 6 所示。步骤一：基本参数设定，包括粒子数量、最大和最小惯性系数、最大运算 次数、加速因子；步骤二：随机初始化粒子种群；步骤三：计算粒子群的适应度值，包括种 群历史最优适应度值和各个粒子的历史最优适应度值；步骤四：根据式（12）对惯性系数进 行递减操作；步骤五：更新粒子的位置和速度；步骤六：更新种群及各个粒子的历史最优适 应度值；步骤七：判断是否满足停止条件，否则转入步骤四；步骤八：根据最终的种群最优 适应度确定调度方案。 170 初始化粒子种群 参数设定 计算适应度值 更新惯性系数 更新粒子速度和 位置 重新计算粒子及 种群的适应度值 确定调度方案 Y 是否满足终止条件 N 图 6 改进粒子群算法流程图 Fig. 6 Improved Particle Swarm Algorithm Flow Chart 4 实验验证 本文以 10×15 的云制造环境下的虚拟制造单元调度优化问题为样本，使用 MATLAB8.3 编写仿真验证程序，硬件环境：CPU 为 Intel(R) Core(TM) i5-2400、主频为 3.1GHz、内存为 4.0GB，操作系统：Windows7(SP1)。 首先通过本文所提改进的模糊 C 均值算法完成虚拟制造单元的构建。样本数据如表 1 所 示。 - 7 - 175 180
    中国科技论文在线 http://www.paper.edu.cn 表 1 10×15 虚拟制造单元构建数据 Tab. 1 10×15 Virtual Manufacturing Cell Build Data T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 R1 0 0 0 0 0 1 0 0 1 0 R2 0 0 0 1 0 0 1 0 0 1 R3 0 0 1 0 0 1 0 0 1 0 R4 0 0 0 0 1 0 1 0 0 1 R5 1 1 0 0 0 0 0 0 0 1 R6 0 0 1 0 0 1 0 1 0 0 R7 0 1 0 0 0 0 1 0 0 1 R8 0 0 1 0 0 1 0 1 0 0 R9 1 1 0 0 1 0 0 0 0 0 R10 0 1 0 0 1 0 1 0 0 0 R11 1 0 0 1 0 0 0 0 0 1 R12 0 0 0 0 0 0 0 1 1 0 R13 1 0 0 1 1 0 0 0 0 0 R14 R15 1 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 1 0 0 0 在改进模糊 C 均值算法计算过程中，本文所提有效性评价指标 CCE 与聚类单元数的关 系如图 7 所示. 185 190 图 7 单元构建效率与聚类单元数关系图 Fig. 7 Cell Construction Efficiency and Number of Cells Relationship Diagram 在聚类单元数 c=3 时，有效性评价指标 CCE 取得最大值，其对应的单元聚类结果即为 最优单元聚类结果，结果如表 2 所示。 表 2 10×15 虚拟制造单元构建结果 Tab. 2 10×15 Virtual Manufacturing Cell Build Results 单元序号 1 2 3 任务 T T1、T4、T5 T2、T7、T10 资源 R R4、R9、R11、R13、R14 R2、R5、R7、R10 T3、T6、T8、T9 R1、R3、R6、R8、R12、R15 本文选择上述虚拟制造单元 3 作为调度算例，单元调度数据见表 3，制造顺序用数字序 号表示，制造时间的单位为 h。 - 8 -
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料