Maravelias和Sung[1]分析整理了集成调度规划的建模方法,模型主要分为4类:①详尽规划模型,模型以子模型描述资源和产品费用的约束,可以直接用于调度的规划; ②松弛与聚合规划模型,大型混合整数问题不能直接求解,需要一定的近似,通过移除部分约束或将一些原始模型的决策进行聚合可以实现问题的求解; ③离线代理模型,模型通过集中计算可行域的约束和仅与产品目标相关的产品费用,避免了约束集成之后的计算; ④混合模型,模型在计算量和准确度之间进行了折衷,模型的前段使用详尽规划模型,后段使用松弛或代理模型。Henriques[2]研究了一种用于过程和产品规划的参数优化模型,模型同时考虑了与技术相关的约束和各服务站基于可支配时间的底层约束。研究结果表明生产率应该限制在最小成本率和最大生产率之间。Sung和Maravelias[3]开发了基于完整调度模型的离线方法,该方法可以用于总生产成本的估计。Erdirik-Dogan和Grossmann[4]提出了基于两级并行方法的规划模型,模型考虑了旅行商问题(Traveling Salesman Problem, TSP)约束。Wan等[5]借助仿真手段提出优化方法对供应链关系进行了分析。该方法由代理模型迭代结构组成,可以分析关键决定变量和供应链表现间的关系。Erdirik-Dogan和Grossmann[6]研究了连续多产品单加工单元厂房的计划和调度,给出了基于连续时间的混合集成线性优化模型。考虑到水平规划的长度增加将导致的计算时间增加,模型中引入了分解算法。Wu和Ierapetritou[7]研究了不确定条件下的生产计划与调度集成优化分层方法。Yan和Zhang[8]研究了三级制造系统的生产计划与调度集成优化模型,采用基于遗传进化的启发式算法对模型进行了求解。路致远等[9]根据车间和库房的实际情况研究了冲压件成批生产车间生产计划和调度的集成优化问题,提出了一种非线性混合整数规划模型,并给出了基于混合遗传算法的模型求解方法。尚文利和范玉顺[10]考虑调度约束,建立了生产计划与调度集成优化模型用于解决多品种批量生产问题。陈琳等[11]针对汽车装配,提出了车间生产计划和调度的优化方法,采用启发式方法来求解。
规划和调度模型的求解方法较多,大致可以分为两类:
1)?逐步分解,将模型进一步的划分为多个层次,之后自顶向下求解[12-13]。逐步分解可以有效地求解大型复杂计划问题,但由于没有考虑具体的能力约束,使得模型的可行性受到了一定的制约。
2)?集成优化,根据不同层次约束条件的分析建立整体优化模型。
模型求解有2种方法:整体法[14-15]同时考虑不同层次的决策和约束,避免了逐步分解求解得不到可行解的缺点,但是牺牲了一定的计算效率;此外还有集成法[16-17],在求解中参考逐步分解的思想,首先分层求解,之后调整计划,反复形成闭环。采用集成的方法可以兼顾整体法和逐步分解的优点。
飞机装配过程复杂,涉及的部门和环节多,制定装配生产计划十分必要。但同时影响工作进度的原因又较多,需要根据当前的状况对资源和计划进行实时调整。本文考虑多级制造和飞机装配的特点,提出飞机装配生产规划和调度集成优化方法,为飞机装配生产线规划提供理论参考。
1 飞机装配生产规划 飞机装配包括组件装配、部件装配及总装几个阶段,从工作流程和体系结构上分析,装配生产过程也属于多级制造过程。考虑多级制造系统的特点,飞机装配系统需要平衡各阶段的生产装配节拍,减少下层装配系统的库存和上层装配系统的等待时间,保证设备和人员工作的连续性。
1)?通过对前M-1级制造系统产品最大完工时间的约束实现生产时间的控制,缩短整体生产周期。
(1) |
式中:M为装配系统总级数,飞机装配从总体上分析分为3级,但在组件和部件装配中存在着更为复杂的装配件关系,级数划分应以装配流程为参照;N(m)为第m级并行子系统数,在飞机装配系统的分析中,指可以同时进行,没有相互制约影响的系统数,需根据装配加工对象和工艺流程确定;ttime(m, n)为第m级制造系统第n个并行子系统的生产产品类型总数;W(m, n, v)为第m级制造系统的第n个并行子系统加工装配的第v种产品的生产计划周期数;e(m, n, v, h)为第m级制造系统第n个并行子系统加工装配的第v种产品在第h个生产周期完工时间的调整系数。产品在首次加工装配时,可能存在的问题会集中暴露出来,同时工人的熟练度也较低,该调整系数较高,随着加工批次的增加,返工等情况减少,加工熟练度也有所提高,该系数相应降低;s(m, n, v, h)为第m级制造系统第n个并行子系统加工装配的第v种产品在第h个生产周期的最大完工时间; χ(m, n, v, h)为第m级制造系统第n个并行子系统加工装配的第v种产品在第h个生产周期的完工费用系数[18]。
2)?由于装配制造系统中底层系统库存容易积累,造成牛鞭效应,应尽量减少前M-1级制造系统的库存量。
(2) |
式中:c(m, n, v, h)为第m级制造系统第n个并行子系统加工装配的第v种零件在第h个生产周期的单件储存费用,不同装配件的储存方法和储存费用不同,对于一些易腐蚀易变性的装配件还存在较大的保养维护费用,因而需要根据具体的存储情况确定费用;u(m, n, v, h)为零件v在第m级制造系统第n个并行子系统第h个生产周期的库存量。
3)?缺货会导致之后的工作不能及时进行使得费用增加,加班可以在一定程度上缓解缺货造成的问题,但也会增加加班的费用,因而需要考虑将系统缺货费用和加班费用之和降低。
(3) |
为了避免上级系统加工装配过多的零组件,需要对超出要求数量的零件数进行惩罚,设置cex(m, n, v, h)为对第m级装配系统第n个并行子系统第v种零件第h个生产周期的惩罚费用;相应地,uex(m, n, v, h)为该零件在第h个生产周期超出要求的数量;通常缺货造成的装配效率下降更大,故需要设置缺货的惩罚系数clw(m, n, v, h)以表征第m级装配系统第n个并行子系统第v种零件第h个生产周期不满足需求部分的单件惩罚数,相应地ulw(m, n, v, h)为第m级制造系统第n个并行子系统第v种零件第h个生产周期的欠产数量。
将上述费用综合考虑,建立目标函数
(4) |
通过对式(4)的求解即可完成飞机装配生产规划。
2 装配调度集成优化 飞机装配耗时长,流程复杂,影响因素多,生产计划的规划对于宏观计划和指令的制定十分必要。但在具体装配生产中,由于受到各过程进度、各外因作用包括政策要求等实时信息的影响,总体计划框架往往不能完全贯彻执行,需要根据具体生产情况对设备、人员等资源进行安排调整。为了保证调整的合理性,需要根据具体装配作业的特征进行调度集成优化。
合理分配飞机装配过程中各种资源占用的时间,以提高装配生产效率是装配调度集成优化的目标。飞机装配过程中,有些装备和人员需要为多个加工过程提供服务,由于加工过程之间存在相互作用关系,各过程的需求不宜或者不能同时满足,故需进行合理调度。随着生产的进行,这种关系还在不断变化,形成了一个动态的调度问题,因而要不断对计划进行调整。
对于批量生产而言,随着批次的增加,外界的影响因素将逐渐稳定,人员操作逐渐熟练,效率逐渐提高。装配作业调度的主要问题是如何提高人员和设备资源的利用率。批量调度可近似地视为一个平行顺次作业的调度问题。
为了便于分析,需要对装配批量调度问题进行抽象:设存在装配单元A,装配现场需要对p个架次的飞机进行装配加工,装配序列T={t1, t2, …, tn}。作业序列要分别经过q个资源服务站(Resource Service Station,RSS)才能完成装配任务。设装配资源服务站为RSSi∈RSS,资源服务站包括设备及人员,每个服务站包含ci个服务单元。批量调度目标要使装配作业的工作周期最短。批量调度要为每项装配作业寻找最合适的资源调配路径。当服务站的服务单元只有1项,即RRSi的ci=1时,需要使用该服务单元的工作就需要等待,在单元空闲之后才能进行操作;当服务站的服务单元不只1项,即ci>1时,则工作可以在服务单元中进行挑选,选择空闲的单元完成加工操作。
经分析可知,装配作业的路径可以以箭线和节点的方式进行简化。建立箭线模型G={N, U, D},以节点序列N表示资源服务的范围,U表示包含的资源服务,D表示周期,箭线表示服务间的关系。如图 1所示使用箭线式结构图可以明确地表达装配现场资源的获取过程,其中u表示资源服务单元。
图 1 箭线式资源服务站结构图 Fig. 1 Activity on arrow (AOA) network diagram of service station of resources |
图选项 |
由于工人工作熟练度的增加和工艺的完善,飞机装配的工作周期将随着批次的增加而有所降低。若设E={e1, e2, …, eci}为服务单元的工作批次,以如下公式对装配周期进行描述[19]:
(5) |
式中:d(ri)为当前批次下资源服务单元ri的服务周期;α为首批作业的工时;β为变化曲线参数,根据经验,装配所需的工时将按照指数形式随批次数量的增加而逐渐降低,最终该数值将趋于稳定。
蚁群算法可以用于处理上面的调度问题。人工蚁在建立的构造图中运动,通过对人工蚁运动路径的分析,可以得到问题的解,即调度方案。参照p架次任务序列T构成的任务矩阵Tp=(tij)n×p和资源点网络模型建立装配批量调度过程构造图。用Gs=(C, L)表示构造图,其中的节点c0表示初始节点,用各节点ci∈C代表一个作业任务tij∈Tp,逻辑关系用L表示。
人工蚁的运动是随机的,其活动范围被限制在构造图中,运动受到一定的流水约束,如图 2所示。人工蚁最后得到的是一个路径π,经过函数φ(π)的映射处理可以得到调度方案的解。飞机装配是一连串工作的集合,为此可以将最后一项工作的结束时间作为调度目标。生产计划限制了可行域,因而需要对求得的解进行处理。
图 2 装配调度的构造示意图 Fig. 2 Schematic diagram of batch scheduling structure of assembly |
图选项 |
人工蚁随机运动过程受到一些因素的影响,包括构造图中其他边的能见度ηij和信息素轨迹的强度τij。边的能见度跟执行工作的逻辑关系和资源站服务单元的约束有关,直接决定可行路径的确定。基于阶段式资源服务站提出穿越方案,搜索沿纵向进行,人工蚁可以看到作业相关的边,即该边的能见度为1,非本服务站的工作能见度则为0。人工蚁纵向运动完成之后,tij∈RSSi的路径即被确定,随后人工蚁进行横向运动,按照构造图运动到下一个服务站。如此反复,直到所有的调度工作都完成。能见度定义了可行路径表,人工蚁记录任务节点,经过的节点将被移动到禁忌表中。
式(6)给出了第k只人工蚁从点ci到cj的运动规则:
(6) |
式中:q为随机数,取值范围为[0,1];q0比例可变,范围在[0,1]之间。人工蚁在运动过程中会积累信息,这种积累和启发式信息对于人工蚁的路径选择具有一定的作用,设置参数α和β以表征这种作用。第k只人工蚁t时刻在构造图中从任务节点ci运动到节点cj的概率用Pijk(t)表示;allowedk为人工蚁可选边的集合。人工蚁之前的选择和知识会对随机过程有一定的影响,因而其路径选择是一个双重决策的过程。q0表示路径选择受到知识的影响,q0越小,则随机性更强,收敛性越差,但是最优解的获取时间越短。
(7) |
人工蚁游走的路径长度通过解映射函数φ的转换得到最优解。人工蚁产生的路径经函数φ转化为装配周期,之后可以检测解是否接近目标函数。
资源的服务时间不等于资源的作业周期,当作业关系比较稳定时,服务单元的数量会对作业周期的长短造成较大的影响。单元数量多的时候,可以并行多个架次,周期相应缩短。而调度序列中任意两个作业间只存在理论上的时差。根据上述分析,规划装配作业周期映射的基本步骤如下。
步骤1??确定迭代后人工蚁最优路径图边序列:Lbest={l1, 2, l2, 3, …, l(n-1), n},及其对应的节点序列:Cbest={c1, c2, …, cn}。
步骤2??构建资源序列的箭线式网络模型G={N, U, D}。
步骤3??装配批量调度的起始时间Tstart,结束时间为Tend,且Tstart=Tend。
步骤4??初始化:将资源服务站和服务单元的起始工作时间TsRSSiTs(rij)均置为Tstart,将资源服务站和服务单元的最后工作结束时间TeRSSiTe(rij)均置为Tend。
步骤5??根据构造图路径更新装配作业的时间,流程如图 3所示。
图 3 装配作业时间更新流程图 Fig. 3 Flowchart of assembly time updating |
图选项 |
步骤6??最后输出装配作业周期的序列DLbesti=TeRRSi-TsRRSi
3 实例分析 以某型机襟副翼装配为实例。投产的数量为10架次,装配站的资源包括:骨架夹具2套、总装夹具2套、补铆夹具2套及检验夹具1套。襟副翼装配任务基本服从串行方式。优化结果如表 1所示,结果表明所提出的方法可以实现装配作业周期的优化。
表 1 襟副翼装配资源调度优化结果 Table 1 Optimization results of resource dispatch in flaperon assembly
工作 | 架次1 | 架次10 | |||
工期 | 资源 | 工期 | 资源 | ||
后腹板装配 | 10.00 | 骨架装配夹具A | 8.45 | 骨架装配夹具B | |
翼梁装配 | 8.00 | 骨架装配夹具A | 6.78 | 骨架装配夹具B | |
铆接骨架托板螺母 | 6.00 | 骨架装配夹具A | 5.07 | 骨架装配夹具B | |
装配下壁板 | 12.00 | 总装夹具B | 10.16 | 总装夹具A | |
装配上壁板 | 12.00 | 总装夹具B | 10.16 | 总装夹具A | |
补铆上下壁板 | 4.00 | 补铆夹具A | 3.39 | 补铆夹具B | |
安装尾部型材 | 15.00 | 补铆夹具A | 12.70 | 补铆夹具B | |
安装前肋 | 6.00 | 补铆夹具A | 5.10 | 补铆夹具B | |
检查外形、偏扭 | 3.00 | 检验夹具 | 2.41 | 检验夹具 |
表选项
4 结论 本文针对飞机装配过程,考虑装配工位数量、工位作业时间、物流和人力等因素的影响,提出了生产规划和调度集成优化方法,主要结论如下:
1)?飞机装配生产影响因素多,生产和资源调配计划的制定既要考虑静态的生产计划规划又要考虑受外因影响的动态调度。
2)?飞机装配是一个多级制造过程,制定合理的飞机装配生产规划即是对生产节拍、零件库存量及缺货加班费等条件所形成的规划问题进行求解。
3)?飞机装配调度是考虑了资源的动态问题。针对飞机装配作业周期与工人作业熟练程度有关的特点,建立了基于蚁群算法的装配调度规划模型。应用模型可以给出资源服务站及站内单元的调度方案。
参考文献
[1] | MARAVELIAS C T, SUNG C. Integration of production planning and scheduling:Overview, challenges and opportunities[J].Computers & Chemical Engineering, 2009, 33(12): 1919–1930. |
[2] | HENRIQUES E. Towards the integration of process and production planning:An optimization model for cutting parameters[J].International Journal of Advanced Manufacturing Technology, 2006, 28(1-2): 117–128.DOI:10.1007/s00170-004-2329-7 |
[3] | SUNG C, MARAVELIAS C T. An attainable region approach for production planning of multi-product processes[J].AIChE Journal, 2007, 53(5): 1298–1315.DOI:10.1002/(ISSN)1547-5905 |
[4] | ERDIRIK-DOGAN M, GROSSMANN I E. Planning models for parallel batch reactors with sequence-dependent changeovers[J].AIChE Journal, 2007, 53(9): 2284–2300.DOI:10.1002/(ISSN)1547-5905 |
[5] | WAN X, PEKNY J F, REKLAITIS G V. Simulation-based optimization with surrogate models-Application to supply chain management[J].Computers & Chemical Engineering, 2006, 29(6): 1317–1328. |
[6] | ERDIRIK-DOGAN M, GROSSMANN I E. A decomposition method for the simultaneous planning and scheduling of single-stage continuous multiproduct plants[J].Industrial and Engineering Chemistry Research, 2007, 45(1): 1–42. |
[7] | WU D, IERAPETRITOU M. Hierarchical approach for production planning and scheduling under uncertainty[J].Chemical Engineering and Processing:Process Intensification, 2007, 46(11): 1129–1140.DOI:10.1016/j.cep.2007.02.021 |
[8] | YAN H S, ZHANG X D. A case study on integrated production planning and scheduling in a three-stage manufacturing system[J].IEEE Transactions on Automation Science and Engineering, 2007, 4(1): 86–92.DOI:10.1109/TASE.2006.872107 |
[9] | 路致远, 严洪森, 沈境. 基于HGA的冲压车间生产计划与调度的集成优化[J].计算机技术与发展, 2007, 17(3): 179–182.LU Z Y, YAN H S, SHEN J. Integrated optimization of production planning and scheduling based on hybrid genetic algorithm[J].Computer Technology and Development, 2007, 17(3): 179–182.(in Chinese) |
[10] | 尚文利, 范玉顺. 成批生产计划调度的集成建模与优化[J].计算机集成制造系统, 2005, 11(12): 1663–1667.SHANG W L, FAN Y S. Integrated optimization modeling of production planning and scheduling for batch production[J].Computer Integrated Manufacturing Systems, 2005, 11(12): 1663–1667.(in Chinese) |
[11] | 陈琳, 严洪森, 刘通, 等. 汽车装配线生产计划与调度的集成优化方法[J].计算机技术与发展, 2009, 19(1): 134–138.CHEN L, YAN H S, LIU T, et al. Approaches to integrated optimization of production planning and scheduling on automobile assembly lines[J].Computer Technology and Development, 2009, 19(1): 134–138.(in Chinese) |
[12] | BOWERS M R, JARVIS J P. A hierarchical production planning and scheduling model[J].Decision Sciences, 1992, 23(1): 144–159.DOI:10.1111/deci.1992.23.issue-1 |
[13] | QIU M M, FREDENDALL L D, ZHU Z. Application of hierarchical production planning in a multiproduct multi machine environment[J].International Journal of Production Research, 2001, 39(13): 2803–2816.DOI:10.1080/00207540110052571 |
[14] | KARIMI B, FATEMI G. The capacitated lot sizing problem:A review of model algorithms[J].The International Journal of Management Science, 2003, 31(5): 365–378. |
[15] | 张晓东, 严洪森. 一类Job-Shop车间生产计划与调度的集成优化[J].控制与决策, 2003, 18(5): 581–584.ZHANG X D, YAN H S. Integrated optimization of production planning and scheduling for a kind of job shop[J].Control and Decision, 2003, 18(5): 581–584.(in Chinese) |
[16] | LASSERRE J B. An integrated model for job-shop planning and scheduling[J].Management Science, 1992, 38(8): 1201–1211.DOI:10.1287/mnsc.38.8.1201 |
[17] | 严洪森, 夏琦峰, 朱敏如, 等. 汽车装配车间生产计划与调度的同时优化方法[J].自动化学报, 2002, 28(6): 911–919.YAN H S, XIA Q F, ZHU M R, et al. Approaches to simultaneous production planning and scheduling in automobile assembly workshops[J].Acta Automatica Sinica, 2002, 28(6): 911–919.(in Chinese) |
[18] | 张晓东, 严洪森. 多级车间生产计划和调度的集成优化[J].机械工程学报, 2005, 41(9): 98–105.ZHANG X D, YAN H S. Production planning and scheduling of multi-stage workshop[J].Chinese Journal of Mechanical Engineering, 2005, 41(9): 98–105.DOI:10.3901/JME.2005.09.098(in Chinese) |
[19] | 陈志祥. 学习曲线及在工业生产运作研究中的应用综述[J].中国工程科学, 2007, 9(7): 82–88.CHEN Z X. Learning curve and its application in production operational research[J].Engineering Science, 2007, 9(7): 82–88.(in Chinese) |