（系统工程专业论文）多阶段多产品流水车间Lot+Streaming调度问题研究.pdf

东北火学颂。1 论文 摘要 多阶段多产品流水车间l o ts t r e a m in g 调度问题研究 摘要 流水车间l o ts t r e a m i n g 调度问题是指n 种产品批量在m 台机器上以相 同顺序进行加工，每种产品批量被划分为若干个子批量，按予批量分别组织 加工和工序问的运输，当在一台机器上一个子批量加工完成以后，而且相继 机器空闲，这个子批量无须等待其余予批量在此机器上的加工完成，就可以 赢接转运到下台机器上进行加工，拍i 即采取平行加工的方式，允许同一产品 加工的相继操作在时间上部分重叠。它比一般流水车l l 白j 调度问题要复杂得 多。流水车洲l o ts t r e a m i n g 调度问题己被证明是n p 难问题。研究这类问题 的快速可行的近优算法是一个挑战性的研究课题，近年来已经引起了国际学 术界的关注。 本文首先介绍了l o ts t r e a m i n g 调度问题的特点与发展现状。在综述 荇类l o ts t l e a r n i n g 调度问题的基础上，对l o ts t r e a m i n g 调度问题进行了 分类。并与传统调度方法进行了比较，表明了l o ts t r e a m i n g 调度的优越 性。 其次对多阶段多产品允许混排流水车间l o ts t r e a m i n g 调度问题，以最 小化总完工时间为目标函数问题设计了f i x e d g a n e h 算法，通过实验证 明了算法的有效性，并与前人算法进行了比较，优于以往的算法。 然后对多阶段多产品考虑设置h , 1f 刚允许混排流水车f 白j l o t s t r e a m i n g 渊度问题进行了研究，以最小化总完工时i 剞为目标函数，设计了 f i x e d g a g a 算法，通过实验证明了算法的有效性。 最后对多阶段多产品无等待流水车间l o ts t r e a m i n g 调度问题，提出 了肩发式算法，通过实验证明了算法的有效性，并于l j 人算法作了比较， 优于6 口人算法。 关键词：批量流：流水车间：遗传算法：启发式算法：子批量 东北人学倾】论义 摘坚 l o ts t r e a m i n ga n ds c h e d u l i n gi nm u l t i s t a g ef l o ws h o p s a b s t r a c t t h el o ts t r e a l l l i n ga n ds c h e dl l i j “g i nf l o ws | 1 0 p sm a yb ed e f i n e da sf o l i o w s t 1 1 e r ea r en p r o d u c t l o t st ob e p r o c e s s e do n朋m a c h inesi nt 1 1 es a me se qu e n c e apr o d u c ic a nb ed i v i d e ds o m es u b l o t s ，as u b i o tn e e d n tw a i tf or t h e p r o c e s s i n g o ro t h e rs u b l o tsa n dc a nb etr a n s p o r i e d t on e x tm a c h i n et ob e p r o c e s s e dw he nt 1 1 es u b i o th a sb e e n c o m p i e t e d a to n em a c h in ea n dt h e d o w ns t r e a mm a c l l i n eisj d l e t h a ljs ，t h ep r o c e s s i n go fap r o d uc tis p a r a i le land t h eo p e r a t i n g o na p r o du c tc a nb eo v e r l a p p e d t h e l o ts tr e a m i n gp 1 。b 1e mis n l or ec o m p l j c a t e dt h a na n yo ft h eg e n er a lr l o ws h o ps c h e d u l j “gpr o b l e m s t h e l o ts t r e a m i n gpr o b l e m h a sb e e n p r o v e d t ob ean p i h ar d p r o b l e ma n dt h e r e s e a r c ho na l g or i i h mst o 。b t a i n 仆i eq u j c ka n df e a s b i en e a 卜0 p t i m a ls o i u t i o n s f ort h is p r o b i e i nisac h a l i e n g in gt o p i ca n dh a sr e c e i v e da i t e n t i o no ft h e i n t er n a t i o n a la c a d e m ei nr e c e n tye a r s f i r s t i y ，t h etj 1 e s si n tr o d u c e st h ec h a r a c t er is t i c sa n dt h ed e v e i o p m e n ts l a i u s o fl o ts t r e a m i n gpr o b l e mt h et h e s ish a v ec l a s s i f i e dl o ts ir e a m i n gp r o b l e mo n t h eb a s iso fs u m m a r i z i n ga l i k i n d so fl o ts t r e a m i n gp r o b i e ms t h ec o m p ar js o n be t w e e nl o ts ”e a m i n gm e t h o d w ；t ht h etr a d i i i o n a l s c h e d u i i n g m e t h o dh a s s h o w nt h es u p er i o r i t yo fi h el o ts tr e a l l l i n gm e t h o d s e c o n d l y ，t h et h e s i s d e s i g n st h ef i x e d g a n e haj g o r i t h mt ot h epr o b ie m w h o s e o b j e c t v eist om in i m i z e m a k e s p a n i nm u l t i s t a g e f l o w s h o p w t h ml i l t ip 1e p r o du c lsw 1 1 0s es l l b i o t sc a nb ea l lo w e dp r e e m p t i o ns l a r g enl i m b e r s o fe x p er i m e n t a ir e s u l t ss | 1 0 wt h e a l g o r i t h mjse f f e c t i v ea n d s u p e r i o rc oi h e a l g o r i t h mi nt h ep a s t t h i r d i y ，l h et 1 1 e s is d e s j g n st 1 1 e f j x e d g a g aa l g or 1 mt ot 1 1e p r o b ien 1 w h os eo b j e c t i v elsi om i n j m i z ema k e s p a n inm uj t is t a g ef i o ws h o pw i t hs e i l i p t i mea n dmu l t jp l e p r o d u c tswh o s es u b l o t sc a nb ea 1 1 0 w e d pr e e mp “o ns l a r g en u m b e r so fe x p e r i m e n t a ir es u i t ss 1 1 0 wi h ea l g or i t h mis v a | i d i i y l a s t l y ，t 1 1 e t h e s is d e s i g n stj 1 e1 1 e ur o b j e c t iv eist ol ”in i m jz em a k e s p a n in s t i ca i g or i t h mf ort 1 1 e p r o b i en 1w h os e m u l t j s t a g e n o w a i tf i o wsh o p l a i g e 东北人学坝l 论文摘要 nl 1 1 1 1 b er so fe x pe ii m e n t a lr esu i tss h o wthe a l g o r i t h mi se f f e c t iv ea n ds u p e l - i ort o t h ea l g o r i t l l mi nt 1 1 e p a s t k e yw o r d s ：l o ts t r e a m i n g ，f l o ws h o p ，g e n e t i ca l g o r i t h l l l s ，h e u r is t ic a l g o r i t h m s su b i o t s i v 声明 本人声明所呈交的学位论文是在导师的指导下完成的。 论文中取得的研究成果除加以标注和致谢的地方外，不包含 其他人已经发表或撰写过的研究成果，也不包括本人为获得 其他学位而使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均己在论文中作了明确的说明并表示了谢意。 本人签名： 日期 荜延竿 2 0 0 4 年2 月 东北人学倾l 。论义 笫一章绪论 1 1 引言 第一章绪论 调度( s c h e d u l i n g ) 问题是一类广泛存在于现实世界中的经典运筹问题， 具有深刻的实际背景，依据不同应用背景，其任务、资源要素可以代表不同 的事物。如工件一机床、进程一c p u 、病人一医生等。可以断言。，现实世界 的各个领域巾，j 、l 是处理多个任务，就存在安排任务执行的相应的调度问题。 它是现代企业生产管理的重要研究问题之一。 调度问题包含三个基本的要素：即任务、资源和目标，要求在空j 旬和时 间上合理安排任务和资源，在满足技术和资源约束限定下，使预定目标达到 最优。 、 由于调度问题涉及合理安排任务与资源，保证目标的最优性，能够带来 效率、效益、成本等方丽的巨大收益，目前已为研究者们广泛重视。因此， 调度问题成为应用数学、运筹学、管理科学的诸多学科的热门研究课题，研 究成果层出不穷 2 5 - 2 6 1 。 1 2 传统调度问题及其分类 调度问题通常可按就绪时间或加工时削进行划分。按工序就绪时间的异 同可划分为动态( d y n a m i c ) 调度问题和静态( s t a t i c ) 调度问题；按工件加 工时间的性质可分为确定型( d e t e r m i n i s t i c ) 调度问题一一加工时间f t 和其它 有关系数是己知的确定的量，和非确定型( s t o c h a s t i c ) 调度问题一一加工时 间和其它有关参数是随机变量。 理论上最常用且能详细刻画不同类型调度问题特点的分类方法是按机 器数、工件加二 ：技术约束和目标函数的特征进行分类，以a b c d 四参数形 式进行表述1 。其中： a 一工件数量( 任意大于l 的整数) ； b 机器数量； c 一由技术和管理要求所确定的加工约束； d 一优化目标函数。 结合上述四参数表述形式，凋度问题可以细划分为不同类型的调度问 题。即：单一： 件调度、多工件调度、单机( s i n g l em a c h i n e ) 调度、多机 查! ! 叁堂堡生丝苎 塑二里笙堡 调度、丌环车间( o p e ns h o p ) 、闭环车削( c l o s e ds h o p ) 、f 1 o ws h o p 和j o b s h o p 、基于不同目标函数的调度( c 。p f ) 等。 在传统的调度问题中，被加工的产品或工件是不可分割的，尽管其中可 以或可能包含若干个子工件。只有在一台机器上被加工产品或工件整体加工 完成以后，才可以整体转运到下一台机器加工。为了缩短加工周期，r e i t e r 6 1 于1 9 6 6 年首次提出单一产品的l o ts t r e a m i n g 问题。 1 3l o ts t r c a m in g 调度问题 r e i t e r 6 】于1 9 6 6 年首次提出单一产品的l o ts t r e a m i n g 问题。与传统调 度不同的是，l o ts t i - e a m i n g 是把一个被加工的产品批量划分为若干个子批量 ( s u b l o t ) ，按子批最分别组织加工和工序间的运输，当在一台机器上一个子批 量加工完成以后：而且相继机器空闲，这个子批量无须等待其余子批量在此 机器上的加工完成，就可以直接转运到下台机器上进行加工，办即采取平行 加工的方式，允许同一产品加工的相继操作在时间上部分重叠。充分利用了 加工机器和加工时r n j ，达到提高生产效率的目的。l o ts t r e a m i n g 问题属于 n p 难问题 4 1 。 k a l i r 和s a t in 【”j 介绍了在流水车间中应用l o ts t r e a m i n g 调度方 法后所带来的一些益处，包括： 1 采用l o ts t r e a m i n g 调度方法使c 。大大缩小，缩短生产时问， 从而缩短交货期。 1 减少工作进程中的库存，减少相关的库存费用。 2 减少中间存储和空间需求。 3 减少了工件对机器加工能力的需求。 2 和3 主要体现在：当交货期相同的情况下，采用l o ts t r e a m i n g 调度方 法，存储材料所需工作进程中的库存和中间存储空间比传统调度方法要小， 因此也就降低了相关的库存费用和空间需求。4 主要体现在：当交货期相同 的情况下，加工相同的工件，采用l o ts t r e a m i n g 调度方法比传统调度方法 所需要的机器加工能力要小。 总之，在调度中采用l o ts t r e a m i n g 调度方法，能够缩短生产时问从而 缩短交货期，提高固定资产的利用率从而降低成本，提高生产能力，提高生 产率，提高竞争力，强化服务。 查些墨堂堡：! ：丝兰一上生二墨! i 鱼 1 4 本文的技术路线和所做工作 本文主要进行了流水车问l o ts t r e a m i n g 调度问题的研究，主要工作和技术路 线如下： 、 1 首先描述了l o ts t r e a m i n g 调度问题，指出了问题的特点，并与 传统调度问题进行了比较。随后对l o ts t r e a m i n g 调度问题的研究现状进行了 综述和分类，给出了本文的研究方向。 2 在考虑不同产品子批量允许混排的前提下，研究了多产品多 阶段静态流水车间l o ts t r e a m i n g 调度问题，基于遗传算法和n e h 算法设计 了求解的启发式算法，通过计算实验与前入算法进行了比较实验结果表明： 本文提出的算法优于前人的算法。 3 在考虑设置时阃与顺序无关的前提下，研究了多阶段多产品 混排的流水车问l o ts t r e a m i n g 调度问题，设计了f i x e d g a g a 算法，通过 仿真计算实验，表明了算法的有效性。 、 4 在无等待约束、考虑设置时删与顺序无关的前提下，研究了 多阶段多产品不允许混排流水车问l o ts t r e a m i n g 问题。设计了f i x e d l p n e h 算法，通过仿真计算实验，与前人算法进行了比较，实验结果表明了本文算 法的优于前人算法。 东北人学硕j 1 论文 第二章l o ts t r e m n i n g 训度问题研咒 第二章l o ts t re a mi n g 调度问题研究 2 1l o ts tr e a m in g 调度问题 所谓l o ts t r e a m i n g 就是把一个被加工的产品批量划分为若干个子批量， 按子批量分别绢织加工和工序间的运输，当在一台机器上一个子批量加工完 成以后，而且相继机器空闲，这个子批量无须等待其余子批量在此机器上的 加工完成，就可以直接转运到下台机器上进行加工，亦即采取平行加工的方 式，允许同一产品加工的相继操作在时间上部分重叠。充分利用了加工机器 和加工时阳j ，达到提高生产效率的目的。 2 2l o ts tr c a mln g 调度问题的一般假设条件和分类 在介绍l o ts t r e a m i n g 类型之前，首先介绍几个概念：一致子批量、可 变子批量、不允许混排、混排。 一致子批量( c o l l s i s t e n t ) ：如果一个产品的一个子批量的大小在各加工 工序保持不变，则称( 为一致子批量，即一个子批量的大小在所有加工机器 上都是相同的。 可变子批量( v a r i a b l e ) ：和一致子批量相反，如果一个产品的一个子批量 的大小在各加工工序是变化的，称它为可变子批量，即一个子批量的大小在 各机器上是不相同的。 不允许混排：一旦一个产品的一个子批量在机器上进行加工，这个产品 的所有 予批量要连续加工，不允许分散加工，直到这个产品的所有子批量都加 工完，刊能加工其它产品的子批量。 混排：在加工一个产品的各个子批量之阳j 允许加工其它产品的子批量， 电就是允许一个产品的子批量不必连续加工，可以是分散加工的。 东北人学坝- + 论曼第二章l 肌s l r e a r n i n g 儡度闷题肼宄 2 2 1l o ts tr e a m in g 调度问题的一般假设条件 1 假设在零时刻，所有产品准备就绪。 2 产品数、机器数、每种产品每个零件在各台机器上的加工时 问及产品加工的工艺约束一加工路线是已知的。 3 被加工的产品批量划分为若干个子批量，按子批量分别组织 加工和工序问的运输。 4 当在一台机器上一个子批量加工完成以后，而且相继机器空 闲，这个子批量无须等待其余子批量在此机器上的加工完成，就可以直接转 运到下台机器上进行加工。 5 子批量的大小是一致的。 6 子批量的加工时问和它的大小成正比，p ：，= 只，r ，。 7 独立的调整时间( 或可分离的设置时阳j ) ：在一台机器上，从 加工一种产品转到加工另一种产品要求机器的调整。 8 允许产品在工序之间等待，允许机器在产品未到达时闲置。 以上假设条件允许改变和放松，由此可构成不同类型的l o ts t r e a m i n g 凋度问题。 2 2 2l o ts t r e a m in g 调度问题分类 l o ts t r e a m i n g 调度问题可按不同的准则进行分类。按被加工产品的数量 ( 种类) ，可分为：单一产品和多产品l o ts t r e a m i n g 调度问题；按加工流程 的不同，可分为：流水车间、单件车间、丌放车间l o ts t r e a m i n g 调度问题： 按机器数量的不同可分为：单台处理机和多台并行处理机l o ts t r e a m i n g 调 度问题研究；按工艺约束的不同可分为：有一般的和无等待l o ts t r e a m i n g 调度问题研究：按目标函数可分为：时恻标准的和费用标准的l o ts t r e a m i n g 问题。 东北人学坝l j 论文 靖一章l o ts t r e a m i n g 制度问题州究 2 3l o ts t r e a m in g 调度与传统调度的比较 2 3 1 传统调度问题描述 ”个任务 。，：，) 要被加工，m 个机器 m ，m ：m 。) 可用，每一个 任务要在这些机器上或其中的一部分机器上加工，任务i ，在机器m ，上的加 工叫做一个操作( o i i ) ，它对应一个加工时间( p ) ，每一个任务还有与之 相对应的就绪时间( 月，) ，即，可以j q ：始进入加工的时间，还有交货期( d ，) ， 即i ，必须完成的期限。每一个任务还需要有一个工艺约束，它要求该任务按 照一定的工序要求在这些机器上加工。所以个调度就是在一定时i 刨内任务 在机器上的一个分派，调度问题就是寻找一个任务在机器之i n 的传递序列， 它要求满足2 个要求： 1 符合工艺要求，即调度是可行的： 2 对应于某些执行目标调度是最优的【2 。 2 3 2 传统调度方法的一般假设条件 调度问题通常遵循以下假设： 1 工件数、机器数、工件在各台机器上的加工时间及工件加工 的工艺约束一加工路线是已知的。 2 一个工件在同一时刻仅能在一台机器上加工，一台机器同一 时间仅能加工一个工件。 3 对整个工件来说，在加工过程中采取平行移动方式。即当上 一道工序完成时，立即送下道工序加工。 4 加工过程不允许中断，一个工件一旦丌始在某工序加工，必 须持续到陔工序加工完毕，不允许中间插入其他工件。 5 允许工件在工序之唰等待，允许机器在工件未到达时闲置。 6 所有工件的就绪时间为0 ，即：在加工开始时，所有工件都具 备加工条件。 7 机器是不会损坏的。 以上假设条件允许改变和放松，由此可构成不同类型的调度问题。满足 以上假设条件的调度问题成为传统调度问题p o 。 东北人学坝j ：论文第二市l o ts t r e a m i n g 训艘问题研究 2 3 3l o ts t r e a m in g 调度与传统调度问题比较 下面以一个简单的流水车问三阶段单一产品的例子对传统方法和i j ( ) t s t r e a m i n g 方法进行比较：在三台机器流水车划中，一个产品包含5 0 个零 件，在三台机器上每个零件的加工时间分别是2 、l 和3 分钟，假设调度没 有机器调整、闲置和运输时问，那么加工这个包含5 0 个零件的产品需要3 0 0 分钊t 。如图2 1 。 m m m 1 0 01 5 0 3 0 0 图2 1 传统调度的甘特幽 f i 9 2 1t h et t a d i t i o n a ls c h e d u l i n gg a n tc h a r t 如果把这个被加工产品批量分成两个子批量，每个子批量含2 5 个零件 那么在三台机器上加工这个产品需要2 2 5 分钟。可以看出应用l o ts t r e a m i n g 调度后总完工时间明显减少。如图2 2 。 从两个图上也可以看出，采用传统方法进行调度比采用l o ts t r e a m i n g 调度所需工作进程中的库存要大，采用了l o ts t r e a m i n g 调度提高了机器的 利用率，因而总成本降低。 鹕一章l o ts t r e a m i n g 训度问题究 m m m 5 01 0 0 15 02 2 5 幽22l o ts t r e a m i n g 调度的甘特隆l f i 9 2 2l o ts t r e a m i n ga n ds c h e d u l i n gg a n tc h a r t 2 4l o ts tr e a m ln g 调度问题研究现状 由于l o ts t r e a m i n g 调度问题是一类很复杂的调度问题，所以早期有关 它的研究是在进行了显著简化假设的条件下进行的，其目的是寻找问题的最 优解。下面文献中介绍的l o ts t r e a m i n g 调度问题都是不允许混排的。 r e i t e r 1 6 】于1 9 6 6 年首次提出单一产品的l o ts t r e a m i n g 调度问题。 c g l a s s 、j g u p t a 和c p o t t s 2j 对三阶段单一产品的l o ts t r e a m i n g 调度 问题做了全面的分析，在不允许混排、子批量数已知、子批量一致的情况下， 对流水车问、单件车间、开放车涮的批量流问题都进行了研究。目标函数是 最小化总完工时间，需要确定的是每个子批量的大小。用的是网格和关键路 径法。在流水车间的情况下，网格法也能解决两阶段情况。并对算法的复杂 性进行了研究。但是他的模型只解决了单一产品三阶段l o ts t r e a m i n g 调度 问题的情况，不能解决多产品多阶段l o ts t r e a m i n g 调度问题。 r a n g av r a m a s e s h h a i z h e nf u ，d u n c a nk l f o n g 和j a c kc h a y y a l j l 研究 了多阶段单一产品的l o ts t r e a m i n g 调度问题，考虑工作进程( w o r k i n - p r o c e s s ) 中的库存费用和子批量的运输费用，子批量数是已知的，所有的子批量的大 小是相同的，考虑运输时间、等待时间和设置时间，目标函数是总相关费用。 这篇论文考虑了实际生产中的运输时间、等待时间和设置时间，但是并没有 东北人学坝：j ：沦义 雄一章l o ts t r e a m i n g 训度问题 ! j | = 究 找到近优的予批量数和予批量大小，而是把问题简化了，所有的子批量大小 都是相同的。 j i a n g 和s t e i n e r l 6 研究了流水车间多机单一产品不允许混排的l o t s t r e a m i n g 调度问题，在不考虑设置时间，子批量数已知，一致子批量情况 下，目标函数是最小化总完工时间，用关键路径的方法找到了能使达到最小 的子批量大小( 整数) 。a a k a i r ，s c s a t i n t sj 研究了流水车间单一产： 品，考虑设置时问l o ts t r e a m i n g 调度问题结构特性，目标函数是最小化总完 工时间，算法是最小化瓶颈闲置时间启发式。 s e n a 和b e n l i 3j 研究了丌放车间两机单一产品和多产品的l o t s t r e a m i n g 调度问题，不考虑机器设置时i 剞，子批量数是已知的，子批量大小 是一致的，所有子批量的大小是相等的。对于单一产品和多产品这两种情况， 都研究了所有予批量路径一样和路径不一样的情况，即单一路径和多路径的 情况，并给出了模型。指出只要有一种产品的加工时间特别大，并且最多只 能有一个那样的产品时采用l o ts t r e a m i n g 调度能大大减少最大流程时问。 但是这篇文章没有找到近优的子批量。 f e r d ac a n c e t i n k a y a 的论文研究了多产品两阶段流水车l 训l o t s t r e a m i n g 调度问题，考虑设置时间、加工时间和运输时间分丌的情况，并 且设置时间、加工时间和运输时间独立于产品问的顺序。目标函数是最小化 总完工时问，其中子批量数是已知，需要确定的是子批量大小和产品的顺序 问题。用多项方式算法解出了批量大小确定和产品序列这个集成问题的最优 解。 s u b o d h ak u m a r ，t a p a np g a g c h i 和c s r i s k a n d a r a j a h 的论文研究了 多阶段多产品无等待流水车嵋j 的l o ts t r e a m i n g 调度问题。其中子批量大小 是一致的，考虑设置时间。其目标函数是最小化总完工时间。提出了一个启 发式算法和一个遗传算法，并对两种算法进行了比较。但是这篇论文所提出 的遗传算法最终结果依赖初始种群。 j i a n g 和s t e i n e r l l 4j 研究了三阶段单一产品流水车问的l o ts t r e a m i n g 调度问题，考虑可分离设景时问、子批量数已知，目标函数是最小化总完工 时i 自j 。论文对子批量大小可变的情况进行了研究，对一致子批量和可变子批 量进行了比较，在可变子批量情况下，目标函数更好。 谢琪【i8 1 研究了三阶段单一产品流水车间的l o t s t r e a m i n g 调度问题。文中 考虑的是三台机器，每加工一个新的子批量机器就增加一个独立的调整时 间，这样子批量数就由调整时问来确定，目标函数是最小化总完工时间。但 蔓j ! ；：! ! ! 兰塑：! 堡：! ! ! ；笙= ：主! ! ! 坠! ! 竺虫! 型丝囹塑型塑 是因为机器加工每个子批量都需要进行调整，是总完工时间变大。 综上所述，虽然关于l o ts t r e a m i n g 调度的研究近年来引起了许多学者 的兴趣，但是它们基本上集中在小规模的理论研究上，许多算法不能处理大 规模问题，并且已有的启发式算法还不够完善。虽然有的算法能够处理较大 规模的问题，但是无论从计算效率还是效果上来说，都有进一步改进的余地。 有些算法还不能充分利用问题的性质，还有深入研究的必要。就本论文研究 的多阶段多产品l o ts t r e a m i n g 调度问题来说，虽然文献 4 提出了遗传算法， 但是实验结果受初始种群的限制，交叉和变异算子设计的不合理，不能找到最优 解。基于这种情况，本文对多阶段多产品l o ts t r e a m i n g 调度设计了新的算法。 东北火学颀。0 论文 第二章多输段多产 罹允海混撵流水书词l o ls l r 档m i n g 础碰闻翘 第三章多阶段多产品允许混排流水车间 l o ts tr e a min g 调度问题 本带掰馓的礤究是：在多阶段流水车闻中，不考虑梳器的设黄时间，允 许湿摊的l o ts t r e a m i n g 阀题。所用算法是f i x e d g a n e h ，即常数子批量数 g a 算法确定予批量大小n e h 算法确定予批量的顺序。对遗传算法和n e h 散了简单酾介绍。问题的露栝函数是使c 。达到最小。最后进行了仿舆试验， 试验表明了本文的g a 算法克服了襁值依赖性，使梳亿过程不陷入简部麓优。 与s u b o d h a 、t a p a n 和c s r i s k a n d a r a j a h 的遗传算法1 4 j 进行了比较，优子 s u b o d h a 、t a p a n 和c s r i s k a n d a r a j a h 的遗传算法。 3 。1f 1o ws h o p 问题攒述及一般假设条俘 f l o ws h o p 问题楚典穗的缝合优化闯憨。这一问题可以描述如下： 假没有个工件，每个工件都按耀同的顺序经过掰台极器船王，求熙器 工件酶加工颗序，使莱种预先规定的鞠标瞒数达到最优。 f l o ws h o p 的般缎设条件： 1 + 一个工件不能同时在不同的祝器上进行船工。 2 对所有的工件柬穗，在加工过程中采敏乎行移动方式。及上 一道工净完王后，立即送下道工跨加王。 3 当一个工件在某个工序上开始加工，必须直进行到党工， 不允谗中途锌下来，也不允许插入其铯工件。 4 。簿道工序只能在一台机器上完成，每台机器智娆完成“道工 序。工序都不是有抗先权熬。 5 工件数押、枫器数m 和力噩工时间“已知，且加工时闻与加工顺 序无关。所有的工 譬都可以在零瞬刘开始翮工。 6 允许工件在工序之间等待，允许枫器在工件未至达时阏黉。 7 。工件加工技术上的约束事先给定。 8 每台机器潲时只能棚工一个工件。 至型生生苎堕生丝苎笙兰至兰! 竺璧量兰! ! j ! ：垒堡塑型：塑垄! 塑! ：! ! ! ! 竺! ! ! ! 坚塑堡塑嬖 9 所有工件在各台机器上的加工顺序相i 司1 3 0 。 3 2 问题描述 在静态流水车间中，假设产品之问、产品的各子批量之间萌设置时问可 以忽略( 即设置时州为o ) ，n 种产品在m 台机器上加工，产品p 包含彤个 相同的零件，可划分为_ 个子批量( 子批量大小可以是零) ，允许混排，予 批量的大小是一致的。需要确定每一产品的各个子批量的大小和务予批量的 力强二 顺序，使舀标函数c 。( 总完3 2 时划) 最小。 求解思路如下：采用g a 算法确定每个产品的各个子批量的大小，分批 届将各产品的每个子批星当作个工件，采用n e h 算法进行排序。 3 3 求解算法设计 3 。3 1 符号和变量 历 流水车i 司中的机器数量。 m ，= 1 。m ，水车间中的聊机器。 加工的产品数目。 ， ， ” n j v 嘭= 羔，r ，。 s ， 器艇，上，产品鼻的第k 个子批量的加工时i 訇。 产品f 的子批量数。 产品p 的子批量的u n i t s ，x ，女是实数( x “0 ) 。 产品p 的子批量女的u n i t s ，f 、。是整数( 。0 ) 。 产品p 的总u n i t s 数。 产品# 在机器m ，上的设置时间。 东北人学坝。l 论文豁二章多蝓段多产品免许混排溃泳年蝇l 埘s t r e a m i n g 蝴废蝇题 a所有产晶的于批量总数。 c ，产品p 在机器m ，上加工的完工时阻j 。 c ! ，品只的第k 个子批量在机器m ，上加工的完工时间。 需要确定的变最 啪产品的子批量k 的u n i t s ，在这最x 是一个实数( x 雎0 ) 。 ，。产品p 的子批量k 的u n i t s ，在这罩r 。是个整数( f 0 ) 。 3 3 2 单一产品分批算法设计 在这_ 部分研究的是单一产品的分批问题，所用算法是遗传算法。首先 介绍一下遗传算法。 遗传算法是种基于自然选择原理和自然遗传机制的搜索( 寻优) 算法， 它是模拟自然界中的生命进化机制，在人工系统中实现特定目标的优化。遗 传算法( g e n e t i ca l g o r i t h m ) 由美国m i c h 堙a n 大学的，h o l l a n d 教授在1 9 7 5 年出版的专著( ( a d a p t a t i o n i n n a t u r ea n d a r t i f i e i a l s y s t e m s ) ) 中首先提出。遗 传算法的主要特点是使用参数的编集，丽不是参数本身进行工作，遗传算法 是在点群中雨不是一个单点上寻优：遗传算法仪使用问题本身所具有的目标 函数进行工作，丽不需要其他任何先决条件或辅助信息；遗传算法使用随机 转换规则面不是确定性规则进行工作。遗传算法主要是用于求解组合优化问 题以及存在l ；可微的目标函数或约束条件复杂的非线性优化问题。 遗传算法的基本原理是在自然进化中，每一物种越来越适应环境；物种 的个体的基本特征被其后代所继承，但后代又不完全同于自己的父代；个体 的性质是由染色体决定的，染色体是由基因有序排列组成的；由染色体决定 的个体对环境有不同的适应性，通过基因杂交和基因突变产生适应性强的个 体；在世代进化中，“适者生存”的自然选择的强制作用，使得更能适应环 境的个体的特征( 对应适应值高的基因结构) 被保存下来。 算法进化过程如下： 1 确定种群大小n 、交叉概率p c 、变异概率p m 、最大中i 上代数 m 东北大学颂卜论义第三章多阶段多产品允许混排流水乖问l o ts t r e a m i n g 训度问题 2 产生n 个染色体的初始种群。 3 判断是否满足中止条件( 迭代次数 m ) ，若满足则算法停 止输出结果，否则转入4 。 4 从父代染色体中复制产生下一代种群。 5 进行交叉和变异操作。 6 计算所有染色体的适值。 7 生成新种群，转3 。 遗传算法中的主要参数有：种群规模、基因编码、适值函数、选择概率、 遗传算子、和停止准则。 遗传算子包括交叉算子和变异算子。遗传算子的选取主要是根据编码方 法和原问题的约束条件，以保证经遗传运算产生的后代位于可行域中，并能 扩展搜索空间进行大范围搜索。 ? 其中，基因编码技术确定了遗传算法的表示方案，它的好坏对遗传算法 的性能起到关键的影响：构造编码的主要原则是使编码空问与原问题的解空 问尽量一致，编码空间既要完全覆盖解集空间避免丢失最优解，又不能比解 集空间大太多而增加不必要的计算量。种群规模的大小影响着算法的搜索效 率和计算的复杂性，若太小，则降低了搜索最优解的速度和可行性：反之， 提高了计算的复杂性和时间。适值函数是表征染色体个体对环境适应能力的 测试函数，建立适值函数的原则是：真实体现染色体对环境的适应能力的大 小；染色体之间的适值比保持合理的差距；满足早期限制竞争、晚期鼓励竞 争的需要。选择策略的指明了如何从采样空间中选择染色体，在一定程度上 决定种群进化的方式和效率。选择概率分成：( 1 ) 随机方式、如轮转法、标 尺法。( 2 ) 确定方式，如( , t t + 丑) 选择法、d e j o n g 提出的精英选择策略1 前者是在i f 个父代与 个后代之阳j 竞争，选出, t t 个最好的父代和后代构成下 一代双亲：后者是通过最是个体无条件进入下一代和无退还随机选择机制减 少选择的随机性。( 3 ) 混合方式，如g o l d b e r g 提出的竞争选择，该方法随 机的选出一组染色体，从中取最好的作为下一代双亲 2 1 , 2 3 , 2 4 】。 3 3 2 1 基因编码 1 产品的基因编码 举例说明。例如：对于产品“彬= 8 ，= 3 ，可以表示成 东北人学坝l 。论文第二章多阶段多产品允| 午混排流水下问l o ts t r e a m i n g 训度问题 其中“幸，代表的是第i 个产品的一个零件，两个“1 ”之削代表这个产品的 一个子批量所含的零件数。也就是，用位来表示，第一位是“l ”，表示一个 子批量从这罩丌始，到下个“l ”之问就是这个子批量所含的产品零件数， 再从这个“1 ”到。f 一个“1 ”是另一个子批量所含的产品零件数，直到最后 一位“1 ”。为了存储方便，基因表示成所有“1 ”所在的位置，如下： 口碉 其中的数字是表示1 所占的f , 2 置。那么这个产品的三个子批量大小是 口 计算公式是：第n 个子批量大小= 第月+ 1 个位置的数值一第”个位置的数值 一1 。 另外“所占据的位置可以表示成 口工正口圈 2 染色体 举例说明：对于4 种产品，每种产品所含零件数分别是2 5 、3 0 、2 4 、 2 8 ，子批量数分别是3 、5 、3 、4 ，子批量大小如表31 中所示这样一个问题， 染色体可以表示成： 3 3 2 2 初始种群 191 62 9 171 92 22 93 6 11 12 0 2 8 11 02 12 73 3 对于产品f 来说，需要满足彤= 乙f 第一个子批量的大小是随机 从l 到彬一n ，+ 1 选的一个整数；第k 个子批量( 第二个到第一一1 个子批量) 东北火学碳= l 论文第二三章多阶段多产品允许混排溉水下间l o ts t r e a m i n g 训度问题 是从1 到彬一( 一一k 一1 ) 一= 】，。中随机选取的整数；第”，个子批量】：， = 嘭一2 2 , r , 。 表3 1 产品的f 批量人小 t a b l e 3 it h et o t a ln u m b e ro fi t e m so fap r o d u c ti nt h es u b l o t s i j b l o t1s u b l o r 2s u b l o t 3s u b l o t 4s u b 】o t 5合计 产鼎176 1 22 5 产晶25 1 12663 0 产晶3 9872 4 产品4 8l o552 8 3 3 2 3 适值函数设计 最初试验用的适值函数是 一“= m a x ( c 。) 一( c ) 。d( 3 1 ) 其中m a x ( c 。) 是这一种群中产生的最大c 。，迭代初期适值函数值相差很 大，选择压力大不适于扩展空间搜索，迭代后期适值函数值相差不大，选择 压力小不适于局部最优搜索。为了改变这种情况，适值函数设计成 f 二d = m a x ( c 。) 一( c 。) 。“+ o 1 m a x ( c 。) 一m i n ( c 。) 】 ( 3 2 ) 在原适值函数加上o 1 + m a x ( c 。) 一m i n ( c ) 】后，迭代初期适值函数值相差不 大，选择压力小，适于扩展空间搜索，迭代后期适值函数值相差很大，适于 局部最优搜索。试验表明后一个适值函数优于前者。 其中c 。的计算如下： c = t i m e ( 3 3 ) c l ，2 t i m e l ，j + c 1l ，一1 ，p l( 3 4 ) c 2 t i m e ，j + c 圳 ，i 1 ( 3 5 ) c ，- 2 m a x ( c ，一l ，c 1 ，jj + t i m e ，f l ， 1 ( 3 6 ) 东北人学坝：i 论文第三章多阶段多产品允许混排流水午问l o ts t r e a m i n g 恻度问题 c 。2 c 。，( 3 7 ) 其中t i m e ，是产品i 在机器上的加工时间