工程科学学报，第40卷，第1期：108-119,2018年1月 Chinese Journal of Engineering,Vol.40,No.I:108-119,January 2018 DOI:10.13374/j.issn2095-9389.2018.01.014;http://journals.ustb.edu.cn 飞机移动生产线物料配送与线边存储集成优化 胡鑫铭，陆志强四 同济大学机械与能源工程学院，上海201804 区通信作者，E-mail:zhigianglu(@tongji..cdu.cm 摘要为了解决飞机移动生产线中多并行作业物料的供给问题，构建了飞机移动生产线物料配送与线边存储集成决策的 模型并设计了求解算法.在物料组批和小车调度的基础上，引入了物料在线边空间的存储决策，建立了以小车出行趟数最小 化为目标的数学模型并设计了一种以免疫算法为框架的启发式算法.在免疫算法较优的全局搜索能力下，综合考虑小车的配 送能力与线边空间的重复使用、共享等因素，使用反向动态小车调度算法和物料存储前瞻算法对物料的组批方式、配送时刻 和在线边的存放位置三类变量联合进行决策.对提出的算法进行了数值实验，实验结果证明了模型与算法的有效性. 关键词飞机移动生产线；物料配送；免疫算法：反向动态小车调度 分类号TP29 Integrated optimization of material delivery and line-side storage problem for aircraft moving assembly line HU Xin-ming,LU Zhi-giang School of Mechanical Engineering.Tongji University,Shanghai 201804,China Corresponding author,E-mail:zhiqianglu@tongji.edu.cn ABSTRACT To solve the material supply problem of multiple parallel assembly jobs in aircraft moving assembly line,an integrated material delivery and line-side storage decision making model and corresponding algorithm were proposed.The decisions about the stor- age of line-side material were introduced on the basis of the material-batching and vehicle scheduling problems.An integrated mathe- matical model with the objective of minimizing the number of deliveries was established and a heuristic algorithm based on the immune algorithm was proposed.A joint decision of batching,delivery time and storage position for each job's material was proposed consider- ing delivery capability,reusing and sharing of line-side space through backward-dynamic vehicle scheduling and look-ahead storage al- gorithms while seeking the advantages of the immune algorithm.The results of the numerical experiments proved the validity of the model and algorithms. KEY WORDS aircraft moving assembly line;material delivery;immune algorithm;backward-dynamic vehicle scheduling 飞机移动装配生产线是近年来被飞机制造企业 多且物料种类复杂，物料配送延迟会导致整条生产 逐步引入的全新生产方式，具有装配效率高、生产稳 线作业装配延期].为了保证移动生产线按需稳 定等优点.移动生产线上的飞机以平稳的速度缓慢 定运作，对装配车间内的物流配送系统提出了极高 通过整条装配线并在不同的工位完成相应的装配作 的要求. 业，装配线速度的调整可以适应不同的生产节拍，满 区别于一般汽车装配线等流水线的物料配送问 足市场的不同需求.飞机装配所需的零部件数量繁 题，飞机移动生产线的装配及物料供应存在以下难 收稿日期：2017-05-03 基金项目：国家自然科学基金资助项目(61473211,71171130)
工程科学学报,第 40 卷,第 1 期:108鄄鄄119,2018 年 1 月 Chinese Journal of Engineering, Vol. 40, No. 1: 108鄄鄄119, January 2018 DOI: 10. 13374 / j. issn2095鄄鄄9389. 2018. 01. 014; http: / / journals. ustb. edu. cn 飞机移动生产线物料配送与线边存储集成优化 胡鑫铭, 陆志强苣 同济大学机械与能源工程学院, 上海 201804 苣通信作者,E鄄mail:zhiqianglu@ tongji. edu. cn 摘 要 为了解决飞机移动生产线中多并行作业物料的供给问题,构建了飞机移动生产线物料配送与线边存储集成决策的 模型并设计了求解算法. 在物料组批和小车调度的基础上,引入了物料在线边空间的存储决策,建立了以小车出行趟数最小 化为目标的数学模型并设计了一种以免疫算法为框架的启发式算法. 在免疫算法较优的全局搜索能力下,综合考虑小车的配 送能力与线边空间的重复使用、共享等因素,使用反向动态小车调度算法和物料存储前瞻算法对物料的组批方式、配送时刻 和在线边的存放位置三类变量联合进行决策. 对提出的算法进行了数值实验,实验结果证明了模型与算法的有效性. 关键词 飞机移动生产线; 物料配送; 免疫算法; 反向动态小车调度 分类号 TP29 收稿日期: 2017鄄鄄05鄄鄄03 基金项目: 国家自然科学基金资助项目(61473211,71171130) Integrated optimization of material delivery and line鄄side storage problem for aircraft moving assembly line HU Xin鄄ming, LU Zhi鄄qiang 苣 School of Mechanical Engineering, Tongji University, Shanghai 201804, China 苣Corresponding author, E鄄mail: zhiqianglu@ tongji. edu. cn ABSTRACT To solve the material supply problem of multiple parallel assembly jobs in aircraft moving assembly line, an integrated material delivery and line鄄side storage decision making model and corresponding algorithm were proposed. The decisions about the stor鄄 age of line鄄side material were introduced on the basis of the material鄄batching and vehicle scheduling problems. An integrated mathe鄄 matical model with the objective of minimizing the number of deliveries was established and a heuristic algorithm based on the immune algorithm was proposed. A joint decision of batching, delivery time and storage position for each job爷s material was proposed consider鄄 ing delivery capability, reusing and sharing of line鄄side space through backward鄄dynamic vehicle scheduling and look鄄ahead storage al鄄 gorithms while seeking the advantages of the immune algorithm. The results of the numerical experiments proved the validity of the model and algorithms. KEY WORDS aircraft moving assembly line; material delivery; immune algorithm; backward鄄dynamic vehicle scheduling 飞机移动装配生产线是近年来被飞机制造企业 逐步引入的全新生产方式,具有装配效率高、生产稳 定等优点. 移动生产线上的飞机以平稳的速度缓慢 通过整条装配线并在不同的工位完成相应的装配作 业,装配线速度的调整可以适应不同的生产节拍,满 足市场的不同需求. 飞机装配所需的零部件数量繁 多且物料种类复杂,物料配送延迟会导致整条生产 线作业装配延期[1鄄鄄2] . 为了保证移动生产线按需稳 定运作,对装配车间内的物流配送系统提出了极高 的要求. 区别于一般汽车装配线等流水线的物料配送问 题,飞机移动生产线的装配及物料供应存在以下难
胡鑫铭等：飞机移动生产线物料配送与线边存储集成优化 ·109· 点：装配作业技术复杂且装配时间长，因此物料种类 的零部件一次性配送至线边存储直至消耗完后重新 较多，需要在仓库进行分拣后以齐套的方式进行配 补货，研究的重点集中于小车的装载和调度问题，工 送：装配线的节拍时间长，考虑到部分物料的特殊 位的线边容量仅给定一个上限值.而飞机移动生产 性，不适宜大批量存放在线边区域，必须以单件的形 线由于并行装配作业多且装配时间长，因此不仅需 式在装配作业开始前进行准时化配送：同一时刻存 要对多作业所需物料进行组批配送决策，同时需要 在多项并行装配的作业，如果物料随意堆放不仅会 为不同作业物料分配在线边的存放位置.另一方 造成现场无序混乱，还会降低线边空间的利用率使 面，由于线边空间容量限制，还必须考虑其在时间上 得部分物料没有合适的位置存放.为了保证多作业 的重复利用.事实上，飞机移动生产线的线边空间 物料在线边的有序存储，线边区域在时间和空间上 资源与物料配送系统存在以下权衡：若以准时制方 的合理分配具有重要意义.因此飞机移动生产线物 式对所有物料进行配送，可以减少物料在线边的存 料配送的研究除了对小车的科学调度外，还需要同 放时间，但会产生较高的配送成本，甚至可能出现小 时考虑线边空间的共享和重复利用.基于上述特 车数量不足导致配送计划无法完成的情况；若将部 点，本文提出了飞机移动生产线物料配送与线边存 分装配作业的物料提前配送并以暂存的形式存放在 储集成决策问题(integrated material delivery and 线边，则可以充分利用线边空间将配送压力转移到 storage problem for aircraft moving assembly line, 存储能力上，但这种方式对线边区域在时间和空间 IMDSP-AMAL) 上的科学分配提出了较高的要求.因此在小车装载 现有文献中针对汽车装配线物料配送问题的研 和调度优化中协同考虑物料在线边空间的存放具有 究对于本文具有一定的参考意义.Caputo等[)总结 重要的理论意义.现阶段我国飞机装配车间的物料 了常用的三类物料配送模式：齐套配送(kitting)、线 配送方式还停留在传统的“面向服务”模式，即工人 边存储(line stocking)和准时化配送(just in time)并 根据装配计划到库房申请领料配送，然后进行装配 建立了配送策略选择模型以优化配送成本，数值实 作业，这种被动的物料供应模式容易导致物料管理 验结果表明多种配送模式的混合使用比采用单一的 混乱并产生生产浪费、装配延误等问题.因此对 配送模式具有更高的经济效益.Sali与Sahin在选 IMDSP-AMAL问题的研究有重要的实际应用价值. 择最优配送策略的基础上对工位线边容量、料箱的 Boysen等对以小车出行趟数最少为目标函 装载量等参数进行了敏感度分析，为物料配送提供 数，在配送能力约束下将物料组批从仓库向单工位 了更高效的决策.Goz等)研究了汽车混流装配线 进行物料配送的问题进行了研究，并证明了其为强 物料准时化配送问题，考虑小车装载能力和物料配 NP-hard问题.本文对飞机移动生产线物料配送问 送完成时间等约束，构建了以最小化小车数量为目 题的研究除了包含上述问题的特性外，还需要考虑 标函数的数学模型并设计了两阶段启发式算法进行 线边空间的在时间上的重复利用与共享，具有较高 求解.Emde和Gendreaut6]在给定行车路线的条件 的复杂度，精确算法在求解这类大规模问题时效率 下，以最小化线边库存水平为目标函数建立了数学 较低.免疫算法由于具有较好的全局搜索能力在调 模型，在证明其为NP-hard问题后提出了基于邻域 度问题中得到了广泛的应用0-)，近年来也有学者 搜索的分解启发式算法.Zhou和Peng)假设小车 对人工内分泌系统(artificial endocrine system,AES) 从物料超市到工位以点对点的方式进行配送，通过 进行了研究，Wang等]将人工内分泌系统与免疫 决策小车的出行时刻和每次配送的工位及物料量以 系统相互影响在控制抗体多样性方面的优势引入免 优化线边库存水平，同时设计了回溯法和改进人工 疫算法中并在车间调度问题中进行了应用. 蜂群算法分别对小规模和大规模问题进行求解. 在分析现有文献中存在的物料配送问题与免疫 Fathi等[8)对小车调度和装载问题进行了拓展，构建 算法在调度领域应用等研究成果的基础上，本文以 了以优化小车出行次数为主目标的多目标混合整数 飞机移动生产线的一个装配节拍为决策周期，从中 规划模型并改进了粒子群算法求解问题. 央仓库到大工位间以点对点的方式完成装配所需物 上述文献的模型与算法的提出主要是为了解决 料的配送，综合考虑了小车配送能力与线边空间重 汽车装配线物料配送问题，但在飞机移动生产线中 复使用、共享等因素，对物料的组批方式与其在线边 进行应用仍存在一定的局限.汽车装配线每个工位 存放的位置与时间进行决策，建立了以最小化小车 装配节拍短且装配作业单一，所需物料类型比较固 出行趟数为目标函数的数学模型，设计了以基于内 定，通常采用小批量配送的方式将多个装配周期内 分泌调节机制的免疫算法为框架的启发式算法
胡鑫铭等: 飞机移动生产线物料配送与线边存储集成优化 点:装配作业技术复杂且装配时间长,因此物料种类 较多,需要在仓库进行分拣后以齐套的方式进行配 送;装配线的节拍时间长,考虑到部分物料的特殊 性,不适宜大批量存放在线边区域,必须以单件的形 式在装配作业开始前进行准时化配送;同一时刻存 在多项并行装配的作业,如果物料随意堆放不仅会 造成现场无序混乱,还会降低线边空间的利用率使 得部分物料没有合适的位置存放. 为了保证多作业 物料在线边的有序存储,线边区域在时间和空间上 的合理分配具有重要意义. 因此飞机移动生产线物 料配送的研究除了对小车的科学调度外,还需要同 时考虑线边空间的共享和重复利用. 基于上述特 点,本文提出了飞机移动生产线物料配送与线边存 储集 成 决 策 问 题 ( integrated material delivery and storage problem for aircraft moving assembly line, IMDSP鄄鄄AMAL). 现有文献中针对汽车装配线物料配送问题的研 究对于本文具有一定的参考意义. Caputo 等[3]总结 了常用的三类物料配送模式:齐套配送( kitting)、线 边存储(line stocking)和准时化配送(just in time)并 建立了配送策略选择模型以优化配送成本,数值实 验结果表明多种配送模式的混合使用比采用单一的 配送模式具有更高的经济效益. Sali 与 Sahin [4]在选 择最优配送策略的基础上对工位线边容量、料箱的 装载量等参数进行了敏感度分析,为物料配送提供 了更高效的决策. Golz 等[5]研究了汽车混流装配线 物料准时化配送问题,考虑小车装载能力和物料配 送完成时间等约束,构建了以最小化小车数量为目 标函数的数学模型并设计了两阶段启发式算法进行 求解. Emde 和 Gendreau [6] 在给定行车路线的条件 下,以最小化线边库存水平为目标函数建立了数学 模型,在证明其为 NP鄄鄄 hard 问题后提出了基于邻域 搜索的分解启发式算法. Zhou 和 Peng [7] 假设小车 从物料超市到工位以点对点的方式进行配送,通过 决策小车的出行时刻和每次配送的工位及物料量以 优化线边库存水平,同时设计了回溯法和改进人工 蜂群算法分别对小规模和大规模问题进行求解. Fathi 等[8]对小车调度和装载问题进行了拓展,构建 了以优化小车出行次数为主目标的多目标混合整数 规划模型并改进了粒子群算法求解问题. 上述文献的模型与算法的提出主要是为了解决 汽车装配线物料配送问题,但在飞机移动生产线中 进行应用仍存在一定的局限. 汽车装配线每个工位 装配节拍短且装配作业单一,所需物料类型比较固 定,通常采用小批量配送的方式将多个装配周期内 的零部件一次性配送至线边存储直至消耗完后重新 补货,研究的重点集中于小车的装载和调度问题,工 位的线边容量仅给定一个上限值. 而飞机移动生产 线由于并行装配作业多且装配时间长,因此不仅需 要对多作业所需物料进行组批配送决策,同时需要 为不同作业物料分配在线边的存放位置. 另一方 面,由于线边空间容量限制,还必须考虑其在时间上 的重复利用. 事实上,飞机移动生产线的线边空间 资源与物料配送系统存在以下权衡:若以准时制方 式对所有物料进行配送,可以减少物料在线边的存 放时间,但会产生较高的配送成本,甚至可能出现小 车数量不足导致配送计划无法完成的情况;若将部 分装配作业的物料提前配送并以暂存的形式存放在 线边,则可以充分利用线边空间将配送压力转移到 存储能力上,但这种方式对线边区域在时间和空间 上的科学分配提出了较高的要求. 因此在小车装载 和调度优化中协同考虑物料在线边空间的存放具有 重要的理论意义. 现阶段我国飞机装配车间的物料 配送方式还停留在传统的“面向服务冶模式,即工人 根据装配计划到库房申请领料配送,然后进行装配 作业,这种被动的物料供应模式容易导致物料管理 混乱并产生生产浪费、装配延误等问题. 因此对 IMDSP鄄鄄AMAL 问题的研究有重要的实际应用价值. Boysen 等[9]对以小车出行趟数最少为目标函 数,在配送能力约束下将物料组批从仓库向单工位 进行物料配送的问题进行了研究,并证明了其为强 NP鄄鄄 hard 问题. 本文对飞机移动生产线物料配送问 题的研究除了包含上述问题的特性外,还需要考虑 线边空间的在时间上的重复利用与共享,具有较高 的复杂度,精确算法在求解这类大规模问题时效率 较低. 免疫算法由于具有较好的全局搜索能力在调 度问题中得到了广泛的应用[10鄄鄄11] ,近年来也有学者 对人工内分泌系统(artificial endocrine system, AES) 进行了研究,Wang 等[12] 将人工内分泌系统与免疫 系统相互影响在控制抗体多样性方面的优势引入免 疫算法中并在车间调度问题中进行了应用. 在分析现有文献中存在的物料配送问题与免疫 算法在调度领域应用等研究成果的基础上,本文以 飞机移动生产线的一个装配节拍为决策周期,从中 央仓库到大工位间以点对点的方式完成装配所需物 料的配送,综合考虑了小车配送能力与线边空间重 复使用、共享等因素,对物料的组批方式与其在线边 存放的位置与时间进行决策,建立了以最小化小车 出行趟数为目标函数的数学模型,设计了以基于内 分泌调节机制的免疫算法为框架的启发式算法 ·109·
·110. 工程科学学报，第40卷，第1期 (HBEI),其中结合了小车反向动态调度算法和物料 放位置，以达到最小化物料配送成本，即小车出行趟 存储前瞻优化算法.最后通过数值实验验证所提出 数最小的目标.图1为飞机移动生产线的物料供应 算法在求解IMDSP-AMAL问题时的有效性. 模式，整条生产线被划分为多个“虚拟大工位”[) 每个大工位内存在大量的并行装配作业，在工位边 1问题描述及数学模型 划定相关的区域用于存放各作业装配所需的物料， 1.1问题描述 并由多载量小车(Tow-train)以点对点的方式将物 飞机移动生产线物料配送问题，是通过优化决 料按时定量配送至相应工位的线边空间 策各作业所需物料的配送时间及其在线边空间的存 IMDSP-AMAL问题的假设与说明如下. 工位1 工位2 工位3 工位4 线边物料存储区 物流通道 警晋小 警肾小 中央仓库 多视量小车 ☐物料存储区 物料通道 图1飞机移动生产线物料供应模式示意图 Fig.1 Schematic of the material supply mode for aireraft moving assembly line (1)以飞机移动生产线的一个装配节拍时间为 的运输时间为t,物料的装卸时间为，任意第r趟 决策周期，假定该周期内某大工位包含n项装配作 配送的物料量不得超过小车的装载能力上限Cv, 业，J={1,2,…,n,任意j∈J的执行工期为，开 r∈R={1,2,…,π}，R表示小车出行趟数集合，IRI 始时间为T,完成时间T=T+1 表示小车出行总趟数 (2)将时间离散化，时间集合为D=1,2,…, (5)一项作业所需的全部物料由一辆小车一次 z},z表示所有作业操作时间总和，任意d∈D表示 性配送完成，一辆小车一次可配送多项作业所需物 离散的时间节点. 料.作业j的物料配送开始时间为T,配送完成时 (3)飞机装配作业所需的物料主要有三类：形 间T=T+t+,配送提前期t=T-T. 状不规则、数量少的大型结构件，包括发动机、大型 (6)如图2所示，将飞机上的作业空间和线边 舱门组件等：需求量大、体积小的通用标准件，如螺 空间离散化.作业空间描述了不同作业在一架飞机 钉螺母等紧固件：体积较小、种类多的装配件，如小 上的不同装配位置，用集合T={1,2,…,p}表示，p 型机电仪器设备、各类支架等.大型结构件由于体 表示飞机的长度，任意L,∈T表示作业j在飞机上的 积较大一般采用吊车、行车等大型物流设备直接进 固定装配位置.线边空间的定义为作业物料在装配 行配送，通用标准件需求量较高且体积小，通常在各 线旁的存储区域，如图2中网格部分所示.离散化 工位线边单独划定存放区域，通过定期补货的方式 的线边空间网络为N(l,c),l∈L={1,2,…,}表示 配送，因此本文重点考虑装配件的配送与存放.任 线边空间位置集合，c1={1,2,…,}表示单位线边 意作业所需的装配件使用标准料箱由小车配送至 空间1内的存储空间编号，ψ为最大容量.对于任意 线边空间并在装配作业结束后统一回收空料箱的方 一架飞机，状态A表示飞机进入移动生产线的起始 式进行供应，作业j对物料的需求为 位置.假定飞机移动生产线的移动速度为V,在时 (4)多载量小车数量为0，K表示小车集合，k∈ 刻T飞机移动到状态B位置时作业j开始装配，经 K={1,2,…,w}.假设小车从中央仓库到工位线边 过t时间段飞机移动到状态D所示位置时作业j装
工程科学学报,第 40 卷,第 1 期 (HBEI),其中结合了小车反向动态调度算法和物料 存储前瞻优化算法. 最后通过数值实验验证所提出 算法在求解 IMDSP鄄鄄AMAL 问题时的有效性. 1 问题描述及数学模型 1郾 1 问题描述 飞机移动生产线物料配送问题,是通过优化决 策各作业所需物料的配送时间及其在线边空间的存 放位置,以达到最小化物料配送成本,即小车出行趟 数最小的目标. 图 1 为飞机移动生产线的物料供应 模式,整条生产线被划分为多个“虚拟大工位冶 [13] , 每个大工位内存在大量的并行装配作业,在工位边 划定相关的区域用于存放各作业装配所需的物料, 并由多载量小车(Tow鄄鄄 train)以点对点的方式将物 料按时定量配送至相应工位的线边空间. IMDSP鄄鄄AMAL 问题的假设与说明如下. 图 1 飞机移动生产线物料供应模式示意图 Fig. 1 Schematic of the material supply mode for aircraft moving assembly line (1)以飞机移动生产线的一个装配节拍时间为 决策周期,假定该周期内某大工位包含 n 项装配作 业,J = {1,2,…,n},任意 j沂J 的执行工期为 t j,开 始时间为 T S j ,完成时间 T F j = T S j + t j . (2)将时间离散化,时间集合为 D = {1,2,…, z},z 表示所有作业操作时间总和,任意 d沂D 表示 离散的时间节点. (3)飞机装配作业所需的物料主要有三类:形 状不规则、数量少的大型结构件,包括发动机、大型 舱门组件等;需求量大、体积小的通用标准件,如螺 钉螺母等紧固件;体积较小、种类多的装配件,如小 型机电仪器设备、各类支架等. 大型结构件由于体 积较大一般采用吊车、行车等大型物流设备直接进 行配送,通用标准件需求量较高且体积小,通常在各 工位线边单独划定存放区域,通过定期补货的方式 配送,因此本文重点考虑装配件的配送与存放. 任 意作业 j 所需的装配件使用标准料箱由小车配送至 线边空间并在装配作业结束后统一回收空料箱的方 式进行供应,作业 j 对物料的需求为 vj . (4)多载量小车数量为 w,K 表示小车集合,k沂 K = {1,2,…,w}. 假设小车从中央仓库到工位线边 的运输时间为 t T ,物料的装卸时间为 t L ,任意第 r 趟 配送的物料量不得超过小车的装载能力上限 CV, r沂R = {1,2,…,仔},R 表示小车出行趟数集合, | R | 表示小车出行总趟数. (5)一项作业所需的全部物料由一辆小车一次 性配送完成,一辆小车一次可配送多项作业所需物 料. 作业 j 的物料配送开始时间为 T DS j ,配送完成时 间 T DF j = T DS j + t T + t L ,配送提前期 t p j = T S j - T DS j . (6)如图 2 所示,将飞机上的作业空间和线边 空间离散化. 作业空间描述了不同作业在一架飞机 上的不同装配位置,用集合 祝 = {1,2,…,渍}表示,渍 表示飞机的长度,任意 l j沂祝 表示作业 j 在飞机上的 固定装配位置. 线边空间的定义为作业物料在装配 线旁的存储区域,如图 2 中网格部分所示. 离散化 的线边空间网络为 N(l,cl),l沂L = {1,2,…,孜}表示 线边空间位置集合,cl = {1,2,…,鬃}表示单位线边 空间 l 内的存储空间编号,鬃 为最大容量. 对于任意 一架飞机,状态 A 表示飞机进入移动生产线的起始 位置. 假定飞机移动生产线的移动速度为 V,在时 刻 T S j 飞机移动到状态 B 位置时作业 j 开始装配,经 过 t j 时间段飞机移动到状态 D 所示位置时作业 j 装 ·110·
胡鑫铭等：飞机移动生产线物料配送与线边存储集成优化 ·111· V.TS v.t 123… 图2飞机移动生产线作业装配点及物料摆放位置示意图 Fig.2 Schematic of the positions of assembly and material storage on aircraft moving assembly line 配完成.则状态C所示位置表示作业j开始执行到 1.2数学模型 完成时间段内飞机在移动生产线上移动距离的中间 IMDSP-AMAL问题的数学模型如下： 位置，定义该位置所对应的线边空间位置为作业j min Z=IRI (1) 所需物料的中心摆放位置，用图中黑色部分表 s.t. VjeJ 示.任意必eL,=「号+.T+V4/21,「门表示向 上取整. (2) (7)线边空间的分配以将任意装配作业所需物 言1ie1 (3) 料存放在距离中心摆放位置较近区域为基本原则， 可允许作业j的物料存放在及其左右两侧各m 三c, (4) 个单位的线边空间内，用图2中阴影部分表示.为 使线边物料存放整齐有序，要求任一作业的全部物 (5) 料连续存放于同一线边单元内. 0=d-(红+2r)+1 本文研究一个装配周期内物料的配送方案，主 豆名s VieD..aeN (6) 要包含三类决策变量： =「+V.1+5V/21jeJ (7) T,={x={0 Vd∈D,Vr∈R},表示第r趟车的 IM +m d-iL-IT 配送时刻，时刻d从仓库出第r趟车时x等于1，否 =d--+1 VjeJ,YdeD (8) 则取0. r19=r29 jeJ,rER},表示第r趟车 j∈J,c∈N,T1、T2∈[T,T] (9) 配送的物料集合，作业j由第r趟车配送时y,等于 =言%re (10) 1,否则取0. ={a=l (11) jeJ,HdeD,HceN},表 会≤IV7ER 示物料在线边空间的存储方案，作业j在时刻d存 Hr∈R (12) 放于线边单元c,内时.取1，否则取0 Hr∈R (13) 同时引人销时系数4(a-位： else xh∈{0,1}，y∈10,1}，，={0,1} 定义YU,d,l)为作业j在时刻d在线边空间l Vj∈J,Hd∈D,Hr∈R,Hc∈(14) 式(1)为目标函数，最小化小车出行趟数：式 处物料存放情况，Y.d,)=三(（三 (2)表示物料需求时间约束，作业装配所需物料必 须在其开始执行前配送完成：式(3)表示一个作业 )） 通过一次配送完成：式(4)和(5)分别表示小车的容
胡鑫铭等: 飞机移动生产线物料配送与线边存储集成优化 图 2 飞机移动生产线作业装配点及物料摆放位置示意图 Fig. 2 Schematic of the positions of assembly and material storage on aircraft moving assembly line 配完成. 则状态 C 所示位置表示作业 j 开始执行到 完成时间段内飞机在移动生产线上移动距离的中间 位置,定义该位置所对应的线边空间位置为作业 j 所需物料的中心摆放位置 l M j ,用图中黑色部分表 示. 任意 l M j 沂L,l M j = 腋l j + V·T S j + V·t j / 2骎,腋骎表示向 上取整. (7)线边空间的分配以将任意装配作业所需物 料存放在距离中心摆放位置较近区域为基本原则, 可允许作业 j 的物料存放在 l M j 及其左右两侧各 m 个单位的线边空间内,用图 2 中阴影部分表示. 为 使线边物料存放整齐有序,要求任一作业的全部物 料连续存放于同一线边单元内. 本文研究一个装配周期内物料的配送方案,主 要包含三类决策变量: Tr = { xdr = { 1 0 坌d沂D,坌r沂R } ,表示第 r 趟车的 配送时刻,时刻 d 从仓库出第 r 趟车时 xdr等于 1,否 则取 0. Jr = { yjr = { 1 0 坌j沂J,坌r沂R } ,表示第 r 趟车 配送的物料集合,作业 j 由第 r 趟车配送时 yjr等于 1,否则取 0. S L J = { vjdcl = { 1 0 坌j沂J,坌d沂D,坌cl沂N } ,表 示物料在线边空间的存储方案,作业 j 在时刻 d 存 放于线边单元 cl 内时 vjdcl取 1,否则取 0. 同时引入辅助函数 滋(u,v) = 1, u = v; 0, else { . 定义 状(j,d,l)为作业 j 在时刻 d 在线边空间 l 处物料存放情况,状( j,d,l) = 移 鬃 cl = ( 1 滋 ( 移 渍+vj-1 渍 = cl vjd渍 , vj ) ). 1郾 2 数学模型 IMDSP鄄鄄AMAL 问题的数学模型如下: min Z = | R | (1) s. t. 移 仔 r = ( 1 yjr·移 z d = 1 xdr·d ) + t T + t L臆T S j 坌j沂J (2) 移 仔 r = 1 yjr = 1 坌j沂J (3) 移 n j = 1 yjr·vj臆CV 坌r沂R (4) 移 仔 r = ( 1 移 d 籽 = d-(tL +2tT ) +1 x籽r ) 臆w 坌d沂D (5) 移 n j = 1 移 鬃 cl = 1 vjdcl臆鬃 坌d沂D,坌cl沂N (6) l M j = 腋l j + V·T S j + t·j V / 2骎 坌j沂J (7) 移 lM j +m l = lM j -m 状(j,d,l) = 移 仔 r = ( 1 移 d-t L -t T 子 = d-t p j -t j+1 x子r·yjr ) 坌j沂J,坌d沂D (8) vj子1 cl = vj子2 cl 坌j沂J,坌cl沂N,坌子1 、子2沂[T DF j ,T F j ] (9) | R |逸 移 仔 r = 1 yjr·r 坌j沂J (10) 移 z d = 1 xdr臆1 坌r沂R (11) 移 n j = 1 yjr - 移 z d = 1 xdr逸0 坌r沂R (12) 移 z d = 1 xdr - 移 n j = 1 yjr / M逸0 坌r沂R (13) xdr沂{0,1},yjr沂{0,1},vjdcl = {0,1} 坌j沂J,坌d沂D,坌r沂R,坌cl沂N (14) 式(1) 为目标函数,最小化小车出行趟数;式 (2)表示物料需求时间约束,作业装配所需物料必 须在其开始执行前配送完成;式(3)表示一个作业 通过一次配送完成;式(4)和(5)分别表示小车的容 ·111·
·112. 工程科学学报，第40卷，第1期 量和数量约束，任意小车每次配送作业的物料数量 量较差甚至可能不存在可行解，在免疫算法迭代 不超过其容量上限，任意时刻小车的使用数量不超 过程中被更新或淘汰.以下分别对免疫算法框架、 过小车总量：式(6)约束了线边空间存储能力，任意 反向动态小车调度算法以及前瞻优化算法进行 时刻物料存储量不超过线边空间容量上限：式(7) 阐述 计算了装配作业所需物料在移动生产线边的中心摆 2.1免疫算法框架 放位置：式(8)和式(9)对线边空间物料的存放规则 免疫算法采用变长度抗体编码方式，以物料的 进行了定义，任意装配作业所需物料允许存放在其 配送批次顺序编码.编码长度表示物料的划分批次 物料中心摆放位置左右两侧一定区域的位置，但该 数，即小车的配送趟数.抗体上的每个基因位包含 作业所有物料必须连续存放在同一个线边单元内； 了该批次配送的作业物料.图3为一包含10项作 式(10)定义了小车的配送趟数：式(11)、(12)和 业所需物料的配送方案，共划分为5个批次配送，其 (13)定义了决策变量x.和y,之间的线性关系，M 中作业1和作业2所需物料由第一趟小车配送 为一足够大的数：式(14)定义了决策变量的可 ③④ 7 ⑨ 行域 (2 (6 (5 (8 (10 2算法设计 图3抗体编码示意图 Fig.3 Schematic of the encoded mode for antibodies 针对IMDSP-AMAL问题的特点，本文设计了一 本文在标准免疫算法中引入了内分泌调节机制 种以基于内分泌调节机制的免疫算法为框架的启发 进一步提升了免疫算法的搜索性能，利用激素分泌 式算法(HBEI),其中结合了反向动态小车调度算法 调节的上升和下降遵循H函数规律设计了自 和物料存储前瞻优化算法.该算法的基本框架与核 适应变异概率函数，随着抗体平均亲和度上升，抗体 心思想为：通过免疫算法较强的全局搜索能力搜寻 群的变异概率增大，加快了免疫算法的收敛速度并 较优的作业批次划分组合，对每一条包含作业批次 有效提高了抗体多样性.抗体变异概率如式(15)所 划分方式的抗体使用反向动态小车调度算法(back- 示，其中p为初始变异概率，afvc和afm分别表示 ward dynamic vehicle scheduling,BDVS)和物料存储 抗体亲和度均值及阈值，α和B为系数因子. 前瞻优化算法(storage look-ahead optimization, （(affavc)B SLAO)进行解码，从而判定该抗体是否属于高亲和 P+(aff ve )(affm ) (15) 度抗体.若抗体亲和度高，则对应的批次划分方式 设定免疫算法的迭代次数为G,入表示当前代 存在较优可行解，该抗体得以保留在记忆池中：若 数.式(16)表示亲和度函数af,P(A)表示配送方 抗体亲和度较低，说明对应的批次划分方式解质 案A的惩罚函数（具体见2.3）.算法框架如图4所 生成初始 抗体群，入=0 初始化 反向动态 物料存放前瞻算法 (SL.40) 是否可行解 引人罚函数 小车调度 算法 !基宇物料存储时长 (BDVS) !的动态调整算法 是 解码 计算亲和度T 选择得到新 抗体 变异得到 抗体 一代抗体群 记忆池 临时抗体样 克隆 免疫算子 1=1+1 A<G? 参数判定 输出最优个体 输出 对应小车趟数 图4免疫算法框架 Fig.4 Outline of the immune algorithm
工程科学学报,第 40 卷,第 1 期 量和数量约束,任意小车每次配送作业的物料数量 不超过其容量上限,任意时刻小车的使用数量不超 过小车总量;式(6)约束了线边空间存储能力,任意 时刻物料存储量不超过线边空间容量上限;式(7) 计算了装配作业所需物料在移动生产线边的中心摆 放位置;式(8)和式(9)对线边空间物料的存放规则 进行了定义,任意装配作业所需物料允许存放在其 物料中心摆放位置左右两侧一定区域的位置,但该 作业所有物料必须连续存放在同一个线边单元内; 式(10) 定义了小车的配送趟数;式(11)、(12) 和 (13) 定义了决策变量 xdr 和 yjr 之间的线性关系,M 为一足够大的数; 式 (14 ) 定义了决策变量的可 行域. 图 4 免疫算法框架 Fig. 4 Outline of the immune algorithm 2 算法设计 针对 IMDSP鄄鄄AMAL 问题的特点,本文设计了一 种以基于内分泌调节机制的免疫算法为框架的启发 式算法(HBEI),其中结合了反向动态小车调度算法 和物料存储前瞻优化算法. 该算法的基本框架与核 心思想为:通过免疫算法较强的全局搜索能力搜寻 较优的作业批次划分组合,对每一条包含作业批次 划分方式的抗体使用反向动态小车调度算法(back鄄 ward dynamic vehicle scheduling, BDVS)和物料存储 前 瞻 优 化 算 法 ( storage look鄄ahead optimization, SLAO)进行解码,从而判定该抗体是否属于高亲和 度抗体. 若抗体亲和度高,则对应的批次划分方式 存在较优可行解,该抗体得以保留在记忆池中;若 抗体亲和度较低,说明对应的批次划分方式解质 量较差甚至可能不存在可行解,在免疫算法迭代 过程中被更新或淘汰. 以下分别对免疫算法框架、 反向动态小车调度算法以及前瞻优化算法进行 阐述. 2郾 1 免疫算法框架 免疫算法采用变长度抗体编码方式,以物料的 配送批次顺序编码. 编码长度表示物料的划分批次 数,即小车的配送趟数. 抗体上的每个基因位包含 了该批次配送的作业物料. 图 3 为一包含 10 项作 业所需物料的配送方案,共划分为 5 个批次配送,其 中作业 1 和作业 2 所需物料由第一趟小车配送. 图 3 抗体编码示意图 Fig. 3 Schematic of the encoded mode for antibodies 本文在标准免疫算法中引入了内分泌调节机制 进一步提升了免疫算法的搜索性能,利用激素分泌 调节的上升和下降遵循 Hill 函数规律[14] 设计了自 适应变异概率函数,随着抗体平均亲和度上升,抗体 群的变异概率增大,加快了免疫算法的收敛速度并 有效提高了抗体多样性. 抗体变异概率如式(15)所 示,其中 p I mut为初始变异概率,affAVG和 affTH分别表示 抗体亲和度均值及阈值,琢 和 茁 为系数因子. pmut = p I mut (1 + 琢 (affAVG) 茁 (affAVG) 茁 + (affTH ) 茁 ) (15) 设定免疫算法的迭代次数为 G,姿 表示当前代 数. 式(16)表示亲和度函数 aff,P(撰)表示配送方 案 撰 的惩罚函数(具体见 2郾 3). 算法框架如图 4 所 ·112·
胡鑫铭等：飞机移动生产线物料配送与线边存储集成优化 ·113· 示，其中免疫算法的通用部分不再赘述，反向动态小 反向动态小车调度算法的具体步骤如下 车调度算法和物料存储前瞻优化算法分别在2.2和 Step1:获取作业批次划分决策方案2={B, 2.3中详细介绍. B2,…,B…}. Step2:令i=I2l,选取最后一批次的作业集合 aff(A)= (16) P(A) B,为其安排小车发车时间为T=T必-t「-t 2.2反向动态小车调度算法 Step3:更新小车资源，计算小车最晚可用时刻 在物料批次划分方式确定情况下，若小车以准 TR=maxT(om-2-kEK] 时制方式对每批物料进行配送，可以缩短物料在线 Step4:i=i-1,计算批次B:最晚配送时刻 边的存放时间，但可能由于小车数量不足导致配送 T份=Tg-t'- 计划无法完成：若允许部分批次物料通过提前配送 Step5:计算物料批次B:发车时刻Tg= 并以暂存的形式存放在线边，则可以充分利用线边 minT,T. 空间将配送压力转移到存储能力上.为了平衡小车 Step6:若i>1,转Step3,否则转Step7. 的配送能力和线边空间存储能力，在参考文献[7] Step7:输出小车调度序列及配送时刻T。= 提出的反向动态调度技术的基础上，基于以下性质 {Tg1B,∈2，r=i∈R. 提出了反向动态小车调度算法，该算法能保证小车 2.3物料存储前瞻优化算法 在完成所有物料配送的前提下使得物料在线边的存 储时间最短.由于文献[7]中的目标函数为最小化 物料在线边的存储可以抽象为一类特殊的带单 线边库存水平，因此求得的解即为目标函数的最终 边时间窗的三维装箱问题.如图5所示，l轴表示线 解.而本文在应用反向动态小车调度算法后将得到 边空间，c1表示单位线边空间l内的存储单元，1表 的线边最短存储时长作为中间解，为后续物料存储 示时间轴，图中方块表示不同作业物料需求量.在 算法的应用奠定基础 2.2中完成小车配送的调度后，可以确定任意批次 性质：在给定的物料配送批次2={B1,B2,…, 物料送达线边的时刻，因此需要决策各作业物料在 B,…},其中B={jaj2,…,j,…}条件下，基于小 规定时间窗[T,T]内在I和c,轴上的存储位置. 车发车时间约束和物料需求时间约束，为使物料在 为了最大化利用线边存储空间，本节设计了物料批 线边存放时间最短，任意批次物料B,的最优配送时 次内和批次间的前瞻优化算法，区别于一般装箱问 间为： 题的前瞻算法，由于飞机移动生产线物料存储位置 皮= 的特殊性，每个“箱体”仅允许在有限区域内选择存 储位置，且多个作业的物料仅在存储时间和允许存 (min,mxk is-1 储位置上均发生重叠时才可能会发生干涉，因此相 g--, i=101 比于通用的前瞻算法，本文设计的物料存储前瞻优 T心表示批次为B,物料的最晚需求时刻，T= 化算法的前瞻搜索空间更小，有利于提高算法的搜 min{Tial Vjs∈B:}. 索速度 T表示小车k第，趟发车的最优时间，则 T+)表示小车k在后一趟发车的最优时间. 证明： 在物料配送批次2={B1,B2,…,B,…}[0,1] 确定条件下，为了满足小车发车时间约束和物料需 求时间约束，即有小车处于空闲状态才能发车，且物 料必须在最晚需求时刻前送达，可得T≤Tg- ,123,4,5,6,7,8,9,10,11,12 F-t,T≤max{Tu+ng-2i-.令T= 图5物料线边存放示意图 T,T<T,对于任意作业j∈B,T和T得到 Fig.5 Schematic of line-side material storage 的提前配送期差值△=△-△=T分-T= T分-T光<0恒成立.说明在T=T时可以使得 图6给出了前瞻算法的优化机理，十项作业的 该批次的任意作业在线边存储提前期最短 物料被划分为5个批次进行配送，各批次物料在线
胡鑫铭等: 飞机移动生产线物料配送与线边存储集成优化 示,其中免疫算法的通用部分不再赘述,反向动态小 车调度算法和物料存储前瞻优化算法分别在 2郾 2 和 2郾 3 中详细介绍. aff(撰) = 1 移r沂R r + P(撰) (16) 2郾 2 反向动态小车调度算法 在物料批次划分方式确定情况下,若小车以准 时制方式对每批物料进行配送,可以缩短物料在线 边的存放时间,但可能由于小车数量不足导致配送 计划无法完成;若允许部分批次物料通过提前配送 并以暂存的形式存放在线边,则可以充分利用线边 空间将配送压力转移到存储能力上. 为了平衡小车 的配送能力和线边空间存储能力,在参考文献[7] 提出的反向动态调度技术的基础上,基于以下性质 提出了反向动态小车调度算法,该算法能保证小车 在完成所有物料配送的前提下使得物料在线边的存 储时间最短. 由于文献[7]中的目标函数为最小化 线边库存水平,因此求得的解即为目标函数的最终 解. 而本文在应用反向动态小车调度算法后将得到 的线边最短存储时长作为中间解,为后续物料存储 算法的应用奠定基础. 性质:在给定的物料配送批次 赘 = {B1 ,B2 ,…, Bi,…},其中 Bi = {j i1 ,j i2 ,…,j i啄,…}条件下,基于小 车发车时间约束和物料需求时间约束,为使物料在 线边存放时间最短,任意批次物料 Bi 的最优配送时 间为: T Dopt S Bi = min {T NL Bi - t T - t L ,max {T(r +1) opt k -2t T - t L |坌k沂K}}, i臆|赘| -1 T NL Bi - t T - t L , i = |赘 { | T NL Bi 表示批次为 Bi 物料的最晚需求时刻,T NL Bi = min {T S j i啄 |坌j i啄沂Bi}. Tr opt k 表示小车 k 第 r 趟发车的最优时间, 则 T(r + 1) opt k 表示小车 k 在后一趟发车的最优时间. 证明: 在物料配送批次 赘 = {B1 ,B2 ,…,Bi,…} [0,1] 确定条件下,为了满足小车发车时间约束和物料需 求时间约束,即有小车处于空闲状态才能发车,且物 料必须在最晚需求时刻前送达,可得 T Dopt S Bi 臆T NL Bi - t T - t L , T Dopt S Bi 臆 max { T(r + 1) opt k - 2t T - t L }. 令 T DS 1 = T Dopt S Bi ,T DS 2 1,转 Step3,否则转 Step7. Step7:输出小车调度序列及配送时刻 TR = {T Dopt S Bi | Bi沂赘,r = i沂R}. 2郾 3 物料存储前瞻优化算法 物料在线边的存储可以抽象为一类特殊的带单 边时间窗的三维装箱问题. 如图 5 所示,l 轴表示线 边空间,cl 表示单位线边空间 l 内的存储单元,t 表 示时间轴,图中方块表示不同作业物料需求量. 在 2郾 2 中完成小车配送的调度后,可以确定任意批次 物料送达线边的时刻,因此需要决策各作业物料在 规定时间窗[T DF j ,T F j ]内在 l 和 cl 轴上的存储位置. 为了最大化利用线边存储空间,本节设计了物料批 次内和批次间的前瞻优化算法,区别于一般装箱问 题的前瞻算法,由于飞机移动生产线物料存储位置 的特殊性,每个“箱体冶仅允许在有限区域内选择存 储位置,且多个作业的物料仅在存储时间和允许存 储位置上均发生重叠时才可能会发生干涉,因此相 比于通用的前瞻算法,本文设计的物料存储前瞻优 化算法的前瞻搜索空间更小,有利于提高算法的搜 索速度. 图 5 物料线边存放示意图 Fig. 5 Schematic of line鄄side material storage 图 6 给出了前瞻算法的优化机理,十项作业的 物料被划分为 5 个批次进行配送,各批次物料在线 ·113·
.114. 工程科学学报，第40卷，第1期 边的存储时长如图6(a)所示.假定允许作业的物 时刻T-T哈+t「+人. 料存放在其中心摆放位置两侧各一个单位的线 Step3:若S2nS≠01js∈B,S←S+ 边空间内.对于作业1，其物料在线边的存储时间与 S,84-6+1. 作业2、3、4和5的物料存储时间发生了重叠，同时 Step4:若8'=lB.I,转Step5,否则转Step3. 它们的物料可存放位置也存在重叠部分(！-1∈[1， Step5:令i'=i+1,若i'>I2l,转Step7,若 3]-2∈[1,3]、-∈[2,4]、=4∈[3,5]=s∈ [T胎，T]n[T路，T]≠且光n≠01 [3,5]),因此将这几个物料在线边存储位置的所有 可能组合列举如图6(b)所示.对所有的组合通过 jseB,SY←-S+S7,8'←+1，转Step6. 式(17)计算物料的有效存储集中度(effective con- Step6:若8'>lBl,转Step7,否则转Step5 centration ratio,ECR),该指标综合体现了线边空间 Step7:计算S中所有组合的有效集中度，选择 的利用率大小，选择有效存储集中度值最高的组合 有效存储集中度最大的作业物料存放位置组合C, 中作业1物料存放线边单元=！=1作为该物料的 将作业js的物料存放在C”所决策的线边位置内，并执 存储线边单元.同理，对于作业2的物料，考察在时 行基于物料存储时长的动态调整算法(2.4节) 间和空间上均发生重叠的物料3、4、5和6，从而确 Step8:i←i+1,若i>I2l,转Step9,否则转 定作业2物料的存储线边单元，依次直至全部作业 Step2. 物料存放完毕.物料在线边单元内的存储方式采用 Step9:获取所有作业的物料在线边网络V(l, 基于物料存储时长的动态调整算法(2.4节中详细 c,)的存储方案S,算法结束. 阐述)，若出现作业没有足够空间存放的情况，则在 2.4基于物料存储时长的动态调整算法 抗体亲和度计算中引入惩罚函数(18)，其中M'为一 对于任一线边空间单元1，若作业j的物料被安 足够大的数 排存入该线边单元内，可能存在线边总容量充足但 ECR()=五A(仔)' 不连续导致物料无法存放的情况.针对这类情况， (17) jeliles 本文提出了基于物料存储时长的动态调整算法，该 P(A)=∑M'(,-) (18) 算法的目的是通过局部调整其他并行装配作业的物 1e,13中 料存放位置，最大化线边空间的利用率，保证在单位 定义符号习表示作业j的物料可存放线边位 线边总容量充足时，装配作业所需的物料有合适的 置集合，S表示当次前瞻算法中所包含作业的物料 空间存放.该算法主要通过调整存储时长较长的作 可存储线边位置集合.前瞻优化算法的具体步骤 业所需物料至线边空间两侧获取较大的连续存储空 如下 间，图7对该算法机理进行了说明.c,表示线边空 Step1:获取各批次作业的配送方案TR={TBI 间1内的存储单元，对于作业7所需物料=，=4，其 B:∈2，r=i∈R},令i=1,8=1,S=0. 在线边的存放时间为t=[7,10],该时间段内剩余 Step2:计算Hjs∈B,的物料配送至线边空间的 可用线边单元为c1=1,2,3,6,最大线边空间容量 1 (3)(4 9) 2 5 10 批次内前瞻 批次间前瞻 个批次编号 (2 (3 (4 四 ③… 10 ②K④…团 ☒ 回…固K④ ④… 囹 ③→… ①作业箱号 回线边空间单元编号 1234567891011121314151617时间 国冠④最优存储位置组合 (a) (b) 图6前瞻算法优化机理.(a)物料在线边存储时长：(b)批次内前瞻和批次间前瞻示意图 Fig.6 Look-ahead optimization mechanism:(a)storage duration of line-side material:(b)look ahead in batch and between batches
工程科学学报,第 40 卷,第 1 期 边的存储时长如图 6(a)所示. 假定允许作业 j 的物 料存放在其中心摆放位置 l M j 两侧各一个单位的线 边空间内. 对于作业 1,其物料在线边的存储时间与 作业 2、3、4 和 5 的物料存储时间发生了重叠,同时 它们的物料可存放位置也存在重叠部分( l j = 1沂[1, 3]、l j = 2 沂[1,3]、l j = 3 沂[2,4]、l j = 4 沂[3,5]、l j = 5 沂 [3,5]),因此将这几个物料在线边存储位置的所有 可能组合列举如图 6( b)所示. 对所有的组合通过 式(17)计算物料的有效存储集中度( effective con鄄 centration ratio, ECR),该指标综合体现了线边空间 的利用率大小,选择有效存储集中度值最高的组合 中作业 1 物料存放线边单元 l j = 1 = 1 作为该物料的 存储线边单元. 同理,对于作业 2 的物料,考察在时 间和空间上均发生重叠的物料 3、4、5 和 6,从而确 定作业 2 物料的存储线边单元,依次直至全部作业 物料存放完毕. 物料在线边单元内的存储方式采用 基于物料存储时长的动态调整算法(2郾 4 节中详细 阐述),若出现作业没有足够空间存放的情况,则在 抗体亲和度计算中引入惩罚函数(18),其中 M忆为一 足够大的数. ECR(装j) = 移 j沂装j 移l沂S j ( L vl j ) 鬃 2 (17) P(撰) = l沂移L,vl > 鬃 M忆(vl - 鬃) (18) 图 6 前瞻算法优化机理. (a)物料在线边存储时长;(b)批次内前瞻和批次间前瞻示意图 Fig. 6 Look鄄ahead optimization mechanism: (a) storage duration of line鄄side material; (b) look ahead in batch and between batches 定义符号 S j L 表示作业 j 的物料可存放线边位 置集合,S J T L 表示当次前瞻算法中所包含作业的物料 可存储线边位置集合. 前瞻优化算法的具体步骤 如下. Step1:获取各批次作业的配送方案 TR = {T DS Bi | Bi沂赘,r = i沂R},令 i = 1,啄 = 1,S J T L = 芰. Step2:计算坌j i啄沂Bi 的物料配送至线边空间的 时刻 T DF j i啄 = T DS Bi + t T + t L . Step3:若 S j i啄 L 疑S j i啄忆 L 屹芰 | 坌j i啄忆 沂Bi,S J T L 饮S J T L + S j i啄忆 L ,啄饮啄 + 1. Step4:若 啄忆 = | Bi | ,转 Step5,否则转 Step3. Step5:令 i忆 = i + 1,若 i忆 > | 赘 | ,转 Step7,若 [T DF j i啄 ,T F j i啄 ] 疑[ T DF j i忆啄忆 ,T F j i忆啄忆 ] 屹芰且 S j i啄 L 疑S j i忆啄忆 L 屹芰 | 坌 j i忆啄忆沂Bi忆,S J T L 饮S J T L + S j i忆啄忆 L ,啄忆饮啄忆 + 1,转 Step6. Step6:若 啄忆 > | Bi忆 | ,转 Step7,否则转 Step5. Step7:计算 S J T L 中所有组合的有效集中度,选择 有效存储集中度最大的作业物料存放位置组合 C J T L , 将作业 j i啄的物料存放在 C J T L 所决策的线边位置内,并执 行基于物料存储时长的动态调整算法(2郾 4 节). Step8:i饮i + 1,若 i > | 赘 | ,转 Step9,否则转 Step2. Step9:获取所有作业的物料在线边网络 N( l, cl)的存储方案 S L J ,算法结束. 2郾 4 基于物料存储时长的动态调整算法 对于任一线边空间单元 l,若作业 j 的物料被安 排存入该线边单元内,可能存在线边总容量充足但 不连续导致物料无法存放的情况. 针对这类情况, 本文提出了基于物料存储时长的动态调整算法,该 算法的目的是通过局部调整其他并行装配作业的物 料存放位置,最大化线边空间的利用率,保证在单位 线边总容量充足时,装配作业所需的物料有合适的 空间存放. 该算法主要通过调整存储时长较长的作 业所需物料至线边空间两侧获取较大的连续存储空 间,图 7 对该算法机理进行了说明. cl 表示线边空 间 l 内的存储单元,对于作业 7 所需物料 vj = 7 = 4,其 在线边的存放时间为 t = [7,10],该时间段内剩余 可用线边单元为 cl = 1,2,3,6,最大线边空间容量 ·114·
胡鑫铭等：飞机移动生产线物料配送与线边存储集成优化 ·115· 1C|=4,但由于线边空间单元不连续无法存储，以 输出结果（图7(b).由于飞机移动生产线中存在 当前物料在线边的存储方案（图7(a))作为算法的 大量的并行装配作业，因此通过该算法对物料的存 输入条件，通过调整其他物料的存储位置，将物料存 储位置进行优化可以有效提高线边空间的利用率， 储时长较长的物料分别移至两侧的线边单元，使得 解决由于线边空间规划不合理导致装配物料无法在 作业7的物料获得充足的空间存放，即获得算法的 线边存放产生的装配延期问题 7 7 6 5 2 5 4 6 2 2 12345678910 123456789101 (a) (b) 图7基于物料存储时长的动态调整算法机理.(a)调整前物料存储方案：()调整后物料存储方案 Fig.7 Dynamic adjusting mechanism based on material storage time:(a)storage solution before adjustment;(b)storage solution after adjustment 给出如下符号定义： 结束 S9表示已完成调整的作业集合，S,-r表示除集 3数值实验 合J'外的作业集合，S9-y表示物料存储位置与作业 集合J'物料存储位置重叠的作业集合，S。表示已完 本文以文献[13]的项目拆分调度结果为基础 成调整的作业集合J所占线边单元集合，P=1表 数据，并根据MDSP-AMAL问题的特点对每个大工 示将作业j的物料存放在线边单元c,内. 位内作业数量分别为30、45、60、120、480、840和 动态调整算法的具体步骤如下： 1200共7类规模的数据进行了扩充.为算例中的每 Stepl:输入当前线边空间的存放方案S8,计算 个作业j随机生成∈(1,8)的装配位置和，∈(5， t∈[T,T]内线边I的最大剩余容量max{ICI}. 10)的物料需求量，并设定飞机移动速度V=0.5,单 Step2:如果max{ICiI}≥U;,转Step3,否则转 位线边空间容量山=20，多载量小车数量0=3，运 Step9. 载能力上限C,=20,物料可占用左右两侧各1个单 Step3:对于Vc,且Ht∈[T,T],若p=1且 位的线边空间.本文在VS2010平台通过C#语言进 p=1,i∈S,-,则S9←S9+i. 行编程测试，并将得到的结果与通过CPLEX软件 Step4:将S中的作业按物料存储时间降序排 (版本12.7.1)求解的结果进行对比，实验平台为主 列，按序分别移至线边空间1的上下两侧单元S内， 频3.6GHz,内存8GB,Intel(R)Core(TM)i7- S←S-s9 4790KCPU的台式计算机. 3.1与CPLEX结果对比 Step5:令s9←-s9,s9=0 为了验证框架的启发式算法的精确性，将MD- Step6:i∈S9,对于Hc且Ht∈[T,T],若 SP-AMAL问题(P)的松弛问题(Pat)通过CPLEX p4=1且p=1,Hi∈S,-S,则SP←-S9+i'. 软件进行求解，可以得到原问题解的低界，其中松弛 Step7:将S中的作业按物料存储时间降序排 问题与原问题的区别为要求任一作业所需物料必须 列，按序分别移至线边空间l的上下两侧单元S内， 存放在同一线边单元l∈[-m,+m]内但允许 S%-S%-S9 其在！内不连续存放.将求得的低界LB。与框架的 Step8:若Hi∈SY或对于Vc(且Ht∈[T,T] 启发式算法得到的结果进行对比.由于CPLEX不 时i'=☑，转Stepl0,若1Sl<lS,l,转Step9,否则更 适用于求解大规模算例，因此表1给出了作业规模 新集合Sy←-S+S,S9←-Sr,转Step6. 分别为30、45、60各10组不同算例的求解结果. Step9:引入惩罚函数P(A),转Step10. CPLEX栏中数据，如12/278.42分别表示CPLEX求 Step10:更新C并输出调整后的结果Sg,算法 得的松弛问题精确解IRl(CPE(即原问题低界)和
胡鑫铭等: 飞机移动生产线物料配送与线边存储集成优化 | Cleft | = 4,但由于线边空间单元不连续无法存储,以 当前物料在线边的存储方案(图 7(a))作为算法的 输入条件,通过调整其他物料的存储位置,将物料存 储时长较长的物料分别移至两侧的线边单元,使得 作业 7 的物料获得充足的空间存放,即获得算法的 输出结果(图 7( b)). 由于飞机移动生产线中存在 大量的并行装配作业,因此通过该算法对物料的存 储位置进行优化可以有效提高线边空间的利用率, 解决由于线边空间规划不合理导致装配物料无法在 线边存放产生的装配延期问题. 图 7 基于物料存储时长的动态调整算法机理. (a)调整前物料存储方案;(b)调整后物料存储方案 Fig. 7 Dynamic adjusting mechanism based on material storage time:(a) storage solution before adjustment; (b) storage solution after adjustment 给出如下符号定义: S D J 表示已完成调整的作业集合,SJ - J忆表示除集 合 J忆外的作业集合,S O J - J忆表示物料存储位置与作业 集合 J忆物料存储位置重叠的作业集合,S O cl表示已完 成调整的作业集合 J 所占线边单元集合,p cl j = 1 表 示将作业 j 的物料存放在线边单元 cl 内. 动态调整算法的具体步骤如下: Step1:输入当前线边空间的存放方案 S O cl ,计算 t沂[T DF j ,T F j ]内线边 l 的最大剩余容量 max { |C t left |}. Step2:如果 max { | C t left | }逸vj,转 Step3,否则转 Step9. Step3:对于坌cl 且坌t沂[T DF j ,T F j ],若 p cl j = 1 且 p cl i = 1,坌i沂SJ - j,则 S O j 饮S O j + i. Step4:将 S O j 中的作业按物料存储时间降序排 列,按序分别移至线边空间 l 的上下两侧单元 S忆cl内, S忆cl饮S忆cl - S O cl . Step5:令 S O I 饮S O j ,S O I忆 = 芰. Step6:坌i沂S O I ,对于坌c忆l 且坌t沂[ T DF i ,T F i ],若 p c忆 l i = 1 且 p c忆 l i忆 = 1,坌i忆沂SJ - S D J ,则 S O I忆饮S O I忆 + i忆. Step7:将 S O I忆中的作业按物料存储时间降序排 列,按序分别移至线边空间 l 的上下两侧单元 S忆cl内, S忆cl饮S忆cl - S O cl . Step8:若坌i沂S D I 或对于坌c忆l 且坌t沂[T DF i ,T F i ] 时 i忆 = 芰,转 Step10,若| S忆cl | < | SI | ,转 Step9,否则更 新集合 S D J 饮S D J + SI,S O I 饮SI忆,转 Step6. Step9:引入惩罚函数 P(撰),转 Step10. Step10:更新 C t left并输出调整后的结果 S O忆 cl ,算法 结束. 3 数值实验 本文以文献[13] 的项目拆分调度结果为基础 数据,并根据 IMDSP鄄鄄AMAL 问题的特点对每个大工 位内作业数量分别为 30、45、60、120、480、840 和 1200 共 7 类规模的数据进行了扩充. 为算例中的每 个作业 j 随机生成 l j沂(1,8)的装配位置和 vj沂(5, 10)的物料需求量,并设定飞机移动速度 V = 0郾 5,单 位线边空间容量 鬃 = 20,多载量小车数量 w = 3,运 载能力上限 CV = 20,物料可占用左右两侧各 1 个单 位的线边空间. 本文在 VS2010 平台通过 C#语言进 行编程测试,并将得到的结果与通过 CPLEX 软件 (版本 12郾 7郾 1)求解的结果进行对比,实验平台为主 频 3郾 6 GHz, 内存 8 GB, Intel ( R) Core ( TM) i7鄄鄄 4790K CPU 的台式计算机. 3郾 1 与 CPLEX 结果对比 为了验证框架的启发式算法的精确性,将 IMD鄄 SP鄄鄄AMAL 问题(P)的松弛问题(PSlack )通过 CPLEX 软件进行求解,可以得到原问题解的低界,其中松弛 问题与原问题的区别为要求任一作业所需物料必须 存放在同一线边单元 l沂[l M j - m,l M j + m]内但允许 其在 l 内不连续存放. 将求得的低界 LBP 与框架的 启发式算法得到的结果进行对比. 由于 CPLEX 不 适用于求解大规模算例,因此表 1 给出了作业规模 分别为 30、45、60 各 10 组不同算例的求解结果. CPLEX 栏中数据,如 12 / 278郾 42 分别表示 CPLEX 求 得的松弛问题精确解 | R | (CPLEX) (即原问题低界) 和 ·115·
·116. 工程科学学报，第40卷，第1期 CPU时间（单位为s),LB=24/一表示CPLEX在可 值.表中DIF和GAP分别表示框架的启发式算法 接受时间(36000s)内无法求出松弛问题可行解，记 得到的小车出行趟数与CPLEX求得原问题下界 录其低界值LB=24:启发式算法栏中数据，如12/ LB。的差值与偏差百分比，计算公式为DIF= 0.44分别表示启发式算法得到的解1RI(BD和CPU IRI (HBEI)-IRI (CHLEX)GAP = IRI (HBED)IRI (CHLEX)x 时间（单位为s):DIF/GAP栏带“*”表示CPLEX IRI (CPEX) 得不到松弛问题可行解时用低界计算DIF和GAP 100%. 表1小规模算例数值实验结果 Table 1 Numerical experiment results of small-scale examples 30job 45job 60job 算例 LBp LBp LBp P(HBEI) DIF/GAP P(HBEI) DIF/GAP P(HBEI) DIF/GAP (CPLEX) (CPLEX) (CPLEX) 12/278.42 12/0.44 0/0.00% 18/6140 19/1.22 1/5.56% 24/19607 26/1.89 2/8.33% 13/242.07 14/0.72 17.69% 19/2361 20/1.43 1/5.26% 24/34972 25/2.11 1/4.17% 3 11/302.73 12/0.98 1/9.09% 18/3748 19/1.24 1/5.26% 22/9927 24/1.88 2/9.09% 12/60.80 12/0.54 0/0.00% 19/2894 21/1.45 2/10.53% 25/25804 27/1.97 2/8.00% 12/299.35 13/0.47 1/8.33% 19/9126 20/1.32 1/5.26% 25/17323 26/1.99 1/4.00% 14/450.43 14/0.63 0/0.00% 17/847 17/1.32 0/0.00% LB=24/- 27/2.21 3/12.50%* 7 12/276.01 13/0.52 1/8.33% 17/2634 18/1.25 1/5.88% 25/31229 26/1.89 1/4.00% 13/284.44 13/0.48 0/0.00% 20/4570 22/1.19 2/10.00% 23/25631 26/2.00 3/13.04% 9 13/172.89 14/0.88 1/7.69% 18/3786 20/1.27 2/11.11% 23/22454 24/2.03 1/4.35% 10 12/344.45 13/0.83 1/8.33% 19/5354 20/1.46 1/5.26% 23/19172 24/1.96 1/4.35% AVG 12.4/271.1613.0/0.650.6/4.84%18.4/414619.6/1.321.2/6.52%23.78/2290225.5/1.991.56/6.59% 通过与CPLEX求解原问题的松弛问题(Ps4) 时间升序排列并编号，然后从编号最小的物料按序 得到的结果进行对比可以发现在小规模问题中，框 开始装载直至第一趟车达到装载量上限，然后将剩 架的启发式算法具有较好的求解精度.当作业规模 余物料继续按编号装人第二趟车至第二趟车达到装 为30、45和60时，与Ps4的精确解偏差百分数均 载量上限，依次直至所以物料组批完成.H-SBP表 值分别为4.84%、6.52%和6.59%，说明原问题 示线边物料摆放时采用顺序存储算法，该算法根据 (P)中框架的启发式算法得到的解与精确解的偏差 物料先送先存(first come first store,FCFS)的原则， 不会超过上述百分数，证明了框架的启发式算法的 为送至线边的物料按序优先配置相应的存放空间. 有效性.随着作业规模增加，CPLEX对问题求解的 在其余条件相同情况下，将上述三种算法的解与本 时间迅速上升，在60job作业规模下，平均计算时间 文设计的框架的启发式算法得到的小车出行次数结 达到了22902s,甚至无法在可接受时间内得到理想 果进行对比，数值实验结果如表2和图8(a)所示， 的低界.而框架的启发式算法不仅能在较短时间内 表2中R表示各个数据规模下30组算例得到的可 得到优质解，且求解时间稳定，说明框架的启发式算 行解的结果均值，DIF和GAP分别表示不同算法得 法在求解时间上也具有巨大的优势 到工期结果的差值和偏差百分数，P-S表示其他三 3.2大规模数据算法效果对比 种算法在30组测试算例下得到的不可行解百分比， 为了测试本文提出的算法在大规模数据求解中 计算公式为不可行解算例数ns与总算例数ns的比 的效果，选取作业规模为120、480、840和1200各30 值.同时，为了验证本文使用的基于内分泌调节机 组算例，并为每组算例增加三类对比实验，对比算法 制的免疫算法框架的有效性，增加了与其他文献设 的构建方式为分别用三种传统的启发式规则替换框 计的人工智能算法的对比实验，主要包括传统的人 架的启发式算法中的相应部分.R-NMO表示作业 工免疫算法(artificial immune algorithm,AIA)和参 物料只能存放在摆放中心位置不允许占用两侧线边 考文献[7]采用的人工蜂群算法(artificial bee colo- 空间规则.MBS-SS表示基于作业开始时间顺序的 y,ABC).特别说明，由于上述文献的算法在物料 最小批量规则，该规则先将作业物料按照需求开始 配送问题的应用中没有考虑物料在装配线边的存储
工程科学学报,第 40 卷,第 1 期 CPU 时间(单位为 s),LB = 24 / —表示 CPLEX 在可 接受时间(36000 s)内无法求出松弛问题可行解,记 录其低界值 LB = 24;启发式算法栏中数据,如 12 / 0郾 44 分别表示启发式算法得到的解| R | (HBEI)和 CPU 时间(单位为 s);DIF / GAP 栏带“*冶 表示 CPLEX 得不到松弛问题可行解时用低界计算 DIF 和 GAP 值. 表中 DIF 和 GAP 分别表示框架的启发式算法 得到的小车出行趟数与 CPLEX 求得原问题下界 LBP 的 差 值 与 偏 差 百 分 比, 计 算 公 式 为 DIF = |R| (HBEI) - |R| (CPLEX) 和 GAP = |R| (HBEI) - |R| (CPLEX) |R| (CPLEX) 伊 100%. 表 1 小规模算例数值实验结果 Table 1 Numerical experiment results of small鄄scale examples 算例 30job 45job 60job LBP (CPLEX) P(HBEI) DIF / GAP LBP (CPLEX) P(HBEI) DIF / GAP LBP (CPLEX) P(HBEI) DIF / GAP 1 12 / 278郾 42 12 / 0郾 44 0 / 0郾 00% 18 / 6140 19 / 1郾 22 1 / 5郾 56% 24 / 19607 26 / 1郾 89 2 / 8郾 33% 2 13 / 242郾 07 14 / 0郾 72 1 / 7郾 69% 19 / 2361 20 / 1郾 43 1 / 5郾 26% 24 / 34972 25 / 2郾 11 1 / 4郾 17% 3 11 / 302郾 73 12 / 0郾 98 1 / 9郾 09% 18 / 3748 19 / 1郾 24 1 / 5郾 26% 22 / 9927 24 / 1郾 88 2 / 9郾 09% 4 12 / 60郾 80 12 / 0郾 54 0 / 0郾 00% 19 / 2894 21 / 1郾 45 2 / 10郾 53% 25 / 25804 27 / 1郾 97 2 / 8郾 00% 5 12 / 299郾 35 13 / 0郾 47 1 / 8郾 33% 19 / 9126 20 / 1郾 32 1 / 5郾 26% 25 / 17323 26 / 1郾 99 1 / 4郾 00% 6 14 / 450郾 43 14 / 0郾 63 0 / 0郾 00% 17 / 847 17 / 1郾 32 0 / 0郾 00% LB = 24 / — 27 / 2郾 21 3 / 12郾 50% * 7 12 / 276郾 01 13 / 0郾 52 1 / 8郾 33% 17 / 2634 18 / 1郾 25 1 / 5郾 88% 25 / 31229 26 / 1郾 89 1 / 4郾 00% 8 13 / 284郾 44 13 / 0郾 48 0 / 0郾 00% 20 / 4570 22 / 1郾 19 2 / 10郾 00% 23 / 25631 26 / 2郾 00 3 / 13郾 04% 9 13 / 172郾 89 14 / 0郾 88 1 / 7郾 69% 18 / 3786 20 / 1郾 27 2 / 11郾 11% 23 / 22454 24 / 2郾 03 1 / 4郾 35% 10 12 / 344郾 45 13 / 0郾 83 1 / 8郾 33% 19 / 5354 20 / 1郾 46 1 / 5郾 26% 23 / 19172 24 / 1郾 96 1 / 4郾 35% AVG 12郾 4 / 271郾 16 13郾 0 / 0郾 65 0郾 6 / 4郾 84% 18郾 4 / 4146 19郾 6 / 1郾 32 1郾 2 / 6郾 52% 23郾 78 / 22902 25郾 5 / 1郾 99 1郾 56 / 6郾 59% 通过与 CPLEX 求解原问题的松弛问题(PSlack ) 得到的结果进行对比可以发现在小规模问题中,框 架的启发式算法具有较好的求解精度. 当作业规模 为 30、45 和 60 时,与 PSlack的精确解偏差百分数均 值分别为 4郾 84% 、6郾 52% 和 6郾 59% , 说明原问题 (P)中框架的启发式算法得到的解与精确解的偏差 不会超过上述百分数,证明了框架的启发式算法的 有效性. 随着作业规模增加,CPLEX 对问题求解的 时间迅速上升,在 60job 作业规模下,平均计算时间 达到了 22902 s,甚至无法在可接受时间内得到理想 的低界. 而框架的启发式算法不仅能在较短时间内 得到优质解,且求解时间稳定,说明框架的启发式算 法在求解时间上也具有巨大的优势. 3郾 2 大规模数据算法效果对比 为了测试本文提出的算法在大规模数据求解中 的效果,选取作业规模为 120、480、840 和 1200 各 30 组算例,并为每组算例增加三类对比实验,对比算法 的构建方式为分别用三种传统的启发式规则替换框 架的启发式算法中的相应部分. R鄄鄄 NMO 表示作业 物料只能存放在摆放中心位置不允许占用两侧线边 空间规则. MBS鄄鄄 SS 表示基于作业开始时间顺序的 最小批量规则,该规则先将作业物料按照需求开始 时间升序排列并编号,然后从编号最小的物料按序 开始装载直至第一趟车达到装载量上限,然后将剩 余物料继续按编号装入第二趟车至第二趟车达到装 载量上限,依次直至所以物料组批完成. H鄄鄄 SBP 表 示线边物料摆放时采用顺序存储算法,该算法根据 物料先送先存(first come first store, FCFS)的原则, 为送至线边的物料按序优先配置相应的存放空间. 在其余条件相同情况下,将上述三种算法的解与本 文设计的框架的启发式算法得到的小车出行次数结 果进行对比,数值实验结果如表 2 和图 8( a)所示, 表 2 中 R 表示各个数据规模下 30 组算例得到的可 行解的结果均值,DIF 和 GAP 分别表示不同算法得 到工期结果的差值和偏差百分数,P鄄鄄IS 表示其他三 种算法在 30 组测试算例下得到的不可行解百分比, 计算公式为不可行解算例数 nIS与总算例数 nS 的比 值. 同时,为了验证本文使用的基于内分泌调节机 制的免疫算法框架的有效性,增加了与其他文献设 计的人工智能算法的对比实验,主要包括传统的人 工免疫算法( artificial immune algorithm, AIA) 和参 考文献[7]采用的人工蜂群算法( artificial bee colo鄄 ny, ABC). 特别说明,由于上述文献的算法在物料 配送问题的应用中没有考虑物料在装配线边的存储 ·116·
胡鑫铭等：飞机移动生产线物料配送与线边存储集成优化 ·117· 决策，因此均采用本文设计的物料存储前瞻算法作 为1200时的小车平均出行趟数收敛曲线，三类算法 为解码算法.图8(b)为三类智能算法在作业规模 均以MBS-SS规则得到的解作为初始解. 表2不同算法结果对比 Table 2 Comparison of different algorithms IRI DIF/GAP/P-IS 作业 R-NMO MBS-SS H-SBP HBEI R-NMO MBS-SS H-SBP 规模 (A) (B) (C) (D) A-D A-D ns - C-Dns D ns C-D D ns 120 61.83 60.53 63.27 57.36 4.47/7.79%/23.33% 3.17/5.53%/3.33% 5.91/10.03%/20.00% 480 226.03 227.90 232.25 216.95 9.08/4.19%/36.67% 10.95/5.05%/6.67% 15.30/7.05%/33.33% 840 386.51 384.75 386.81 367.69 18.82/5.12%/46.67% 17.06/4.64%/13.33% 19.12/5.20%/46.67% 1200 533.88 502.90 509.50 488.80 45.08/9.22%/60.00% 21.10/4.32%/10.00% 23.70/4.85%/66.67% 对上述数值实验结果分析可以得出以下结论： 线边空间的分配与使用上有巨大优势.当作业规模 (1)本文设计的框架的启发式算法相比于物料 为1200时，一个配送周期内H-SBP算法平均多产 不能占用两侧线边空间的规则有效提升了线边空间 生了23.7次的小车出行成本，且算例的不可行解比 的利用率.在各作业规模下框架的启发式算法得到 例达到了66.67%，说明前瞻算法在飞机移动生产 小车出行趟数相比于R-NMO规则得到的结果优化 线这类存在多并行作业的物料存放位置决策中具有 比例都能达到或接近5%，当作业规模为1200时平 优越性 均优化比例可以达到9.22% (4)通过图8(b)可以看出本文使用的基于内 (2)框架的启发式算法在各个规模问题下得到 分泌调节机制的免疫算法在求解时间和求解质量上 的结果都优于MBS-SS算法得到的结果.当项目作 均具有一定的优越性.人工免疫算法与人工蜂群算 业规模为120、480、840和1200时，在其余条件相同 法在前期都具有较好的收敛性，但随着目标函数值 情况下，相比于MBS-SS算法所得小车出行趟数结 的下降，容易陷入局部最优，收敛速度下降.而框架 果的平均优化差值分别为3.17、10.95、17.06和 的启发式算法中引入变异概率随着目标均值下降逐 21.10,说明本文设计的基于内分泌调节机制的免疫 渐上升的机制能有效帮助其在迭代后期跳出局部最 算法在对作业配送批次的划分上相较于传统的经验 优，在更短的时间内搜索到更优质的解. 规则具有优势 3.3多元响应曲面分析 (3)对比框架的启发式算法和H-SBP算法得 为了探讨IMDSP-AMAL问题中各因素对小车 到的小车出行趟数和后者产生的不可行解百分数说 出行趟数的影响，选择了三类可能影响目标函数值 明框架的启发式算法中设计的物料存储前瞻算法在 的因素，包括小车运载能力C,(因素A),单位线边 580 (a) b 600 -R-NMO 一HBEI 8-1g-g5 -AIA 500 H-SBP 560 一ABC HBEI 400 P-ISR. 口P-Ses 300 □P-ISHs 四540 至200 520 100 70 500 20 48 120 480 840 1200 0 20406080100120140160 作业规模 迭代次数（作业规模=1200） 图8不同算法结果对比.(a)目标函数和不可行解百分数：(b)智能算法收敛曲线 Fig.8 Comparison of experimental results between different algorithms:(a)objective and percentage of infeasible solution;(b)convergence curve of intelligent algorithms
胡鑫铭等: 飞机移动生产线物料配送与线边存储集成优化 决策, 因此均采用本文设计的物料存储前瞻算法作 为解码算法. 图 8( b)为三类智能算法在作业规模 为 1200 时的小车平均出行趟数收敛曲线,三类算法 均以 MBS鄄鄄 SS 规则得到的解作为初始解. 表 2 不同算法结果对比 Table 2 Comparison of different algorithms 作业 规模 | R| DIF / GAP / P鄄鄄IS R鄄鄄NMO MBS鄄鄄 SS H鄄鄄 SBP HBEI R鄄鄄NMO MBS鄄鄄 SS H鄄鄄 SBP (A) (B) (C) (D) A - D A - D D nIS nS B - D B - D D nIS nS C - D C - D D nIS nS 120 61郾 83 60郾 53 63郾 27 57郾 36 4郾 47 / 7郾 79% / 23郾 33% 3郾 17 / 5郾 53% / 3郾 33% 5郾 91 / 10郾 03% / 20郾 00% 480 226郾 03 227郾 90 232郾 25 216郾 95 9郾 08 / 4郾 19% / 36郾 67% 10郾 95 / 5郾 05% / 6郾 67% 15郾 30 / 7郾 05% / 33郾 33% 840 386郾 51 384郾 75 386郾 81 367郾 69 18郾 82 / 5郾 12% / 46郾 67% 17郾 06 / 4郾 64% / 13郾 33% 19郾 12 / 5郾 20% / 46郾 67% 1200 533郾 88 502郾 90 509郾 50 488郾 80 45郾 08 / 9郾 22% / 60郾 00% 21郾 10 / 4郾 32% / 10郾 00% 23郾 70 / 4郾 85% / 66郾 67% 对上述数值实验结果分析可以得出以下结论: (1)本文设计的框架的启发式算法相比于物料 不能占用两侧线边空间的规则有效提升了线边空间 的利用率. 在各作业规模下框架的启发式算法得到 小车出行趟数相比于 R鄄鄄NMO 规则得到的结果优化 比例都能达到或接近 5% ,当作业规模为 1200 时平 均优化比例可以达到 9郾 22% . 图 8 不同算法结果对比. (a)目标函数和不可行解百分数;(b)智能算法收敛曲线 Fig. 8 Comparison of experimental results between different algorithms: (a) objective and percentage of infeasible solution; (b) convergence curve of intelligent algorithms (2)框架的启发式算法在各个规模问题下得到 的结果都优于 MBS鄄鄄 SS 算法得到的结果. 当项目作 业规模为 120、480、840 和 1200 时,在其余条件相同 情况下,相比于 MBS鄄鄄 SS 算法所得小车出行趟数结 果的平均优化差值分别为 3郾 17、10郾 95、17郾 06 和 21郾 10,说明本文设计的基于内分泌调节机制的免疫 算法在对作业配送批次的划分上相较于传统的经验 规则具有优势. (3)对比框架的启发式算法和 H鄄鄄 SBP 算法得 到的小车出行趟数和后者产生的不可行解百分数说 明框架的启发式算法中设计的物料存储前瞻算法在 线边空间的分配与使用上有巨大优势. 当作业规模 为 1200 时,一个配送周期内 H鄄鄄 SBP 算法平均多产 生了 23郾 7 次的小车出行成本,且算例的不可行解比 例达到了 66郾 67% ,说明前瞻算法在飞机移动生产 线这类存在多并行作业的物料存放位置决策中具有 优越性. (4)通过图 8( b)可以看出本文使用的基于内 分泌调节机制的免疫算法在求解时间和求解质量上 均具有一定的优越性. 人工免疫算法与人工蜂群算 法在前期都具有较好的收敛性,但随着目标函数值 的下降,容易陷入局部最优,收敛速度下降. 而框架 的启发式算法中引入变异概率随着目标均值下降逐 渐上升的机制能有效帮助其在迭代后期跳出局部最 优,在更短的时间内搜索到更优质的解. 3郾 3 多元响应曲面分析 为了探讨 IMDSP鄄鄄 AMAL 问题中各因素对小车 出行趟数的影响,选择了三类可能影响目标函数值 的因素,包括小车运载能力 CV (因素 A),单位线边 ·117·