基于超立方路径规划的发动机再制造物流作业调度策略

本资料包含pdf文件1个，下载需要1积分

航空发动机再制造不同于传统的航空发动机生产制造，其具有多品种，小批量等特点，尤其对于发动机主件和附件的再制造，其工艺工序的多样性程度和复杂程度十分突出，这与传统的刚性离散制造系统依据输入/输出来作决策有着本质的区别。当我们把众多型号发动机的传统生产方式转化为规模化可重构的制造模式时，这就要求其生产组织形态必须适应经常变化的作业过程。

目前，面向系统的可重构研究主要集中在以机器为拈进行制造系统的重构 。

自动导航车(Automated Guided Vehicles，AGV)是-种自动化的无人驾驶的智能化搬运设备，属于移动式机器人系统，能够沿预先设定的路径行驶，是现代计算机集成制造系统中的关键设备之- ∩重构制造系统就是利用AGV的循迹特点进行生产组织形态的重组，从而使得航空发动机再制造车间能够适应经常变化的加工流程。目前这方面研究集中在AGV本身技术以及AGV作业规划调度方面。

对于复杂再制造系统，其车间作业调度路径的拓扑结构可以有多种选择，其算法主要解决的是AGV4车从起点到目标点的路径问题 ，主要有状态空间法 、神经网络法嘲、栅格法 们、免疫网络算法隅、粒子群算法 和遗传算法H伽等。

但是，现有的拓扑规划理论和调度策略普遍存在着难以解决多 目标，多约束，很少涉及实时调度，依赖输入/输出进行决策等问题：因此，研究探索能够快速响应生产形态变化和过程决策传导的作业规划调度理论是航空发动机再制造系统实现可重构的重点和难点。

1 基于超立方路径规划的新方法1.1超立方的概念本文提出的超立方路径规划思想，源于数学物理上的 超立方体”概念 ，超立方体描述方法是寻找-个聚类的最小外接立方体，使其包含数据集中所有的数据 心 。我们从超立方体中抽取-个胞粒作为基本立方体，如图1(a)所示，由于它的八个角点可以通过多条路径相连，于是可将每个角点都规为-个加工工位、仓储货架等。当需要并行协同加工工位或仓储货架之间的作业流程时，我们可按-定的规则来定义连接在立方体上的角点。

：(a) (b)图1 在物流作业路径中引入超立方概念收稿日期：2013-03-05 ，作者简介：高健 (1988-)，男，江苏人，硕士，研究方向为企业信息化集成、计算机辅助设计等。

第35卷 第8期 2013-08(上) 49 l 匐 化设两个相邻角点的连接为-个链接语句，并以 面”为基本单元，如图1(a)中 0-1-2-3的上平面和 4-5-6-7的下平面。如果把-个链接语句，定义成两个角点连接的 链接阀”，则-个基面四个角点的两两互连，可用图1(b)的链接展开图来表示。同时，第-平面的每-个角点都可以与第二平面的任-角点相连且每-种链接方式都有唯-展开图与之对应。如用图1(a)所示的角点3和角点 4之间的连线，将立方体上下两基面连接起来，我们便可得到-种如图2所示的立方体角点链接展开图。

