?2198?
面向多订单的JSP建模及其蚁群算法实现———李言刘永李淑娟等
于加工的零部件之间存在一定的装配优先顺序的约束,所以在对零部件的加工调度过程中有必要考虑产品结构约束。传统的车间调度是针对某个时段的零部件的加工任务来进行集中调度的,没有考虑零部件之间的装配约束,这样的调度结果只能得到某个时段内的局部最优解。本文指出面向多订单的车间作业调度问题已不属于传统车间调度的范畴,其目标是考虑产品装配顺序约束下寻求多个订单生产作业调度的全局最优解,从而满足企业实施JIT生产策略、及时响应市场需求的要求。
示产品p中的零部件g,Jpv为产品p的零部件元素总数;φpgh表示产品p中零部件的父子关系,vph为vpg的父节,且Πvph、pg∈Vp时φrgh=1,其他v情况下φpgh=0;epgh为产品p的零部件之间的数量约束关系,表示产品p中部件vph需要由epgh个零部件vpg组成(仅当φpgh=1时),epgh为非负整数;Npg为产品p中零部件g的数量,假设E={epij|epij∈Ep且φpij=1}为零部件g的父辈数量关系集合,则有Npg=
e
∏e
∈E
pij
;Bpg为产品
pij
p中零部件g的所有工序集合,Bpg={bpgq|
1SP的描述及模型J
单件小批量生产企业的产品结构复杂,为多层次结构。多层次产品结构的产品BOM层级大于1,BOM中的部件与零件之间形成了装配中的父子优先关系。实际生产过程中大多是在每批零部件经过检验合格后才能进行装配加工,故仅考虑零件或部件的整体加工工艺而不考虑其装配工艺。对于本文讨论的问题,给出如下假定:①产品BOM结构、订单及其交货期已知;②各零部件的工序在不同资源上的加工时间已知,且同一工序在不同机床上的加工时间不等;③各设备资源间的物料运输时间已知。1.1问题描述现考虑订单中有多种产品,不同产品的零部件可以共享,零部件的加工工序可以在多个机床上以测定的时间完成,并且同一零部件的工序之间有强制性优先关系,同一机床在同一时段内仅能完成一道工序。对单件小批量生产进行作业调度时,一般要求最大化机床利用率,即缩短生产资源闲置时间。缩短闲置时间能降低作业车间的在制品库存水平,因此最小化因资源闲置产生的成本是综合优化的目标之一。另一个目标是要使所有产品的完成时间尽可能接近其交货期,若提前完成,会产生库存费用;若延期完成,则会受到客户的
经济惩罚。因此要在满足客户需求、减少在制品库存的同时,考虑多资源能力约束和因产品结构而产生的物料工序之间复杂的优先序约束。首先,引入以下用于描述研究对象的符号:Oi为不同的产品订单,Jo为订单数;Pi为订单Oi订购的产品集合,PiΑ{1,2,…,p},p为产品种类编号;Qi为Pi中各产品的订购数量,
Qi={Qip},Qip表示订单Oi中产品p的订购数
工工序,Jb为工序总数;Rpgq为可完成加工工序
bpgq的资源集合,Rpgq={rm|Πm∈(1,2,…,Jr)},rm表示加工资源,Jr表示可用资源总数;tmn
为资源rm与rn之间的运输时间;tpgqm为工序bpgq
在资源rm上的加工时间;Sipgqm、ipgqm分别为订单E
Oi中工序bpgq在机床rm上的开始加工时间、完成Oi的完成时间;Li为订单Oi的延期交货时间,用
时间;Cmax为作业工序的最大流通时间;Ci为订单
ceil(Li)表示Li的上取整后的值;Hi为订单Oi的
提前交货时间,用ceil(Hi)表示Hi的上取整后的值;LCi、Ci分别为订单Oi的延期和提前单位时H间的惩罚费用;I为资源闲置的时间成本。基于上述约定,最终作业车间调度的任务就是将这些带有订单信息且存在产品结构约束的工序加工任务分配到有限的生产资源上去,寻求最优调度方案。作业调度优化模型的建立敏捷制造策略以及JIT生产策略在企业的实施,使得考虑了提前-延期惩罚的作业车间调度
1.2
量;Di为订单Oi的交货期限;Vp为产品p的所有零部件集合,Vp={vpg|g=1,2