一种多工序生产作业安排方法

一种多工序生产作业安排方法

0企业动态生产作业计划的设计在现代经济和社会环境中，产品生产变得越来越复杂。通常，公司可以在一个公司的内部或多个形式的公司（以下简称公司）中生产不同的产品。一个产品需要经过多个阶段的过程，并且可以根据公司的实际生产能力和设备条件精心选择最合适的生产操作方案。然而，如果市场上竞争激烈，需求变频繁，公司规模发生变化，如何快速调整生产操作计划，不仅可以动态适应公司内部环境的变化，而且可以指导公司的实际生产（例如，特定设备部门需要详细说明时间间隔内必须完成的加工任务），以实现降低成本和提高效率。通过分析和动态规划网络，我们解决了上述问题。这种方法尤其适用于零件加工和安装公司。1问题的计算过程企业在实际生产作业安排中,存在的制约因素有交货期限、生产能力、库存容量等,需要实现的目标有按时交货、降低成本、平衡生产能力等.而且不同企业会产生不同的制约和目标.若企业有d种产品,m道工序.i表示产品代号,j表示工序代号,每道工序的可用工时划分成jn段时间片(时间片是指将机器工时划分成相等的时段,可以是日、小时甚至分钟.应根据要求结果精确度和计算量大小来确定),xjkijki表示i产品在j工序上第k个时间片是否安排生产的决策变量:xjki={1产品i在j⌶序k时间片上安排生产0产品i在j⌶序k时间片上不安排生产f(x)表示某个生产作业计划下的成本函数,不允许缺货和仅考虑成本目标的情况下,生产作业安排的问题可表述为:其中:X表示x的可行域(满足不发生生产能力不足,库存超容以及能按时交货的限制条件).由于现实问题的复杂性以及对生产作业计划及时性要求,本文解决问题的计算过程通过总体生产能力安排,单台设备时间片安排和合成调整三个阶段进行,每个阶段由相应的步骤组成.2计算过程2.1全球生产能力的配置2.1.1工序过程vi,vj将整个企业各产品的流程和工序标绘成一个网络D=(V,A,C),其中V是产品生产起始点和所有工序结束点的集合,A是紧前工序结束点指向紧后工序结束点弧的集合,可理解为在其上完成了某道工序的加工任务,C是弧上容量的集合,可理解为每道工序加工能力.对每条弧标注上(b*ij,aij),其中b*ij表示某一产品在工序(vivj)上最优经济批量时的单位产品的生产成本(包括半成品从紧前工序运输到该工序单位产品运输成本和该道工序单位产品加工成本),aij表示该工序的加工能力.本文的产品流程和工序网络略不同于一般运筹学中定义的网络,它有多个起点和终点,并且在有些点和弧有其特殊的性质,下面举一简单的例子来说明其特殊性.图1描绘有两种产品的流程和工序网络.S1,S2分别表示产品1和产品2的生产起点.E1,E2分别表示产品1和产品2的生产终点.a,b,…,g表示各工序的结束点,可以理解为有a,b,…,g台设备,某道工序结束就表示在某台设备上完成了加工任务(为方便论述,以后都称为设备a,b,…,g),每条孤表示一道工序,记作(vi,vj),如:(vs1,va);(va,vd),…,其中(va,vd)表示产品1在设备a上加工完毕后的半成品送往设备d并在设备d上完成加工任务的工序,弧(va,vd)上的标注(4,6)表示产品1完成该工序所需单位生产成本(包括产品1在设备a上加工完毕后的半成品从设备a所在地运往设备b所在地的单位运输成本和在设备b上的单位加工成本)为4个货币单位(如4元),特定时期内该工序生产能力为6个单位(如6件).图上与终点相连的虚线表示没有真实的工序,仅表示某产品生产完毕后从流程中流出.从图1上可以看出产品1可选择生产流程有P11(S1,a,d,f,E1)和P21(S1,a,c,f,E1),同理产品2也有P12(S2,b,c,g,E2),P22(S2,b,e,g,E2)两条生产流程.注意图中特殊的点c,f,g,这些点共同的特点是有多于1条弧指向它们,以点f为例,有(vd,vf),(vc,vf)两条弧指向f点,两条弧上的标注分别为(4,6)和(3,3).这里有两种情况,第一种情况:标注adf项6表示产品1经设备d加工之后,设备f对设备d交来的产品1的半成品的加工能力为6件.若产品1经设备c加工之后,设备f对设备c交来的产品1的另一种形式的半成品加工能力为3件.表明产品1在设备c和d上完成加工后的半产品是不同的,后继工序需要的加工时间也将不一样.对于从设备d交来产品1的半成品,设备f的加工能力为对设备c交来产品1的另一种半成品的2倍.所以假设由设备c交来1件产品1的半成品需要设备f进行加工,则对弧(vc,vf)来说剩余的加工能力为2(2=3-1)个单位,而此时对于弧(vd,vf)来说剩余的加工能力为4(4=6-6/3×1)个单位.第二种情况:设备f是对设备d和c交来的半成品进行组装,这其实是同一流程的不同工序的衔接.只需将装配点前所有紧前工序的单位生产成本记为:至装配点完工后总的单位生产成本减去该工序前所有可用流程(有剩余生产能力)的单位生产成本的最小值.在这里,点c、f和g均属于第一种情况.2.1.2弧的集合cij1)绘制形如图1的整个企业的流程和工序网络.其中弧上标注的b*ij是某产品在(vi,vj)工序上最优经济批量下的单位生产成本.在计算过程中得到某个生产作业安排实际的单位生产成本,记为bij,得出的bij可能会大于b*ij,这个问题在第三阶段进行讨论.2)从第一步所形成的网络中分离出各产品的分网络(弧上标注的含义均不变).对每一产品的分网络,使用最小费用最大流方法确定每一产品成本最低的生产流程安排.单条流程的生产能力不足的情况下,可能选择其中的多条生产流程.但要注意的是使用最小费用最大流方法(详见参考文献).解题时,在寻找新的增广链前,对于类似图1中指向f点各弧的剩余加工能力要同时按相应值一并减少.此外,第k次调整量θ应按以下公式确定:θ=min{minu+(Cij-fk-1ij),minu-fk-1ij,(Οi-fk-1)}(4)其中:θ为弧(vi,vj)第k次调整的流量;u+为前向弧的集合;u-为后向弧的集合;Cij为弧(vi,vj)的容量(加工能力);Oi为产品i的订单量;fk-1ij为第k-1次弧(vi,vj)的流量;fk-1为第k-1次的可行流.第k次可行流:fkij={fk-1ij+θ(vi,vj)∈u+fk-1ij-θ(vi,vj)∈u-fk-1ij(vi,vj)∉u(5)重复寻找新的增广链,直到某次k使得(Oi=fk)则第二步停止.如图1,若产品1和产品2的订单量分别为3件和4件,对于产品1选择成本最低的流程P21就能完成3件的订单量.对于产品2首先按Dijkstra算法(见文献)选择流程P12,按公式(4)确定θ=min{3,∞,4}=3,则弧(vc,vg)和(ve,vg)的剩余加工能力应同时减少为1(1=4-3)和2(2=8-(8/4)×3)件.用含负权的最短路径算法(详见参考文献)寻找到新的增广链p22,确定θ=min{2,∞,1}=1,调整后就能完成4件订单量.3)再将分网络合并成整个企业的流程和工序网络,判断每道工序是否有冲突(即现有设备的加工能力不足完成合并后的的生产任务).如图1中点c,生产产品1与产品2共需要设备c加工能力为6件,而设备c仅有3件的加工能力.找到这些冲突点,并且选择与现有加工能力差距最大的冲突点,绘制出除去最大冲突点各产品的分网络.分网络弧上标注aij项改为工序的剩余加工能力,但在被删除的最大冲突点所在流程上的弧以及最大冲突点紧后工序对应支流的弧(如:弧(vc,vf)和(vc,vg)分别对应的弧(vd,vf)(ve,vg))上标注aij项改记为工序剩余的加工能力加上按最大冲突点加工能力不足量所换算的工序加工能力,因为发生了冲突表示要选择另外的流程,某产品的全部或部分冲突的加工量将可能由不经过冲突点所在流程上来实现,则相应的加工能力给予还原.4)从第3)得出新的各产品分网络的基础上,找到各产品新的一条增广链,计算各产品新增广链的单位产品成本(记为Ti)以及该新增广链的单位产品成本与此前最后一次需通过冲突点安排产品生产的流程的单位产品成本(记为T′i)之差,选择成本差最小的i产品(mini(Τi-Τ′i))的分网络来进行调整,θ表示i产品新增链上的最大可调整量,θ*表示冲突量,则调整量为min{θ,θ*}.如图1,对于产品1,T1=as1a+aad+adf=2+4+4=10,T′1=as1a+aac+acf=2+3+3=8,T1-T′1=10-8=2;类似产品2的T2=12,T′1=6,T2-T′2=6,公式mini(Τi-Τ′i)中的i为1,调整量为3件(3=min{4,3}).5)再将各产品的分网络合并,判断是否存在冲突点.若无冲突点则可以进入第二阶段,若还存在冲突点,返回到第三步.当各产品分网络都不存在新的增广链且冲突点仍然存在,则表明企业整体生产能力不足以满足订单对生产能力的需求,进行相应追加设备投资或拒绝部分订单等决策,以消除整体生产能力的不足.2.1.3设备c的按需加工和运输时间t在实际企业产品生产过程中,在前一道工序加工完毕运到后一道工序是需要时间的,特别是前后两道工序所使用的设备安置在相隔距离较远的地点时,还有设备等待所需半成品的时间.在计算设备生产能力时必须要考虑途中的运输时间和设备等待时间.如图2所示(带箭头的虚线表示可能存在多道工序),设备a完成对产品i半成品的加工任务后由设备c继续加工,则设备c的可用工时应为:在特定期间内设备c总工时减去第一批半成品运达设备c之前所有工序所需加工和运输时间以及所有后续工序对设备c交来的最后一批半成品加工和运输所需时间.设备a可用工时的计算也应作类似处理.如果有两道紧前工序,并且不同紧前工序的加工和运输时间有差异,可以把设备c看成两台设备,其中一台表示某紧前工序由于时间差原因独占设备c的加工能力.如图3,点C2表示点b专占的由于时间差计算的设备c的加工能力.但半成品有库存的情况下,上述情况就不存在.若各产品的交货期不同,也可按上述方法将交货期时间差所计算某设备加工能力作为某产品的专属加工设备.交货期重叠的时间的加工能力由各产品共同占用.如果半产品可以出售的情况,看作一新的产品并且单独绘制该半产品的分网络.如果一台设备同一时刻能完成两种加工任务,视作两台设备.2.2动态优化方法如果每道工序可看成一台设备,则需要考虑将这些加工任务分配到单台设备的时间片上.本文简单介绍由文献提出的使用动态规划的解决方法.该方法的基本思路是:将单台设备的加工能力划分成若干较小的时间片,假设每个时间片只能被一种产品所占用.对每一个需要在设备上加工的产品按其各自的约束条件通过动态规划解出各自成本最低的设备时间片上的生产安排,然后进行合并,检查是否发生冲突(即一个时间片被一种以上的产品同时占用).若有冲突发生,在冲突的时间片加一罚值(限于片幅,加罚值方法详见参考文献),表示占用该时间片需承担额外的费用.在加罚值的情况下再对各产品进行动态规划.经过反复调整罚值、动态规划和合并检查过程,求得最优解.公式如下:δit={1产品i在第t个时间片上安排生产0产品i在第t个时间片上不安排生产(6)库存状态转移方程:xit=xi(t-1)-rit+Piδit(7)成本方程:Ci(1-δi(t-1))δit+hixit+uvtδit(8)上式Ci(1-δi(t-1))δit表示如第t-1个时间片设备被i产品占用,则第t个时间片就不需要重新启动设备,设备启动费用也不存在.成本递推方程:Lit(δit,xit)=minδi(t-1){Ci(1-δi(t-1))δit+hixit+uvtδit+Li(t-1)(δi(t-1),xi(t-1))}(9)文献中建设按以下公式设定uvt的值:uv+1t=uvt+max{0,αgt(δv)}(10)其中:gt(δv)}=Ι∑i=1δit-1(11)i为产品编号(i=1,2,…,I);t为设备时间片编号(t=1,2,…,T);Ci为产品i的设备起动费用;Pi为产品i在单位时间片内的生产量;hi为产品i的单位存储费用;rit为产品i在第t个时间片的需要量;xit为产品i在第t个时间片末的库存量;ximax为产品i库存上限;uvt为拉格朗日乘数,迭代到v步第t个时间片的罚值和;α为单位罚值;δit为变动系数.文献还讨论了设备启动时间跨越几个时间片和单位罚值α选择等问题,限于篇幅详见原文.此外,动态规划过程的约束条件应根据企业实际的情况来设立.2.3根据重和重的要求进行的生产作业安排.在合成阶段主要解决以下两个问题:(1)如图4,要解决点b,c与点a时间上的衔接问题.在设备b和设备c上单台设备时间片安排确定情况下,在设备a不发生冲突的条件下和规定时间内保证设备b和设备c所需半成品的供应.(2)在第一阶段总体生产能力安排所使用的是每道工序最优经济批量下的单位生产成本,而在第二步单台设备时间片安排的结果不一定是最优经济批量下的单位生产成本,它们之间的成本差异要进行处理.合成按以下步骤进行:1)从所有最后的工序开始,考虑订单交货期及其它约束条件下进行第二阶段的动态规划过程.2)如有图4的情况时,检查所有最后的工序在单台设备时间片安排下对紧前工序提出的半成品供应时间的要求是否在所有前道