一种船体分段组合嵌套作业工时优化方法研究

张 波 梁利东

(广东科学技术职业学院1) 珠海 519090) (安徽工程科技学院2) 合肥 230009)

船厂开展中间产品专业化,不同中间产品任务包对应不同的组合作业方案,作业人工分配的不同对于其生产工时产生直接影响,在中间产品作业过程中如何协调人工获得合理工时具有实际意义.中间产品作业工时优化涉及的变量多且作业关系复杂,属有约束混合离散优化问题,因此难以针对整个过程建立统一的优化模型.目前关于造船工时的研究主要集中在中间产品定额工时及其工时物量之间关联领域[1-3].本文基于遗传算法及动态规划理论提出将中间产品嵌套作业的工时优化问题分解为两个嵌套层次建模并进行工时优化,通过实例计算,方法具可行性.

1 中间产品的组合作业、归类及其工时问题分析

1.1 中间产品及其作业归类

在造船系统中,中间产品是生产的作业单元,是对最终产品进行作业任务分解的一个组成部分,也是逐级形成最终产品的组成部分.其内容十分广泛,既包括船体的分段、组件、部件和零件,也包括舾装的托盘、模块、单元和管件等.造船成组技术依据作业的相似特征,将种类繁多的中间产品分类成组,用相同的施工处理方法扩大中间产品的成组批量,以建立批量的流水定位,从而提高造船生产率[4].以中间产品为对象进行专业化造船,其作业过程及作业对象相对传统造船更为固定,建立柔性流水线是中间产品专业化造船的实质.以柔性流水线的建立为对象,根据作业关联,中间产品建造的组合作业类型可以单元化为如下3类,见图1～3所示.

图1 串联式作业

图2 并联式作业

图3 嵌套式作业

1.2 中间产品的作业工时问题分析

其中,在实际建造过程中,多数中间产品的生产过程是上述3类单元作业的组合,而以上述3种作业形式单独生产的中间产品比例很少.针对第1类串联单元作业(各单元作业之间存在紧前开工与紧后开工关联),网络计划法已经能够很好的根据不同作业的紧前及紧后关系对整个作业的最优工时进行求解;第2类并联单元(各作业单元可以独立开工不受其他作业影响)能够以阶段为单元基于传统动态规划法进行求解;第3类嵌套作业(子层各单元作业为并联作业关系执行完成后又与父层形成新的并联作业)包括多重并联作业组合(图示为2层),其工时优化无法直接应用相关工具及软件求解,而该类作业在中间产品的生产过程中其比例最大,因此本文重点对第3类工时问题进行优化.

2 基于遗传算法及动态规划法的嵌套并联作业工时优化

2.1 作业工时的基本概念及嵌套并联作业工时优化问题描述

总工时(T) 指某个作业施工所需的“工人数量×工人工作的时间”,对于一个作业,从一定时期而言,由该作业的生产设备及方法决定,故不论其工人数量或工人作业时间怎么调整,这两者的乘积认为是不变的.

作业时间(t) 某个作业步骤完成所需绝对时间,一般来说,作业时间等于工人的实际工作时间.作业时间的研究对于控制该作业实际作业工时具有重要作用.

总工期(∑t) 各分段作业耗费的总时间.总工期等于关键路径上所有工序作业时间的总和.

典型嵌套并联作业(以两层嵌套为例)的工时优化问题描述为如下

某工序i由队伍A执行完成,该队伍有m个工人,工序i包括n项作业(每个人工均可执行任意工序作业),其中1,2,…,n-j+1项作业构成一个子工序,n-j+1,…,n为子工序独立作业2≤j≤n-1,每项作业的总工时可按经验获得分别为 T1,T2,…,Tn,子工序及各作业之间无关联,均需从开工到完工结束,该工序才算完工,求该作业工序i作业时间最短的人工分配方案及作业工时.

2.2 遗传算法及动态规划方法在嵌套并联作业中的应用

2.2.1 遗传算法在子层并联作业的应用 遗传算法是一种广泛用于求解寻优问题的方法.它是按概率在解空间进行搜索,因此能较为有效地避开局部极值,以较高的效率逼近全局最优解.同时,将待解决问题转化为编码序列问题,对设计变量和目标函数要求少,因此适用面广[5].

由前所述,典型的子层并联作业可描述为m个工人在n项工作中的分配,各项工作的总工时T已知,要求由人工分配不同而形成所有作业共同完成工作时间最少的方案,优化目标为:t=min{max(ti)}.式中:ti为工作i的作业时间:i=1,2,…,n.

