（机械电子工程专业论文）基于多品种小批量订货型的平行机分批调度方法研究.pdf

摘要 摘要 多品种小批量订货式生产在制造业中占据着很重要的地位。柔性制造单元( f m c ) 是用于多品种、中小批量生产的具有高柔性且自动化程度高的制造系统。近年来，许 多中心批量生产的企业已经将此单元应用在实际生产中。 交货期是订货型企业的生命线。在车间安排生产任务时，多难以兼顾多订单的交 货期要求。f m c 的生产环境下，为降低单元的使用成本，提高设备的利用率，可以将 不同订单的相同类型工件组成若干批次进行加工。组批和调度方案的好坏直接影响着 企业经济效益和声誉。因此，对这样的实际问题如何编制合理优化的组批调度方案是 非常有必要的。 本文以一家大型轮胎模具生产企业为背景，研究一类集成批量计划和平行机调度的 问题，该问题具有订单交货期、到达时间和n - r _ 准备时间等约束。首先在订单到达时 间确定的情况下，建立单个数学模型描述集成问题，以降低单元加工费用和订单拖期 惩罚费用为目标；提出一种带启发式规则的遗传模拟退火两阶段算法( g a s a ) 。算法 引入启发式规则生成基础批有效减少了染色体长度，从而加快搜索速度。遗传算法对 基础批进行全局搜索，在批量确定的情况下，模拟退火进行局部搜索，得到当前分批 情况下的优值。然后以此模具企业的实际生产例检验该算法的收敛性，证明该算法在 可以接受的时间内是有效可行的；通过对比g a s a 和g a 算法的求解效果，说明相比 于g a 算法，这种带启发式规则的混合算法确实能够更快更好的求得问题的较优解； 选取五种不同规模的实际生产例进行数值仿真，分别采用该算法和一种经典算法在相 同的计算时间内进行求解。对计算结果对比分析表明随着是任务规模的增大，该种算 法的优势更加明显，从而说明了该模型和算法针对这一类特殊问题更为有效和可行。 接着下一步，针对上述分批调度数学模型，考虑到实际生产中的订单到达时间不确定 因素，且订单的到达过程符合泊松过程，从而建立期望值模型，在随机变量的概率密 度函数已知的情况下，将问题模型按照确定性模型来处理，采用前文所提带启发式规 则的遗传模拟退火两阶段算法进行求解。通过大规模的数值仿真实验，证明该算法对 待订单到达时间不确定问题的求解同样有效，并且这一类问题的求解过对订程单到达 时间不敏感。最后，运用先进的建模和仿真工具e m p l a n t ，结合应用面向对象的方法， 进一步深入面向平行机的分批调度模型。利用e m p l a n t 中的s i m t a l k 语言对各个对象 广东工业大学硕士学位论文 及活动进行编程控制，还原现实生产环境。对比仿真模型运行结果和g a s a 结算结果， 证明g a s a 在现实生产中具有可行性。 关键词：分批；调度；遗传模拟退火两阶段算法；仿真 a b s t r a c t a bs t r a c t t h ep r o d u c t i o nm o d e l o f m u l t i v a r i e t y , s m a l lb a t c ha n dm a k et oo r d e r si sv e r yi m p o r t a n t i nt h em a n u f a c t u r ei n d u s t r y f l e x i b l em a n u f a c t u r i n gc e l li su s e di np r o d u c t i o nm o d e lo f m u l t i - v a r i e t ya n dm i d d l e - s m a l lb a t c h f m ci st h em a n u f a c t u r i n gs y s t e mw i t hh i g hf l e x i b i l i t y a n dh i g ha u t o m a t i o n i nr e c e n ty e a r s ，f m ci sa p p l i e di nt h em u l t i - v a r i e t ya n dm i d d l e s m a l l b a t c h sf a c t o r y d u et i m ei st h el i f e l i n eo f t h em a k et oo r d e re n t e r p r i s e i t sd i f f i c u l tt ot a k ei n t oa c c o u n t t h er e q u i r e m e n to f t h ed i f f e r e n to r d e rd e l i v e r yw h e nm a k i n gt h ew o r k s h o pp l a n i nt h e p r o d u c t i o ne n v i r o n m e n to ff m c ，i no r d e rt or e d u c et h ec o s t so f u n i ta n di m p r o v ee q u i p m e n t u t i l i z a t i o n , d i f f e r e n to r d e r sc a l lb ec o m p o s e do fs e v e r a lp a r t sw h i c hc o n t a i nt h es a m e t y p e ，a n dt h i sp a r t sc a nb ep r o c e s s e ds u c c e s s i v e l y t h ep r o g r a mo f b a t c h i n ga n ds c h e d u l i n g d i r e c t l ya f f e c t st h ee c o n o m i ce f f i c i e n c ya n dr e p u t a t i o no f e n t e r p r i s e s a l a r g et i r em o l dm a n u f a c t u r i n ge n t e r p r i s e s 嬲t h eb a c k g r o u n d ，a ni n t e g r a t e dp r o b l e m w a ss t u d i e df o rl o t - s i z i n gs t r a t e g ya n dp a r a l l e lm a c h i n e ss c h e d u l i n g ，i nw h i c ht h ec o n s t r a i n t s o fo r d e r sd u et i m e ，a r r i v a lt i m ea n ds e t u pt i m ew e r ec o n s i d e r e di nt h i sp a p e r a tf i r s t ，i nt h e e n v i r o n m e n to fo r d e r sa r r i v a lt i m ei sd e t e r m i n e d ，t or e d u c et h em a n u f a c t u r i n gc o s t sa n d t a r d i n e s sp e n a l t yc o s t s ，as i n g l em o d e lw a sb u i l tu pt od e s c r i b et h ew h o l ep r o b l e m a g e n e t i c - s i m u l a t e da n n e a l i n ga l g o r i t h mw i t hh e u r i s t i cr u l e s ( g a s a ) w a sp r o p o s e d t h e h e u r i s t i cr u l ew a si n t r o d u c e df o rs h o r t e nt h el e n g t ho fc h r o m o s o m ea n di n c r e a s i n gt h es e a r c h s p e e d l o t s i z i n gs t r a t e g yw a sd e r i v e dg l o b a l l yb yg e n e t i ca l g o r i t h m t h e nt h eo p t i m a l s c h e d u l e rw a ss e a r c h e db ys i m u l a t e da n n e a l i n ga l g o r i t h mi np r e s e n tl o t - s i z i n gs t r a t e g y s e c o n d l y , t oe x a m i n et h ee f f e c t i v eo fg a s a ，s o m er e a lp r o d u c t i o ne x a m p l e so ft h i sm o l d m a n u f a c t u r i n ge n t e r p r i s ew e r eu s e d t h er e s u l t s h o w st h a tt h ea l g o r i t h mi se f f e c t i v e c o n v e r g e n c ei nt h ea c c e p t a b l et i m e u n d e rt h es a m ec o m p u t i n gt i m e ，c o m p u t a t i o n a l s i m u l a t i o n sa n dc o m p a r i s o n sb a s e do nf i v ek i n d so fa p p l i c a t i o nc a s e sw i t hd i f f e r e n ts i z e s w e r ep r o v i d e d r e s u l t sd e m o n s t r a t e dt h a tt h ep r o p o s e da l g o r i t h mo b t a i n e db e t t e rr e s u l t so n t h el a r g e rs i z ep r o b l e m s i ti ss h o w no u tt h a tt h es c h e d u l i n gm o d e la n dt h ea l g o r i t h ma r e i l l 广东工业大学硕士学位论文 m o r er e l i a b l ea n de f f e c t i v e t h i r d l y , t h em a t h e m a t i c a lm o d e lf o rb a t c hs c h e d u l i n gw a sb u i l t u p ，a n dt a k i n gi n t oa c c o u n tt h ea r r i v a lt i m eo fo r d e r si np r o d u c t i o ni su n c e r t a i n l yi nr e a l p r o d u c t i o ne n v i r o n m e n t t h er e s e a r c hs h o w st h a tt h ep r o c e s so fo r d e r s a r r i v a lc o n s i s t e n t w i t hap o i s s o np r o c e s s i nt h ee n v i r o n m e n to ft h ep r o b a b i l i t yd e n s i t yf u n c t i o no fr a n d o m v a r i a b l e sw a sc u r t a i n e d ，e x p e c t a t i o n sm o d e lw a se s t a b l i s h e d s ot h em o d e lc a nd e a lw i t ha sa d e t e r m i n i s t i cm o d e l t h i sp r o b l e mc a nh es o l v e db yg a s aw h i c hm e n t i o n e d t h r o u g h l a r g e s c a l en u m e r i c a ls i m u l a t i o ne x p e r i m e n t s ，t h er e s u ks h o w st h a ti t se f f e c t i v et os o l v et h e p r o b l e mo fo r d e r s a r r i v a lt i m eu n c e r t a i n l yb yg a s a p r o b l e ms o l v i n gp r o c e s si s n o t s e n s i t i v et ot h eo r d e r s a r r i v a lt i m e a tl a s t ，t h es i m u l a t i o nm o d e lw a sb u i l tu pb y a d v a n c e dm o d e l i n ga n ds i m u l a t i o nt o o l sn a m e de m - p l a n tw i t ht h em e t h o do fo r i e n to b j e c t i no r d e rt or e s t o r et h er e a lp r o d u c t i o ne n v i r o n m e n t ，e v e r yo b j e c ta n da c t i o nc o n t r o l l e db y s i m t a l ki ne m - p l a n t i ti ss h o w no u tt h a tt h eg a s aa l g o r i t h ma r em o r er e l i a b l ea n d e f f e c t i v ei nt h er e a l i t yt h r o u g ht h er e s u l to fr u n n i n gt h es i m u l a t i o nm o d e la n dc o m p u t e rb y t h en u m e r i c a ls i m u l a t i o n k e yw o r d s ：l o t s i z i n g ；s c h e d u l i n g ；g a s a ；s i m u l a t i o n 广东工业大学硕士学位论丈 c o n t e n t s a b s t r a c t ( i nc h i n e s e ) i a b s t r a c t ( i ne n g l i s h ) i i i c o n t e n t s ( i nc h i n e s e ) j 1 ， c o n t e n t s ( i ne n g l i s h ) v i i i c h a p t e r1i n t r o d u c t i o n 1 1 1r e s e a r c ho r i g i n 1 1 2b a c k g r o u n do f r e s e a r c h 1 1 2 1i n t r o d u c t i o no f m u l t i - v a r i e t y , s m a l lb a t c ha n do r d e r 1 1 2 21 1 1 ea p p l i c a t i o n so f t h ef m c 2 1 2 3i n t r o d u c t i o no f w o r k s h o ps c h e d u l ep r o b l e m 3 1 2 4t h er e s e a r c hp r o b l e mo f p a p e r 一5 1 3t h er e s e a r c hs t a t u sa th o m ea n da b r o a d 6 1 3 1b a t c hs c h e d u l i n ga l g o r i t h mf o rp a r a l l e lm a c h i n e s 6 1 3 2i n t e l l i g e n to p t i m i z a t i o na l g o r i t h m 8 1 4g e n e r a lo v e r v i e w o f p a p e 9 1 4 1r e s e a r c ht a r g e t 9 1 4 2r e s e a r c ho b j e c t i v e s 9 1 4 3c h a p t e r sa r r a n g e m e n t 1 0 c h a p t e r2p a r a l l e lm a c h i n e sb a t c hs c h e d u l i n gb a s e d o ng a s a 1 l 2 1i n t r o d u c t i o n 1l 2 2p r o b l e md e s c r i p t i o n 11 2 3m a t h e m a t i c a lm o d e l 13 2 3 1m o d e l a s s u m p t i o n s 1 3 2 3 2m a t h e m a t i c a ld e s c r i p t i o n 1 3 2 4g a s a 1 6 2 4 】i n t r o d u c t i o no f g aa n ds a 1 6 v l l c o n t e n i s 2 4 2h e u r i s t i ca l g o r i t h mb a s e do nr u l e 18 2 4 3c h r o m o s o m ec o d i n gr u l ea n dg e n e r a t ei n i t i a lp o p u l a t i o n 19 2 4 4i n d i v i d u a la s s e s s m e n t 2 0 2 4 5s e l e c t i o na l g o r i t h m 2 0 2 4 6c r o s s o v e r 2 1 2 4 7v a r i a t i o n 2 1 2 4 8s a 2 2 2 5s u m m a r y 2 2 c h a p t e r31 1 圮r e s e a c ho f a l g o r i t h mc o m p r i o n 2 4 3 1i n t r o d u c t i o n 2 4 3 2c o n v e r g e n c ev e r i f i c a t i o no fg a s a 2 4 3 2 1e x a m p l e sd a t a s 2 4 ：；2 2c a l c u l a t i o nr e s u l t s 2 6 3 3c o m p a r i s o na n da n a l y s i sb e t w e e ng a s aa n dg a 2 7 3 4c o m p a r i s o na n d a n a l y s i sb e t w e e ng a s a a n db b a 3 1 3 4 1i n t r o d u c t i o no f b b a 3l 3 4 2c a l c u l a t i o na n d a n a l y s i s 3 2 ：；5s u m m a r y 3 4 ” c h a p t e r4 p a r a l l e lm a c h i n e sb a t c hs c h e d u l i n gb a s e do na r r i v a lt i m eu n c e r t a i n 3 5 4 1i n t r o d u c t i o n 3 5 4 2p o i s s o np r o c e s s 3 5 4 2 1c o n c e p to f p o i s s o np r o c e s s 3 5 4 2 2c o n d i t i o n a ld i s t r i b u t i o no f a r r i v a lt i m e 3 7 4 2 3a p p l i c a t i o n so f p o s s i o n 3 7 4 3p r o b l e md e s c r i p t i o n 3 7 4 4m a t h e m a t i c a lm o d e l 3 8 4 4 1c o n c e p to f e x p e c t e dv a l u em o d e l 3 8 4 4 2e x p e c t e dv a l u em o d e lb u i l tu p 3 9 4 5s i m u l a t i o ne x p e r i m e n t 4 0 4 5 1e x a m p l ed a t a s 4 0 l 广东工业大学硕士学位论文 4 5 2r e s u l t sa n da n a l y s i s 4 2 4 6s u m m a r y 4 4 c h a p t e r5b a t c hs c h e d u l es i m u l a t i o nm o d e lb a s e d o ne m - p l a n t 4 5 5 1i n t r o d u c t i o n 4 5 5 2b a t c hs c h e d u l es i m u l a t i o nm o d e l 4 6 5 2 1b a s i cr e s o u r c e si nm o d e l 4 5 5 2 2f u n c t i o nm o d u l e sa n da c h i e v e m e n t 5 0 5 3e x a m p l eo f b a t c hs c h e d u l e 5 4 5 3 1e x a m p l ed a t a s 5 4 5 3 2r e s u l t sa n da n a l y s i s 5 7 5 4s u r m n a r y 5 9 s u m m a r ya n dp e r s p e c t i v e 6 0 s u m m a r y 6 0 p e r s p e c t i v e 6 1 r e f e r e n c e 6 2 p a p e rl i s t 6 5 o r i g i n a lc r e a t i o na n n o u n c e m e n t ，6 6 a c k n o w l e d g e m e n t s 6 7 p 巾p e n d i x i 6 8 a p p e n d i x l i 6 9 a 巾p e n d i x l i i 7 0 x 第一章绪论 1 1 课题来源 第一章绪论 课题来源于陈庆新教授和毛宁教授主持或主要参与的多个研究项目，包括：国家 自然科学基金( 编号：5 0 6 7 5 0 3 9 ，5 0 8 7 5 0 5 1 ) ；广东省教育部产学研结合重大科技专项 面向模具、装备定制型离散制造业信息化服务平台关键技术研发及示范应用( 编号： 1 0 1 2 2 1 1 5 0 0 2 2 0 ) 。 1 2 研究背景 1 2 1 多品种小批量订单式生产问题概述 制造业是工业的主体，是一个国家国民经济的依托，是经济持续发展的动力。制 造业一直是工业发达国家国民经济的支柱产业。 。 由于市场的竞争日渐变得激烈，企业为赢得客户和市场占有率，往往在价格：质 量和交货速度上狠下功夫。随着新技术的发展和应用，许多企业为了提升自身的竞争 力，开始从原先的备货式生产方式转向订单式( m a k et oo r d e r ，m t o ) 生产方式；于 此同时，顾客需求的个性化、易变性也驱动企业从单一、大批量的生产模式向多品种、 小批量的生产模式转换。某些产品( 如模具) 生产方式的特殊性，决定了其制造商必 须采取这种多品种小批量订单式的生产模式。据统计，多品种小批量生产条件下生产 的产品约占全世界产品总量的7 0 ，在我国，机械行业中的9 0 左右的企业属于多品种 小批量生产，其总产值约占整个机械行业的7 5 。可见，多品种小批量生产在生产业 中占据着很重要的地位。 交货期是订货型企业的生命线。由于订单的随机性和在制品种类较多的因素，因 此与大批量生产相比，订货式生产的计划稳定性较差。多品种小批量生产般每种产 品产量较少，品种繁多，专业化程度不高，这些产品大多属于一次性生产的产品，通 广东工业大学硕士学位论文 常只生产少数几件，而且大部分产品今后不再重复生产，即使重复也无确切的时间。 所以在车间安排生产任务时，多难以兼顾多订单的各自交货期要求，从而产生订单拖 期的惩罚费用，提高了产品的制造成本，而且会影响企业的声誉。 用最低的消耗创造满足社会市场需求的产品不仅是企业自身生存和盈利的前提， 还应将是企业的社会责任和义务。因而，资源的获取、转换和分配成为了制造企业经 营活的主要内容，而资源获取、转换和分配是通过计划与控制来完成的，从而使计划 与控制成为了制造企业的核心。 车间批量生产在多品种小批量订单式企业中具有普遍性，车间优化调度问题尤其 是批量调度技术关系到企业的生存和前途。有效地生产排程方法与优化技术的研究和 应用已成为先进制造业发展的基础和关键。 1 2 2 柔性制造单元( f m c ) 在实际生产中的应用 柔性制造单元( f l e x i b l em a n u f a c t u r i n gc e l l 缩写f m c ) 是由一台或数台数控机床 或加工中心构成的加工单元。在各机床、装卸站、缓冲站之间存在运送零件和刀具的 传送系统。柔性制造单元主要由托盘、运输带、有轨小车( r g v ) 、无轨小车( a g v ) 、 加工中心、机器人等单项或多项装置组成。 在生产活动中，车间操作人员需要在装卸站将工件放置在托盘上。托盘和缓冲区 紧密相连，托盘是加工工件的载体，而缓冲区也是托盘的载体。每个托盘上放置央具， 用于固定工件以便于加工。由于产品种类的多样化，因此不同种类的工件就需要有适 应各自类型的夹具。当指令发出后，机器人会从缓冲区内抓取托盘( 前提为该托盘上 已经放置待加工工件) ，送至指定机床装夹、加工。工件的工艺过程通过n c 程序实现。 由于柔性制造单元配有集中刀库( 某些单元内的机床自身带有刀库) ，在加工过程中可 以实现自动换刀，由n c 程序控制。 柔性制造单元是用于多品种，中小批量生产的具有高柔性且自动化程度高的制造 系统。产品生产批量的增加和市场竞争的加剧使得产品更新速度大大加快，这就要求 产品制造产商具有快速应变能力。柔性制造单元具有高度柔性和自动化的加工能力， 适应了产品快速变化的要求。近年来，随着柔性制造单元技术的飞速发展己同渐成熟， 购置柔性制造单元硬件设备的成本也大大降低，许多中小批量生产的企业已经将此单 元应用在实际生产中。 第一章绪论 缓冲区 人r l 一水! f 方向 - ”水! f 力i 司 1 2 3 车间调度问题概述 机眯3 漱叠啊咖咖咖 装载站 图1 。1 柔性制造单元示意图 f i g 1 - 1s c h e m a t i cc h a r to ff m c 所谓生产调度( s c h e d u l i n g ) ，就是组织并且执行生产进度计划的工作。生产调度以 生产进度计划为依据，生产进度计划要通过生产调度来实现。调度产生的原因在于多 项任务共享特定的资源，而有限的资源却无法以相对于各个单独任务的最优状态同时 满足所有任务的处理需求，同时需要寻求一种优化其中一部分或者整批任务的某种处 理性能指标的方案。 车间调度问题一般可以描述为：生产车间有m 台机床种工件，每种工件有m 个， 且每种工件有多道工序，每道工序可在多台性能不同的机床上加工。问如何为这些工 件分配机床，使某个生产指标( 如制造成本) 最优。简而言之，车间调度就是对一些 可用的加工机床在时问上进行任务排序和任务分配，从而可以达到一个性能指标集。 从数学规划的角度看，车问调度问题可表达为在等式或不等式约束下，对目标函数的 优化。 调度问题可以分为经典调度( c l a s s i c a ls c h e d u l i n g ) 和现代调度( m o d e r ns c h e d u l i n g ) 。 根据e l a w l e r 等的观点，经典调度问题有如下三个基本假设：1 ) 确定性：所研究的 调度问题所需的输入参数必须是完全确定的，而且是静态的；2 ) 资源的类型。类似的 假设比如一台机床最多只能同时加工一个工件，并且一个工件同时也最多只能被一台 机床加工；3 ) 可运算性：在川。以运算的程度上研究经典调度问题，4 i 去考虑交货期的 蜘幽一藕 广东工业大学硕士学位论丈 变更、加工时间的变更、机器发生故障及人员变更等动态状况。 由于实际生产的需要，在不同的机器上装夹和更换加工设备时，需要一定的准备 时间，这是车间调度问题的一个特点。为了减少工件的库存，常采用提高切换加工次 数的方法，但是这种做法会导致生产率下降。所以，如何在库存成本和工件切换加工 频率之间取得平衡，非常有必要。 影响车间调度的因素有很多，常见的有：产品交货期，生产能力，加工顺序，加 工设备状况，加工路径，批量划分以及成本等，这些因素都是约束条件。为了提高企 业的声誉，某些约束条件必须满足，比如交货期等。而有些为了提高企业的经济效益， 对某些约束也要达到一定的满意度，比如生产成本等。进行调度时也要将一些因素作 为非确定性因素考虑，比如设备故障，生产任务变化等情况。 在早期对调度问题的研究方法中，大多数是集中在数学规划、仿真以及一些简单的 规则上，但是这些方法的调度结果往往不理想，有些甚至是无法解决一些复杂的调度 问题的。经过5 0 多年的发展，车间调度方法已经有了长足的进步。特别是随着各种新 的相关学科和优化技术的建立与发展，许多新的调度方法相继出现，类似基于计算智 能、人工智能和实时智能的各种调度方法，都已经成为调度方法的主流n 1 。 数学规划法在车间调度中应用的非常广泛，调度问题可以用整数规划法、混合整 数规划法和动态规划法来描述。从数学规划的角度，车间调度问题可以用以下语言描 述：在等式约束或者不等式约束下，优化目标为一个或者多个目标函数。但是调度问 题属于n p 问题，计算的复杂性使得数学规划方法的应用一直受到限制。随着新的解决 技术、更强有力的启发式规则的发展和现代计算机所提供的计算机能力的提高，才使 得这些方法重新得到重用。 鉴于易实现、计算复杂度低等原因，调度规则经常用于动态实时调度系统中，而 且一直吸引学者们的研究兴趣，许多调度规则推陈出新。其中p a n w a l k a rse ta 在文献 【3 中总结、叙述了1 1 3 条规则，这1 1 3 条规则基本可以分为简单规则、复杂规则和启 发式规则三类。m o n t a z e r im e ta 在文献 4 】中列举了常见的2 0 条规则，通过一个f m s 的实例，分析了这2 0 条规则对系统性能的影响，比如机床的平均利用率、作业的平均 等待时间、作业总加工时间等指标。调度系统的性能取决于规则的选择，因为启发式 规则的全局敏感性。所以在利用不同的规则产生不同的调度方案的同时，可以看到相 同的规则在不同的场合所起的作用也不同。 邻域搜索技术应用的也是非常广泛。邻域搜索技术常常用可以求得理想的结果， 4 第一章绪论 若是结合其他的启发式算法应用，甚至会有更好的效果。在这一类技术当中，应用最 为普遍的是遗传算法( g e n e t i ca l g o r i t h m s ) 、禁忌搜索( t a b us e a r c h ) 、模拟退火 ( s i m u l a t e da n n e a l i n g ) 。这些方法都有自己独特的添加干扰技术、停止搜索规则和防 止局部最优等功能。 在混合调度方法中，模糊逻辑理论的应用得到广泛共识。模糊逻辑理论主要用来 解决车间调度问题中的某些不确定性参数，比如加工时间、准备时间、运输时间等。 这些不确定性可以用模糊数据来表示。t s u j i m u r ae ta 在文献 5 】中建立一个混合调度系 统，在该系统中通过模糊理论为流水车间中的加工时间建模，并且采用三角模糊数 ( t r i a n g u l a rf u z z yn u m b e r s ) 来表示加工时间，用两个三角模糊数来定义每一个工件， 一个定义为下界，一个定义为上界。 1 2 4 本文研究问题 j b 本论文所依托课题合作企业是一家轮胎模具企业，该企业具有传统模具企业的共 性，是典型的多品种小批量面向资源的工程订货型生产方式，完全按订单生产，某些 订单具有相同的产品，而且制造精度要求高。同时，这家企业的产品极具特点，某一 重要部件的零件具有标准件的特征，而且这些零件生产模式趋于多品种小批量生产方 式。该公司已装备一个柔性制造单元( f m c ) ，该单元由四台加工中心、工业机器人和 物料运输储存装置组成。交货期不同的不同订单具有相同类型的零件，根据柔性制造 单元的实际生产能力成组加工这些零件，以达到节约成本，提高生产效率的效果。 面向柔性制造单元( f m c ) 的实际生产中大多数生产是按批量完成，而在经典作 业车间调度中假设每种工件只有一件，这种假设限制了经典调度问题在实际车间计划 调度中的应用。通过实际调研该模具厂的生产现场可知，按照先到先加工的顺序生产 方式不仅会导致大量设备闲置，而且会使得大量订单的交货期延误。因此，考虑将这 些订单的工件分成不同的批次加工可以避免上述问题。但是，分批结果产生的批次数 量、每批次包含的工件数量以及不同批次的加工顺序也都会影响到设备利用率和生产 管理方式，甚至是订单的履约率等。类似于当批次的数量多时( 每批包含的工件数量 越少) ，不同批次间加工的准备时问增加，同时生产管理更为复杂；批次越少，则设备 限制时间越长，则可能造成大量订单的拖期。如何合理安排工件数量和批次问题，就 是所谓的分批调度问题。 广东工业大学硕士学位论文 本论文所研究的是一个集成批量计划和平行机调度的问题，并且希望采用单个模 型来描述整个集成问题。此平行机批量调度问题具有一定的特殊性：在f m c 生产环境 中，对所有订单内的工件组批加工需考虑工件毛坯的到达时间和加工准备时间的约束； 一个订单内工件将可能拆分成多个批次加工，一个批次内将会包含不同订单的工件； 从满足订单交货期并提高资源利用效率，最终降低生产成本的角度，对所划分的批次 进行车间任务调度。批次划分的特殊性对加工顺序提出更高的要求。 问题重点考虑同一个批次中工件具有不同达到时间和交货期，以及不同批次工件 共享相同的到达时间和交货期的调度状况( 根据生产实际情况对该问题中订单的到达 时间分为确定及不确定两种情况分别考虑) 。 1 3 平行机批量调度及智能算法的研究现状 1 3 1 平行机批量调度国内外研究概述 在生产调度的理论和应用研究中，平行多机调度问题得到了很多人的关注，这些 研究多集中在讨论总完工时间和最大延误时间这两个问题上。文献 6 和文献 7 重点 考虑在并行机成组调度的问题中，不同组工件连续加工需要的装夹时间，文献以解决 调度问题为主，对成组的策略考虑略少。 同时考虑交货期和准备时间的平行机调度问题，在国外也引起了学者们的研究兴 趣。文献 8 针对考虑加工准备时间和交货期约束的平行机调度问题，调度目标为任务 加权总完工时间最少，提出一种调度方法a t c s r ( a p p a r e n tt a r d i n e s sc o s tw i t hs e t u p s r u l e ) 。该规则在调度过程中允许部分机器空闲一定时间，为之后到达优先级别高的生 产任务做准备。在此文献中，文章作者假设订单是同一时间到达的，并且未从任务组