面向订单的铜板带生产组批及优化

面向订单的铜板带生产组批及优化晏晓辉1,2,朱云龙1,吕赐兴1【摘要】摘要:如何有效地解决计划中的组批问题是铜板带加工首要考虑的问题。在深入研究铜板带生产中订单组批规律的基础上，建立了综合考虑铸锭化学成分、工艺路线以及经济性的多目标组批优化模型,采用一种基于基因段思想的遗传算法，设计了基于基因段的编码、解码、交叉和变异规则，并通过加权因子综合了铸锭个数和工艺路线重合度，将多目标问题转化为单目标进行求解。生产数据试验表明，采用的方法能够减少需要的铸锭数量和中间工序分卷次数，有效地解决了生产中的组批优化问题。【期刊名称】计算机集成制造系统【年(卷)，期】2011(017)009【关键词】关键词:订单组批;装箱问题;遗传算法;基因段;铜板带1问题的提出典型的铜加工过程包括熔铸和压延两部分，属于混合制造模式。其中熔铸部分是连续加工，而压延工艺相对复杂，涉及步进炉加热、热轧、双面铣、初轧、切边、钟罩炉退火、酸碱洗、精轧、气垫炉退火、清洗、拉弯矫直以及剪切包装等十几道工序，部分工序为离散加工，而在步进炉加热和退火等工序中，需要聚批连续加工。初轧之前，所有产品的工艺路线大致相同，初轧之后根据不同的订单和产品工艺路线进行分卷处理，分卷之后的料卷根据各自的工艺继续进行加工，如图1所示。由于铜板带价格高昂，为减小库存积压,订单往往表现出即时、小批量等特性,通常多个订单的订货量组合到一起才能达到一个标准规格铸锭的重量。因此，在制定熔铸生产计划时,对于订货量小的订单似及大订单分配到铸锭中后的剩余部分,需要将其按照牌号相同、工艺路线相近、交货期相近的规则组合到各个标准规格铸锭中进行生产，并在后续的压延、剪切工序中将中间产品分配给各个订单，这个将订单分配到各个标准规格铸锭中生产的过程即为铜加工订单组批过程。组批问题并非铜加工行业独有，在钢铁行业已有两种关于组批的研究，一种关注的是在某道工序上对多个铸锭的加工进行计划排序如赵瑁等对冷轧板组批调度进行了建模，采用单亲遗传和临域搜索相结合的方法来求解该问题［1］,SungdeukMoon等采用了整数线性规划的方法对退火炉的组批生产进行了求解［2］;另一种研究是针对钢管生产过程中短尺合同进行组批，以确定钢管在热区分割时的热分区长度，如李虎等对该问题进行了建模，将特定规则加入到一步算法中来对该问题进行求解［3］。铜板带加工的订单组批问题与上述钢铁行业的第二种组批类似，但也有不同之处:钢管的合同组批目的是使热分区长度符合更多的订单长度，铜加工的订单组批则是将多个订单合并到铸锭中去。另外，前者只需考虑合同要求的长度而后者在熔铸之前必须考虑牌号、工艺路线等多种因素。因而钢铁行业组批优化在铜加工行业中不具有直接借鉴意义。目前，对铜板带加工的生产组批优化还缺乏相关的研究和应用，铜加工行业生产组批主要由计划员根据经验手工完成，存在铸锭余量较大、占用增加、中间工序分卷次数多等不足。在牌号、重量、工艺路线等条件的限制下，如何合理地实现生产组批，减少需要生产的铸锭个数，提高成品率，并将工艺路线相近的订单组在一起，使得制造分离点向后推移，成为铜板带加工行业迫切需要解决的一个实际组合优化问题。为此，本文采用整数规划方法对铜板带生产组批问题进行建模，进而把组批问题抽象为一个带特性的多目标装箱问题，应用一种基于基因段思想的遗传算法，以解决面向订单的铜板带生产组批优化问题。2组批问题建模在接收订单后，首先要对订单进行工艺设计，确认订单的加工路线及加工方法，根据产品的成品率计算订单需要的熔铸重量，工艺设计完毕后，再对订单进行组批,确认各种牌号铸锭需要生产的数量，以便进行后续的排产。在组批时，对熔铸重量大于标准规格重量的订单，需要拆分到多个铸锭中，对拆分后的剩余重量和熔铸重量较小的订单，需要组合到标准规格铸锭中。组批分为横向组批和纵向组批：i横向组批指组在一个铸锭中的订单工艺完全相同，铸锭可以作为一个整体一直加工，最后在剪切工序分卷，交付给不同用户;④纵向组批指组在一起的订单工艺路线只有一部分相同，必须在中间工序分卷，分卷之后各自单独进行加工。中间工序分卷给物料加工和跟踪造成了不便同时，也加大了设备占用和能源的消耗因此，组批时在不增加料卷的前提下应尽量以横向组批为主，避免中间分卷似实现批量经济。由上所述，订单组批的目标为：i尽量使用最少的铸锭来满足订单;④组在同一个铸锭中的订单的工艺路线尽量一致。在组批时需考虑如下约束条件：i组在同一个铸锭中的订单熔铸重量之和不超过—个标准规格铸锭的重量;④组在同一个铸锭中的订单牌号必须相同。牌号代表铸锭的化学成分，在同炉次熔铸的铸锭成分相同。用一个四元组来表示订单:order=-id,w/a/c-。式中:id为订单编号,w为订单考虑成品率之后的重量,a为订单牌号,c为工艺规程编号。设标准规格铸锭重量为WS,对于订单重量大于标准规格铸锭重量的情况，只需考虑订单分配给铸锭之后的剩余部分，不失一般性，可以假定对所有订单，均有w<WS。对n个订单的组批问题，建立订单牌号对比矩阵A,建立订单工艺路线重合度矩阵C,假设初始预估铸锭数为m,建立分配矩阵X,则需要的铸锭数最少的目标函数表示为：同时,工艺路线重合度最大的目标函数可表示为：根据一个订单只能被分配到一个铸锭中去，有约束：根据一个铸锭中的订单总重量不超过一个标准铸锭的重量，有约束：根据同一个铸锭中订单的牌号全部相同这一要求可知，当XijXkj=1时,要求Aik=1,当XijXkj=0时Aik=0或1,i=123,...,n,j=123,...,m,故该约束可表示为：综上，建立组批问题的模型上述模型可以抽象为一种特殊的装箱问题——带特性的多目标一维装箱问题。订单代表需装箱的物品,有牌号、工艺规程、重量等属性，铸锭相当于固定重量的箱子,寻求一种装箱方案,在同种牌号才能组合在一个铸锭中且同一铸锭中的订单重量不能超过标准铸锭重量的前提下，使所需铸锭数最少，并且装箱组合尽量使工艺路线重合度较高。装箱问题是一个NP-hard问题,根据装箱问题考虑的维度可以分为一维、二维和三维装箱。根据箱子大小是否可变，可分为固定装箱问题和大小可变装箱问题。根据物品在装箱时的要求,可分为带特性的装箱问题和不带特性的装箱问题。对于不带特性的装箱问题,有许多算法进行求解，主要包括近似算法如首次适应（降序)法FF/FFD(firstfit/decreasing)、下次适应(降序)法NF/NFD(nextfit/decreasing)、最佳适应(降序)法BF/BFD(bestfit/decreasing)和调和算法［4-6］;智能算法如:启发式算法、遗传算法、粒子群算法、禁忌搜索算法等［7-9］。近似算法是基于特定规则来求解,不能保证求得最好解，但规则适合问题的情况下可能求得满意解。智能算法采用随机试探的方式，在针对二维、三维等存在摆放方位约束的问题上有较好的表现。对于带特性的装箱问题，由于换箱时有特性限制，常规的智能算法在换箱操作即编码变换时存在困难，该类装箱问题通常采用FFD-k、NFD-k、BFD-k等近似算法求解。董一鸿等针对有色装箱问题采用KC-FD,KC-FF和KC-FFD等多种方法进行了对比,并提出了SCPF-A(samecolorpackedfirst)算法，在装箱之前先对颜色进行分类排序［10］。HansKellerer等对带有特性的装箱问题(k-BP)的近似算法进行了时间复杂度分析［11］。LeahEpstein等在此基础上进一步分析了特性种数k在不同取值时各近似算法的时间复杂度变化［12］。但这些近似算法所求得的解的优劣受限于问题的数据，并且上述研究均为单一特性约束，不能处理多特性约束的装箱问题。针对前述多目标组批优化模型，本文采用了一种基于基因段的遗传算法,使得在随机搜索时仍能保证只有同种牌号才能组到一个铸锭中，既保留了遗传算法的优点，又克服了它在处理带特性问题上的困难。基于基因段的遗传算法是在原遗传算法的基础上加入基因段的概念，将个体编码即整个基因分成若干个基因段，只有同一个基因段内的基因才能相互交换,在变异时也局限于该基因段之内。对于带特性的装箱问题，在对个体进行编码时可以按照物品特性将编码分为若干个基因段，保持基因只能在同基因段内交叉和变异，这样，就解决了特性，而其他目标和约束条件可以放在目标函数中通过适应度来体现。采用基于基因段的遗传算法求解组批问题的流程图如图2所示。3.1基于基因段的编码规则针对装箱问题，有两种常见的编码方式［13F基于箱子的编码表示(Bin-BasedRepresentation,BBR),用基因的位置表示物品，基因的值表示该物品所放入的箱子:④基于物品的编码表示(Object-BasedRepresentation,OBR),只对物品的排列进行编码，然后应用解码器得到对应的解。本文采用BBR法，即个体编码为定长编码，长度为订单的数目，基因位置代表订单编号,基因值代表该订单所分配的箱号，箱号不超过初始箱子数m。由wvWS可知，对于n个订单，最多需要n个铸锭就能把他们全部装进去，且为了保证在后面的交换过程中有足够的空间使订单在铸锭之间得到充分交换，对上述模型，可以取初始铸锭数m=n。本文中的特性为订单牌号,基因段根据订单的牌号特性来确定。为方便交换，首先按照牌号将各订单排序，分析牌号种类及每种牌号订单的个数,假设这n个订单牌号有k种，第i种牌号订单个数为对长度为n的编码，分为k个基因段，第i个基因段的长度为Qi,取值范围为只有在同一个基因段之间的订单才能交叉互换，以保证不同牌号的订单不会装到同一个铸锭中去,并且变异时的取值也限定在本基因段的取值范围内。3.2解码规则对于基于上述编码的个体，可以将其解码为前述分配矩阵X。对于矩阵X,当基因位置i上的基因值为j时置Xij=1,其他元素为0。由于在编码时，先对订单按照牌号特性进行了排序，在解码时也要对基因个体还原顺序。3.3交叉设定交叉因子，并以交叉因子的概率随机选中两个个体，再随机选择交叉点，判断交叉点所在的基因段,对该基因段内交叉点之后的基因进行交换，其他位置的基因取值均不变。3.4变异设定变异因子，并以变异因子的概率选中一个个体，再随机选择一个变异点，判断变异点所在的基因段，重新生成变异点的基因值，该基因值取值范围为所在基因段的取值范围。3.5适应度函在组批问题基本模型的基础上，将工艺路线重合度目标以加权因子a加入到铸锭个数目标中,将多目标问题转化为单目标，目标函数变为由于Xij,Xkj=0或1,Cik<1,m<n,又因为矩阵X为稀疏矩阵,值较小，通常都不会超过n2,故将该部分目标放大，取使工艺路线目标不超过1,在优化时以减少需要的铸锭个数为主要优化目标。XijXkj<Aik这一牌号相同的约束条件已经在编码中得到保证，对于重量约束将以罚函数的形式加入到目标函数中来进行限制。设惩罚因子为同在原目标函数上加上来对超出限制的重量进行惩罚。取惩罚因子p=io,对一个铸锭中订单重量超过标准规格重量的,每超过0.1XWS的重量惩罚相当于增加一个铸锭。综上启标函数变为：对种群中的各个个体，取适应度为目标函数越小，适应度越大，用2次方加强较优基因被选中的概率。4生产数据试验带特性的装箱问题常用FFDk,NFDk和BFDk等近似算法求解，本文分别采用基于基因段的遗传算法和近似求解方法中表现较好的FFDk来对数据进行求解。由于FFDk不能直接求解多目标问题，在采用FFDk法时先以重量为限制条件求解然后再按式(2)和式(6)得到工艺路线重合度和总目标值。4.1试验一试验数据取自洛阳某铜加工企业电子铜板带厂的实际订单。订单数据经处理如表1所示有12个订单，订单的牌号、工艺路线编号、重量分别如表1所示，不同牌号之间不能组批,工艺路线11与12的重合度为0.8,11与13之间的重合度为0.6,12与13之间的重合度为0.7,21与22之间的重合度为0.9,21与23之间的重合度为0.7,22与23之间重合度为0.8,据此建立牌号可交换矩阵A和工艺路线重合度矩阵C,C矩阵具有一致性。对基于基因段的遗传算法，设定种群大小为50,交叉因子为0.1,变异因子为0.07,进化100次,10次求解，7次求得最优组批方式为:(1,7),(2,12),(3,8),(4,5,11),(6,9,10)，其中每个括号中的数字代表组批在一个铸锭中的订单号，需要铸锭个数为5,工艺路线重合度为0.1944,总目标值f=4.8056,3次求得组批方式为:(1,7),(2,12),(3,8),(4,9,11),(5,6,10),需要铸锭个数为5,工艺路线重合度为0.1889,总目标值f=4.8111。用FFDk法对该问题求解,求得组批方式为(1,7),(3,8),(2,12),(4,10),(5,6,11),(9)。需要铸锭个数为6,根据结果计算工艺路线重合度为0.1681,总目标值f=5.8319。该结果表明,使用基于基因段的遗传算法，比FFDk法少用一个铸锭，并且工艺路线的组合上也更优。4.2试验二为测试算法在处理大规模订单组批时的性能,采用30个订单、5种牌号;30个订单、7种牌号;50个订单、7种牌号;50个订单、10种牌号；100个订单、7种牌号;100个订单,10种牌号这六种情况的订单数据进行试验。试验结果如表2所示，基于基因段的遗传算法结果为10次求解的平均值。由试验结果可以看出，基于基因段的遗传算法所求得的铸锭个数基本上都优于FFDk法求得的结果，仅在订单数量为30、牌号种数为7时遗传算法与FFDk法求得的铸锭个数相同。随着订单数的增加，基于基因段的遗传算法表现出更优越的特性。需锭个数少与工艺路线重合度高这两个目标在一定程度上是相互冲突的,需锭个数越少，组批越紧密，由式(2)可知工艺路线重合度可能也越小。在工艺路线重合度高这一目标上,基于基因段的遗传算法有5次是最优的，仅在订单数量为100、牌号种数为10时次于FFDk法，但差别很小，且在需要铸锭个数最少目标上远优于FFDk法。以上试验表明，基于基因段的遗传算法比传统的FFDk法优越，能较好地解决组批优化问题。5结束语铜板带的订单组批是生产组织优化的第一步，如何更合理地进行组批,是铜板带生产过程中提高生产效率、降低原料成本和减少能量消耗的关键。本文采用整数规划方法对实际铜板带加工的生产组批问题进行了建模，并把该模型抽象为一类特殊的装箱问题——带特性的多目标一维装箱问题。同时，针对常用装箱问题算法在求解这一特殊的装箱问题时的不足，应用了一种基于基因段的遗传算法对组批问题进行优化求解。通过洛阳某铜加工企业的应用结果表明，与历史记录相比,采用本文提出的模型和优化组批方法后，熔铸所需铸锭减少4.1%,中间工序分卷次数减少8.4%。在缩减熔铸成本的同时还能降低压延部分的能量消耗和设备损耗，为该企业创造可观的经济和社会效益。参考文献：ZHAOJun,WANGWei,LIUQuanli.Modelandalgorithmofgroupingbatchschedulingforcoldroilingsheetproductionline[J].ComputerIntegratedManufacturingSystems,2008,14(10):1957-1965(inChinese).[赵瑁，王伟,刘全利.冷轧薄板生产线组批调度模型与算法[J].计算机集成制造系统,2008,14(10):1957-1965.]MOONS,HRYMAKAN.Schedulingofthebatchannealingprocess—deterministiccase[J].ComputersandChemicalEngineering,1999,23(9):1193-1208.LIHu,HUOJiazhen.Aheuristicalgorithmforseamlesssteeltubeorder-groupingproblem[J].IndustrialEngineeringandManagemen,2004,9(1):86-88(inChinese).[李虎,霍佳震.钢管生产的合同组批优化算法[J].工业工程与管理,2004,9(1):86-88.]GUXiaodong,XUYinlong,CHENGuoliang,etal.Astochasticanalysisoftheharmonicbin-packingalgorithm[J].ChineseJournalofComputers,2001,24(5):548-552(inChinese).[顾晓东，许胤龙,陈国良，等.调和装箱算法的平均性能分析[J].计算机学报,2001,24(5):548-552.]KONGLiang,DUBin,ZHUJun.Multi-constrainedvariablesizedbinpackingproblem[J].ControlEngineeringofChina,2008,15(5):176-178(inChinese).[孔亮，杜斌，朱俊.多约束的箱子大小可变的装箱问题[J].控制工程,2008,15(5):176-178.]BEINW,CORREAJR,XINHan.Afastasymptoticapproximationschemeforbinpackingwithrejection[J].TheoreticalComputerScience,2008,393(1/2/3):14-22.ZHAIYu,SUNXiaoming.Aheuristicalgorithmforthree-dimensionalcontainerloadingproblemwithnon-identicalitems[J].JournalofShanghaiJiaotongUniversity,2007,41(8):1244-1247(inChinese).[翟钰，孙小明.多种物品三维装箱问题的一种启发式算法[J].上海交通大学学报,2007,41(8):1244-1247.]JIANGBaochuan,XIONGWeiqing.Hybridgeneticalgorithmsolvingforthree-dimensionalcontainerloadingproblem[J].ComputerEngineeringandApplications,2007,43(26):200-202(inChinese).[江宝钏，熊伟清.一种求解三维集装箱装箱问题的混合遗传算法[J].计算机工程与应甩2007,43(26):200-202.]LIUDS,TANKC,HUANGSY,etal.Onsolvingmultiobjectivebinpackingproblemsusingparticleswarmoptimization[J].EuropeanJournalofOperationalResearch,2008,190(2):357-382.DONGYihong,ZHAOJieyu.Approximationalgorithmsfortheconstrainedbinpackingproblem[J].ComputerEngineeringandApplications,2003,39(18):41-44(inChinese).[董一鸿,赵杰煜.带约束的一维装箱问题近似算法的研究[J].计算机工程与应用,2003,39(18):41-44.]KELLERERH,PFERSCHYU.Cardinalityconstrainedb