（系统工程专业论文）面向单元制造企业的单元构建和调度方法的研究.pdf

，r 。、： ad i s s e r t a t i o nf o rt h ed e g r e eo fd o c t o ri ns y s t e m se n g i n e e r i c e l lf o r m a t i o na n d s c h e d u l i n g f o rc e l l u l a rm a 1 n e n t e r p r i s e s b yw a n gx i a o q i n g s u p e r v i s o r ：p r o f e s s o rt a n gj i a f u n o r t h e a s t e r s nu n i v e r s i t y m a y 2 0 0 9 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的 研究成果除加以标注和致谢的地方外，不包含其他人已经发表或撰写过的 研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示诚挚 的谢意。 学位论文作者签名： 签字e t期 ： 炒厂一- 7 卅_ ， 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名：否则视为不同意) 学位论文作者签名： 脚舞 j 导师签名： 签字 日 期，：砂歹一7 0 签字日期：纱吖一7 ，乞i 一一 叁 东北大学博士学位论文 摘要 面向单元制造企业的单元构建和调度方法的研究 摘要 随着少量生产、多样化消费时代的到来，制造企业面临着产品生命周期和交货期进 一步缩短、产品种类逐渐增多、个性化要求不断提高等问题的考验。在这种情况下，如 何保证并不断提高生产效率、快速反应不断变化的市场需求成为制造企业在日趋激烈的 市场竞争中占领世界市场最有力的战略武器和立于不败之地的关键。单元生产方式是随 需而变的生产方式，综合了单件生产的高柔性与大批量生产的高效率的优点，并克服了 单件生产成本高和批量生产过度刚性的缺点，使制造系统达到了效率和柔性的统一，使 企业组织内实现了自律和自主的统一。目前单元生产方式已经越来越受到人们的重视。 实践证明，单元生产系统具有在制品库存少、成品库存少、订单响应时间短、运输时间 短、设备调整时间短、以及生产费用低等优点。 目前我国绝大多数制造企业采用大批量生产的粗放经营方式，过分关注生产产量， 忽略了多品种小批量的市场需求，且忽视了这种大批量生产方式下存在的库存、人力、 物料、时间、空间和搬运等大量浪费。这导致了企业在成本和交付以及质量方面都存在 巨大压力，难以适应当今买方市场的新特点，缺乏竞争力。为此，通过生产革新和生产 方式的改造，来建立因需而变的满足个性化需求的单元生产系统，是国内制造企业向集 约化经营迈进，提升企业核心竞争力，保持与世界先进制造水平同步的重要途径。 作为国家杰出青年科学基金和国家创新研究群体科学基金的重要组成部分，本文以 离散制造企业单元生产方式的实施和运作为研究背景，在对单元生产方式研究现状，特 别是单元构建和调度问题进行深入分析的基础上，研究了单元生产方式实施和运作过程 中的单元构建和调度的若干重要问题。本文的研究成果及核心内容主要有以下五个方 面： ( 1 ) 研究了市场需求变化情况下生产单元内部配置可调整的多周期多目标动态单 元构建问题。考虑了设备重置费用、设备利用率和零部件跨单元移动数目， 提出了非线性多目标动态单元构建的数学模型。根据问题和模型的特点，开 发了一种基于启发式的分散搜索算法。该算法采用了多样性产生方法、全局 判断方法和参考集更新方法等多种改进机制来实现单元生产系统的动态构 建。 一i i i 一 |0r。 东北大学博士学位论文 摘要 ( 2 ) 研究了设备冗余情况下的多周期多目标动态单元构建问题。考虑了同一计划期 内多个生产单元中可能存在相同类型设备的情况，通过对单元生产构建过程 中的总费用、设备负载与能力之间最大偏差以及零部件跨单元移动数目这三 个目标进行权衡，建立了该问题的非线性多目标数学规划模型。采用自适应 小生境技术、惩罚技术、双轮盘赌法和精华选择策略，提出了基于精华保留 策略的随机权重多目标遗传算法来求解设备冗余情况下的多目标动态单元构 建问题。 ( 3 ) 研究了单元制造环境中零部件生产工艺不相同情况下零部件跨单元生产的调 度问题。分别以最小化单元制造系统的总生产时间和拖期惩罚为目标，对单 元内设备上的零部件进行生产调度，提出了该问题的非线性数学规划模型， 开发了针对该问题的分散搜索算法。该算法改进了多样性产生器，使算法生 成一系列多样性好的初始解，并针对该零部件调度问题的特点，开发了参考 集更新方法、子集产生方法、子集合并和解改进方法等多种机制来实现对单 元制造系统中零部件调度的有效管理。 ( 4 ) 研究了单元构建和调度的联合决策问题，以最小化单元制造系统的总拖期费用 为目标，建立了嵌入计算规则的整数规划模型。为了有效地求解该模型，提 出了基于启发式的拉格朗日松弛分解算法。采用该算法将联合决策问题分解 为单元构建子问题和单元调度子问题。对单元构建子问题进行线性化，并采 用c p l e x 进行求解；同时采用分散搜索算法求解单元调度子问题。通过合并 拉格朗日乘子，使调度子问题在对零部件进行生产调度时考虑到设备和零件 族在单元中的分配情况，以此来求解单元构建和调度的联合决策问题。 ( 5 ) 研究了设备冗余情况下的单元构建和调度的联合决策问题。考虑了单元生产系 统中每种设备和零部件数量为多个、零部件分批量调度的情况，为该联合决 策问题建立了包含整数变量和连续变量的非线性数学规划模型。为了有效地 求解该模型，提出了一个嵌入调度规则的分散搜索算法，该算法引入了一个 合并的调度规则，考虑了两种不同的合并方法和改进方法，扩充了分散搜索 算法的框架来更好的适应该联合决策问题。提出的算法对整数变量进行搜索， 并采用合并调度规则来求解整数解对应的调度子问题。最终通过该分散搜索 算法求解了这个设备冗余情况下的单元构建和调度的联合决策问题。 关键词：单元生产；单元构建；单元调度；优化模型；亚启发式；分散搜索；遗传算法 一一 t l - _ ， j ， 东北大学博士学位论文 a b s t r a c t c e l lf o r m a t i o na n ds c h e d u l i n gf o rc e l l u l a r m a n u f a c t u r i n g e n t e r p r i s e s a bs t r a c t s h o r tp r o d u c t i o nl i f ec y c l e s ，s h o r td e l i v e r yt i m e s ，h i g i lp r o d u c t i o nv a r i e t y , a n dd i v e r s e c u s t o m e rn e e d sh a v ec h a l l e n g e dm a n u f a c t u r e r st oi m p r o v et h e i rp r o d u c t i o ne f f i c i e n c ya n d m e e tc h a n g i n gm a r k e td e m a n d sq u i c k l yf o rh o l d i n gas o l i dm a r k e ts h a r ei nt h ef i e r c e c o m p e t i t i o n c e l l u l a rm a n u f a c t u r i n gi sal e a nm a n u f a c t u r i n ga p p r o a c ht h a ti n t e g r a t e st h eh i 曲 f l e x i b i l i t yo fi n d i v i d u a lp r o d u c t i o na n dt h eh i g l le f f i c i e n c yo fm a s sp r o d u c t i o n , a n dr e d u c e s t h ec o s to fi n d i v i d u a lp r o d u c t i o na n dt h er i g i d i t yo fm a s sp r o d u c t i o n c e l l u l a rm a n u f a c t u r i n g i n c o r p o r a t ee f f i c i e n c ya n df l e x i b i l i t y , a n dd e v e l o p ss e l f - d i s c i p l i n ea n di n d e p e n d e n c ei na n e n t e r p r i s eo r g a n i z a t i o n c u r r e n t l y , c e l l u l a rm a n u f a c t u r i n gi sb e c o m i n gm o r ea n dm o r e p o p u l a r r e p o r t e db e n e f i t so ft h ei m p l e m e n t a t i o no fc e l l u l a rm a n u f a c t u r i n gs y s t e m si n c l u d e r e d u c t i o n si n w o r k - i n - p r o c e s s ，f i n i s h e dg o o d si n v e n t o r y , r e s p o n s e t i m et oo r d e r s ， t r a n s p o r t a t i o nd i s t a n c e t i m e ，s e t u pt i m ea n dp r o d u c t i o nc o s t c u r r e n t l y , m o s tp r o d u c t i o ne n t e r p r i s e s i nc h i n ae n g a g ei ne x t e n s i v e m a n a g e m e n t p r o c e d u r e s ，w h i c hf o c u so ni m p r o v i n gp r o d u c t i o no u t p u t b u tt h ee n t e r p r i s e si g n o r et h eh u g e w a s t eo fi n v e n t o r y , l a b o r , m a t e r i a l ，t i m e ，s p a c ea n dt r a n s p o r t a t i o ni nt h et r a d i t i o n a lm a s s p r o d u c t i o n ，w h i c hm a k et h e md i f f i c u l tt oc o p e 谢t ht h o s ep r o b l e m su n d e rt h ec o n s i d e r a b l e p r e s s u r eo fc o s t ，d e l i v e r ya n dq u a l i t y h e n c e ，c h i n ac o m p a n i e sa r er e q u i r e dt oe s t a b l i s ha f e a s i b l ec e l l u l a rp r o d u c t i o ns y s t e mt oi m p l e m e n tt h ei n t e n s i v em a n a g e m e n t ，e n h a n c ec o r e c o m p e t i t i v e n e s sa n dk e e pp a c e 、 ，i t l lt h ew o r l d sl e a d i n gm a n u f a c t u r i n gc o m p a n i e s t h i sr e s e a r c hw a sf i n a n c i a l l ys u p p o r t e db yn a t i o n a ls c i e n c ef u n df o rd i s t i n g u i s h e d y o u n gs c h o l a r sa n di n n o v a t i v er e s e a r c hg r o u p s t h eb a c k g r o u n do ft h i sd i s s e r t a t i o ni st h e i m p l e m e n t a t i o na n do p e r a t i o no fc e l l u l a rm a n u f a c t u r i n gs y s t e m sf o rd i s c r e t em a n u f a c t u r i n g e n t e r p r i s e s b a s e do na n a l y z i n gt h er e s e a r c hs t a t u sq u oo fc e l l u l a rm a n u f a c t u r i n g ，e s p e c i a l l y f o rc e l lf o r m a t i o na n ds c h e d u l i n gp r o b l e m ，t h i sd i s s e r t a t i o ns t u d i e ss e v e r a lc r u c i a lp r o b l e m s o nc e l lf o r m a t i o na n ds c h e d u l i n g t h em a j o rr e s e a r c hr e s u l t so ft h i sd i s s e r t a t i o nf a l l s0 1 1f i v e a s p e c t sa sf o l l o w s ： ( 1 ) am u l t i - p e r i o d ，m u r i - o b j e c t i v ed y n a m i cc e l lf o r m a t i o np r o b l e m 、) r i t ha l t e r a b l ec e l l c o n f i g u r a t i o nu n d e rv a r y i n gm a r k e td e m a n d se n v i r o n m e n t i ss t u d i e d m a c h i n e r e l o c a t i o nc o s t ，u t i l i z a t i o nr a t eo f m a c h i n ec a p a c i t ya n dt o t a ln u m b e ro fi n t e r - c e l l m o v e sa r ec o n s i d e r e d ，a n dan o n l i n e a rm u l t i o b j e c t i v em a t h e m a t i c a lp r o g r a m m i n g v 一 厂= 盘奎二二i i n c l u d e sd i v e r s i f i c a t i o ng e n e r a t i o nm e t h o d ，g l o b a lc r i t e r i o nm e t h o d ，r e f e r e n c es e t u p d a t em e t h o da n do t h e ri m p r o v e m e n tm e t h o d st of o r ma l t e r a b l em a n u f a c t u r i n g c e l l s ( 2 ) am u l t i - p e r i o d ，m u l t i o b j e c t i v ed y n a m i cc e l lf o r m a t i o nw i t hm a c h i n e sd u p l i c a t i o ni s s t u d i e d c o n s i d e r i n gs a m et y p em a c h i n e sa s s i g n e di ns e v e r a lc e l l si no n ep e r i o d ，a n o n l i n e a rm u l t i o b j e c t i v em a t h e m a t i c a lm o d e lo ft h ea d d r e s s e dp r o b l e mi sb u i l tb y w e i g h i n gt h et h r e eo b j e c t i v e si n c l u d i n gt h et o t a lc o s ti n t h ep r o c e s so fc e l lf o r m a t i o n , m a x i m u md e v i a t i o no fw o r k l o a df r o ma v a i l a b l ec a p a c i t i e so fm a c h i n e s ，a n dt o t a l n u m b e ro fi n t e r - c e l lm o v e s u s i n ga d a p t i v en i c h et e c h n i q u e ，p e n a l t yt e c h n i q u e ， d o u b l er o u l e t t ew h e e lm e t h o d , a n dr e s e r v i n ge l i t e s t r a t e g y , ar a n d o mw e i g h t m u l t i o b j e c t i v eg e n e t i ca l g o r i t h mb a s e do nt h er e s e r v i n ge l i t ei sd e s i g n e df o rs o l v i n g t h em u l t i o b j e c t i v ed y n a m i cc e l lf o r m a t i o np r o b l e mw i t hm a c h i n e sd u p l i c a t i o n ( 3 ) ap a r t ss c h e d u l i n gp r o b l e mi nc e l l u l a rm a n u f a c t u r i n gs y s t e mc o n s i d e r i n gp a r t sw i t h d i f f e r e n t p r o c e s sr o u t i n g s i nm u l t i p l ec e l l si ss t u d i e d t od e v e l o pp r o c e s s i n g s e q u e n c e sf o rt h ep a r t si nc e l l s ，t w on o n l i n e a rm a t h e m a t i c a lp r o g r a m m i n g m o d e l so f t h ep r o b l e ma r ep r o p o s e dr e s p e c t i v e l yw i t ht h eo b j e c t i v eo fm i n i m i z i n gt h ef l o w t i m ea n dt a r d i n e s sp e n a l t yi nac e l l u l a rm a n u f a c t u r i n gs y s t e m as c a t t e rs e a r c h a p p r o a c hf o rt h ep r o b l e mi sd e v e l o p e d ，w h i c hi m p r o v e sd i v e r s i f i c a t i o ng e n e r a t o rt o g e n e r a t eac o l l e c t i o no fd i v e r s ei n i t i a ls o l u t i o n s ，a n dd e v e l o p st h er e f e r e n c e s e t u p d a t em e t h o d ，s u b s e tg e n e r a t i o nm e t h o d ，s o l u t i o n c o m b i n a t i o nm e t h o da n d i m p r o v e m e n tm e t h o df o rt h ep a r t ss c h e d u l i n gp r o b l e m ( 4 ) aj o i n td e c i s i o no fc e l lf o r m a t i o na n dc e l ls c h e d u l i n gi nac e l l u l a rm a n u h c t u r i n g s y s t e mi ss t u d i e d a ni n t e g e rp r o g r a m m i n gm o d e li n c l u d i n gac o m p u t a t i o n r u l ef o r t h ej o i n td e c i s i o np r o b l e mi sp r o p o s e dw i t ht h eo b j e c t i v eo fm i n i m i z i n gt h et o t a l t a r d i n e s s p e n a l t yc o s t t o s o l v et h em o d e le f f e c t i v e l y , al a g r a n g er e l a x a t i o n d e c o m p o s i t i o nm e t h o dw i t hh e u r i s t i ci sd e v e l o p e d u s i n gt h em e t h o d ，t h ea d d r e s s e d p r o b l e mi s s o l v e db yd e c o m p o s i n gi n t ot w os u b - p r o b l e m s ，i e c e l lf o r m a t i o n s u b p r o b l e ma n dc e l ls c h e d u l i n gs u b p r o b l e m a f t e rl i n e a r i z i n g t h em o d e lo fc e l l f o r m a t i o ns u b p r o b l e m ，i ti ss o l v e db yt h eo p t i m i z e rc p l e x as c a t t e rs e a r c h a p p r o a c hi sd e v e l o p e dt os o l v ec e l ls c h e d u l i n gs u b - p r o b l e m c o m b i n e dw i t ht h e l a g r a n g em u l t i p l i e r s ，c e l ls c h e d u l i n gs u b p r o b l e m t a k e si n t oc o n s i d e r a t i o nt h e a s s i g n m e n to fp a r tf a m i l i e sa n dt h ea s s o c i a t e dm a c h i n eg r o u p st oe a c hc e l l ，w h e ni t s e q u e n c e st h ep r o c e s s i n go ft h ep a r t so ne a c hm a c h i n ei nc e l l s u s i n gt h em e t h o d ， t h ei o i n td e c i s i o no fe e l lf o r m a t i o na n dc e l ls c h e d u l i n gi ss o l v e d ( 5 ) aj o i n td e c i s i o no fc e l lf o r m a t i o na n dp a r t ss c h e d u l i n gw i t hm a c h i n e sd u p l i c a t i o ni s v i 一 ， ， - ， - k ， ， ， f t t 、 l - ， 东北大学博士学位论文a b s t r a c t s t u d i e d ，w h i c hc o n s i d e re a c ht y p eo fm a c h i n ea n dp a r tw i t hm u l t i p l en u m b e r sa n d p a r t sr e q u i r e dp r o c e s s i n ga n dt r a n s f e r r i n gi nb a t c h e si nac e l l u l a rm a n u f a c t u r i n g s y s t e m am a t h e m a t i c a lm o d e lf o rt h ej o i n td e c i s i o np r o b l e m ，w i t hn o n l i n e a rt e r m s a n di n t e g e rv a r i a b l e s ，i sd e v e l o p e d t os o l v et h em o d e lf o rp r a c t i c a lp u r p o s e s ，a s c a t t e rs e a r c ha p p r o a c hw i t i ld i s p a t c h i n gr u l e si sp r o p o s e d ，w h i c hi n t e r a c t i v e l yu s e sa c o m b i n e dd i s p a t c h i n gr u l ea n dc o n s i d e r st w od i f f e r e n tc o m b i n a t i o nm e t h o d sa n dt w o i m p m v e m e n t m e t h o d st of u r t h e r e x p a n d t h e c o n c e p t u a l f r a m e w o r ka n d i m p l e m e n t a t i o no ft h es c a t t e rs e a r c hs oa st ob e t t e rf i tt h ea d d r e s s e dp r o b l e m t h i s s c a t t e rs e a r c ha p p r o a c hi n t e r a c t i v e l yu s e sac o m b i n e dd i s p a t c h i n gr u l et os o l v ea s c h e d u l i n gs u b p r o b l e mc o r r e s p o n d i n gt oe a c hi n t e g e rs o l u t i o nv i s i t e di nt h es e a r c h p r o c e s s t h ej o i n td e c i s i o no fc e l lf o r m a t i o na n dp a r t ss c h e d u l i n gw i t hm a c h i n e s d u p l i c a t i o ni ss o l v e db yt h ep r o p o s e da p p r o a c h k e y w o r d s ：c e l l u l a rm a n u f a c t u r i n g ；c e l lf o r m a t i o n ；c e l ls c h e d u l i n g ；o p t i m i z a t i o nm o d e l ； m e t a h e u r i s t i c ；s c a t t e rs e a r c h ；g e n e t i ca l g o r i t h m v i i 东北奎堂蔓主堂垡笙壅笪型 ： 一-_-_-_-_-_-_一 一 一v i i i t 屯 小 p 上 东北大学博士学位论文 目录 目录 独创性声明i 摘要。l i i a b s t r a c t v 第一章绪论l 1 1 问题背景及研究工作的意义1 1 2 研究目标与研究内容3 1 2 1 研究目标3 1 2 2 研究内容。3 1 3 研究的技术路线4 1 4 主要研究成果6 1 5 参加的科研项目。8 第二章单元构建和单元调度相关问题及算法的研究综述9 2 1 生产方式的基本类型9 2 2 单元生产的概述9 2 2 1 单元生产的基本概念与产生背景9 2 2 2 单元生产的特征与优势l o 2 2 3 单元生产的发展阶段1 2 2 3 单元构建问题及算法综述1 4 2 3 1 单元构建的基本概念与问题描述1 4 2 - 3 2 单元构建的策略1 5 2 3 3 单元构建的常用目标1 5 2 3 4 单元构建方法概述1 6 2 4 单元调度问题及算法综述1 7 2 4 1 单元调度的基本概念与问题描述1 7 2 4 2 成组调度问题及算法概述18 2 4 3 零部件调度问题及算法概述1 9 2 5 本章小结1 9 第三章基于分散搜索的多目标动态单元构建方法2 1 3 1 动态单元构建问题的背景2 1 3 2 动态单元构建问题的多目标模型。2 2 3 2 1 动态单元构建问题的描述2 2 一i x 东北大学博士学位论文 目录 3 2 2 动态单元构建问题的多目标模型2 2 3 3 分散搜索算法的研究综述。2 5 3 3 1 分散搜索算法简介2 5 3 3 2 分散搜索算法的基本原理和特点2 6 3 3 3 分散搜索算法的改进2 8 3 3 4 复杂环境下分散搜索算法的研究2 9 3 3 5 分散算法的应用“3 0 3 4 求解动态单元构建问题的分散搜索算法的设计。3 2 3 4 1 产生多样性初始解3 3 3 4 2 评估目标值3 4 3 4 3 更新参考集3 5 3 4 4 产生子集3 5 3 4 5 合并子集3 6 3 4 6 解改进3 6 3 4 7 修复新解3 7 3 5 计算实验与结果分析3 7 3 5 。1 实验设计3 7 3 5 2 算例分析3 7 3 5 3 实验与结果分析4 0 3 6 本章小结4 3 第四章基于遗传算法的设备冗余情况下多目标动态单元构建方法4 5 4 1 设备冗余情况下动态单元构建问题的背景4 5 4 2 设备冗余情况下动态单元构建问题的多目标模型4 5 4 2 1 设备冗余情况下动态单元构建问题的描述4 5 4 2 2 设备冗余情况下动态单元构建问题的多目标模型4 5 4 3 求解动态单元构建问题的多目标遗传算法的设计4 8 4 3 1 染色体编码及其初始化4 8 4 3 2 适应值4 9 4 3 3 遗传算子j 5 0 4 3 4 精华保留策略5 0 4 4 实验算例51 4 5 本章小结5 4 第五章基于分散搜索的跨单元生产的零部件调度方法5 7 5 1 单元调度问题的背景j 5 7 5 2 生产单元内零部件调度问题的数学模型。5 7 一x 一 气 工 寸 p 上 东北大学博士学位论文 目录 5 2 1 跨单元生产的零部件调度问题的描述5 7 5 2 2 单元调度问题的模型5 9 5 3 求解单元调度问题的分散搜索算法6 l 5 3 1 解的编码与解码6 2 5 3 2 产生多样性初始解6 2 5 3 3 产生初始的参考集6 3 5 3 4 产生子集6 3 5 3 5 合并子集6 4 5 3 。6 解改进6 5 5 3 7 更新参考集6 5 5 3 8 停止准则6 6 5 4 计算实验与结果分析6 6 5 4 1 实验设计6 6 5 4 2 总生产时间下的计算实验与结果分析6 6 5 4 3 拖期惩罚下的计算实验与结果分析6 8 5 5 本章小结7 3 第六章基于拉格朗日松弛的单元构建与调度的联合决策方法7 5 6 1 单元构建与调度的联合决策问题的背景7 5 6 2 拉格朗日松弛算法概述7 7 6 2 1 拉格朗日松弛的基本原理和特点7 8 6 2 2 特殊形式的拉格朗日松弛7 9 6 2 3 拉格朗日松弛算法8 0 6 3 单元构建与调度的联合决策问题的数学模型8 1 6 3 1 单元构建与调度的联合决策问题的描述8 1 6 3 2 动态单元构建问题的多目标模型8 1 6 4 基于启发式的拉格朗日松弛算法的设计8 5 6 4 1 模型特性和两个子问题8 5 6 4 2 线性化构建子问题8 6 6 4 3 求解调度子问题8 6 6 4 4 更新拉格朗日乘子8 7 6 4 5 调整启发式8 7 6 4 6 基于启发式的拉格朗日松弛算法框架8