面向多订单的JSP建模及其蚁群算法实现

面向多订单的J SP 建模及其蚁群算法实现李　言　刘　永　李淑娟　杨明顺西安理工大学,西安,710048摘要:以实施J IT 生产策略为目标,研究了多品种小批量生产企业在多订单生产环境下的作业车间调度问题,建立了基于提前和延期惩罚的作业调度问题优化的整数规划模型。

该模型着重考虑产品装配结构约束和订单交货期约束,以降低由在制品库存引起的生产成本,确保最终获得全局最优可行解。

设计了带精英策略的蚁群算法来求解该模型,并通过实例仿真验证了所建模型的正确性以及蚁群算法求解该问题的可行性和有效性。

关键词:面向多订单;作业车间调度问题;蚁群算法;精英策略中图分类号:TP29 文章编号:1004—132X (2009)18—2198—05Modeling and Ant Colony Algorithm Implementationof Multi -order Oriented Job -shop Scheduling Problem Li Yan Liu Y ong Li Shujuan Yang Mingshun Xi ’an University of Technology ,Xi ’an ,710048Abstract :Wit h t he aim of implementing J IT p roduction st rategy ,t his research st udied t he J SP of batch p roduction enterp rise under t he circumstance of satisfying multi -order p roduction ,established an integer programming model t hat optimized t he job scheduling based on t he earliness and tardiness penalties of t he J SP.This integer p rogramming model mainly took into account t he const raint s of p roduction assemble and order delivery time so as to reduce t he co st increased by inventory management of work in process and event ually obtain t he global optimal feasible solution.Finally ,t his research designed an an ant colony algorit hm wit h elitist st rategy to solve t he mat hematical model ,provided an instance emulation mode to illust rate t he correct ness of t he model and t he feasibility and validity of t he algorit hm.K ey w ords :multi -order oriented ;job -shop scheduling p roblem (J SP );ant colony algorit hm ;elitist strategy收稿日期:2008—11—17基金项目:陕西省教育厅资助项目(08J K389);教育部春晖计划资助项目(Z2005-1-61004)0　引言作业车间调度问题(job -shop scheduling p roblem ,J SP )是一类典型的具有约束满足的调度问题,它要求在一定的机器集上完成一批工件的调度加工,每个工件由若干道具有次序约束不重叠的工序完成,每道工序又有一定的加工时间和唯一的机器需求,属于强N P 难题[1]。

对该问题的研究通常着重于在某些工艺优先约束和资源约束情况下建立一个目标函数,采用不同的优化算法来求得满足特定约束条件下的目标函数值最佳的方案,该方案即为最终的调度方案。

文献[2]提出了一种集成不同策略来产生初始群体的遗传算法,用以求解柔性作业车间调度问题,以加速最优解的出现;文献[3]采用田口免疫算法来求解J SP ,并对由不同规模的问题采用不同算法得到的结果进行比较,说明田口免疫算法的优越性;文献[4]利用拉格朗日松弛法解决带提前和延期惩罚的调度问题;文献[5]提出了一种改进的合作型协同进化算法来求解Job Shop 调度问题;文献[6]采用一种启发式算法解决了多工艺路线条件下的车间调度问题,并讨论了工艺路线对调度结果的影响。

上述研究都是致力于求解J SP 的算法研究,其求解前提是:车间有多个任务需要完成,而每个任务又有多个操作工序,每个任务按固定顺序在相应的资源上完成。

其间忽略了任务之间的优先约束,即没有考虑产品组成结构的关系。

而实际生产过程中,零部件的生产加工存在一定的装配约束关系,特别是在一些单件小批量生产过程中,只有子类的零部件加工完毕才能进行父类零部件的整装加工。

本文主要以单件小批量生产企业为研究对象。

模具制造企业就是典型的单件生产类型的企业,该类企业的产品结构复杂,为多层次结构,由・8912・于加工的零部件之间存在一定的装配优先顺序的约束,所以在对零部件的加工调度过程中有必要考虑产品结构约束。

传统的车间调度是针对某个时段的零部件的加工任务来进行集中调度的,没有考虑零部件之间的装配约束,这样的调度结果只能得到某个时段内的局部最优解。

本文指出面向多订单的车间作业调度问题已不属于传统车间调度的范畴,其目标是考虑产品装配顺序约束下寻求多个订单生产作业调度的全局最优解,从而满足企业实施J IT生产策略、及时响应市场需求的要求。

1　J SP的描述及模型单件小批量生产企业的产品结构复杂,为多层次结构。

多层次产品结构的产品BOM层级大于1,BOM中的部件与零件之间形成了装配中的父子优先关系。

实际生产过程中大多是在每批零部件经过检验合格后才能进行装配加工,故仅考虑零件或部件的整体加工工艺而不考虑其装配工艺。

对于本文讨论的问题,给出如下假定:①产品BOM结构、订单及其交货期已知;②各零部件的工序在不同资源上的加工时间已知,且同一工序在不同机床上的加工时间不等;③各设备资源间的物料运输时间已知。

