工程科学学报，第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·