基于SA-QPSO算法的多层制造单元内部布局方法.pdf

中国新技术新产品2024 NO.3（上）-5-高 新 技 术设施布局（Facility Layout Problem，FLP）是智能工厂建设的重要环节，科学合理的设备布局有重要的意义1。随着使用智能化物流的智能工厂兴起，多层制造单元的布局方式越来越多，许多学者对制造单元布局问题进行深入研究，例如王沙沙等2针对双向环形过道布置问题建模并使用混合鲸鱼算法有效求解。丁祥海等3以“U”形生产单元为研究对象，建立了单元生产可重构设施布局决策集成模型，并设计了决策问题的遗传算法。目前国内外主要研究单层制造单元，多层制造单元相关研究较少，其中，单目标优化模型或双目标优化模型的搬运成本最低、单元利用率最高。基于此，本文考虑了众多制造车间的实际需求，构建多目标优化数学模型，研究多层制造单元内部设备布局方法。1 多层制造单元车间内部布局问题描述以及数学模型构建1.1 问题描述及假设多层制造单元内部设备形状以矩形为主，常见分类有直线形制造单元、“U”形制造单元和环形制造单元。通过构建X、Y、Z 坐标系，可立体表述制造单元，如图 1 所示。其中，Z1为 XOY 平面，Z2为与 XOY 平面平行的平面，Z3为 YOZ 平面，Z4为与 YOZ 平面平行的平面，Z1、Z2、Z3和 Z4均穿过设备中心，同层设备中心在同一条水平线上。将单元布局平面抽象化。如图 2 所示。其中，直线形制造单元内设备布局仅在平面 Z1和 Z2内；“U”形制造单元内设备布局仅在平面 Z1、Z2和 Z3内；环形制造单元内设备布置在所有平面内。通过构建相同的目标函数，采用约束条件选择不同的布局形式，求解不同的设备排列组合中最优的顺序布置，获得最佳布局。1.2 目标函数本文以单元体积最小、物流搬运强度最低、制造损失时间最短和单元稳定性最高为目标构建多目标数学模型。1.2.1 单元体积目标多层制造单元占用空间为单元体积，主要受长、宽和高 3 个要素影响，当 3 个要素最小时，单元体积就最小，目标函数如公式（1）所示。minV=LWH（1）式中：V 为单元体积；L 为单元长度，在单元内设备的中心坐标的 x 值与设备投影到 X 轴上的一半之和或之差组合的集合中，最大值和最小值之差即单元长度目标；W 为单元宽度，在单元内设备的中心坐标的z值与设施投影到Z轴上的一半之和或之差组合的集合中，最大值和最小值之差即单元宽度；H 为单元高度目标，可将单元内每个设备的中心在 Y 轴上的坐标值y 与该设备投影到 Y 轴上尺寸的一半相加，求得的结果组成的基于SA-QPSO算法的多层制造单元内部布局方法郭轶男姜雪松张宇晨刘森王婧（东北林业大学，黑龙江 哈尔滨 150040）摘 要：针对多层制造单元内部的设备布局优化问题，本文建立考虑单元尺寸、物料搬运量、损失时间以及单元稳定性的多目标优化数学模型。为更快速、高效地求解该问题，使用模拟退火算法（Simulated Annealing，SA）确定单元内设备所在平面以及层面，使用量子粒子群算法（Quantum Particle Swarm Optimization，QPSO）确定设备具体坐标值和所在高度。以某汽车零件加工车间为实例，运用 SA-QPSO 算法生成直线形、“U”形和环形3种最优空间布局方案，验证了 SA-QPSO 算法在多层制造单元内部布局方法设计方面的可行性。关键词：多层制造单元；布局优化；模拟退火算法；量子粒子群算法中图分类号：TU318 文献标志码：A基金项目：黑龙江省自然科学基金资助项目“基于调制电子增强的高功率脉冲磁控溅射新技术及其应用研究”（项目编号：LH2019E001）。图 1 多层制造单元布局立体图ZZ1Z4Z2Z3r=2Y注：L为单元长度；W为单元宽度；G1、G2为给定常数值。图 2 制造单元平面抽象图LZ134781112151613141056129G2G1Z3Z2Z4LYXOZWW中国新技术新产品2024 NO.3（上）-6-高 新 技 术集合为单元高度集，集合中最大值就是制造单元所需的最低高度，即单元高度目标。1.2.2 物料搬运目标本文搬运距离采用与物流搬运实际距离更接近的曼哈顿距离，如公式（2）所示。dij=|xi-xj|+|yi-yj|+|zi-zj|（2）式中：dij为设备 i 到设备 j 的曼哈顿距离，设备 i 中心坐标为（xi，yi，zi），设备 j 中心坐标为（xj，yj，zj）。第 p 号产品从设备 i 到设备 j 的物料搬运批量为 ceilVpBp，搬运目标如公式（3）所示。min DceilVBdpppPjMiMji?111 （3）式中：D 为物料搬运强度；M 为设备总数量；P 为产品总数量；i、j 为设备编号；p 为加工产品种类编号；ceil 为取整；Vp为第 p 号产品待加工总数量；Bp为第 p 号产品一次搬运数量。1.2.3 损失时间目标在生产线平衡问题中，损失时间为衡量制造单元平衡的重要指标之一，因此设损失时间目标，如公式（4）所示。minmaxTnqqceilVBpiiinPppp?1（4）式中：T 为损失时间目标；np为设备总数；qi为第 i 个设备加工以及运输到第 i+1 个设备的时间。1.2.4 稳定性目标在多层制造单元设备布局中，需要考虑设备的稳定性，稳定性目标 B 越小就越稳定，目标函数如公式（5）所示。min By wiii?（5）式中：yi为设备 i 的中心高度；wi为设备 i 的质量。1.3 约束条件在设定具体约束前，须设定的基本约束如下。设备 i 的中心坐标（xi，yi，zi）为优化问题的决策变量；（li，wi，hi）为设备对应的长、宽、高；设备单元集均在 X、Y、Z 轴正方向上，不考虑 X、Y、Z 轴负方向，任意设备不能超过单元的边界。1.3.1 边界约束边界约束为设备对应长度 li的一半与中心点 xi坐标之和单元 Z 轴方向的长度边界约束 Lg，设备所对应宽度 wi的一半与中心点 yi坐标之和单元 X 轴方向的宽度边界约束 Wg，设备对应高度 hi与中心点 zi坐标之和单元 Y 轴方向的高度约束 Hg。1.3.2 设备位置约束设备中心必须位于平面 Z1、Z2、Z3和 Z4上，zi为非负区域。假设 PSi I 为设备中心 Zi面的归属，当 PSi=1 时，zi=0；当 PSi=2时，zi=Z2_value；当 PSi=3 时，xi=0；当 PSi=4 时，xi=Z4_value。其中，Z2_value 为 Z2面的 z 坐标，Z4_value 为 Z4面的 x 坐标。1.3.3 单元集形状约束假设 Type_choose 1，2，3 为单元集形状，当 Type_choose=1 时，直线形仅选择平面 Z1、Z3；当 Type_choose=2 时，“U”形仅选择平面 Z1、Z2以及 Z3；当 Type_choose=3 时，环形选择平面 Z1、Z2、Z3以及 Z4。1.3.4 高度层级约束假设 Yk为第 k 个高度层级，Yi=0 只能从 Yk（k=1，2，r）中取值，即 yi Yk：k=1，2，r。2 基于 SA-QPSO 算法的目标函数求解2.1 设备布局方案的编码与生成在优化问题中，粒子群优化算法（Particle Swarm Optimization，PSO）和模拟退火算法（Simulated Annealing，SA）都是常见且有效的算法，量子粒子群算法（Quantum Particle Swarm Optimization，QPSO）是基于PSO算法提出的一种改进算法4。本文采用了一种改进的混合算法，称为量子粒子群优化算法（SA-QPSO），并将其应用于求解单元内部设备布局最优化问题。流程如图 3 所示。2.1.1 初步布局方案设备 j 随机生成数 i 和数 k，i 1，2，3，4，k 1，2，r，表示将设备 j 分配至 Zi面的第 k 层中，由此可得Aik，即 Zi面第 k 层高度的设备编号升序向量。设 Aik共有 mik个元素，如果 mik 0，则生成一个 mik维的各分量取值为（0，1）的随机向量 Vik，根据 Vik各分量的大小关系对 Aik进行排序，结合 Aik和 Vik可得设备在 zi面第 k 层上沿 x 正向或 z 正向的有序排布，得到初步布局方案。2.1.2 Z4的 x 值生成仅考虑 x 方向的干涉，从平面 Z1、Z2找出 x 坐标最大的设备，使其不与 Z4内最长的设备发生干涉，又因为换行约束，所以 Z4Lz，Z4的下界 lb4和上界 ub4如公式（6）、公式（7）所示。lbLZlGlzi jkikjjk41422?max,maxmax,end?（6）注：ratio为分配比例；Z4_ratio为设定的Z4平面X轴方向的分配比例；Z2_ratio为设定的Z2平面Z轴方向的分配比例。图 3 SA-QPSO 算法流程图生成随机设备布局方案，包括各设备的高度层级以及平面Zi从属信息生成最优设备布局方案QPSO计算出各设备坐标，求出各分目标值并转化为单目标将OPSO的最优解对应的目标函数作为SA的目标函数，以评价SA中的随机设备布局方案生成（0，1）均匀分布的随机数并赋值ratio、Z4_ratio，Z2_ratio、ra和yratio中国新技术新产品2024 NO.3（上）-7-高 新 技 术式中：Lz为换行约束；Zik，j为 Zi的第 k 层中的第 j 个设备的前向中心间隔；lik，end为平面 Zi第 k 层高度最后 1 个设备的长度；l4k，j为平面 Z4第 k 层高度设备 j 的长度；G1为给定常数值。ubLljk442?gmax,（7）式中：Lg为单元 Z 轴方向的长度边界约束。由于此时最大余量为正，因此 ub4lb4，如公式（8）所示。Z4=lb4+(ub4-lb4)Z4_ratio （8）式中：Z4_value为随机数且 Z4_ratio（0，1）。2.1.3 Z2的 Z 值生成Z2的下界 lb2和上界 ub2如公式（9）、公式（10）所示。lbWZwGwzi jkikjjk23222?max,maxmax,end?（9）式中：Wz为换行约束；zik，j为 Zi的第 k 层中的第 j 个设备的前向中心间隔；wik，end为平面 Zi第 k 层高度最后 1 个设备的宽度；w2k，j为平面 Z2第 k 层高度设备 j 的宽度；G3为给定常数值。ubWwgjk222?max,（10）式中：Wg为单元 X 轴方向的宽度边界约束。设随机数 Z2-ratio（0，1），如公式（11）所示。Z2=lb2+（ub2-lb2）Z2-ratio （11）至此，分配至 Z1、Z2、Z3和 Z4的设备都已定 x 坐标和 z坐标：平面 Z1的 z=0；平面 Z2的 z 值已生成；平面 Z3的 x=0；平面 Z4的 x 值已生成。2.1.4 高度层级 Yk的生成假设 k为第 k 层设备的最大高度，那么以层级 r=3 为例进行分析，如图 4 所示。对各层的最高设备按层级顺序编号，计算步骤如下。步骤一：计算设备最大余量，如公式（12）所示。MarginHrGygkkrmax?12121 （12）式中：Marginymax为设备上侧 Y 轴坐标的最大边缘值即最大余量；k为第 k 层高度设备的最大高度；r 为高度层；Hg为设备对应高度 hi与中心点 zi坐标之和单元 Y 轴方向的高度约束；G2为给定常数值。如果最大余量 0，则判定无解 Marginymax为最大余量。步骤二：生成 r-1 维（0，1）随机向量，如公式（13）、公式（14）所示。ra=ra1，ra2，rar-1 （13）?kkkyykGyMargin?1212ratiomax （14）式中：k为第 k 个最高设备的前向中心间隔，1取 0，k2；y为占比向量；yratio为生成随机数且 yratio（0，1）。步骤三：生成高度层级，如公式（15）所示。Ykkjk?1 （15）至此，生成布局方案且各约束均得到了满足，可得到可行布局方案或判定无解。该问题外层为带有简单约束的组合优化问题，使用带有罚函数的 SA 算法进行优化，使各高度层级均有设备；内层为无约束优化问题，使用 QPSO 算法进行求解。2.2 SA 算法2.2.1 解的编码与初始化假设共有 n 个设备，以 2n 的整数矩阵来表示设备组的 Zi面属性和高度层级属性，每列对应 1 个设备，第一行为 Zi面属性，第二行为高度层级属性。根据矩阵进行。编码下界矩阵如公式（16）所示。lb?1 111 112n（16）直线形上界矩阵如公式（17）所示。ub?2222rrrn （17）“U”形上界矩阵如公式（18）所示。ub?3332rrrn （18）环形上界矩阵如公式（19）所示。ub?4442rrrn （19）2.2.2 适应度函数对该嵌套形式的优化问题来说，SA 算法的适应度为内层 QPSO 算法的最优适应度值。在最大化目标中，令适应度为-M；在最小化目标中，令适应度为 M。其中，M 为充分大的正数。2.3 QPSO 算法在 QPSO 算法中，通过粒子可以搜索整个可行解空间，并将粒子群算法中的速度和位置更新公式进行了替换5。同时该算法以概率分布机制替代原有机制，提高了全局搜索的能力，也提高了算法收敛的精度和速度6。QPSO 算法的具体步骤如下。步骤一：初始化粒子位置，并设置初始个体最优值。步骤二：计算各粒子的适应度值。步骤三：比较粒子适应度值的大小，更新个体最优和全局最优。步骤四：更新粒子位置，如公式（20）所示。注：y1、y2和y3为设备一的高度，y=Y1=0为第k层设备的中心在Y轴上的坐标值与第k层的高度相等；Hg为单元高度目标，即制造单元所需的最低高度；y=Hg为制造单元上界的Y轴坐标值等于单元高度目标值；1=0，2、3为设备二的前向中心间隔。图 4 第 k 层设备最大高度示意图设备三最大余量设备二设备一y=Hgy=Y3y=Y22G2G23y3y2y1y=Y1=0中国新技术新产品2024 NO.3（上）-8-高 新 技 术xpxCui jti jti jtjt,ln?11?（20）式中：xt+1i，j为最新粒子位置信息；pit，j为局部吸引子；Cjt为粒子当前个体最优的均值；为控制参数；u 为随机变量，由此得到新位置。步骤五：按照一定的变异概率对个体最优进行高斯扰动，即加入服从高斯分布的随机数来提升算法多样性。步骤六：重复步骤二 步骤四直到满足停止条件。3 应用实例3.1 实例描述采用上述算法对某汽车零件单元生产车间进行布局优化，本文选择该车间的 15 台设备为研究对象，共生产 12 种产品，设备信息包括设备编号、设备尺寸（长、宽和高）、设备质量以及每台设备加工 1 次的加工时间，具体信息见表 1。表 1 设备信息表设备长宽高/m质量/kg加工时间/s10.91.11.42002521.61.41.24502931.61.41.45003041.31.61.44503450.91.01.32003061.21.41.23003070.61.21.42002780.91.01.4902490.80.91.29016100.70.90.55030110.90.60.46020120.71.00.810025131.20.51.115017140.71.20.88024150.71.21.410019根据产品的工艺性对产品进行编号，该车间的加工产品信息包括加工批量、搬运批量以及加工产品所经过设备的工艺路径，具体信息见表 2。表 2 产品信息表产品加工批量/件搬运批量/件工艺路径13 750304-3-7-6-5-2-122 500304-2-3-6-8-4-931 800804-3-1-2-541 900806-4-3-5-252 500301-3-6-11-761 800552-12-4-1-671 800803-6-8-9-13-2-4-182 500808-11-14-7-6-4-5-1093 100302-13-11-4-5102 5008015-11-6-7-2-1113 200801-3-15-6-11-8121 9005512-5-6-4-10-33.2 结果比较和分析通过实例求解得到 3 种布局形式的最优布局方案，解码后得出了 3 种形状的最优单元布局方案。在直线形单元布局中，平面 Z1有 7 台设备，平面 Z2有 8台设备。具体布局方案如图 5 所示。在“U”形单元布局中，平面 Z1有 8 台设备，平面 Z3有1 台设备，平面 Z2有 6 台设备。具体布局方案如图 6 所示。在环形单元布局中，平面 Z1有 5 台设备，平面 Z3有 2 台设备，平面 Z2有 6 台设备，平面 Z4有 2 台设备。具体布局方案如图 7 所示。SA-QPSO 算法当更新解时不会受目标数值的数量级大小影响，而是比较 2 个解对应目标值的大小关系，这更有利于迭代寻优。综合实例求解结果，可以得出结论，将 SA 算法与QPSO 算法相结合，在求解多层制造单元内设备布局问题中表现良好，寻优能力更强。图 7 环形单元布局方案图 6 “U”形单元布局方案图 5 直线形单元布局方案4 结语本文基于SA-QPSO算法提出了一种多层制造单元内部布局优化设计方法。该方法根据多层制造单元的多个目标函数构建嵌套优化模型，进行求解，并应用于某汽车零件加工车间实际案例，得出直线形、“U”形以及环形 3 种最优的空间布局方案，验证了当较小规模的多层制造单元布局问题求解时，SA算法与QPSO算法相结合具有有效性。该方法可为相关的多层制造单元智能工厂提供一定的单元内部布局设计依据。SA-QPSO 算法的求解思路扩展了 QPSO 算法的应用范围，可应用于类似问题的求解。参考文献1 董峰.建设智能工厂推进智能方案落地 J.中国工业和信息化，2022（1）：44-47.2 王沙沙，张则强，刘俊琦，等.双向环形过道布置问题建模及混合鲸鱼算法求解 J.计算机集成制造系统，2021（10）：27.3 丁祥海，查稳，徐双燕.“U”形生产单元可重构设施布局方法研究 J.工业工程与管理，2015，20（1）：6.4 迟佳，梁秋艳，张晓玲，等.改进量子粒子群自适应优化算法 J.中国科技信息，2023（11）：86-90.5 胡松琪.量子粒子群算法的研究及应用 D.兰州：兰州理工大学，2019.6 张婧婧，施亭亭，汪强.基于量子粒子群算法的公共空间主功能区布局优化设计方法 J.齐齐哈尔大学学报（自然科学版），2023，39（6）：66-71.作者简介：郭轶男（1998-），女，硕士研究生，主要研究方向为生产车间布局优化。电子邮箱：。通信作者：姜雪松（1979-），男，博士，副教授，研究方向为工业工程与管理、制造系统工程及信息化。电子邮箱：。