（管理科学与工程专业论文）差异工件单机批调度问题的优化算法研究.pdf

摘要 摘要 差异工件的单机批调度问题，具有古典调度和批调度的双重性质，在实际生 产中有着广泛的应用；在计算复杂性方面，单机的制造跨度最小化问题为强 n p - h a r d ，加权完工时间最小化问题为n p - h 矾，单机问题的高复杂性对优化算法 提出了挑战。因此对差异工件单机批调度问题的研究具有重要的现实意义和理论 价值。本文首先对确定性单机问题进行求解，针对单机问题复杂度高、可行解数 量大的特点，设计了有效的优化算法。然后将单机问题扩展到更接近现实情形的 模糊环境中，建立模糊调度模型，并设计了求解模糊问题的优化算法。本文的主 要工作和创新点如下： ( 1 ) 研究了蚁群算法( a n tc 0 1 0 n yo p t i m i z a t i o n ，a c o ) 在差异工件单机批调度 问题中的应用。设计了高效的编码和解码方法；为了解决蚁群算法易陷入 局部最优的问题，本文引入了m e t r o p o l i s 准则的概率选择机制作为路径激 励策略，避免了由于路径重复而造成的局部最优；仿真实验验证了改进算 法的有效性。另一方面，本文采用了混沌优化算子，将混沌优化的全局性 能嵌入蚁群算法中，有效改进了解的质量。 ( 2 )研究了微粒群算法( p a r t i c l es w 蝴o p t i m i z a t i o n ，p s o ) 在差异工件单机批 调度问题中的应用。首先设计了微粒的编码方法；然后采用了基于优先值 向量的排序方法对微粒进行解码，有效的利用了微粒群算法在离散优化中 的优势；最后利用批调度策略进行分批处理，获得优秀的可行解。 ( 3 )研究了d n a 进化算法( d n ae v o l u t i o n a l g o r i t h m ，d e a ) 在差异工件单机 批调度问题中的应用。引入了分裂、水平选择、变异、垂直选择四种算子， 对垂直选择算子进行了重新设计。充分利用了d n a 进化算法实现简单、 时间性能好的优势；同时，设计了随机选择机制对变异个体进行选择，使 得求解过程能够跳出局部极值，实现全局优化。仿真实验的结果表明改进 的d n a 进化算法是有效的。 ( 4 ) 研究了在模糊环境下的差异单机工件批调度问题。在现实生产过程中，加 工信息的不确定性存在于两个方面：工件在批中的加工时间和批的间隔时 摘要 间。因此本文将n s b m 问题从上述研究的理想环境拓展到更接近现实情 况的模糊环境中，建立了基于模糊数的制造跨度模型。在此基础上，设计 了基于微粒群算法和差异演化的混合优化算法，获得了满意的实验结果。 关键词：生产调度；批处理机；不同尺寸工件；蚁群算法；微粒群算法；d n a 进化算法；模糊加工时间 a b 咖c t a b s t r a c t t h es c h e d u l m go fas i n g i eb a t c h - p r o c e s s i n gm a u c h i n ew i t l ln o n - i d e n t i c a lj o bs i z e s i s 谢d e l yu s e dm t 1 1 er e a lm a i l u f 砬t u r i n ga n dt 1 1 ep r o b l e m so ft h j sk i i l da r ei n t e 伊a t e d w i t ht 1 1 ec h a r 2 u c t e r i s t i c so ft l l ec l a s s i c a ls c h e d u l i n ga n dm eb a t c hs c h e d u l i i l g t h e p r o b l e m so fm i l l i m i z i n gm em a k e s p a i la n d t l l ew e i g h t e dc o m p l e t i o nt i m eo fas i g n l e m a c h i n ea r er e s p e c t i v e l ys t r o n g l yn p - h a r d a n dn p - h a r d t h eo p t 硫i z a t i o no fas i n g l e b a t c h - p r o c e s s i n gm a c h i n e 、i t hn o n - i d e m i c a lj o b s i z e sh a sa l li 1 1 f l u e n c eo nt 1 1 e i n d u s t r y 趾dt h e o r e t i c a lr e s e a r c h i nt h i sp a p e r i r l t e ：i l i g e n ta l g o r i t l l n l sa r ea p p i i e dt 0 s o l v em ep r o b l e m so nas i n g l eb a t c h - p r o c e s s i n gm a c m n e 丽mn o n - i d e n t i c a lj o bs i z e s a 1 1 dm e i l ，t 1 1 ed e t e 珊i i l i s t i c p r o b l e m s a r ee x t e n d e dt 0 f 位z ye n v i r o 衄e n ta r l d a l g o r i t h m s a u r ed e s i g n e df o rt 1 1 e o p t i m i z a t i o no ft 1 1 ef 吆z yp r o b l e m s t h em a i n i i m o v a t i o n so ft h i sp a p e ra r el i s t e da sf o l l o w s ( 1 ) t h e 觚tc o l o n yo p t i m i z a t i o n ( a c o ) m e t h o di ss t u d i e da n dd e s i g n e df o ras i n g l e b a t c h - p r o c e s s i n gm a c h j n e 诹t hn o n i d e n t i c a lj o bs i z e s ( n s b m ) t h ec o d i n ga 1 1 d d e c o d i n gm e c h a n i s mo fa c o i si m p r o v e da r l di 1 1o r d e rt oc o n q u e rt h el o c a l o p t i m u mo fa c o ，t h em e t r o p o l i sc r i t e r i o ni sa d o p t e da st h es e l e c t i o nm e 也o do f t l l ep a t h st os o l v et h ep r o b l e m t h es i m u l a t i o nr e s u l t sd e m o n s t r a t et h ee 伍c i e n c y o ft h ea l g o r i t l n a d d i t i o n a l l y ，t h ec h a o t i co p t i m i z e ri si n t r o d u c e dt oi m p r o v et h e q u a l i t ) ro f a c o ( 2 ) t h ep a n i c l es w 黝o p t i m i z a t i o nm e t h o d ( p s 0 ) i s 印p l i e dt 0n s b m f i r s t l yt h e c o d i n g 印p r o a c hi sd e s i 印e da i l dm e nt 1 1 ep a n i c l e sa r es e q u e n c e du s i n gt h e p r i o r i 够v a l u ev e c t o r sw m c hm a k ep s oa p p r o p r i a t ef o rt h ed i s c r e t eo p t 证l i z a t i o n p r o b l e m 1 1 1t 】1 ed e c o d i n gs e c t i o n ，t 1 1 ef l e a s i b l es o l u t i o n sa r ep r o d u c e dw i t hb a t c h s c h e d u l i n gm e c h 砌s m ( 3 ) d n ae v o l u t i o n a r ya l g o 棚u n ( d e a ) i sa p p l i e dt ot h ep r o b l e m t h eo p e r a t o r so f d i v i s i o n ，l e v e ls e l e c t i o n ，m u t a t i o n 觚dv e n i c a is e l e c t i o na r ei n t r o d u c e d d e ah a l s as i m p l ei m p l e m e n t a t i o na 1 1 da no u t s t a i l d i n gt i m ec o m p l e x i 够a d d i t i o n a l l y ，t h e i i i a b s t r a c t v e n i c a ls e l e c t i o no p e r a t o ri si m p r o v e db yi n t e g r a t i n ga 啪d o ms e l e c t i o nm e t l l o d a ne 疏c t i v eg l o b a lo p t i m i z a t i o ni sa u c l l i e v e d b yj 啪p i n g 舶mt 1 1 el o c a lo p t h 啪 t h en u m e r i c a lr e s u l t sd e m o n s t m t et 1 1 ee 街c i e n c yo fd e a ( 4 ) t h en s b mi i lf 泣：z ym a r m f a c t i l r i n gs y s t e mi ss t i l d i e di i l 口缸sp 印e r 1 1 1t h er e a l i n d u 蛐t l l eu n c e r t a i n t yl i e si n 铆of a c t o r sw h i c hc o i l s i s to ft 1 1 ep r o c e s s i n gt i m e o ft h eb a t c h e sa 1 1 dt 1 1 ei n t e m a l sb e t w e e nt h eb a t c h e s t h en s b mi se x t e n d e df b m t h ec u r r e mi d e 出e n v i r o n m e n tt o 血z z ye r i r o l l m e n ta 1 1 dt h ef u z z ym o d e lo f m i 血m i z i n gt h em a k e s p a i li s e s t a b l i s h e d ah y b 订da l g o r i 岫lb a l s e do nd i 丘e r e n t e v o l u t i o n ( d e ) a n dp s oi sp r o p o s e df o rt 1 1 eo p t i m i z a t i o n 7 i h es i m u l a t i o nr e s u l t s s h o wt h eg o o dp e 响m a n c eo ft h em e t h o d k e y w o r d s ：s c h e d u l i n g ，b a t c h p r o c e s s i n gm a c l l i n e s ，n o n i d e n t i c a lj o bs i z e s ，a n tc o l o n y o p t i m i z a t i o n ，p a n i c l es w 锄o p t i i i l i z a t i o n ， d n ae v o l u t i o n a l g o r i t h m ，f h z z y p r o c e s s i n gt i m e 图序 v i i i 图序 图2 1小规模问题的运行时间对比2 4 图2 2 大规模问题的运行时间对比2 4 图2 3h d e a 在5 0 0 次迭代内的进化2 9 图3 1c p s o 求解小规模算例的结果3 7 图3 2c p s o 求解大规模算例的结果3 8 图4 1d e a 求解j 1 和j 2 类问题的结果4 6 图4 2d e a 求解j 3 类问题的结果4 6 图4 3d e a 求解j 4 类问题的结果4 7 图4 4h d e a 与g a 和s a 的运行时间对比5 l 图6 1 五种算法求解j 3 和j 4 类问题的结果对比6 7 图6 2 五种算法求解j 3 和j 4 类问题的结果对比6 7 图6 3 五种算法的时间性能对比6 8 表序 表序 表2 1工件的加工时间和尺寸示例2 0 表2 2 分批的结果一2 0 表2 32 4 种算例的仿真结果对比2 3 表2 4c a c o 算法与s a 和g a 的性能比较2 8 表3 1基于优先值向量的排序方法3 5 表3 2c p s o 的时间性能3 8 表4 11 0 工件n s b m 问题的初始化4 3 表4 21 0 工件n s b m 问题的单链表示4 3 表4 3单链的分批结果4 3 表4 4d e a 与g a 和s a 的运行时间对比4 7 表4 5h d e a 与g a 和s a 的性能比较5 0 表5 i刀= 1 0 的模糊n s b m 问题示例6 1 表5 2 分批结果及批的模糊延迟6 1 表5 3 模糊制造跨度的仿真结果6 3 i x 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确 的说明。 作者签名：阻二 签字日期： 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人 提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 口公开口保密( 年) 作者签名：塑二一 导师签名： 签字日期： 签字日期： 第一章绪论 第一章绪论 生产调度问题是在工业领域中有着广泛应用的组合优化问题，经过半个多世 纪的探索，生产调度的研究成果已经非常丰富，其中大部分集中在古典调度问题 和批调度问题上。本文研究的n s b m 问题，兼具古典调度和批调度的双重特征， 在实际工业中有着广泛的应用，因此对其优化算法的研究不仅具有理论价值，而 且能够为工业生产提供支持。本章的内容安排如下：1 1 节简要介绍了生产调度 问题的研究情况，1 2 节介绍了批调度问题的研究情况，1 3 节对n s b m 问题的 研究成果进行了总结，然后介绍了本文的研究内容和具体的结构安排。 1 1 生产调度问题研究简介 生产调度问题，简单的说，就是给定可用资源和生产规则，通过设计合理的 调度方案，来完成指定的生产目标。生产调度问题的描述采用的统一表示方法为： 口iply 。其中参数a 表示机器环境：1 为单机，p 为同速平行机，q 为恒速平行 机，r 为变速平行机；f ，d ，分别为f 1 0 ws h o p 、o p e ns h o p 、j o bs h o p 调度模 型。如砌表示所个同速平行机，砌( 6 ) 表示平行批处理机，一个批处理机一次 至多可加工6 作业。f 2 ( 6 。，屯) 表示两阶段的f l o ws h o p 批调度模型，第一阶段处 理机的批容量为6 ，第二阶段处理机的批容量为6 ：。参数卢表示作业约束，例如 ( b ，s ，) 约束，指的是批调度问题中，批的最大容量为b ，每一批中所有工件的尺 寸_ 应满足一b 。参数y 表示优化目标，根据企业生产的具体要求，学者们 提出了各种不同的优化目标，例如制造跨度o ，指所有工件从开始加工到全部 完成的时间，再如加权总完工时间c u l e ，先按照重要性赋予不同工件特定的 权重，对其加权时间的总和进行优化。 第一章绪论 1 1 1 古典调度问题 古典调度问题的研究分类复杂，可以按照不l 司的机器模型分类，也司以按照 各种不同的加工约束又进行细分。下面简要介绍三类代表性的机器模型，分别为 单机、平行机和车间作业调度问题；对于批调度问题，也采用上述三类机器模型 进行介绍。 ( 1 ) 单机调度问题 单机调度问题l | f w q 由加权最短处理时间( w e i 曲t e d s h o n e s tp r o c e s s i n g t i m e ，w s p t ) 分派规则可以求得最优解，但问题1oi q 已是n p 难的( l e n s t r a e ta 1 ，1 9 7 7 ) 。对于问题li 乃l _ q ，h a ue ta 1 ( 1 9 9 7 ) 给出了性能比为 3 + s ，v g 0 的确定性在线算法；g o e m a n se ta 1 ( 2 0 0 1 ) 给出了性能比为1 6 8 5 3 的随机在线算法。另一方面，a 胁ie ta 1 ( 1 9 9 9 ) 则设计了该问题的多项式时间 近似策略( p 0 1 y n o m i a lt i m ea p p r o x i m a t i o ns c h e m e ，p 1 a s ) 算法，即性能比可任 意接近于1 。 ( 2 ) 平行机调度问题 问题pi i c 一，即平行机的制造跨度最小化问题是强n p 难的( g a r ya n d j o h n s o n ，1 9 7 5 ) ，h o c h b a 啪和s h r n o y s ( 1 9 8 7 ) 设计了该问题的p t a s 算法，这 是调度问题p t a s 算法研究的一个突破。问题尸| | c 一的l p t ( l o n g e s t p r o c e s s i n g t i m e ) 分派规则的性能比为4 3 1 3 m ，且这个界是紧致的；而对于问题 尸j0je 嬲，l p t 分派规则是3 2 的近似算法( h o c h b a u m ，1 9 9 5 ) 。 对于问题尸0 q ，即平行机的总完工时间问题，可以使用最短处理时间 ( s h o n e s tp r o c e s s i n gt i m e ，s p t ) 优先规则获得最优解；同时，变速机问题 r l l q 可由二部图匹配( b i p a n i t em a t c m n g ) 方法在多项式时间内求得其最优 解( h o m ，1 9 7 3 ) 。但对于问题p0 叶c ，也即加权总完工时间的最小化问题， 即使只有两台机器，也已经是n p 难的( l e n s 仃ac ta 1 ，1 9 7 7 ) 。对于平行机调度 问题poi q ，c h e k 嘶e ta 1 ( 1 9 9 7 ) 运用抢占式单机松弛算法获得性能比为 2 第一章绪论 3 1 历的近似算法。对于问题rioi w c j ，h a l l ( 1 9 9 7 ) 基于线性规划给出 了性能比为1 6 3 的离线算法，而s 鼬e l l a ( 2 0 0 1 ) 基于半正定规划松弛设计了性 能比为2 的近似算法。另一方面，删e ta 1 ( 1 9 9 9 ) 则给出了问题poi _ c j ， 尺，z oi _ q 的p t a s 算法。 ( 3 ) 车间作业调度问题 目标函数为制造跨度c 一：对于聊= 2 ，问题f 2 0c 一、，2i 印2c 一( 印 为作业的最大工序数) 、d 2l lc 一分别可在d 1 0 9 刀) 、d 仍1 0 9 ，z ) 、d 仍) 时间求 得最优解( j o h n s o n ，19 5 4 ；j a c k s o n ，19 5 6 ；g o n z m e z ，19 7 6 ) 。 而当机器数朋3 时，问题砌i lc 一、咖l lc 一是强n p 难的( g 哪j o l l l l s o n a n ds e t h j ，1 9 7 6 ) 。问题砌i i c 蛳、锄l | c 一、0 m i i c 一已有p t a s 算法( h a l l ，1 9 9 8 ； j a n s e na n ds o l i s - o b 毛2 0 0 3 ；s e v a s t i a n o va 1 1 dw b e g i n g e r ，1 9 9 8 ) 。 针对强n p 难的问题，2 | ，lc 一( l e n s t r ae ta 1 ，1 9 7 7 ) ， p o t t s ( 1 9 8 5 ) 给 出了性能比为5 3 的启发式算法；h a l l ( 1 9 9 4 ) 基于j o l l i l s o n 算法设计了该问题 的p t a s 算法。 目标值为( 加权) 完成时间和( _ ) q ：g o n z a l e z 和s a l l i l i ( 1 9 7 8 ) 首先给 出了问题砌i l q 的基于s p t 的启发式算法，性能比为聊；s m u t n j c h ( 1 9 9 8 ) 证明了问题砌ip r m “i w ，c ，的基于w s p t 的启发式算法的性能比也为聊。 h o o g e v e e n 和k a w a g u c l l i ( 1 9 9 9 ) 证明了问题，2l | q 的基于s p t 的启发式算 法的性能比为2 卢 + 卢) ，a 为所有2 疗个工序中最小的处理时间，j 6 i 为所有2 聆 个工序中最大的处理时间；赵传立等人( 2 0 0 2 ) 证明了如果作业权重具有一致权 因子，那么问题f 2i | q 的基于w s p t 的启发式算法的性能比也为 2 卢( 口+ 卢) 。另外，f i s l l l ( i ne ta 1 ( 2 0 0 3 ) 设计了问题咖ld p j l l ，oi m q 的 p t a s 算法( i “为常数) 。 第一章绪论 1 1 2 批调度问题 批调度问题是调度领域的另一个研究热点，在加工约束方面，批调度问题要 求工件分成批次进行加工，每个批次的工件总尺寸不能超过批的容量。下面同样 按照单机、平行机、车间作业批调度的顺序简要介绍批调度问题的研究进展。 ( 1 ) 单机批调度问题 目标值为制造跨度c 一：对于问题1 ( ) i lc 一、l ( 1 ) i | c 一是平凡问题；而对 于6 ( 2 6 刀) 的问题1 ( 6 ) i ic i 懈，b r u c k ee ta 1 ( 1 9 9 8 ) 给出了s p t 批最优调度算 法，时间复杂性为m i l l d ( 胛l o g ，2 ) ，d 0 2 6 ) ) 。 对于问题l ( 6 ) i ，p ，= p c 一，1 1 ( u r a 和g i m p l e ( 1 9 8 6 ) 给出了求最优解的 有效算法。对于问题l ) 10lc 一，l e e 和u z s o y ( 1 9 9 9 ) 设计了时间为d ( 刀2 ) 的 求最优解的算法，而p o o n 和z h a n g ( 2 0 0 0 ) 给出了时间为d ( ，z l o g 门) 的求最优解 算法。对于强n p 难的问题l ( 6 ) i ，ic 一( b m c k e e ta 1 ，1 9 9 8 ) ，l e e 和u z s o y ( 1 9 9 9 ) 对该问题的几种特殊情况分别给出了多项式时间和伪多项式时间的算法；而l i u 和y u ( 2 0 0 0 ) 证明了问题1 ( 6 ) l ，lc 一的贪心启发式算法性能比为2 ，并且证明 了问题l ( 2 ) i ， 0 ，r ) ic 一是n p 难的，给出了问题1 ( 2 ) l ，ic 一在不同到达时间 数目固定情况下的伪多项式时间算法。对于问题1 ( 6 ) i ，ic 一，d e n g e ta 1 ( 1 9 9 9 ) 给出了时间复杂性为d ( 4 2 他刀引抖1 6 2 倌s 4 脂2 ) 的p t a s 算法。 目标值为( 加权) 完成时间和( w ) c j 问题的研究当中，对于问题 1 ( ) o m q ，b m c k e e ta 1 ( 1 9 9 8 ) 已经给出了后向动态规划( b a c 删d y n a l i c p r o 伊锄瑚i i l g ，b d p ) 算法，时间复杂性为d 伽1 0 9 刀) ；而对于固定的6 ( 2 6 歹= 1 ，2 胛；尼= 1 ，2 所 瓦o 喜考咒 ( 1 - 1 ) ( 1 - 2 ) ( 1 - 3 ) ( 1 4 ) ( 1 5 ) ( 1 6 ) ( 1 - 7 ) 其中，聊为分批之后的总批数，坛为。一1 变量，当工件j f 6 k 时，琢= 1 ； 否则取= o 。式( 1 - 1 ) 表明模型的优化目标为制造跨度；( 1 2 ) 限定一个工件 只能分配到一个批中；( 1 3 ) 即为机器容量的约束；( 1 4 ) 为批的加工时间的计 算方法；( 1 6 ) 、( 1 7 ) 式为问题的基本约束。n s b m 的另一个典型的目标函数 为加权总完工时间，其模型在上述c 弧的基础上，约束条件保持不变，最小化的 目标函数为q = q 。u z s o y ( 1 9 9 4 ) 对l i b ，t l c 旅的复杂度进行了严格的 证明，同时设计了优化制造跨度的启发式算法。u z s o y 的证明方法为，首先假定 n s b m 问题中所有工件的加工时间均相等，那么c 衅问题等价于装箱问题，其中 箱子容量b ，物品体积为s ，而装箱问题是强n p 问题，因此工件加工时间完全相 同的情况下，n s b m 的c r 麟已经等价于装箱问题，故c 腻是强n p 问题。 针对c 二问题，u z s o y 设计了b f f ( b a t c hf i r s tf i t ) 算法，这是在早期文献 中，求解非常有效的一种算法，算法的实现步骤为： 步骤1 ：将所有工件任意排序，依次编号； 步骤2 ：将第一个工件放到第一个能够容纳该工件的批中，如果当前的批没 有能够容纳该工件的，新建一个批。重复步骤2 直到所有工件都安排到批中。 7 第一章绪论 步骤3 ：将这些批以任意顺序在机器上进行加工。 对所有工件加工时间相同的n s b m 问题，由b f f 获得的解记为c 雠一职f ， 最优解记为乞，那么有c 雌一肥f 鼍吒+ ，其中f 为工件的加工时间，且这 个上界是紧致的。 上述介绍的是目标函数为l 的问题，而在实际生产中，根据企业自身的条 件和客户、供应商的具体需求，制造企业会有不同的生产要求，因此，对n s b m 问题的研究，也采用了不同的目标函数，目前研究中常见的几种为： ( 1 ) c 姗，即制造跨度，具体定义如上所述； ( 2 ) w c ：，即加权完工时间，其中e 为工件f 的加工时间，而w 为e 的 权重； ( 3 ) k ，即最大延迟时间。工件的延迟厶等于实际加工时间c l 减去其交 货期z ；k 等于所有工件的延迟中最长的延迟时间； ( 4 ) 玑，即加权延迟工件数，对工件f ，如果加工完成的时间符合交货期， 则= o ，如果加工被延迟，则v = 1 ，= w j v 为总体加权延迟工件数，其 中w 是工件f 的权重。 ( 5 ) ，即最大提前时间，工件f 的完工时间比交货期z 小，则互= 4 一c f ， 而= m 野巨。 1 2 2 研究进展 与古典调度问题和批调度问题相比，n s b m 问题的研究时间很短，因此成果 较少。上世纪9 0 年代中期n s b m 问题的研究开始兴起，早期的研究集中在问题 复杂度的证明和启发式算法的研究上，后期由于新的智能算法不断出现，不少学 者开始将智能算法引入n s b m 问题中，而智能算法在n s b m 问题中的应用也成 为了一个很有价值的研究方向。 8 第一章绪论 u z s o y ( 1 9 9 4 ) 首先对半导体芯片预烧和食品加工的过程进行抽象，提出了 n s b m 问题，证明了n s b m 的制造跨度问题( 1 i b ，0l c 诚) 和( 1 i b ，0l g ) 的复 杂度，进而设计了优化c 眦和q 加权完工时间的启发式算法。s u n g 和c h o u l l g ( 2 0 0 0 ) 对优化c m 。的启发式算法做了改进，并对静态n s b m 问题进行优化， 这类问题中工件的到达时间是确定的；另外，文中提出了动态工件到达时间的 n s b m 问题，这类问题中的工件并不在同一时刻到达，作者首先采用了分枝定界 法进行了求解，而后针对这类问题设计了性能较好的启发式算法。d u p o n t 和f l i p o ( 2 0 0 2 ) 采用了结合穷举策略的分枝定界法进行求解，通过大量的仿真实验，表 明在引入了穷举策略之后，分枝定界方法在求解多工件问题时，性能有着明显的 改进。但上述的启发式算法普遍存在运行时间长的问题，在应用上受到了限制， 因此其他学者采用了性能更优的智能优化算法，这类算法在时间性能和解的质量 上均有一定的改善。s e v a u x 和p e r e s ( 2 0 0 2 ) 首先引入了遗传算法，对加权延迟 工件数进行优化；k o k s a l a l l 和k e h a ( 2 0 0 3 ) 利用遗传算法进行多目标优化，采 用的目标函数为加权延迟工件数和最大提前时间。k a l s h a l le ta 1 ( 2 0 0 6 ) 设计了 优化制造跨度的两种改进的遗传算法，第一种为基于工件排序的遗传算法 ( s e q u e n c eb a s e dg a ，s g a ) ，首先随机产生工件序列，然后利用分批规则对这 些工件序列进行分批；第二种是基于批次的混合遗传算法( b a t c hb a s e dh y b r i d g a ，b h g a ) ，b h g a 首先随机产生批次，根据问题的规则确保这些批次能够形 成可行解，然后在设计算法时，在g a 中混合了配对交换的启发式算法( p a i 而s e s w 印p i gh e 面s t i c ，p s h ) ，这种混合设计能够有效提高g a 的寻优能力。 d e m o d 删le ta 1 ( 2 0 0 6 ) 则采用了改进的算子对c 。进行优化，针对n s b m 问题 在加工序列和分批两个方面的约束，作者将g a 的交叉和变异算子进行了新的设 计，并通过大量的实验证明了算法在性能上的改进。 但遗传算法存在一定的问题，在解决大规模的n s b m 问题时，其收敛性能较 差。m e l o u kc ta 1 ( 2 0 0 4 ) 首先引入了模拟退火算法对制造跨度进行优化，并采 用了随机方式获得不同规模的算例，这些算例已被其他学者采用，作为n s b m 仿真的通用算例，但s a 的收敛精度不如g a 。另外，在单机问题上，吴超超和 顾幸生( 2 0 0 4 ) 、马建辉和牛海军( 2 0 0 2 ) 考虑了带有提前拖期惩罚单机批调 9 第一章绪论 度的问题，赵玉芳和唐立新( 2 0 0 6 ) 提出了单机连续型批调度问题及优化方法， 将单机问题进一步扩展；张玉忠等( 2 0 0 6 ) 研究了工件分两批到达的单机批调度 问题，并设计了一种性能比不超过3 3 1 4 的启发式算法。另外，在非单机问题中， d e m o d a r a n 和c h a l l g ( 2 0 0 8 ) 研究了差异工件的并行机调度问题，证明并行机的 制造跨度最小化问题的复杂度为n p - h 砌，并设计了启发式算法进行优化； 鼬d o u a r de ta 1 ( 2 0 0 8 ) 研究了差异工件动态到达的在线调度算法，对于机器尺寸 有限和无限这两种情况，证明了问题的上下界，在此基础上，设计了在线调度方 法；z h a n g 和c a o ( 2 0 0 8 ) 从装箱问题的渐进p t a s 出发，设计了优化差异工件 批调度问题的渐进p t a s 方法，该算法近似比的下界为3 2 ，提高了近似解的质 量。 1 3 本文研究简介 1 3 1研究内容 本文的研究内容主要分为两个方面：首先，研究并设计性能优异的算法来求 解n s b m 问题，进一步推进n s b m 问题优化算法的研究；其次，将n s b m 问题 扩展到更接近实际加工情形的模糊环境中，从而更好的为工业制造提供可借鉴的 参考。 在工业生产中，有很多问题属于差异工件批调度问题。例如，在半导体芯片 制造系统中，芯片制造末端的高温预烧工序是将芯片暴露在高温之下以排除有潜 在缺陷的芯片，通常它的加工时间为1 2 0 小时以上，是其它工序加工时间的几倍、 几十倍，每块芯片的预烧工序时间由客户( 如军用、民用等) 根据需要指定，在 芯片预烧时，可以将客户指定的芯片预烧工序时间延长，但不能缩短客户指定的 预烧工序时间。预烧芯片大小也可能不一样，但一个炉子可以同时容纳多个预烧 芯片，因此在同一炉中的批预烧时间为批中预烧芯片的最长预烧工序时间。如果 将预烧芯片看作作业，炉子看作机器，则在机器上处理的作业不仅具有处理时间， 还有大小不同，这是一个作业有大小的单机调度问题。 又如在船闸调度系统中，每天有大量的船舶需要通过船闸，每个船舶大小不 1 0 第一章绪论 一，而且船舶中所载货物的重要程度差异很大，如客轮优先级最高、运输新鲜蔬 菜水果的船舶优先级次之，而运输水泥、钢材等船舶优先级最底。如果将每级闸 室看作一个机器，过闸船舶看作作业，则所有作业加工时间相同，但大小不一定 相同，每一级闸室的调度就是一个n s b m 问题。 实际中这样的例子还有许多，如港口货物装卸、带托盘的车床加工、汽车货 物运输等。n s b m 问题的研究具有重要的现实意义，以芯片制造系统为例，芯片 加工的调度方案直接决定了半导体芯片工业的效率和对客户需求的响应速度，并 且该工业在整个经济发展中扮演了重要角色，而预烧工序通常又是半导体制造企 业进行有效生产调度的关键之一。预烧工序相对于其它工序，它的加工时间特别 长，并且它发生在制造过程的末端，几乎没有可能通过后续工序的挖潜来补偿预 烧工序的延迟，因此该工序对按期交货有直接影响。而且相对于其它的制造业来 说，半导体制业的设备费用十分昂贵，因此资源有效使用就显得更为关键。因此， 研究设计优秀的调度方案，能够提高生产效率，节约生产成本，有效满足客户需 求，从而提升企业的竞争能力。 另一方面，目前对n s b m 问题的研究都集中在确定性问题当中，而这类问 题要求加工过程是理想化的。从工业生产角度看，这种理想化分为下述三个方面： 首先，工件的加工时间是确定的，在加工之前已经明确，并且在加工过程中不会 发生变化；其次，批的就绪时间和处理时间也是确定的，加工机器处于理想状态， 不存在任何的故障；最后，人员的操作不存在任何失误，整个加工过程能够完全 按照既定的调度方案进行。但在现实加工中，这三类因素很明显都不是理想化的， 工件质量问题、设备故障问题以及操作人员的失误不可能完全避免，甚至会出现 其他各种难以预料的问题。因此，研究不确定性环境下的n s b m 问题能够更接 近现实生产，从而更有效的指导现实生产。本文采用了模糊技术，将确定性问题 扩展到模糊环境中，更直接的描述现实加工情形，并对模糊环境中的n s b m 设 问题计了优化算法。 1 3 2 结构安排 目前对单机问题的研究采用的多为启发式算发，这类算法在解决多工件、复 第一章绪论 杂加工的问题时，性能较差，而遗传算法和s a 均存在自身的缺陷，因此，本文 引入了新的智能算法，对算法进行了针对性的改进设计，有效提高求解性能。另 外，建立了模糊环境下的n s b m 问题，构造了制造跨度的优化模型，并提出了 优化算法。 第二章研究了蚁群算法( a n tc o l o n yo p t i m i z a t i o i l ，a c o ) 在n s b m 问题中的 应用。蚁群算法( d o r i g oe ta 1 ，1 9 9 6 ) 属于元启发式算法，是群智能的一个典型 应用，算法的核心是根据人工蚁的集体行为而设计的多智能体系统。但作为分布 式算法，a c o 在求解复杂问题的过程中会产生过早收敛的问题( b l 啪a n d s 锄p e l s ，2 0 0 4 ) 。在搜索过程的前期，人工蚁不能充分获取全局信息，主要通过 独立搜索的方式来获得可行解。如果多数人工蚁都集中到了局部最优的路径上， 该路径上的信息素便会不断累积，这样会影响到后期迭代过程中其他人工蚁对路 径的正确选择，从而陷入局部最优。本文针对性的改进了路径激励策略，在算法 运行的早期选择的优秀路径较多，避免了求解过程向局部最优解的收敛，在后期， 随着选择条件的加强，选择的路径迅速减少，保证了算法的搜索效率。 第三章研究了微粒群算法在n s b m 问题中的应用。微粒群算法是一种基于 迭代进化计算方法( k e n n y d ya n de b e r h a r t ，1 9 9 5 ) 。p s o 在实现过程中，需要的 微粒个数少，计算简单，而且具有很好的鲁棒性。但p s o 也存在一定的问题， 在进化过程中p s o 通过微粒自身搜索的最好解和全局最好解来改进当前解，如 果不能有效跳出局部的深度搜索，那么容易形成算法的早熟收敛。本文改进了微 粒群算法的性能：一方面引入随机选择机制，强化微粒的广度搜索，来改进种群 的质量；另一方面，设计了混沌局部优化算子，通过混沌方法改进p s o 的性能。 第四章研究了d n a 进化算法在n s b m 问题中的应用。d n a 进化算法( d n a e v o l u t i o na l g o r i t h m ，d e a ) 是一种新的元启发式算法( 丁永生等，2 0 0 1 ) ，算法 模拟了单细胞分裂过程中d n a 的演变和进化机制。d e a 首先被应用于连续优化 问题的求解，但d e a 算法的垂直选择算子，采用的是确定性最优选择方法，约 束了算法的收敛性能。本文在优化n s b m 问题时，提出了一种改进的垂直选择 算子，将模拟退火算法的全局优化策略嵌入d e a ，有效的解决了进化过程容易 陷入局部最优的问题：同时采用分批的启发式算法对d n a 单链进行解码，取得 了很好的实验效果。 1 2 第一章绪论 第五章研究了模糊生产系统中的n s b m 问题。现实生产中存在的大量的不 确定性因素，使得工件的加工信息往往不能准确预知，存在着模糊不确定性( 舢l 乩 2 0 0 3 ；w 抽g ，2 0 0