1.1问题描述现考虑订单中有多种产品,不同产品的零部件可以共享,零部件的加工工序可以在多个机床上以测定的时间完成,并且同一零部件的工序之间有强制性优先关系,同一机床在同一时段内仅能完成一道工序。

对单件小批量生产进行作业调度时,一般要求最大化机床利用率,即缩短生产资源闲置时间。

缩短闲置时间能降低作业车间的在制品库存水平,因此最小化因资源闲置产生的成本是综合优化的目标之一。

另一个目标是要使所有产品的完成时间尽可能接近其交货期,若提前完成,会产生库存费用;若延期完成,则会受到客户的经济惩罚。

因此要在满足客户需求、减少在制品库存的同时,考虑多资源能力约束和因产品结构而产生的物料工序之间复杂的优先序约束。

首先,引入以下用于描述研究对象的符号:O i为不同的产品订单,J o为订单数;P i为订单O i订购的产品集合,P iΑ{1,2,…,p},p为产品种类编号;Q i为P i中各产品的订购数量, Q i={Q ip},Q ip表示订单O i中产品p的订购数量;D i为订单O i的交货期限;V p为产品p的所有零部件集合,V p={v pg|g=1,2,…,J pv},v pg表示产品p中的零部件g,J pv为产品p的零部件元素总数;φpgh表示产品p中零部件的父子关系,v ph 为v pg的父节,且Πv ph、v pg∈V p时φrgh=1,其他情况下φpgh=0;e pgh为产品p的零部件之间的数量约束关系,表示产品p中部件v ph需要由e pgh个零部件v pg组成(仅当φpgh=1时),e pgh为非负整数;N pg为产品p中零部件g的数量,假设E={e pij|e pij∈E p且φp ij=1}为零部件g的父辈数量关系集合,则有N pg=∏ep ij∈Ee pij;B pg为产品p中零部件g的所有工序集合,B pg={b pgq|Πq=1,2,…,J b},b pgq表示零部件v pg的第q道加工工序,J b为工序总数;R pgq为可完成加工工序b pgq的资源集合,R pgq={r m|Πm∈(1,2,…, J r)},r m表示加工资源,J r表示可用资源总数;t mn 为资源r m与r n之间的运输时间;t pgqm为工序b pgq 在资源r m上的加工时间;S ipgqm、E ipgqm分别为订单O i中工序b pgq在机床r m上的开始加工时间、完成时间;C max为作业工序的最大流通时间;C i为订单O i的完成时间;L i为订单O i的延期交货时间,用ceil(L i)表示L i的上取整后的值;H i为订单O i的提前交货时间,用ceil(H i)表示H i的上取整后的值;L Ci、H Ci分别为订单O i的延期和提前单位时间的惩罚费用;I为资源闲置的时间成本。

基于上述约定,最终作业车间调度的任务就是将这些带有订单信息且存在产品结构约束的工序加工任务分配到有限的生产资源上去,寻求最优调度方案。

1.2作业调度优化模型的建立敏捷制造策略以及J IT生产策略在企业的实施,使得考虑了提前-延期惩罚的作业车间调度越来越多地为人们所关注[4,7Ο8],这是因为提前完成订单产品,必然引起库存等相关费用,而延期则会造成企业声誉的影响、市场份额的下降以及来自订单合同的惩罚等。

基于此,以企业有限资源利用率最大化、实现J IT生产为目标,本文提出一个面向多订单的车间作业调度问题的数学模型,该模型明确地考虑了多订单环境下资源的能力约束、产品装配约束、订单提前期和交货期,模型的输出是对应每一个订单每个产品的部件或零件的工序加工开始时间与完成时间。

根据上述讨论,首先建立如下优化目标:F=min[I(J r C max-∑J oi=1∑p∈P i∑J pvg=1∑J bq=1t pgqm N pg Q ip)+∑J oi=1(L Ciceil(L i)+H Ciceil(H i))](1)・9912・显然,目标第一部分是上述生产闲置成本,第二部分则为延期惩罚。

考虑的约束条件如下:(1)每个订单完成的时间不能迟于最大流通时间:C max≥C i　Πi=1,2,…,J o(2)(2)由于父零件只有在其所有子零件加工完成后才能进行装配加工,故根据产品结构约束,父零件的第一道工序开始时间应晚于任意子零件的最后一道工序的结束时间:S iph1m≥E ipgJb n+t m n　Πg,h且φpgh=1(3)E ipgJb n =S ipgJb n+t pgqn N pg Q ip(3)同一机床上同一时刻最多只能加工一个零件,且任意时刻同一零件只能出现在一台机床上:[S ipi gqm ,E ipi gqm]∩[S jpjhrm,E jpjhrm]= (4)Πi,j,g,h,q,r,m(4)考虑任何订单的完成时间为其所有最终产品的最后一道工序的完成时间,即max E ipgqm=C i　Πi,p,g,q,m(5)(5)定义订单的交货提前与延期时间:H i=D i-C i,H i-1<ceil(H i)≤H i　Πi=1,2,…,J o(6) L i=C i-D i,L i-1<ceil(L i)≤L i　Πi=1,2,…,J o(7)上述模型与约束中的变量为非负数值,结合该模型便可进行目标函数求解算法的设计。