遗传算法设计 将遗传算法用于子层并联作业的人工分配问题关键是采用有效的编码和解码方式以及适当的交叉、变异操作.遗传算法对种群重复地进行选择、交叉、变异等基本遗传操作,不断产生出比父代更适应环境的新一代种群,直到满足要求条件为止.

个体编码 针对本文编码有两种.(1)直接编码,以工序为对象,将分配工人数作为码值;(2)间接编码,以工人为状态,将工人的分配作业作为状态,算法优化结果即包括最短工时,也包括各人工的分配状态,对每一位工人可以有n(作业数)个编码位选择,仅选择其中一位,不同工人的分配码值构成基因.相比较而言,后者的基因会因工人数的增多而变长,影响算法运行,同时,前者编码方法也避免了同一工人在不同作业中的操作运算产生死锁现象,本文选择前者编码,以3个工人在4项作业中的2种分配方案为例:

n1 n2 n3 n4 m1 0 1 0 0 m2 1 0 0 0 m3 1 0 0 0 n1 n2 n3 n4 m1 0 1 0 0 m2 0 0 1 0 m3 1 0 0 0

获得染色体编码如下(以两位二进制码构成基因座,根据实际作业工人数调整二进制码位)

10 01 00 00 01 01 01 00

群体规模选择:合适的群体规模对遗传算法的收敛具有重要意义.群体太小难以求得满意的结果,群体太大则计算复杂,根据经验,群体规模一般取10～160.

适值函数:由于并行作业具独立性,面向并行作业工人作业分配理论上可以有多种方式,如部分作业先不执行,待部分作业完工后再进行等,本文模型建立考虑最复杂的情况,假设n项并行作业经过m个过程完成,其中(A1,A2,…Aa)k表示第k个作业组内同时开工的作业项目,其中,0≤a,b,m≤n,m≥1各作业组的作业时间,故得到适值函数为

在造船过程中,由于工时及工序的固定性,多项并行工序多存在一次人工分配,尽管二次或者更多次的分配能够进一步优化缩短工时,但是对实际作业过程而言,其人工分配及调整相对烦琐,多项并联作业如果按照分工序进行人工分配,其工序基本已经限定,因此模型中本文选取m=1,即n项作业单独作为一项工序优化求其最短工时,尽管将问题简化,但是可以在此基础上对工厂实际并联作业的多项工序分别进行优化,最后求其总和,结果趋近于最优工时,同时缩短了程序的运行时间及操作过程.

选择:选择是用来确定重组或交叉个体,以及备选个体将产生多少个子代个体.选择的第一步是计算适值,采用按比例的适应度分配,是利用比例于各个个体适应度的概率决定其子孙的遗留可能性.若有m个个体,其中某个个体i,其适值为fi,则其被选择的概率表示为

然后对各个染色体计算其累积概率,如第k个个体的累积概率为

第二步用轮盘赌选择法进行选择.为了选择交配个体,需要进行多轮选择,每一轮产生一个[0,1]均匀随机数,将该随机数作为选择指针来确定备选个体.

交叉与变异:交叉在遗传操作中起核心作用,交叉概率较大可增强遗传算法开辟新搜索空间的能力,但性能好的基因串遭到破坏的可能性较大,算法收敛速度降低且不稳定;若交叉概率较小,则遗传算法搜索可能陷入迟钝状态.本文采用循环交叉操作即对子个体中的代码进行顺序调换(本文选择3个码串为一基点进行相互调换)如图4.遗传算法的变异主要是为了保证其具有局部的随机搜索能力和维持种群的多样性.当遗传算子在接近最优解时,变异可以加速向最优解的收敛,但当已接近最优解时,也可能使最优解遭到破环,因此同时变异的概率应取较小值.本问题的变异算子采用如下方法:在随机选中染色体(个体串码)当中首先针对一个基点(即作业人员)增加一个单位,然后采用随机原则,任选其他一个基点减少一个单位,即符合变异保证在全局范围内,又保证了变异的前提条件即作业人员的总数不变,但对个体串码而言实现了重排序操作,如图5所示.

图4 基因交叉过程

图5 基因变异过程

2.2.2 动态规划法 动态规划法是研究多阶段决策问题的数学方法,其原理概括为:无论过去的状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略.因此,多阶段决策问题的求解过程可看成一个连续递推过程,由后向前逐步计算[6].

本文通过遗传算法针首先对子层并联作业交叉变异优化获得的不同人工分配方案及对应的最优工时后,将其作为一个阶段与该工序内其他的独立作业构成一族同类型的子问题,建立动态规划模型,再进行逐个阶段求解,以下为动态规划模型的建立.