基攘臀图2 单胞粒上下基面角点的连接路径1.2链接算法的简单介绍现规定：设定- 设链接语句函数式为 link(x，y)，X为起始角点值，y)9终止角点值，它们的三位二进制表达式为：x (x2xlXo)Y( 2Y1Y0)设定二 设 Box(i，j)为超立方角点链接阀，它的状态对应于链接语句link(x，y)的 位”状态值，并定义：当 Box(i，j)0时，则表示i与i直链，或j与j直链 ；当 Box(i，j)1时，则表示i与J交链， 与i交链：于是，link(x，Y)的位状态可表示为：link(x，y)Box(x，J)Box(i，j)Box(I，y)] (1)例如，当角点 0与角点1的链接，其 link(0，1)[10，则有：link(O，1)Box(0，1)Box(0，1)[10I501 第35卷 第8期 2013-08(上)可见，Box(0，1)1，表示角点0与角点1交链；Box(0，1)O，表示角点0与角点1直链。

设定三 设链接语句的运算规则为二进制的位加”运算，即两个二进制同位相加后取其个位的值，并用运算符 0”来表示。根据定义，我们对图2中上虚框所表示的第-基面角点的链接算法推导如下：1)相同角点的直链语句：Link(x，y)：00I ：y (2)Link(0，0)Link(00，0o)2[(0(壬》0)(000)[00；Link(1，1)Link(O1，01)2[(0。0)(101)1[001；Link(2，2)Link(10，lO)2(101)(00O)0O；Link(3，3)Link(1 1，1 1)2(101)(101)l[00。

2)不同角点的直链语句：Link(x，Y)(x00y0)(0)l z y：1 (3)Link(x，y)[(0)×(y-x-1))(x 1###y2)(xOOyO)f(4)例如：Link(0，1)Link(O，1)2[(001)(0)[1 0；Link(0，2)Link(00，10)2[(0)(001)(00O)]：Ol0；Link(1，3)Link(01，1 1)2(0)(001)(101)]010； rLink(2，3)Link(10，l 1)2(101)(o(t31)：[013)间隔角点的链接语句：由于不同角点的直链语句具有可逆性，因而可以用它来生成间隔角点的链接状态，即把相邻角点的首尾状态值连接后消去，可用 o ”表示。通常，间隔角点的链接具有多条路径可以选择，如：Link(0，3)Link(0，1)Link(1，3)[101001O1010]；Link(0，3)Link(O，2)OLink(2，3)[0101o[01[0101]；Link(1，2)Link(1，3)OLink(3，2)[0101o010101]；Link(1，2)Link(1，O)OLink(O，2)[101o[010]lOLO1；4)交叉角点的链接语句：Link(3，4)Link((1ink(x，y))(1)(1ink(x，y) (5)对于图2中下虚框所表示的第二基面角点的链接算法，只需将角点值减去(k-1)×4后 (k为立方体的基面数)，套用上平面的链接算法，然后将 、I lI8 似上下两个基面的链接值带入交叉链接语句即可。

1.3引入估价函数由上述算法介绍得知，两角点之间时常存在多条链接路径，因此存在路径最优问题，选择的依据通常有时间因素，距离因素，拥堵因素以及直角拐点因素等u引，为方便起见，本文只引入距离估价函数以取得最优解。引入笛卡尔坐标系，保存每个角点的坐标值。估价函数形式：(”)∑i1其中 (f) 。

上述算法，我们把它定义为 基于超立方模型的路径链接算法”。

2 调度流程如图3所示，根据车间实际情况设置节点布置位置，并提融点笛卡尔坐标值，设置不连通路径，当AGVd'车接受任务时应先根据任务的起始和终止点求出两节点分别所在基面，以便得出链接路径中共有多少交叉角点链接。

图3 调度流程根据调度算法求出的路径不-定都符合车间的实际情况，此时就需要剔除原先设定的不连通路径。每-条符合要求的路径均由若干节点组成，每依次相邻节点间均有-估价函数值，而这条路径的估价函数值是所有节点函数值的总和，最优路径就是依据最小估价函数值来选择。

3 调度算法模型与物理形态的转换我们可进-步将图2所示的链接规则，转换为相应的制造物流作业路径连接的物理形态，为方便可行，我们将工位 2与工位 3的位置互换，将工位 6与工位 7的位置互换，图4就是采用交链语句来连接上下两个基面的多工位路径链接的物理形态示意图。 。

- 符 ㈣ - ：.案》-- - 啊 图4 超立方路径的物理结构对于多基面问题，我们只需要在图4的基础上加以顺延即可，如图5所示。

- 誓 -曩 - - - -- -- i 图5 多重超立方路径的物理结构在此基础上，根据航空发动机再制造车间特点，本文给出了车间布局的示意图，如图6所示。

·： t- t：， - - - 曩 ； 齄蹙赣辅辘主斡辩耩赣簟蠢4 $： ! ： · mt二 C - # i 埔曩 曩 啊 曩 ： t：l I ：l#《：#-·：， #《： ll： l ：l，图6 航空发动机再制造车间布局示意图4 算例例如某-航空发动机再制造车间布局如图7所示。其中O-3节点为航空发动机主体再制造单元，第35卷 第8期 2013-08(上) 151]