（管理科学与工程专业论文）蚁群粒子群混合优化算法及应用.pdf

iiillrllr l 1 l l 1 l lr l l i f l i l ! l l ! ! l l l ! l lr 1 l l l 1 l l l y 1 5 3 1 7 5 8 天津大学博士学位论文 蚁群粒子群混合优化算法及应用 h y b r i do p t i m i z a t i o na l g o r i t h mo fa n tc o l o n y a n d p a r t i c l es w a r m w i t ha p p l i c a t i o n 一级学科：管理科学与工程 学科专业：管理科学与工程 作者姓名：张维存 指导教师：郑丕谔教授 所在学院：管理学院 2 0 0 7 年1 2 月 中文摘要 柔性作业车间调度问题( f j s p ) 比传统作业车间调度问题的复杂性更高，其 求解难度更大。本文利用蚁群和粒子群混合优化算法研究了柔性作业车间调度一 类问题的求解方法，主要工作与创新点如下： 1 、研究了蚁群粒子群混合优化算法在单目标柔性作业车间调度问题中的应 用。首先，根据f j s p 的求解特点，建立了主从两级协调的蚁群粒子群混合算法 结构。然后，对于主级蚁群优化算法构建了工序可选加工设备吸取图模型，设计 了蚂蚁的解构造图和蚂蚁在工序可选加工设备间的转移概率；对于从级粒子群优 化算法，采用位置矩阵的粒子表示方法，以粒子元素向量中优先权值的次序表示 作业车间调度问题( j s p ) 中工件调度的次序，并在此基础上设计优先权值向量的 解码方法。最后，以实验方式分析了蚁群粒子群混合优化算法中主要参数的取值 问题。 2 、研究了蚁群粒子群混合优化算法在能力约束和多目标柔性作业车间调度问 题中的应用。针对上述两类柔性作业车间调度问题分别重新设计了蚁群优化算法 中蚂蚁转移概率的局部启发式信息的计算和更新方式，使主级蚁群优化算法既能 够在能力约束的柔性作业车间调度问题中处理能力约束条件，又能够在多目标柔 性作业车间调度问题中实现设备总负荷和关键设备负荷最小两个优化目标。 3 、研究了蚁群粒子群优化算法在多模式资源受限项目调度问题( m r c p s p ) 中的应用。首先，根据m r c p s p 的求解特点，建立了主- 从两级协调的蚁群粒子 群混合算法结构。然后，对于主级蚁群优化算法设计了蚂蚁在任务间游历的转移 概率和蚂蚁在任务执行模式间游历的模式优选概率；对于从级粒子群优化算法， 采用基于任务的粒子表示方法，以任务优先权值标示任务的执行次序，并在粒子 的解码中设计了任务优选概率的优选规则。最后，选用项目调度标准问题库 ( p s p l i b ) 中的测例，以实验的方式对蚁群粒子群混合优化算法中的主要参数取 值进行优化。 关键词：蚁群优化算法粒子群优化算法柔性作业车间调度项目调度能力约束、 多目标多模式资源约柬 a bs t r a c t d h et om a c h i n ec o n s t r a i n t ，f l e x i b l ei o bs h o ps c h e d u l i n gi sm u c hm o r ec o m p l e x t h a nt r a d i t i o n a li o bs h o ps c h e d u l i n ga n de v e nm o r ed i f f i c u l tt ob es o l v e di nv i e wo f o p t i m i z a t i o n i nt h i sd i s s e r t a t i o n 。ah y b r i do f a n t c o l o n y a n dp a r t i c l es w a r m o p t i m i z a t i o na l g o r i t h m si su s e dt os o l v ef l e x i b l es c h e d u l i n gp r o b l e m ss u c ha sf l e x i b l e i o bs h o ps c h e d u l i n g i nt h i sd i s s e r t a t i o n 。t h em a i nw o r ka n di n n o v a t i o n sa r ea sf o i l o w s ： 1 f l e x i b l ej o bs h o ps c h e d u l i n gp r o b l e m sw i t hs i n g l eo b j e c t i v ea r es t u d i e du s i n g t h eh y b r i do fa n tc o l o n ya n dp a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h m s f i r s t , ah y b r i do f a n tc o l o n ya n dp a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h m sw i t hm a s t e r - s l a v es t r u c t u r ei s p r o p o s e db a s e do nt h ec h a r a c t e r i s t i co ff l e x i b l ej o bs h o ps c h e d u l i n gp r o b l e m st ob e s o l v e d t h e n a na n ts o l u t i o nc o n s t r u c t i o ng r a p hi sp r e s e n t e da n dt h et r a n s f e r p r o b a b i l l t yo fa n tb e t w e e nm a c h i n e sw h i c hc a nb es e l e c t e dt op r o c e s si o bb a s e do nt h e e x t r a c tg r a p ho fj o bp r o c e s s i n gm a c h i n e sf o rt h ea n tc o l o n ya l g o r i t h ma tt h em a s t e r l e v e i 、i l e a tt h es l a v el e v e l ad e c o d i n gm e t h o di sd e s i g n e df o rp a r t i c l eb a s e do nt h e s e q u e n c eo fp r i o r i t yn u m b e ri np a r t i c l ep o s i t i o nm a t r i x f i n a l l y , t h ev a l u eo fp r i m a r y p a r a m e t e r si nt h eh y b r i da l g o r i t h mi sa n a l y z e db ye x p e r i m e n t s 2 c a p a c i t yc o n s t r a i n e da n dm u l t i - o b j e c t i v ef l e x i b l ej o bs h o ps c h e d u l i n gp r o b l e m s a r es t u d i e du s i n gt h eh y b r i do fa n tc o l o n ya n dp a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h m t h ec o m p u t i n ga n du p d a t i n gm e t h o do fl o c a lh e u r i s t i ci n f o r m a t i o ni na n tt r a n s f e r p r o b a b i l i t yi sr e d e s i g n e db a s e do nt h ec h a r a c t e r i s t i c so ft h ep r o b l e m sa b o v e m e n t i o n e d t h e r e f o r e n o to n l yt h ec a p a c i t yc o n s t r a i n t sc a nb ed e a l tw i t h ，b u ta l s ot h em i n i m u mo f t o t a lm a c h i n el o a da n db o r i c n e c km a c h i n el o a dc a nb er e a li z e db yt h ea n tc o l o n y o p t i m i z a t i o na l g o r i t h ma tm a s t e rl e v e l 3 t h em u t l i m o d er e s o u r c e c o n s t r a i n e dp r o j e c ts c h e d u l i n gp r o b l e m sa r es t u d i e d u s i n gt h eh y b r i do fa n tc o l o n ya n dp a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h m f i r s la h y b r i do fa n tc o l o n ya n dp a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h mw i t hm a s t e r - s l a v e s t r u c t u r ei sp r o p o s e db a s e do nt h ec h a r a c t e r i s t i co fm u t l i m o d er e s o u r c e - c o n s t r a i n e d p r o j e c ts c h e d u l i n gp r o b l e m st ob es o l v e d t h e n ，t h et r a n s f e rp r o b a b i l i t i e s o fa n t b e t w e e nt a s k sa n db e t w e e nt a s k m o d e sw h i c hc a nb es e l e c t e dt op e r f o r mt a s kb a s e do n t h ee x t r a c tg r a p ho ft a s kp e r f o r m i n gm o d e l sf o rt h ea n tc o l o n ya l g o r i t h ma tt h em a s t e r l e v e l 肌i le a tt h es l a v el e v e l ，ad e c o d i n gm e t h o di n c l u d i n gt a s k s e l e c t i n gp r o b a b i l i t y i sd e s i g n e df o rp a r t i c l eb a s e do nt h es e q u e n c eo fp r i o r i t yn u m b e ri np a r t i c l ep o s i t i o n v e c t o r f i n a l l y , t h ev a l u eo fp r i m a r yp a r a m e t e r si nt h eh y b r i da l g o r i t h mi sa n a l y z e db y 图目录 图1 1 论文结构1 2 图2 1 蚁群觅食行为示意1 5 图2 2 蚁群算法流程图2 0 图3 1 蚁群一粒子群两级算法结构3 9 图3 23 道工序，3 个可选设备析取图4 0 图3 3 工件1 的可选加工设备析取图的结点分布4 3 图3 4 工件1 的工序可选加工设备析取图“ 图3 5 工件2 的工序可选加工设备析取图4 4 图3 6 工件3 的工序可选加工设备析取图，4 4 图3 7 工件2 的工序可选加工设备解构造图4 5 图3 8 蚁群优化算法求解工艺路线流程4 7 图3 9 粒子矩阵与调度方案的映射关系。5 0 图3 1 0 粒子群优化算法求解j s p 的流程5 3 图4 1 蚁群和粒子群算法的优化关系7 2 图4 2a 0 时的收敛区域：7 6 图4 4 根据矩阵么得出的收敛区域7 8 图4 5j s p 最优解示例7 9 图5 1 约束类别甘特图8 8 图5 2 工件2 的工序可选加工设备解构造图9 2 图5 3 更新后的工件2 的工序可选加工设备解构造图9 3 图5 4 测例2 优化解9 8 图6 1 各优化目标间的关系1 0 6 图6 2 工件2 的工序可选加工设备解构造图1 0 8 图6 3 工件2 更新后的工序可选加工设备解构造图1 图7 1 项目网络图及其两种调度方案j 1 1 5 图7 2 蚁群粒子群优化算法结构”6 图7 3 粒子向量元素结构”7 图7 4 各实例中屈的不同取值1 2 1 表目录 表1 1f j s p 描述实例1 4 表1 2f j s p 描述实例2 4 表1 3f j s p 的性能指标6 表2 1w a s 、蚁群和蚂蚁算法对旅行商问题求解情况比较2 5 表3 1f j s p 描述实例4 2 表3 2 粒子位置的多维表示方法4 9 表3 33 4 型f j s p 工序可选加工设备和加工时间5 5 表3 48 8 型f j s p 工序可选加工设备和力n - r - 时间5 5 表3 51 5 1 0 型f j s p 工序可选加工设备和加工时间5 6 表3 6 不同蚁群规模下测试结果5 9 表3 7 可选加工设备数与蚂蚁数之间关系6 0 表3 8 不同口和取值下实验结果6 1 表3 9 不同信息素强度p 取值下实验结果6 3 表3 1 0 不同信息素挥发因子p 取值下实验结果6 5 表3 1 1 不同粒子群规模9 p 下实验结果6 8 表3 1 2r l w 和l d w 不同粒子群规模q 尸下平均收敛代数6 9 表3 1 3 与遗传算法的计算结果比较6 9 表4 1j s p 优化示例7 9 表4 2 相等性能指标下的不同优先权值次序8 0 表4 3 与优先权值次序1 对应的部分极值点8 0 表5 1 问题1 工序设备、加工时间和设备能力9 5 表5 2 问题2 工序设备、加工时间和设备能力9 5 表5 3 本文算法两组测试问题的计算结果9 7 表5 4 文献 1 0 7 算法两组测试问题的计算结果9 7 表6 1 问题( 8 8 ) 算法结果与比较1 1 0 表6 2 问题( 1 0 1 0 ) 算法结果与比较”1 表7 1 舐：反不同取值下的优化结果1 2 0 表7 2 啦：屈不同取值下的优化结果1 2 1 表7 3 与其他算法计算结果的比较 2 2 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得苤壅盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：独引谵 签字日期：研年月勋日 学位论文版权使用授权书 本学位论文作者完全了解苤鲞盘堂有关保留、使用学位论文的规定。 特授权苤鲞盘茔可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：多弓1 治 导师签名： 签字日期：力卯罗年月劬日签字日期： 天津大学博士学位论文 1 1 研究背景 第一章绪论 调度( s c h e d u l i n g ) 是指在一定的约束条件下，合理地分配资源( r e s o u r c e ) 完 成一批给定的任务( t a s k ) 或者作业( j o b ) ，获得某些性能指标( p e r f o r m a n c e c r i t e r i o n ) 如加工时间或生产成本等的最优化n 1 。这里的资源是一种泛指，如人 员、金钱、设备、工具、材料和能源等，而任务也可以有不同的解释，从制造系 统的设备分配到计算机系统的信息处理等等。在有些文献中乜3 ，调度问题也被称 为排序问题( s e q u e n c i n g ) 。但“排序”与“调度”存在一定的区别，以生产车间 的设备加工为例，“排序”主要考虑的是在所有设备上一个工件序列的分配和置 换问题。而“调度”不仅要考虑次序问题( 包括被加工对象“工件”的次序和提供 加工对象“设备”的次序) ，而且更重要的是对时间的分配。因此，有些学者聆1 认 为“排序是一种特殊的“调度，“调度一词也被更广泛地使用。 在企业编制生产作业计划时，经常影响到个工件在m 台设备上加工的次序 问题，即当多个工件经过多台设备加工时，如何安排加工次序使某些目标达到最 优，这就是生产管理领域一直研究的n x m 类型作业车间调度问题( j o b - s h o p s c h e d u l i n gp r o b l e m - j s p ) 。调度问题产生的背景虽然主要源于制造行业，但其 理论被广泛地应用于计算机系统、交通运输、物流等众多领域，因此，调度问题 中的工件和设备都应理解成抽象的概念，可以代表极为广泛的具体对象，如服务 机构、作业设施和操作人员等统称为“设备”，而被服务的顾客、任务和零件统 称为“工件”。如生产管理中的流水线调度问题( f l o ws h o ps c h e d u l i n gp r o b l e m ) 和作业车间调度问题，物流系统中配送车辆优化调度问题( v e h i c l es c h e d u l i n g p r o b l e m ) 和自动化立体仓库堆垛机拣选作业调度问题，港口生产中的设备调度问 题，如泊位调度问题( b e r t ha l l o c a t i o np r o b l e m ) 。其中生产管理的作业车间调 度问题是最复杂、最困难和最普遍的一类问题。作业车间调度是针对一项可分解 的工作( 如工件制造) ，探讨在尽可能满足约束条件( 如交货期、工艺路线、资源 情况) 的前提下，通过下达生产指令，安排其组成工序使用哪些资源，加工时间及 加工的先后次序，以获得工件加工时间或成本的最优化。 作业车间调度问题已越来越引起企业界的重视。由于高新技术特别是信息技 第一章绪论 术的迅速发展，推动着企业全面变革，同时客户需求的定制化，经济的全球化已 成必然趋势，这些变化都使企业在国际市场上的产品竞争日趋激烈。企业要想在 激烈的竞争中生存，就必须对市场的急剧变化做出快速反应，必须引进越来越复 杂的生产制造系统，如柔性制造系统( f l e x i b l em a n u f a c t u r i n gs y s t e m f m s ) 。针 对这些新系统又产生了一些新的柔性作业车间调度问题( f l e x i b l ej o b - s h o p s c h e d u l i n gp r o b l e m - f j s p ) 。f j s p 是企业界迫切需要解决的，但较j s p 更具复杂 性的类调度问题。制造系统中好的调度方案和快速形成优化调度方案的计算技 术，不仅能够优化资源的利用，降低生产成本，而且能够提升企业的生产经营效 率和快速反应能力，从而为企业带来较强的竞争优势。 自1 9 5 4 年，j o h n s o n 提出对两台设备的流水车间调度问题的研究以来，以j s p 为主的调度问题和理论的研究已经经历了几十年的发展，生产调度理论已经在运 筹学和工业工程等学科中形成了一个独立的分支方向，其问题的复杂性和求解的 困难性使得调度问题一直都是很多学者研究的热点问题。调度问题的核心是模型 和算法，因此，调度理论的研究也一直围绕着两个方面展开，一方面是研究一些 新出现的调度问题，如e t ( 提前拖后期) 调度问题、多处理器调度问题等，另一 方面则是一些新的优化技术，如遗传算法( g a ) 、模拟退火( s a ) 、粒子群优化算法 等不断被应用到调度问题中以改善调度问题的优化结果，这两个方面的研究一直 不断地推动着调度理论的发展。 在理论界，由于许多复杂理论研究( 如数学规划、人工智能、控制理论等) 的 发展，已经为f j s p 的研究积累了丰富的文献。f j s p 作为生产管理最为困难的问题 之一，已经证明属于n o n d e t e r m i n i s t i cp o l y n o m i a l - h a r d 问题，且调度方案随设 备数和工件数的增加而呈指数增长。因此，对f j s p 的研究，近年来吸引了国内外 许多学者和实际作业车间调度人员的关注。研究j s p 最初主要采用最优化方法，尽 管可以获得最优解，但计算规模不可能很大且实用性差，所以对f j s p 的优化性能 更差。然而，近年来人工智能、进化计算等的迅速发展，为f j s p 的研究开辟了新 的思路和方向。 1 2 研究意义 现代日益强化的竞争趋势和客户定制化需求促使生产者重新估计生产制造战 略，采用更先进的制造和管理技术，从有限的设备中选择最恰当的组合方式，满 足被加工任务的各种约束，并确定工件在相关设备上的加工次序和时间，以保证 所选择的性能指标最优，能够潜在地提高企业的经济效益。因此，f j s p 具有了越 2 天津大学博士学位论文 来越多的实际应用背景，开发有效而精确的f j s p 求解算法是调度和优化领域重要 而崭新的研究课题。 尽管j s p 在最近的5 0 多年来已经成为生产管理的研究热点，但由于实际生产 的复杂性和不确定性，j s p 仍是一个相当困难的问题。在以往的j s p 研究中，仅 考虑每一工件具有唯一确定加工工艺路线的情况。而实际的加工环境中，某道工 序应该可以在多台设备上加工，特别是加工技术、自动化技术的发展及f m s 的出 现，工件加工工艺路线必须唯一确定的传统限制已被突破，工件具有多个可选择 的工艺路线，即路线柔性已成为生产的实际需求。f j s p 由于考虑了工件可选工艺 路线，对充分发挥j o bs h o p 灵活特点是至关重要的m 1 。它可有效地规划生产活动 和资源，平衡设备负荷，缩短加工时间，减少在制品库存，而且可以避免j o bs h o p 正常运行过程中的阻塞和拥挤，甚至在系统出现异常状态( 如故障) 时，仍能维持 生产的继续进行，从而给j o bs h o p 调度系统带来了很大的灵活性，大大提高制造 系统的整体性能。但也给j o bs h o p 的优化调度问题带来新的挑战。因为这类j o b s h o p 的可行调度的数目要比传统相同规模的无路线柔性的j s p 的可行调度数目大 得多，在这样大的可行解范围内寻找最优解几乎不可能，只能求其近似最优调度 解。因此，研究f j s p 不仅具有较大的实用价值，而且还有相当大的理论意义。一 方面，f j s p 的解决本身具有现实的应用价值，一个好的作业调度方案不仅可以降 低生产成本，而且可以提高企业产品的准时交货能力，从而增强企业的竞争力； 另一方面，f j s p 的研究推动了遗传算法、禁忌算法、粒子群优化算法、蚁群优化 算法、启发式方法等优化方法的发展与融合，这也为其他领域类似问题的解决提 供了条件与手段。 1 3 柔性作业车间调度问题的国内外研究概况 1 3 1f j s p 的描述 f j s p 是近些年来一个十分活跃的研究课题。它们通常是针对如何配置制造系 统，特别是柔性制造系统的资源而实现目标优化而展开的。一般的f j s p 可以这样 描述： 1 有m 台加工设备m l ，m 2 ，册f ； 2 有 r 种待加工工件口，e ：，e ，每种工件的加工由若干道工序组成； 3 可加工某一工序的设备有多台，同一工序在不同的可选设备上的加工时间 随设备性能不同而不同； 第一章绪论 目标是选定每个零件的工艺路线( 工序加工设备) ，并找到各设备上一个可 行的调度方案，使一些给定的性能指标得到优化。 可以用一个二维表格描述f j s p 问题，表中的数字表示工件e ，的某工序在设备 肌上的加工时间，“木”表示设备m 不能加工相应的工序，每一行数据对应的设备 组成的集合表示工序可选j n - f 设备集合。表1 1 和表1 2 均描述了一个3 x4 ( 即3 个工件、4 台设备) 类型的f j s p 问题。 表1 1f j s p 描述实例1 表1 2f j s p 描述实例2 在f j s p 中，工艺路线的约束是由工艺约束和技术约束合成的。但与j s p 相比， 在f j s p 中技术约束被放松了，工件的工艺路线是可以变化的，所以问题的解空间 较j s p 更大，增大了求最优解的难度。 1 3 2f j s p 的分类 4 天津大学博士学位论文 根据研究的侧重点不同，f j s p 有多种分类方式。 1 根据生产环境的特点，可将其分为确定性f j s p 和随机性f j s p 。 2 根据加工特点，可分为静态f j s p 和动态f j s p 。 静态f j s p 是指所有待安排加工的工件均处于待加工状态，因而进行一次调度 后，各工件的加工顺序被确定，在以后的加工过程中就不再改变。 动态f j s p 是指工件依次进入待加工状态，各种工件不断进入系统接受加工， 同时完成加工的工件又不断离开，还要考虑加工环境中不断出现的动态扰动，如 加工超时、设备的损坏等，因此动态f j s p 要根据系统中工件、设备等的状况，不 断地进行调度。 3 根据工序可选择的设备数量，可分为完全f j s p 和部分f j s p 。 完全f j s p 是指任意工件e ，( f = l ，n ) 的某工序可以在所有设备上加工，如 表1 1 所示。 部分f j s p 是指存在一个工件e ，( 江1 ，n ) 的某工序只能在所有设备中的部 分设备上加工，如表1 2 所示。 1 3 3f j s p 的特点 1 复杂性 由于装卸作业、运输作业、仓库之间相互影响、相互作用，每个工件又要考 虑它不同的工艺路线中的加工时间、装卸时间、搬运时间、准备时间、操作顺序、 设备能力、交货期等，因而相当复杂。由于f j s p 是在等式或不等式约束下求性能 指标的优化，在计算上往往是n p 完全问题，即随着问题规模的增大，对于求解最 优化的计算量呈指数增长，使得一些常规的最优化方法往往无能为力。 2 动态随机性 在实际的生产调度系统中存在很多随机的和不确定的因素，比如工件到达时 间的不确定性，加工时间也有一定的随机性，而且生产系统中常出现一些偶然事 件，如设备的损坏修复、交货期的改变等。 3 多目标 实际的计划调度往往是多目标的，并且这些目标间可能发生冲突，这种多目 标性导致调度的复杂性和计算量急剧增加，而且这些目标往往相互冲突。这时， 需要同时考虑多种性能指标，这就是所谓的多目标调度。 1 3 4f j s p 的性能指标 第一章绪论 f j s p 的性能指标是调度人员和生产管理人员评价调度的标尺。由于f j s p 属 于j s p 的扩充，所以近些年f j s p 相关文献对调度方案选择的评价指标跟j s p 的性 能指标有很大的相似性。下面的表1 3 里包含了f j s p 常见的一些性能指标。 表1 3f j s p 的性能指标 1 3 5f j s p 的研究方法 车间调度问题历来是诸先进优化技术的试验平台，特别是其中最具复杂性、 普遍性的j s p 。由于f j s p 的复杂性且近些年来逐渐成为作业车间调度的研究热点， 其解决方法更多采用了近年来的先进技术。下面先简单回顾j s p 的主要研究方法， 再介绍f j s p 的研究方法。可以看到，由于两者的研究历程部分重叠，所以研究方 法上有部分的相似性。 1 j s p 的研究方法回顾 j s p 是典型的n p 一难问题，其特点是没有一个有效的算法能在多项式时间内求 出其最优解，求解该问题具有一定的挑战性。历史上求解j s p 问题的方法主要有精 确算法和近似算法。精确算法主要是基于分支定界( 韶) 方法晦1 ，其原理是通过一 种动态的树状结构枚举所有的可行解，由于费时且只能求解一些小规模问题而很 快被放弃，许多研究人员把目光投向了近似算法。 尽管近似方法不保证能达到最优解，但它可以在合理的计算时间内对大规模 问题求得较优解，因此更适合于大规模问题。应用于j s p 的近似方法最早是一些分 派规则，它们容易执行且需要很少的计算资源，但由于其只考虑了当前设备状态， 所以求解的质量比较差而且随问题规模的增大求解的质量会更差。 随着便宜且高速的计算机的使用，研究人员开始探讨邻域搜索技术，它是一 种基于局部改进的搜索技术，比经典的运筹学方法更容易执行。研究的焦点主要 集中于模拟退火，禁忌搜索和遗传算法以及近些年出现的粒子优化算法，它们的 6 天津大学博士学位论文 共同特点是：对当前解用预先定义的邻域算子进行修改，产生新的可行解，希望 新的可行解针对目标函数有所改进或至少不比先前解差。主要的研究成果包括v a n l a a r h o v e n 等的模拟退火方法嘲，t a i l l a r d 口3 ，d e l l a m i c o 和t r u b i a n 馆1 以及 n o w i c k i 和s m u t n i c k i 四1 的禁忌搜索方法，a a r t s 等人n 伽的遗传算法方法，l e t i c i a 等人n 的粒子群优化方法。 近些年来，混合算法越来越流行，因为它发挥了算法的各自优越性，主要有 k o l o n k o 提出的将模拟退火算法植入遗传算法框架的s a g e n 算法n 剖，a l e x 提出的并 行贪婪随机自适应搜索算法n 3 1 ( g r a s p ) ，p e z z e l l a 和m e r e l l i 提出的禁忌搜索和瓶 颈转移混合算法n 射。 2 f j s p 的研究发展过程 相对于j s p 的研究历程，f j s p 的研究历程要短的多。f j s p 最早由b r u k e r 和 s e h l i e u 鄙在1 9 9 0 年提出。由于客户化定制对制造系统的适应性提出了更高要求， 所以关于f j s p 的研究日益受到更多研究者的重视。 ： 由于已经证明了两个工件以上的j s p 问题是n p 难题，f j s p 优化更是如此，它是 典型的组合优化问题，优化极其复杂。所以，在尝试了一些传统的方法解决f j s p 收效甚微之后，人们开始转向近些年出现的一些新的优化方法，如遗传算法、粒 子群算法等，而且提出了一些混合算法提高了求解f j s p 的效果，如夏蔚军等人利用 模拟退火和粒子群算法相结合求解多目标f j s p ，取得了较好的效果u 旬。 由于f j s p 的复杂性及实用性，因此吸引更多研究者浓厚兴趣的同时，人们对 其研究的范围逐步扩大。从最初的单目标拓展到多目标、模糊目标；从最初考虑 工艺约束拓展到考虑批量和准备时间等。在过去的1 0 多年里，很多的研究成果相 继问世，总计有1 0 0 篇左右关于f j s p 的科技论文在国内外期刊上发表。 值得一提的是国内在这方面的研究起步相对较晚，从国内公开发表的科技论 文可将f j s p 研究最早追溯到2 0 0 1 年，即文献 1 7 。但近几年有关f j s p 研究逐渐 受到诸多国内研究单位的重视，这其中包括上海交通大学、中国科技大学、西北 工业大学等。 3 f j s p 的研究方法 在对f j s p 的研究过程中，已有很多方法出现在不同决策研究的期刊中，它们 在某种程度上都获得了成功。这些方法无一例外地吸收了近些年来的一系列先进 技术。这些技术包括遗传算法、禁忌搜索和模糊逻辑等。 在b r u k e r 和s e h l i e u 钉提出f j s p 的同时也给出了一种多项式算法，但该算法只 针对两个工件，且工件各工序的n t 时间相同的简单实例进行了求解。当工件很 多时，算法的运行时间太长，而使算法并不适用。之后也有人试图用传统的启发 7 第一章绪论 式方法，如文献 4 中，l e e 等人先是用p e t r i 网对f j s p 进行建模，然后应用l 1 算法 搜索最优解，l 1 算法是人工智能中著名的搜索方法胁算法的一种改编算法，其本 质是分枝定界法和动态规划法的混合运用。h o l s a p p l e 等人n 羽用遗传代码先确定各 工件类型的调度先后顺序，然后用传统人工智能中的f b s ( f i l t e r e db e a ms e a r c h ) 搜索方法，对各个工件的每道工序按顺序进行安排调度。这种f b s 搜索方法是宽度 优先搜索法的一种改进方法。上述两种方法的主要缺点是运行时间长，且需要很 大的存储空间，搜索到的解也不一定是最优解甚至是较优解。为此，姜思杰等n 钔 人提出了一种基于遗传的优化调度算法来求解该问题，由于遗传算法存在早熟收 敛的问题，故姜思杰等脚1 人在文献 1 9 的基础上，进一步提出了基于遗传和禁忌 搜索的优化调度算法，使求解效果进一步改善。 在解决f j s p 所采用的方法中应用最多的是遗传算法。遗传算法是通过在算法 上仿效生物遗传与进化理论搜索适应于给定环境( 问题领域) 的最优个体( 问题的 解) ，是一种兼顾优化效果和计算效率的方法，适合于在复杂而庞大的搜索空间中 寻找优化解，在搜索过程中自动获取和积累有关的知识，并自适应地控制搜索过 程，算法简单、鲁棒性强，易于并行分布处理。遗传算法以其优良的计算性能和 解决组合优化问题的显著效果而倍受学者青睐。在应用遗传算法求解f j s p 时，染 色体如何编码是首先要解决的问题。如c h e n 等硷人应用a 、b 两串染色体分别表示 工序和设备的方式对染色体编码；m e s g h o u n i 等1 人应用并行设备和并行工件表示 法对染色体进行编码；k a c e m 等口朝人用二维分配表法对染色体进行编码；杨晓梅 等采用分部编码相继确定各工序的加工设备及所有工序的优先调度顺序。其次， 如何进行遗传操作是算法高效运行的关键。如p e z z e l l a 等瞳5 1 人采用随机生成、最 大设备剩余和最大工序剩余三种规则产生初始种群，n h ub i n hh o 等乜6 1 在遗传操作 中加入设备学习机制，使遗传进化的方向性更强。z h a n g 等乜铂基于工序提出一种多 阶段的遗传算法，从动态规划的角度求解f j s p 问题。 其次，禁忌算法是另一种在解决f j s p 时采用较多的一种算法。禁忌搜索是一 种邻域搜索方法，首先按照某种方式产生初始可行解，然后搜索其邻域中的所有 可行解，取其最优解作为新的当前解。为了避免重复搜索，它使用列表记录搜索 过的路线，每搜索一次，更新一次列表，同时允许一定程度地接受较差解，从而 避免陷入局部最优解。如b r a n d i m a r t e 晗鲫采用禁忌搜索算法解决排序子问题； t u n g 幢鲫发展了一种与文献 2 8 相似的方法并将其应用于柔性制造系统，取得了良 好的效果；d a u z 6 r e p 6 r 6 s 等啪1 针对f j s p 问题特点提出了扩展的狄更斯图论模型， 并在此基础上建立了新的邻域结构，再用禁忌算法解决f j s p 。m a s t r o l i l l i 等u 对文献 3 0 的禁忌搜索方法进行了改进，提出了两种邻域结构并将禁忌搜索与局 天津大学博士学位论文 部搜索法相结合解决f j s p 。j u r i s c h 恤1 应用禁忌算法同时进行工序设备选择和工 件排序。h u r i n k 提出了一种禁忌搜索方法，将再分配和再调度设计成两种不同 的移动( m o v e s ) 。 此外，还有其他一些优化技术用于解决f j s p 。如w u 等1 利用多a g e n t 技术 对f j s p 中工件提前与延期双重目标进行优化。m a s t r o l i l l i 等人m 1 针对f j s p 提 出两种邻近函数，并用智能启发式优化技术求解f j s p 。 实际生产中，不同的企业，甚至同一个企业在不同的时间、不同的环境下， 其目标要求往往也不同。因此，有些学者开始关注多目标的f j s p n 6 崩、3 引。这些文 献对多个目标的处理方式基本相同，即将各目标加权求和或求各目标之积后将多 目标问题转化为单目标问题。而p i n e d o 旧1 指出，这种加权求和( 或积) 方法在许 多情况下其作用是有限的。此外，l i 等和吴秀丽等m 3 还研究了各工件调度目标 不相同的多目标f j s p 。 另一方面，p i n e d o 汹1 指出建立在精确参数基础之上的问题模型及其处理方法， 很难适应生产实际的需求，但以参数随机变化的方法来处理问题，也有很大的局 限性。所以模糊集合、模糊逻辑越来越多地引入调度研究，用来处理不确定信息。 模糊逻辑理论一般用在混合调度方法中。它主要用来解决f j s p 中不确定的加工时 间、约束和辅助时间。这些不确定性可以用模糊数据表示。如卢冰原等h 1 1 研究三 角模糊数工序加工时间下，应用遗传算法求解f j s p 加工时间最小的单目标优化问 题。袁坤m 1 在传统f j s p 中，考虑调度目标的多样性和不确定性，拓展了问题模型， 提出了模糊决策处理方法，并在遗传算法的自适应计算中加以实现。此外，庞哈 利考虑工件所选工艺路线成本因素的前提下，研究了柔性作业车间计划与调度 集成化问题，建立了两层混合整数规划模型。综合运用门槛接受算法、遗传算法 和启发式规则，提出了混合启发式求解算法。 目前收集的相关文献中，研究者很少采用蚁群算法、粒子群算法及两者结合 而成的混合算法求解f j s p 。 从研究思路看f j s p 的解决方法目前可以分为分步法和集成法两大类。分步法 基本思想是将复杂问题分解为几个子问题，以降低其复杂性，在f j s p 调度中，将 工序设备选择( 确定工艺路线) 问题和设备工件排序问题分开考虑。集成法是将 上述两问题同时解决。分解方法由于比较贴近实际情况且有利于使问题简单化而 被大多数研究者采用。该方法首先在文献 2 8 3