阶段变量 以n项作业来划分阶段,前述子层并联作业在此视为其中一项作业.

决策变量 uk为分配给第k阶段的作业工人单位数.

状态变量 xk表示分配给第k至第n项作业的人工单位累计数,显然,x1=m;n-k+1≤xk≤m-k+1;k=2,3,…,n.

状态转移方程 xk+1=xk-uk.

允许决策集合 Dk(xk)={uk∣1≤uk≤min(xk,m-n+1)},uk为正整数.

最优指标函数 fk(xk)表示用 xk单位工人分配给第k至第n项作业时,在各种决策方案下完成任务时间的最小值,得到动态规划基本方程

3 实例研究

本文以某船厂对一批“太古船”采用沉浮法改装加长的合拢工艺进行工时优化为研究对象.改装方案是将原船在 81.5号肋位切断,嵌入长28.305 m的平行舯体,然后合拢.改装内容共有15个大项43个小项,增加重量860～950 t.为提高改装效率,要求对该船进行工时优化(见表1).其中,新增中部总段与原尾半条船合拢是其主要工序,工作量占整个船舶改装作业的60%.对该节点的作业进行工时控制是本文的主要目标,限于篇幅,本文以该工序的某组合作业(检查纵向定位板、检查合拢口两端前后水尺及合拢工装设备)为对象进行案例优化.

表1 太古船某工序的组合作业及其完工工时

由表1,该工序共有8项作业,其中作业1,2,3,4属于父层并联作业,四项作业之间无关联,可以独立开工;5,6,7三项作业属于子层(5,6,7子并联作业完成后,再执行8作业成为独立作业,本文用[(5,6,7),8]表示其关联关系),故该工序的各项作业属于2层嵌套并联作业,为便于优化分析,分别设为独立作业I(1),II(2),III(3),IV(4),V[(5,6,7),8].现已知该厂安排30名员工(10个班组)进行该工序作业,现要求对10个班组进行合理分配,使完成该工序的作业时间最短.

优化步骤一 针对5,6,7子层作业采用遗传算法进行优化,计算其不同人工分配方案及对应的最短工时,由表一获得已知数据,设置种群规模为20,交叉概率 0.8,进化次数 100,变异概率0.1,由VISUAL BASIC软件编制程序得到优化结果,见表2所列.

表2 子层作业的优化结果

优化步骤二 在获得子层作业的不同分配小组方案及对应最短作业工时的基础上,采用动态规划计算I(1),II(2),III(3),IV(4),V(5,6,7)的最优工时及人工分配方案,将第[(5,6,7),8]子层作业视为第五阶段 V,得到各阶段的 tk=tk(uk).其结果见表3.

表3 第5阶段优化结果

由上述计算可知:f5(u5)=t5(u5);u5=x5;3≤x5≤6,得出作业五的数据如表4所列.

表4 第5阶段最优指标

依次得到,当k=3时,f3(5)=4,f3(6)=2.5,f3(7)=2.5,f3(8)=2;当 k=2 时,f2(6)=4,f2(7)=3,f2(8)=2.5;当 k=1 时,f1(x1)={max[t1(u1),f2(x1-u1)]},x1=10,得到f1(x1)=2.5.

通过优化,得到该组合作业的最短完工时间是2.5 h.同时得到获得最短完工的组合作业分配小组数:u1*=2,u2*=2,u3*=1,u4*=2,u5*=1,=1=1.

4 结 束 语

本文针对造船过程中的嵌套并联作业工时优化及人工分配方案问题提出基于遗传算法和动态规划法的解决方法,将嵌套并联作业的子层视为父层相似阶段,较为满意的解决了工时优化问题,通过实例验证了该方法的有效性,为造船工时及人工的控制提供决策支持.

[1]陈民俊,潘 斌,刘建峰.应用BP网络测算造船作业任务包定额工时[J].中国造船,2003,44(2):1-5.

[2]刘 滨,蒋祖华.船舶装配作业工时智能估算技术[J].上海交通大学学报,2005(12):20-24.

[3]赵 东,马晓平,蒋志勇.船舶制造中的工时/物量数据统计分析系统研究[J].造船技术,2003(2):8-10.

[4]高介估.现代造船工程[M].哈尔滨:哈尔滨工程大学出版社,1998.

[5] 陈国良,王煦法.遗传算法及其应用[M].北京:人民邮电出版社,1996.

[6]冯 杰,黄力伟.数学建模原理与案例[M].北京:科学出版社,2006.