（机械电子工程专业论文）基于粒子群算法的混合flow+shop生产调度问题的研究.pdf

一 冬 合肥工业大学li 螋 本论文经答辩委员会全体委员审查，确认符合合肥工业大学硕 士学位论文质量要求。 答辩委员会签名：( 工作单位、职称) 主席：p 幺砺为形钐掳级徭 委员： 够敞呻k 国 工监么刁刍l ， 怪孚3鑫胁 殴 一2 严f 肥嘴搬 ： 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所 知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得金旦巴王些太堂或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签字：王春芳签字日期：如，年4 厚埘日 学位论文版权使用授权书 本学位论文作者完全了解金月墨王些太堂有关保留、使用学位论文的规定，有权保留并向 国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人授权金壁王些太 兰l 可以将学位论文的全部或部分论文内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名： 王孑奏若 导师签名： 鲈扩 签字日期：幽，年4 月2 日签字日期：小j 年乒昂妇日 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编： 一，毒 t p 一 ， 户 基于粒子群算法的混合f l o ws h o p 生产调度问题的研究 摘要 生产调度问题具有复杂性、多约束性、动态随机性和多目标性，是一个已经被证 实了的n p 问题。混合流水车间生产调度问题作为典型流水车间生产调度问题的一种推 广，由于其在各阶段存在并行机调度问题，从而大大增加了问题的求解难度。粒子群 算法是一种基于群体智能的进化方法，由于其简单易编程实现，须调整的参数较少而 被广泛应用。 本文从混合流水车间生产调度问题的工业背景出发，研究混合流水车间生产调度 问题的特点，并综合分析了各调度目标，从而选择以生产周期最小化、拖期惩罚与提 前完工保管费用最小化为调度目标，建立考虑了前期准备的混合流水车间生产调度问 题数学模型。 本文又从粒子群算法的产生背景开始，介绍了粒子算法的基本原理，并在研究分 析大量现有的改进方法的基础上，提出基于粒子适应度的惯性权重调整策略、扰动机 制，以及基于位置相似度的禁忌策略三者相结合的改进粒子群算法，同时对改进算法 使用了测试函数验证，证明改进后的算法性能有所提高。 最后，本文选择了纺织生产调度问题作为混合流水车间生产调度问题的实例，在 全面了解其生产工艺流程并分析其调度问题特点的基础上，采用本文提出的改进算法 对问题进行求解，得到了较优解，从而证明了本文改进算法与先前建立的数学模型在 求解混合流水车间调度问题的有效性。 关键词：混合流水车间生产调度，粒子群算法，适应度，扰动机制，位置相似度 一 毒 r e s e a r c ht ot h eh y b r i df l o ws h o ps c h e d u l i n gb a s eo n p 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 a b s t r a c t p r o d u c t i o n s c h e d u l i n g i sac o m p l e x ，m u l t i - c o n s t r a i n t s ，d y n a m i cr a n d o ma n d m u l t i - t a r g e t sp r o b l e m ，w h i c hh a sb e e nv e r i f i e da san p - h a r dp r o b l e m t h es c h e d u l i n g p r o b l e mo fh y b r i df l o ws h o pa sap r o m o t i o no f at y p i c a lf l o ws h o ps c h e d u l i n gp r o b l e m ，h a s b e e nf o u n dg r e a t l yi n c r e a s e dd i f f i c u l t i e sw h i l ei t sb e i n gs o l v i n g ，b e c a u s eo ft h ep r e s e n c ei n v a r i o u ss t a g e so fp a r a l l e lm a c h i n es c h e d u l i n gp r o b l e m p s oi sas w a r mi n t e l l i g e n c eb a s e d e v o l u t i o n a r ya p p r o a c ha n di sw i d e l yu s e df o ri t ss i m p l i c i t yo fp r o g r a m m i n ga n dl e s s p a r a m e t e r st ob ea d j u s t e d t h i st h e s i sf o c u s e so nr e s e a r c ho fc h a r a c t e r i s t i co fh y b r i df l o ws h o ps c h e d u l i n g p r o b l e mf r o mi n d u s t r i a lb a c k g r o u n do fh y b r i df l o ws h o pp r o d u c t i o ns c h e d u l i n g , a n d c o m p r e h e n s i v e l ya n a l y z e st h es c h e d u l i n go b j e c t i v e t h e nt h eh y b r i dl o ws h o ps c h e d u l i n g p r o b l e mm o d e lh a sb e e ne s t a b l i s h e d t oc o n s i d e re a r l y - s t a g e p r e p a r a t i o n s ，a i m i n g a t m i n i i i 此i i l gt h ep r o d u c t i o nc y c l e ，a n dp e n a l t yc o s tc a u s e db yt h et a r d i n e s sa sw e l la st h e e x p e n s e sf o rk e e p i n ga h e a do fs c h e d u l ea st h es c h e d u l i n go b j e c t i v e s t h i st h e s i si n t r o d u c e dt h eb a s i c p r i n c i p l e s o f p a r t i c l ea l g o r i t h ma g a i n s t t h e b a c k g r o u n do fp 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 ，a n do nb a s i so fa n a l y s i so fal a r g e n u m b e ro fe x i s t i n gi nt h ei m p r o v e dm e t h o dp r o p o s e sf o r w a r di m p r o v e dp a r t i c l es w a r m a l g o r i t h mb a s e do nt h ea d a p t i v eo fp a r t i c l ei n e r t i aw e i g h ta d j u s t m e n ts t r a t e g y , d i s t u r b a n c e m e c h a n i s ma n dt a b o os t r a t e g yo ft h e1 0 c a t i o n - b a s e ds i m i l a r i t yd e g r e e m e a n w h i l et h e i m p r o v e da l g o r i t h mi sv e r i f i e dt ob ei m p r o v i n gb yu s i n gt h et e s tf u n c t i o n s f i n a l l y , t h et h e s i st a k e sa ne x a m p l eo ft h et e x t i l ep r o d u c t i o ns c h e d u l i n gp r o b l e ma sa h y b r i df l o ws h o ps c h e d u l i n gp r o b l e m b yc o m p r e h e n s i v eu n d e r s t a n d i n go f t h e i rp r o d u c t i o n p r o c e s s a n d a n a l y z i n g t h e c h a r a c t e r i s t i c so ft h es c h e d u l i n gp r o b l e m ，t h ei m p r o v e d a l g o r i t h mp r o p o s e di nt h i st h e s i si sa d o p t e dt os o l v et h ep r o b l e ma n d ，h e n c e ，g e tam o r e o p t i m u ms o l u t i o nw h i c hp r o v e st h ee f f e c t i v e n e s so ft h i si m p r o v e da l g o r i t h mw i lt h e p r e v i o u sm a t h e m a t i c a lm o d e lf o rs o l v i n gh y b r i df l o ws h o ps c h e d u l i n gp r o b l e m k e y w o r d s ：h y b r i df l o ws h o ps c h e d u l i n g ；p a r t i c l e s w a r mo p t i m i z a t i o n ；a d a p t i v e ； d i s t u r b a n c em e c h a n i s m ；l o c a t i o ns i m i l a r i t y 致谢 值此论文完成之际，忠心感谢我的导师张建军教授和张利教授近三年来的指导与 教诲。本论文无论是选题还是后来的写作过程，无不是在两位张老师自始至终的指导、 支持与鼓励下完成的，凝聚了两位张老师的心血与汗水。三年来，两位张老师严肃的 科学态度，严谨的治学精神，精益求精的工作作风，还有和蔼的师者风范深深地影响 着我，并将让我受益终生。在此，谨向两位张老师致以衷心的感谢和最崇高的敬 意! 忠心感谢实验室的刘小平老师和徐娟博士在论文方面给予的指导与帮助；感谢 三年来共同奋斗的同学，许垄，彭亚丽，朱明，李县军，崔世辉，王为，刁新超，路 园，谢敬芝等，感谢您们在各方面给予我的帮助，和您们相处和合作将让我终生难忘。 感谢分布式控制实验的所有老师和同学，是您们为我创造了一个良好学习、工作环境。 特别感谢我的父母，我的姐姐和弟弟，感谢您们长期以来的支持与鼓励。我所取 得的成就，都凝聚着您们的心血和汗水，在此，祝贺您们身体健康，事事顺心。 最后，再次向所有关心、支持和帮助过我的老师、同学、亲人和朋友致以诚挚的 谢意! 作者：王春芳 2 0 1 1 年4 月 目录 第一章结论1 1 1 引言一1 1 2 生产调度问题描述与分类1 1 2 1 生产调度问题描述1 1 2 2 生产调度问题分类2 1 3 生产调度问题的求解方法4 1 3 1 运筹学方法4 1 3 2 启发式方法4 1 3 3 人工智能方法4 1 3 4 进化方法5 1 4 本文研究内容与安排6 1 4 1 研究内容6 1 4 2 论文安排6 第二章混合流水车间调度一8 2 1 混合流水车间调度。8 2 1 1 混合流水车间调度问题描述。8 2 1 2 混合流水车间调度物理模型8 2 2 混合流水车间调度的特点8 2 2 1 流程工业简介8 2 2 2 混合流水车间调度问题的特点9 2 3 调度目标9 2 3 1 调度目标的确立9 2 3 2 多目标的求解策略1 0 2 3 3 评价函数法1 2 2 4 混合流水车间调度的数学模型1 3 2 4 1 生产调度问题建模方法分析1 3 2 4 2 混合流水车间调度问题数学建模一1 3 2 5 本章小结15 第三章粒子群算法及其改进策略的研究1 6 3 1 粒子群算法概述1 6 3 1 1 粒子群算法产生背景【6 】1 6 3 1 2 基本粒子算法17 3 1 3 粒子群算法的发展：1 8 3 2 基于适应度的惯性权重调整策略1 9 3 2 1 惯性权重分析1 9 3 2 2 现有的惯性权重改进策略1 9 3 2 3 基于适应度的惯性调整策略2 2 3 3 扰动机制2 4 3 3 1 基于速度与位置的扰动机制。2 4 3 3 2 测试函数验证2 5 3 4 基于位置相似度的禁忌策略2 5 3 4 1 禁忌搜索算法基本原理2 5 3 4 2 粒子群算法与禁忌搜索算法混合方式2 7 3 4 3 基于位置相似度的禁忌策略。2 8 3 5 改进后算法的流程2 8 3 6 本章小结3 0 第四章改进p s o 在混合流水车间调度问题中的应用研究3 1 4 1 纺织生产调度问题描述3 1 4 1 1 纺织生产过程介绍3l 4 1 2 纺织生产特点3 2 4 1 3 纺织生产调度问题分析3 4 4 2 编码分析3 4 4 2 1 编码方法3 4 4 2 2 基于工件与工序的矩阵编码_ 3 5 4 3 问题求解3 5 4 3 1 问题求解流程3 5 4 3 2 算法过程控制3 7 4 4 实例分析分析3 7 4 4 1 实例l 。3 7 4 4 2 实例2 3 9 4 4 3 结果分析4 4 4 5 本章小结4 4 第五章总结与展望4 5 5 1 总结4 5 5 2 展望4 5 参考文献一4 7 攻读硕士期间主要发表的学术论文和参加的科研项目5 1 插图清单 图2 1 混合流水车间调度图8 图3 1 基本p s o 算法流程图18 图3 2 几种改进惯性权重的p s o 算法优化性能比较( s p h e r e ) 。2 1 图3 3 几种改进惯性权重的p s o 算法优化性能比较( g r i e w a n g k ) 2 1 图3 4 本文改进的p s o 与其它形式比较( s p h e r e ) 。2 3 图3 5 本文改进的p s o 与其它形式比较( g r i e w a n g k ) 2 3 图3 - 6 惯性权重变化曲线2 4 图3 7 使用扰动机制的改进p s o 算法与未使用的对比2 5 图3 8 四城市非对称t s p 2 6 图3 - 9 改进p s o 算法流程图2 9 图4 1 纺织工艺流程图3 1 图4 2 调度结果甘特图3 8 图4 3 算法收敛性比较3 9 图4 4 种群飞行历史过程中最大流程时间分布- 3 9 图4 5 各订单生产安排4 3 表格清单 表4 1 各工件工序加工时间表( 6 6 ) 3 8 表4 21 5 份订单各工序的加工时间表4 0 表4 3 切换加工产品机器的调整时间表4 0 表4 - 4 各订单交货期、保管费用及拖后惩罚表4 1 表4 6 各订单工序机器分配情况4 3 第一章结论 1 1 引言 随着市场经济的发展，产品的个性化趋势日益加强，使得企业生产也必须朝着多 品种、小批量、短周期、快交货、零库存的方向发展。因此，如何根据市场需求，合 理地、最佳地安排组织生产过程并能迅速地对市场作出准确响应变得尤为重要。 生产调度就是在满足生产设备资源和工艺要求的条件下，根据客户订单或市场需 求，合理地、高效地组织生产过程，并以提高过程系统的操作最优性，为生产企业带 来显著经济效益为目的【。它是以生产进度计划为依据，同时生产进度计划必须通过 生产调度来实现。生产调度的必要性是由工业企业生产活动的性质决定的，它在企业 生产过程中起到了保证生产过程顺利进行和组织实现生产作业计划的作用。 2 0 世纪初，在h e n r yg a n t t 等先驱者的努力下，调度开始在制造业受到重视【2 1 。 到上世纪5 0 年代起，人们对调度问题进行了大量的研究工作，普遍地将c o n w a y ， m a x w e l l 和m i l l e r 三人有关调度的研究工作作为调度理论研究的正式开始【3 】。 调度问题应用背景十分广泛，它包括了制造业生产调度、电力系统调度、港口船 舶调度、工程项目资源分配管理和通信等关系到国计民生的多个领域，其中研究最为 深入的是制造业的生产调度问题。在制造业中，生产调度问题就是指在满足生产工艺 要求和资源数量等相关约束条件下，通过确定各工件所在的加工机器和在相应机器上 的加工顺序，力n - r _ 开始时间，工件组批方式和投料策略及其他关键资源的分配使用计 划等调度策略，使调度目标达到最优。实现生产优化调度对钢铁、纺织、石化、机械 等行业缩短制造周期、降低资源消耗、提高按时交货率和机器使用效率及产品质量、 降低生产成本、提高经济效益和市场竞争力等具有极其重要的作用【4 1 。 然而，许多调度问题已经被证明为n 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 ) 完全问题 i s 】。因此，调度问题大多是复杂的组合优化问题，是没有一个精确解的，传统的数学 方法根本无法解决这个问题，只能通过优化方法求解最优解。粒子群优化算法是近年 来发展十分迅速的一种新的优化方法，它具有算法简单易实现，并且没有太多参数需 要调整等优点【6 】。本文研究的就是应用粒子群算法解决一类生产调度问题。 1 2 生产调度问题描述与分类 1 2 1 生产调度问题描述 生产调度问题就是在指定的生产周期内，对生产任务进行排序，并对生产车间内 的可用设备资源进行分配，以满足企业指定的性能指标。简单地说，生产调度问题就 是按时间分配设备资源来完成任务的问趔1 1 。 生产调度问题通常可以这样来描述：在一定的约束条件下，针对某些可以分解的 任务( 订单或计划) ，如何安排其组成部分( 操作或工序) 所占用的资源，以及其加 工时间及先后顺序，以获得产品生产周期最短或生产成本最小等目标。 影响生产调度问题的因素很多，一般可以将其归纳为车间因素和任务本身因素两 大类。车间因素是相对于生产企业而言的，它主要包括了车间可用的加工设备数量、 可用原料的多少、生产能力、安排的加工顺序以及生产成本；任务因素主要就是客户 提出的要求，最主要就是产品的交货期、产品需求量、产品质量等。这些因素都是生 产调度过程中的约束条件，而这些约束条件也存在着必要性与非必要性之分。由于生 产调度问题往往是一个多目标的组合优化问题，因此，在进行调度前必须先确定哪些 是必须满足的约束条件哪些是非必须的，以便在调度过程进行合理的取舍。通常情况 下，如交货期、生产能力就是必须满足的，而另外有些条件只须达到一定的满意度即 可，如生产成本。以上约束条件往往在进行调度时作为确定性因素考虑，而对于设备 资源的故障，原料供应的变化，紧急任务的出现等都是事先不能确定的，在进行调度 时大多作为不确定因素考虑。 生产调度中涉及的调度资源包括原材料、加工设备资源、人力资源、资金以及能 源等，资源的详细分配受到以上分析的多重因素的制约。生产调度的调度目标一般有 生产成本最低、生产周期最短、设备利用率最高以及企业获得的收益最大等，它是企 业为评价调度方案的指标。实际生产调度的目标大致可以归纳为以下三类【1 ，7 】： ( 1 ) 最大能力指标，它是调度的基本。主要包括企业的最大生产能力、完成任 务的最短生产周期等，这些都受到了车间设备资源数量，以及设备本身生产能力的影 响。这类目标通常可以理解为在一定的生产任务或无限的客户需求下，最大化企业生 产能力以获得最大的经济效益。 ( 2 ) 成本指标，它也企业考虑的较为重要的一方面。成本指标包括多个方面， 主要有生产成本( 机器成本，工人工资等) 、运输成本、库存成本等，降低成本可以 有效的减少流动资金的投入。 ( 3 ) 客户满意度指标，它是根据订单客户要求提出的。主要包括客户允许的最 短延迟和最小提前期，以及拖期过长的惩罚。 在传统的调度中，许多时候都是以追求生产周期最短为目标，而在现实生产中， 往往由于提前完成生产任务却带来了一定保管费用，从而增加了成本，所以，在实际 调度中应重视提前或者拖后惩罚带来的影响。 1 2 2 生产调度问题分类 生产调度问题根据分类方式的不同可以分为多种，简要介绍如下 2 】：( 1 ) 根据生 产过程中机器环境特性的不同，可划分为单机、并行机、作业车间调度问题、流水车 间调度问题等典型调度问题；( 2 ) 根据是否存在调度问题相关的不确定因素，可划分 为确定性调度问题和不确定性调度问题；( 3 ) 根据具有加工先后约束的不同工序的工 件是否可在同一机器上加工，可划分为可重入调度问题和不可重入调度问题；( 4 ) 根 据待加工工件工序数的不同，可划分为单工序调度问题和多工序调度问题；另外，还 可将生产过程调度问题划分为动态调度问题和静态调度问题，其中，动态调度问题包 2 含实时调度问题和重调度问题等。 以上各种分类是从不同方面进行的，因此，实际中的生产调度问题往往包括以上 多种类型的特点：如f l o ws h o p 生产调度问题所涉及的参数可能包括不确定因素也可 能不包括。最常见的分类方法是第一种，而在第一种分类方法中最见的是f l o ws h o p 和j o bs h o p 两种，又根据各种生产调度的实际情况这两又可以进行细分。 1 2 2 1 作业车间生产调度问题( j o bs h o ps c h e d u l i n gp r o b l e m ，简称j s p ) 该问题可以这样来描述：有刀个工件在m 台机器上加工，每个工件须完成若干道 工序的加工，且每道工序又可以在这m 台机器中的若干台机器上完成。调度时必须满 足：( 1 ) 每一台机器在任一时刻只能加工某一个工件；( 2 ) 每一工件只能在上一道工 序完成加工之后才能进行下一道工序的加工。前一条件称为占用约束，后一条件称为 顺序约束。 通常将以上两个约束条件统称为车间调度问题的技术约束，在求解这类生产调度 问题过程中除满足技术约束外，一般还假设： ( 1 ) 各工件的各工序的准备时间已知： ( 2 ) 各工件的某一工序一旦在指定机器上开始加工就不能中断，且认为在整个 加工过程中机器不会出现故障； ( 3 ) 各工件不能有多个工序在同一机器上完成加工； ( 4 ) 所有机器处理各工件工序的时间均已知； ( 5 ) 各操作之间充许等待，且认为缓冲区为无穷大。 作业车间生产调度的决策内容包括工件的加工顺序、各工件各工序的开始加工时 间和各工件各工序的加工设备资源的分配。其特点是多个工件的多个工序在有限台机 器上加工，每台机器在切换到不同工件加工时需要一定的机器调整时间。切换频率高 时有利于减少工件的库存，却增加了机器调整时间降低了生产效率。因此，在此类问 题的调度过程中需要在库存成本与切换频率之间取得平衡。 1 2 2 2 流水车间生产调度问题( f l o ws h o ps c h e d u l i n gp r o b l e m ，简称f s p ) 此类问题一般这样描述：假设有m 个机器，刀个作业，每个作业包含m 个任务， 各零件的工艺顺序相同，即每个作业在m 个机器上加工顺序是相同的。要求合理安排 各作业的加工顺序以达到生产调度目标。常见的调度目标有：最后作业完成时间的最 小化、总的拖期最小化、拖期生产的作业个数最小化、提前完工时间最小化等。 传统的f l o ws h o p 问题允许每个机器上有不同的工件序列，并且假定缓冲区是无 限的，工件可以在机器上或机器之间等待。在现在这样一个要求高效的社会，更多的 强调是零等待，因此，在具体情况中要综合考虑设置缓冲区的大小，工件在各机器之 间的运送时间等因素，从而使得实际的调度问题也变得更为复杂。 流水车间调度问题和作业车间调度不同之处仅在于前者作业加工在不同的机器 上有固定的顺序，但优化目标通常情况下却是相同的。所以，研究使用的优化方法基 本也是相同的。 3 当流水车间调度问题中的某一或多个加工阶段出现了多台并行机的情况，我们则 定义为混合流水车间调度，它是本文研究的重点，将从下一章开始进行较为详细的讨 论。 1 3 生产调度问题的求解方法 前面已经提到生产调度问题是复杂的组合优化问题，没有精确解，只能通过优化 方法寻求最优解。由于生产调度问题在企业生产中起到了极其重要的作用，使得生产 调度这个问题从提出到现在引起了许多专家学者的广泛研究。随着各种优化方法的不 断发展，为求解生产调度问题提供了不少的新思路。应用于生产调度较为常见的方法 归纳如下： 1 3 1 运筹学方法 在生产调度问题优化方法研究中常用运筹学方法有【2 】：分枝定界、动态规划、拉 格朗日松弛等，它是求解生产调度优化问题的经典方法之一，但是前面已经讲述了生 产调度问题是n p 问题，随着调度问题规模的增大，一般会产生指数爆炸现象。因而 此方法主要用于求解规模较小的、简单的生产调度问题，用于求解较为复杂的生产调 度问题时须与其它一些方法相结合。 1 3 2 启发式方法 启发式方法是求解生产过程调度问题常用的一种近优方法【2 】，它最初是作为人工 智能中问题求解程序的搜索器而被开发的，依靠任务无关信息简化搜索过程，在很多情 况下，可将求解问题的过程看成是系统化地构造或查找解答的过程【9 】。它包括基于规则 的方法、基于人工智能的方法和随机搜索的方法等。基于规则的方法一般是根据工件 或设备的某些简单属性直接确定任务优先权，所以，它在生产过程调度中应用最为普 遍。 为了进一步提高算法的性能，以获得更为理想的调度方案，许多学者在基本启发 式方法基础提出了一些改进的方法，如加权规则法、组合规则法和模糊规则法等。目 前，启发式方法在生产调度应用研究方面主要集中在针对不同类型的生产过程调度问 题构造启发式方法或对相应的启发式方法进行性能分析f 2 1 。 启发式方法优点在于描述简单、可解释性好、计算量较小，并且可以利用具体问 题的知识和经验，以获得较为理想的问题解决方案；其缺点在于对于规模较大，约束 较多且较为复杂的多目标调度问题，启发式方法往往搜索效率不高且不能够获得理想 的解决方案 2 , 9 1 。 1 3 3 人工智能方法 2 0 世纪8 0 年代，人们开始借助于人工智能方法寻求解决生产调度问题新思路， 该类方法主要包括专家系统、智能代理、约束满足( 模糊优化) 、神经网络等方法。 利用人工智能技术结合专家的丰富经验，建立问题的数学模型并进行求解，可以获得 令人满意的调度方案，但是人工智能的方法应用到实际往往存在很多瓶颈，如评价函 4 数、知识过于依赖实际问题；系统维护、升级难度大；当调度问题规模比较大时，算法 会产生指数爆炸现象等掣1 。2 9 】。 1 3 4 进化方法 根据达尔文进化论的起源理论，进化不断地发生在自然选择和自适应过程之中。 根据这一生物学基本模型，计算机科学界设计出了很多种模拟进化的算法，我们将其 统称为进化方法。进化计算是通过模拟自然界生物进化过程或群体活动行为来寻求问 题的最优解。现在研究较为广泛的进化计算有：遗传算法( g e n e t i ca l g o r i t h m ，g a ) 、蚁 群算法( a n tc o l o n yo p t i m i z a t i o n , a c o ) 、粒子群算法( p a r t i c l es w a r mo p t i m i z a t i o n ，p s o ) 等以及它们的各种改进算法。以下对在生产调度问题应用范围最广的遗传算法和近年 来在生产过程调度问题研究中得到较多关注的蚁群算法、粒子群算法等进化计算方法 做简要介绍。 ( 1 ) 遗传算法：它是由j h o l l a n d 于1 9 7 5 年受生物进化论的启发而提出的一种 模拟生物在自然界的遗传和进化过程的随机搜索算法【l 。遗传算法的提出在一定程度 上解决了人工智能方法在知识表示，信息处理和解决组合爆炸等方面所遇到的困难， 它所具有的自组织，自适应，自学习和群体进化特点使其适合于求解大规模复杂优化 问题【l2 1 。随着计算机技术的发展，遗传算法在生产调度领域得到了较为广泛的应用， 并且国内外专家学者针对各个具体的调度问题又相应地提出了改进的遗传算法。 张国辉等【l3 】在考虑各个机器负荷平衡，并且所有机器上的总负荷最小及最大完工 时间最短等性能指标更加合理情况下，设计一种全局搜索、局部搜索和随机产生相结 合的初始种群产生方法，从而提高种群初始解的质量，加快遗传算法的收敛速度。 赵韩等【1 4 】提出了一种改进的白适应免疫遗传算法，算法根据搜索的历史信息，自 适应地调整遗传进化过程中的遗传参数以提高算法的稳定性和寻优效率，从而克服了 遗传算法的局部搜索能力差与全局搜索效率低的缺点。 黄明等【1 5 】根据生命科学中免疫系统的信息处理机制，在基本遗传算法的基础上， 将免疫算法和d n a 遗传算法相结合，提出了一种用于车间调度的新d n a 免疫遗传 算法；并且引入一个遗传密码表，用于d n a 碱基链的解码；算法中子群体之间的信 息交换采用孤岛模型；另外还引入了一个疫苗库，通过接种疫苗提高抗体的适应度， 通过免疫选择防止种群的退化。 ( 2 ) 蚁群算法：蚁群算法是由意大利米兰理工大学d o r i g o 掣1 6 】于1 9 9 1 年提出 的一种模拟蚁群觅食行为的进化计算方法，并且他于1 9 9 4 年首先将蚁群算法应用于 求解j o bs h o p 调度问趔1 1 7 1 。随着研究的不断深入，蚁群算法在国内外有了更为广泛的 应用。王万良等【1 8 】将蚁群算法进行了改进并应用到了柔性作业车间调度问题的求解； s h y u 掣挎】将其应用到了流水车间调度问题的求解当中；h e i n o n e n 等【2 0 】则将蚁群算法 应用到了作业车间调度问题的优化求解中。 蚁群算法在生产调度问题中的应用研究主要涉及信息素的更新方式、状态的转移 策略、邻域拓扑结构的设计方法、算法参数确定方法等，另外，一些学者针对不同类 5 ， 型的生产调度问题，将启发式算法、约束搜索、禁忌搜索等方法与蚁群算法相结合， 提高算法性能，以获得更为理想的调度方案【2 】。 ( 3 ) 粒子群优化算法：由美国社会心理学家k e n n e d y 等【2 1 】于1 9 9 5 年提出的一种 模拟鸟群觅食行为的进化计算方法，该算法通过个体之间的协作来进行迭代优化。土 耳其f a t i h 大学t a s g e t i r e n 掣2 2 】于2 0 0 4 年首先将粒子群优化算法用于求解置换f l o w s h o p 调度问题。随后，国内外许多专家学者进行了广泛的研究，本文将在第三章作比 较详细的介绍。 除以上几种常用的进化算法外，还有模拟退火算法和禁忌搜索算法也是比较常用 的，另外还有多种根据实际调度问题而提出的各种算法以及它们的改进算法或是它们 的多种算法融合的算法【2 3 。2 卯。 经过对以上进化算法的分析研究得出其具有以下优点：由于进化算法本身是一种 并行计算方法，所以其搜索效率较高；进化算法采用的是随机搜索策略，具有较理想 的全局搜索能力；其搜索过程是基于对决策变量编码后的字符串，因而对目标函数没 有连续性、可导性等特殊的要求。基于以上优点，进化计算成为了求解生产过程调度 问题的主要方法之一。 1 4 本文研究内容与安排 1 4 1 研究内容 本文以流程工业作为混合流水车间调度问题的应用背景，研究分析其特点，建立 了混合流水车间调度问题的数学模型，并且提出改进的粒子群算法对其进行优化求 解。本文研究的主要内容包括： ( 1 ) 从混合流水车间生产调度问题的物理模型出发，结合其具体应用背景，研 究分析其特点，建立以生产周期最短、拖期惩罚和提前完成保管费用最小为调度目标 的数学模型； ( 2 ) 对现有的生产调度算法进行对比分析与研究，找出各种算法的优点与不足， 寻找适合流水车间生产调度问题的有效方法； ( 3 ) 以纺织生产调度问题作为混合f l o ws h o p 调度问题的实例进行研究，学习 纺织行业背景知识，研究分析纺织生产行业的生产特点； ( 4 ) 结合纺织企业的生产计划，生产订单情况设计粒子群算法，求解生产调度 的最优解。 1 4 2 论文安排 第一章绪论，描述了生产调度问题，并简要介绍了其常见的分类方法和几种典型 的形式；然后综述了求解生产调度问题的常用方法，分析其优缺点。 第二章描述混合流水车间生产调度问题，分析其特点，建立建立以生产周期最短、 拖期惩罚和提前完工保管费用最小为调度目标的数学模型；同时研究了多目标决策方 法。 6 第三章从粒子群算法的产生背景出发，介绍了其基本原理及现在的改进策略；在 此基础上，提出了基于适应度的惯性权重调整策略、扰动机制和基于位置相似度的禁 忌策略的多重改进粒子群算法，并使用了常用的算法性能测试函数进行了改进后算法 性能的测试。 第四章研究以上改进粒子群算法在混合流水车间生产调度问题中的应用，以纺织 生产调度作为混合流水车间生产调度问题的实例，分析纺织生产特点，结合其实际情 况，设计基于工件工序的矩阵编码方式的粒子群算法，通过实例仿真验证了改进算法 在求解混合流水车间生产调度问题的可行性。 第五章总结与展望，总结了本文的主要研究内容，同时指出本文中存在的不足与 下一步改进方向。 7 第二章混合流水车间调度 混合流水车间调度问题( h ) b r i df l o w s h o ps c h e d u l i n gp r o b l e m ，简称：h f s p ) 是 一般f l o w s h o p 调度问题的推广，比一般的f l o w - s h o p 调度问题更复杂。它的特点是 在某些工序上存在并行机，它很具有代表性，广泛地存在于化工、钢铁、制药等流程 工业当中【1 1 。 2 1 混合流水车间调度 2 1 1 混合流水车间调度问题描述 混合流水车间调度是传统流水车间调度问题的一种推广，可以这样来描述【1 2 】：n 个工件须进行m 个阶段( 工序) 的加工，对于阶段，有机器r ，台( 对于任意阶段， r ， - 1 ，且至少存在一个阶段使得r ， 1 ) ，并且同一阶段上各机器上的处理功能相同， 在每一阶段各工件均要完成一道工序，各工件的每道工序可以在相应阶段上的任意一 台机器上加工，己知工件各道工序的处理时间，要求确定所有工件的排序以及每一阶 段上机器的分配情况，使得调度目标最小。 2 1 2 混合流水车间调度物理模型 图2 1 是一个典型的混合流水车间调度问题，其中m 表示n 个工件有m 个阶段 ( 即有m 道工序) 要加工，m l ，m 2 m m 表示各阶段可用的机器台数，箭头表示 各工件的各工序可以在对应阶段上的任意机器上加工且只能在一台机器上加工。 n 个工件的 o o o o o o 图2 - 1 混合流水车间调度图 混合流水车间调度问题的决策内容包括：确定各工件的各工序在对应阶段的哪台 机器上加工以及同在该机器上加工工件的加工顺序和各工件的各工序的开始、结束加 工时间。 2 2 混合流水车间调度的特点 2 2 1 流程工业简介 流程工业是加工工业的一个大类，它包括炼油、化工、冶金、造纸、电力、制药、 酿造、建材等原材料加工和能源工业行业。在此工业过程中，生产原料按照一定的工 艺流程连续不断地通过一系列设备和装置，被加工处理成产品，其中一般伴有化学、 物理、相变等变化过程。流程工业在我国国民经济中是占主导地位的，其发展状况直 接影响国家的经济基础，它是我国的重要基础支柱产业 2 8 】。 2 2 2 混合流水车间调度问题的特点 混合f l o ws h o p 调度问题是s a l v a d o r t e 2 9 】于1 9 7 3 年基于石油工业背景提出来的， 它是标准流水车间调度问题和并行机调度问题的推广。因此，混合流水车间调度问题 具有以下特削3 0 3 1 】： ( 1 ) 复杂性：复杂性是调度问题中最为普遍的特点。流程工业中一般都具有生产工 艺复杂、工序繁多、产品种类多的特点，因此，在这类生产过程中经常会出现不同产 品在加工设备上进行频繁切换的情况。生产设备上的产品进行了切换，设备也要做相 应的调整，这种调整往往也是比较复杂的。另外，调度过程还受到具体的生产车间环 境的影响，如缓冲区大小、搬运系统等以及它们与之间的相互作用相互影响等等。混 合流水车间调度问题是在等式或不等式约束下进行目标优化求解的，是一个n p 问题， 随着问题规模的增大，对于优化求解的计算量会呈