基于阻塞流理论的船舶建造中管件加工虚拟单元调度问题研究-韩文民.pdf
《基于阻塞流理论的船舶建造中管件加工虚拟单元调度问题研究-韩文民.pdf》由会员分享,可在线阅读,更多相关《基于阻塞流理论的船舶建造中管件加工虚拟单元调度问题研究-韩文民.pdf(12页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、57卷第3期(总第219期)2016年9月中 国 造 船SHIPBUILDING OF CHrNAV0157 No3(Serial No219)Sop2016文章编号:1000-4882(2016)03016412基于阻塞流理论的船舶建造中管件加工虚拟单元调度问题研究韩文民1,高龙龙1,翁红兵2,黄劲松1(1江苏科技大学经济管理学院,镇江212003;2沪东中华造船集团有限公司,上海200129)摘 要虚拟单元制造系统是适用于多品种小批量的生产组织模式,其在船舶建造中的应用有利于提高船舶建造的效率和柔性;但如果调度方案不当,容易引起交货期延迟的现象。鉴于船舶建造生产的特点,论文对船舶建造中虚拟
2、单元制造系统的调度问题进行了研究。以某船厂舾装作业中的管件加工为例,在对管系托盘中的管件聚类分析的基础上,采用阻塞浇理论,以设备与加工工序的分配和时间为约束,将调度问题转交为最小时间最大流问题。采用改进的预估时间增量算法求解管件族在不同工作地之间加工的最优路径。在生产任务既定的情况下,以完工周期最小化、设备最大负荷最小化、等待时间最小化为优化目标,构建了管件加工多目标优化模型,并采用免疫遗传算法求解。将求解结果与当前企业管件加工实际数据进行对比,并采用Witness软件对存在着多种动态因素的实际生产过程进行仿真,验证了方案的可行性及有效性,该方法对船舶建造中其他生产环节的生产组织亦具有参考和推
3、广意义。关 键 词:阻塞流;虚拟单元;调度;Witness仿真优化中图分类号:F273 文献标识码:A0引 言单元制造系统是运用模块化的方式组织生产,是在成组技术基础上的进一步延伸和发展。单元生产可以兼顾效率和柔性,能满足多品种、小批量的生产的要求。虚拟单元制造系统是单元制造模式的新发展【l】。虚拟制造单元(以下简称为虚拟单元)是将完成具体加工任务所需要的设备在逻辑上形成单元组合,通过控制器对单元内的设备进行通讯及控制,而设备的物理位置一般并不进行重置。当完成具体作业的加工任务后,虚拟单元中的设备会自动释放,以供其它虚拟单元构成所需。船舶建造具有物料种类多、产品的工艺流程复杂、工艺路线长、各生
4、产环节之间相互约束且密切联系,同类工件在加工阶段复杂性及相似性高,加工设备较庞大,且不容易搬运【23J。采用虚拟单元制造系统的生产模式组织安排船舶生产,能够有效地提高造船生产效率、加快船舶建造进度、缩短建造周期。但如果虚拟单元调度方案不当,容易引起交货延迟的现象。收稿日期:20160711:修改稿收稿日期:2016-0919基金项目:国家自然科学基金资助项目(71271105);教育部人文社会科学研究规划基金项目(12YJA630036);江苏省研究生刨新资助项目(SJLXl6 0452)万方数据57卷第3期(总第219期) 韩文民,等:基于阻塞流理论的船舶建造中管件加工虚拟单元调度问题研究虚
5、拟单元制造系统的调度问题得到了国内外学者的广泛关注。在虚拟单元调度模型方面,Ghahve等【4】以完工周期最小以及总运输成本最小为目标,构建了考虑外包情况的虚拟单元调度模型。Aksoy等垆J和Kesen等【6】在动态多变的系统环境下构建了一个多目标混合整数规划模型,用来解决加工工艺路径有多条可选时的虚拟单元作业调度问题。代乙君等17对两阶段多车间调度的特点进行分析,构建了运输能力有限情况下的两阶段多车间调度模型,解决了船舶分段生产过程中存在的返工、运输能力限制以及堆场面积约束等问题。笔者【8】在船舶生产虚拟单元制造系统调度模型中考虑了加工任务动态需求、设备加工能力、负荷平衡以及同类设备有多台的
6、情况,提出了共享资源协调排序策略。在虚拟单元调度算法方面,Kesen等【6】以加权时间和总运输距离最小为目标,运用遗传算法解决虚拟单元调度问题;Kesen9】等还提出了一种虚拟单元制造环境下基于遗传算法的编码方式,以解决工件批量流动下的虚拟单元调度问题。Rezazadeh等【10】提出了一种基于粒子群的混合算法,解决虚拟单元制造设计系统中的虚拟单元构建和调度问题。孟令玉【ll】研究了带有并行机的开放车间调度问题,将线性规划模型转化为网络模型,并应用网络最大流算法求解。然而,目前对虚拟单元调度模型的研究着重考虑多因素下的模型构建,很少从图论的角度进行研究。在调度模型求解方面大都采用启发式算法求解
7、,该算法具有较好的搜索速度以及快速收敛性。阻塞流理论12】是网络流规划中非确定性、随机多值性研究领域中的一个新的分支,能很好地解决城市交通网络阻塞问题,并提出阻塞消解的办法。本文基于阻塞流理论研究船舶生产调度中的虚拟单元调度问题。借鉴城市交通运输网络的构思,从生产物流阻塞的角度,引入船舶建造过程中的设备加工能力约束,以及设备和加工工序相匹配条件下的虚拟单元调度问题。这样不仅能够清晰地表示出设备及加工工序的相互关系,发现生产组织过程中的瓶颈环节。以某船厂舾装作业中的管件加工为例,通过改进的FGS(Fuzzy Gap Statistic)算法,对管系托盘中的管件进行聚类分析;构建了管件加工中完工周
8、期最小化、设备最大负荷最小化以及等待时间最小化的多目标优化模型,并采用免疫遗传算法求解模型。1 基于阻塞流理论的管件加工虚拟单元调度模型的构建11问题描述在管件加工的虚拟单元制造系统中具有多种类型的作业,批量大小己知,且所分配的作业都在单元内部完成。每个工件的工艺路线己知,每个设备在一个单元内只能完成一类相同或相似作业的加工。设备在车间内的位置固定。调度的目标是让每道工序在最合适的设备上加工,并确定作业在各设备上的加工顺序及适当的开工时间,使整个系统达到最优。在构建数学模型时,假设如下:(1)对于工件的任意加工工序,在设备集之中至少有一台可以完成加工,且用于加工的时间是确定的。(2)在每个加工
9、周期内,每个工件的需求量是确定的。(3)每个设备的能力是确定的。(4)设备位置固定不变。(5)每个工件的加工工艺是确定的。(6)每个工件在一个时间段内只能在一台设备上加工。换言之,只有在完成前一道工序时,工件才能在后一道工序进行加工。12多目标优化模型 在基于阻塞流理论的阻塞最短时间问题求解时,一般采用预估时间增量算法(该算法的基本思路在本文中不进行讨论,可参考相关文献13】)。将预估时间增量算法运用到船舶建造中管件加工多目标优化模型的关键在于:在生产制造的网络流中,工件具有固定的加工工艺,需要严格按照工件的工艺流程进行加工。因此,本文对预估时间增量算法进行了改进,将设备与工件的加工路径作为约
10、束,添加到模型中进行求解。针对船舶建造中管件加工的考虑阻塞时间最短的阻塞流模型为万方数据中 国 造 船 学术论文毛()=h=ljffili=1(只一也一崛tYi,j,h XYkj,(h-OM) (1)式中,瓦为工件在增广路(工件的加工路径)上的加工及运输时间之和,“。为增广路(g=1,2,w),i为设备序号,i=1,2,m;为工件序号,=l,2,门;h为工序序号,h:l,2,;Iilf为第歹个工件的工序总数;k为设备序号,七=i,2,m; 层,为Dm在设备f上进行加工的加工时间;o为第个工件的第h道工序;M,。为第个工件在第h道工序的可选加工机器数:口。为工件从设备f搬运到脚需要的运输帆为圳的
11、批燃,怯鬻在设备上进御旺。改进的预估时间增量算法中,每次流量的增加是以1个单位流量的进度迭代进行。其步骤如下。(1)设初始流量为oJ=0。厂表示流量,即通过网络的工件的数量。(2)构造当前的流,o的增广网络。(3)在增广网络N中寻找满足工件加工需求的由开始节点J到结束节点t的全部增广路径“。,按式(I)计算该的路径中的加工及运输时间之和。(4)寻找瓦()最小的增广路径,并在该路径的各段中增加一个单位流量(即,将一个需要在该增广路中完成加工的单位流量,添加到其各组成路段中,但网络中总流量只增加一个单位),令当前流f=f+1,转步骤1。(5)直到流量分配完毕,算法停止。通过以上步骤可以得到管件在不
12、同工作区加工的最优工作路径。虚拟单元下的船舶建造中管件加工多目标调度优化模型的是一个复杂的问题,本文在管件各工作区的最优加工路径确定的基础上,构建了完工周期最小化、等待时间最小化、设备最大负荷最小化为船舶建造调度模型的三个目标函数最小化的调度模型。调度优化模型:曲(蹬q) c2, 一 、嘶nm。a。g百i石ne一xgi,j,h Xq J 。),H m n hj m 、minlq一(Mz_。霉囊。+z_。耳_。口,。)I (4)J2l i2l卢121 121 式(5)式(13)为约束条件:互,+M墨,置,q, i=1,2,3-,m:,=l,2J,3一:h=1,23一,(5)式中,2j,为工序Oj
13、,的开始时间;c,为工件,的第h道工序的完工周期。q,丁,舯) =I,2,J,3一:h=1,2J,3一,hjl (6)I,+只_乃+M【l一口uL,) ,=1,2,3,n h=1,2,3,办, 歹=1,2,3,z式中,为工件序号,备i上加工的优先级:1,2,3-,嘭气江1,2,J,-3一,m (7)h为工序序号,=1,2,吩;ai,为工件与工件J 7在设芸蠢,先于q,功口工。;M为一个很大的正数。几h=乞L一=肼气万方数据57卷第3期(总第219期) 韩文民,等:基于阻塞流理论的船舶建造中管件加工虚拟单元调度问题研究 167e,+1)+M【1ai(+1)j=l,2,3,;h=l,2,3,hj一
14、J=1,2,3,刀h=1,2,3j办一f-1,2,3,m (8)N,鬈_。=l h=l,2,3,哆:J=1,2,3,z (9)i=lcj咒, J=1,2,3,l (10)式中,兕,为工件的交货期。H h,口f_,=k i=1,2,3,m;7=1,2,3,n:Jil=1,2,3,hj, (11)j=l h=ln ,。=I_ j=l,2,-3刃:h=l,2,3,嘭,i=1,2,3,m (12)J=l=l 乃,0,cj,0 J=l,2,3,l:h=1,2,3,哆 (13)约束条件中,式(2)表示网络中工件的完工周期最小化。式(3)表示网络中设备最大负荷最小化。式(4)表示网络中所有工件的等待时间最小
15、。式(5)和式(6)表示网络中每个工件的工序先后顺序约束;式(7)和式(8)表示网络中同一时刻同一设备只能完成一道工序的加工;式(9)表示网络中一道工序在同一时刻只能在一台设备上进行加工。式(10)表示网络中工件的完工时间必须在交货期内。式(11)和式(12)表示同一台设备可以循环加工。式(13)表示各个参数变量必须为正数。与传统的调度模型相比,本模型更能清晰地表达出每台设备负荷水平以及作业在每台设备开始及完工时间,并使整个网络中总阻塞最小。该模型属于多目标非线性整数动态规划,采用传统的优化算法很难求出最优解。为此,下节将采用免疫遗传算法求解。2基于免疫遗传算法的调度模型求解遗传算法是一种平行
16、最优搜索算法,具有较高的鲁棒性和平行搜索能力。但是,传统的遗传算法偏向收敛于单个解,而多目标问题的是要找到一组(而不是一个)接近于Pareto最优边界的最优解。为此,采用免疫遗传算法(基于免疫原理的遗传算法)对模型求解。免疫遗传算法可以自我调节,具有产出适当数量抗体的功能,以对应于进化算法中个体之间的抑制或促进。免疫系统中的抗体就像多目标优化进化算法中的种群多样性,以避免传统遗传算法收敛于单个解那样的情况。21染色体编码与解码染色体编码是免疫遗传算法的第一步也是最重要的一步。本文提出的问题共涉及三个重要决策,即分配、调度以及加工批量大小。因此,每种解决方案能够被染色体表示为三个部分:(1)设备
17、载体(1,):该基因表示工序分配到设备中进行加工的设备编码。(2)工件加工顺序载体(1,):此处用染色体表示工件可行的操作顺序。(3)工件的加工批量载体(1,3):表示每个工件的加工批量大小。如图1N示染色体的编码信息可以表述为工序q:在设备M:上进行加工、工件l的加工批量为15等。当工序的设备确定后,将对工序进行排序。万方数据中 国 造 船 学术论文盖霉殛1编码 3工件 1批量 l:图l根据设备与工序的对应关系及染色体编码,03,0H q5堕MLIMs12 13 142 3 3染色体编码图l中的工件的加工顺序可以表示为oj广-q,一q。一D3:一0l:一D2:一D3广q3-D23一q广ckq
18、sq。一Q,22模型求解管件加工是船舶舾装过程的主要组成部分,一艘船舶建造对管件的需求量可达几万根,管件加工进度对船舶生产周期具有较大影响。船舶的管件加工具有数量大、品种多、批量小、结构复杂等特点,适用于虚拟单元生产。现以某船厂船舶舾装过程中的部分管件加工为例进行研究,但不失一般性。某船厂管件加工车间内有6类共享的工作区,选择某个管系托盘中的10个工件进行加工(相关数据见表1、表2和表3)。表1管件基本信息表2基本加工信息万方数据57卷第3期(总第219期) 韩文民,等:基于阻塞流理论的船舶建造中管件加工虚拟单元调度问题研究在表2的“作业顺序方口工时间”栏中,字母顺序表示作业顺序,数字表示加工
19、时间,以小时为单位。如B005表示工件J1的第一道加工作业为B,耗时005h。表3工作区及设备信息管系托盘中的管件种类繁多,在加工过程中,按照工件特点及加工工艺的相似性,对相同或相似的管件进行聚类,形成工件族,进行成组加工,可以减少设备的准备与调整的时间和次数,缩短加工周期,提高设备利用率,进而提高生产效率(这也正是虚拟单元生产适用于多品种、小批量生产的前提)。为此,本文在对管件加工调度方案进行优化之前,采用改进的FGS(Fuzzy Gap Statistic)算法,先对管件进行工艺设备需求聚类。FGS表示工件的加工设备需求,该算法的基本步骤如下(算法的相关理论部分,可参考文献14)。(1)定
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 阻塞 理论 船舶 建造 中管件 加工 虚拟 单元 调度 问题 研究 韩文民
限制150内