（计算机应用技术专业论文）复杂产品柔性调度优化研究.pdf

哈尔滨理工人学下学硕十学位论文 复杂产品柔性调度优化研究 摘要 柔性调度问题是实际生产系统中的核心问题之一，它是由传统车间调度问 题逐渐引申、发展而来的。传统车间调度问题是一个经典问题，至今还是一个 研究热点，由于传统车间调度问题对机器加工路线做了限定，因此难以适用于 柔性制造系统。柔性调度问题允许一个工序可以在多台机器上进行加工，从而 更加接近以数控机床或加工中心为基础的实际工作环境。现有的柔性调度的研 究只能解决工件间无约束的简单产品的柔性车间调度问题，没有考虑工件间存 在约束关系的复杂产品的情况。本文所研究的是复杂产品柔性调度问题，既考 虑了工件间的约束关系，同时又考虑了工序可在多台设备上加工的情况，具有 重要的理论和实际意义。 对复杂单产品柔性调度问题，本文在改进加工工艺树模型的基础上，提出 一种新的分步式求解算法。该算法对工序优化分配子问题，采用短用时策略和 设备均衡策略，确定每道工序的加工时间及) j 口- r 设备，把柔性调度问题转化为 标准调度问题；对工序优化调度子问题，根据工序的不同特点，把工序分为局 部相关工序和独立工序两种，对不同种类的工序采用不同的算法进行调度。 对复杂多产品柔性调度问题，本文采取工艺树根对齐的方式将多产品柔性 调度问题转化为虚拟单产品柔性调度问题。对虚拟单产品柔性调度问题提出一 种基于拟关键路径法的集成式算法，实现同时解决复杂多产品柔性调度问题的 工序优化分配与工序优化调度两个子问题。 对复杂多产品动态柔性调度问题，将未加工完的部分产品与动态到达的产 品构造成一棵新的虚拟改进加工工艺树，从而把多产品动态柔性调度问题转化 为虚拟单产品柔性调度问题。对虚拟单产品柔性调度问题采用和解决复杂单产 品柔性调度问题同样的分步式算法来解决。 本文对复杂产品柔性调度问题中的单产品、多产品和多产品动态提出了相 应的算法，通过算法分析和实例验证，算法具有令人满意的复杂度，且近优效 果好。因此，算法具有一定的理论和现实意义。 关键词柔性调度；复杂产品；改进加工工艺树；短用时策略；设备均衡策略 哈尔滨理t 大学t 学硕士学位论文 r e s e a r c ho nf l e x i b l es c h e d u l i n go p t i m i z a t i o n o fc o m p l e xp r o d u c t a b s t r a c t f l e x i b l es c h e d u l i n gp r o b l e mi so n eo ft h ek e yp r o b l e m si na c t u a lp r o d u c t i o n s y s t e m ，w h i c hg r a d u a l l y e x t e n d sa n d d e v e l o p s f r o mt h et r a d i t i o n a lj o b s h o p s c h e d u l i n gp r o b l e m t r a d i t i o n a lj o b s h o ps c h e d u l i n gp r o b l e mi sac l a s s i c a lp r o b l e m ， a n di ti ss t i l lah o t s p o tu n t i ln o w b e c a u s et h et r a d i t i o n a lj o b s h o ps c h e d u l i n g p r o b l e ml i m i t st h ep r o c e s s i n gr o u t eo fm a c h i n e s ，i ti sn o ts u i t a b l ef o rt h ef l e x i b l e m a n u f a c t u r es y s t e m a no p e r a t i o nc a nb ep r o c e s s e do nm a n ym a c h i n e si nf l e x i b l e s c h e d u l i n gp r o b l e m ，s oi t i sm o r ec l o s et ot h ea c t u a lw o r k i n ge n v i r o n m e n tw h i c hi s b a s e do nc n cm a c h i n et o o l so rm a c h i n i n gc e n t e r s t h ee x i s t i n gr e s e a r c ho ff l e x i b l e s c h e d u l i n gc a l lo n l ys o l v et h es i m p l ep r o d u c tf l e x i b l ejo b - s h o ps c h e d u l i n gp r o b l e m w i t hn o n r e s t r a i n ta m o n gj o b sa n dd i dn o tt a k ei n t oa c c o u n tt h ec o n s t r a i n ta m o n g j o b s i nt h i sp a p e r , t h ec o m p l e xp r o d u c tf l e x i b l es c h e d u l i n gp r o b l e mi ss t u d i e d ， w h i c hc o n s i d e r st h ec o n s t r a i n ta m o n gj o b sa n dc o n s i d e r st h ec o n d i t i o nt h a to p e r a t i o n c a nb ep r o c e s s e do nm a n ym a c h i n e sa tt h es a m et i m e s oi th a si m p o r t a n tt h e o r e t i c a l a n dp r a c t i c a ls i g n i f i c a n c e f o rt h ef l e x i b l e s c h e d u l i n gp r o b l e m o fc o m p l e x s i n g l ep r o d u c t ，an e w h i e r a r c h i c a l s c h e d u l i n ga l g o r i t h mi sp r e s e n t e d b a s e do ni m p r o v e dp r o c e s s i n g o p e r a t i o nt r e em o d e l a i m i n ga tt h er o u t i n gp r o b l e m ，s h o r t - t i m es t r a t e g ya n d m a c h i n e b a l a n c es t r a t e g ya r ea d o p t e dt oa s s i g ne a c ho p e r a t i o nt oam a c h i n eo u to fa s e to fm a c h i n e s t h e nt h ef l e x i b l es c h e d u l i n gp r o b l e mi sc o n v e r t e di n t ot h es t a n d a r d s c h e d u l i n gp r o b l e m f o rt h es e q u e n c i n gp r o b l e m ，o p e r a t i o n sa r ed i v i d e di n t o d e p e n d e n to p e r a t i o n s a n d i n d e p e n d e n to n e sa c c o r d i n gt o t h e i rc h a r a c t e r i s t i c s d i f f e r e n ta l g o r i t h m sa r ea d o p t e dt os c h e d u l ed i f f e r e n to p e r a t i o n s f o rt h ef l e x i b l es c h e d u l i n gp r o b l e mo fc o m p l e xm u l t i - p r o d u c t ，t h em e t h o do f a l i g n i n gt h er o o tn o d e si sa d o p t e dt ot r a n s f o r mt h ec o m p l e xm u l t i - p r o d u c tf l e x i b l e 1 1 哈尔滨理t 大学t 学硕十学位论文 s c h e d u l i n gp r o b l e mi n t ot h e v i r t u a l s i n g l e - p r o d u c tf l e x i b l es c h e d u l i n gp r o b l e m a i m i n ga tt h ev i r t u a ls i n g l e p r o d u c t f l e x i b l es c h e d u l i n gp r o b l e m ，a r li n t e g r a t e d a l g o r i t h mb a s e do nt h ea l l i e dc r i t i c a lp a t hm e t h o di sp r o p o s e d t h er o u t i n gs u b - p r o b l e ma n ds e q u e n c i n gs u b - p r o b l e ma r es o l v e da t t h es a m et i m eb yt h ep r o p o s e d a l g o r i t h m f o rt h ed y n a m i cf l e x i b l es c h e d u l i n gp r o b l e mo fc o m p l e xm u l t i - p r o d u c t ，an e w v i r t u a l p r o c e s s i n go p e r a t i o nt r e e i sc o n s t r u c t e db yt h ep r o d u c tr e m a i n e da n dt h e d y n a m i ca r r i v i n gp r o d u c t a n dt h ec o m p l e xm u l t i - p r o d u c td y n a m i c f l e x i b l e s c h e d u l i n gp r o b l e mi sc o n v e r t e di n t ot h ev i r t u a ls i n g l ep r o d u c tf l e x i b l es c h e d u l i n g p r o b l e m t h ev i r t u a ls i n g l ep r o d u c tf l e x i b l es c h e d u l i n gp r o b l e mi ss o l v e db yt h e h i e r a r c h i c a la l g o r i t h mp r o p o s e d t h ec o r r e s p o n d i n ga l g o r i t h m sa r ep r o p o s e dt os o l v et h ec o m p l e xs i n g l ep r o d u c t f l e x i b l es c h e d u l i n gp r o b l e m ，t h ec o m p l e xm u l t i - p r o d u c tf l e x i b l es c h e d u l i n gp r o b l e m a n dt h ec o m p l e xm u l t i p r o d u c td y n a m i cf l e x i b l es c h e d u l i n gp r o b l e m e x p e r i m e n t r e s u l ts h o w st h a tt h ea l g o r i t h mp r o p o s e dh a sf a v o r a b l ec o m p l e x i t ya n dc a no b t a i n b e t t e rr e s u l t s s ot h ea l g o r i t h mh a si m p o r t a n tv a l u eb o t hi np r a c t i c ea n dt h e o r y k e y w o r d s f l e x i b l es c h e d u l i n g ，c o m p l e xp r o d u c t ，i m p r o v e dp r o c e s s i n go p e r a t i o n t r e e ，s h o r t - t i m es t r a t e g y , m a c h i n e - b a l a n c es t r a t e g y i i i 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文复杂产品柔性调度优化研 究，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期间独立进行研 究工作所取得的成果。据本人所知，论文中除已注明部分外不包含他人己发表 或撰写过的研究成果。对本文研究工作做出贡献的个人和集体，均已在文中以 明确方式注明。本声明的法律结果将完全由本人承担。 作者签名：都法叉殇日期：砸7 年弓月加日 哈尔滨理工大学硕士学位论文使用授权书 复杂产品柔性调度优化研究系本人在哈尔滨理工大学攻读硕士学位期 间在导师指导下完成的硕士学位论文。本论文的研究成果归哈尔滨理工大学所 有，本论文的研究内容不得以其它单位的名义发表。本人完全了解哈尔滨理工 大学关于保存、使用学位论文的规定，同意学校保留并向有关部门提交论文和 电子版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学可以采用影印、 缩印或其他复制手段保存论文，可以公布论文的全部或部分内容。 本学位论文属于 保密口，在年解密后适用授权书。 不保密口。 ( 请在以上相应方框内打4 ) 作者签名：禾平法叉劾期：妒c 年弓月加日 别噬轹谗叫2 j 醐：7 钾肭日 哈尔滨理t 大学工学硕上学位论文 1 1 课题研究的背景 第1 章绪论 加工和装配是产品制造的主要任务，加工和装配任务调度对产品质量、生 产率和经济性都有很大的影响。加工和装配任务调度算法是研究虚拟制造、敏 捷制造和精益制造中设计计算机模拟制造过程的基础，是当前调度理论中所研 究的重要问题之一，此项研究既可以促使调度问题的发展及其相关问题的研 究，又可以使企业实现产品加工和装配计划的合理编排，从而减少人们的繁杂 劳动，合理优化地组织生产，缩短生产周期，降低成本，提高生产效率。 目前国内外多品种、小批量产品制造调度问题，主要分二部分解决：一部 分为加工调度优化n 。3 1 ，另一部分为装配调度优化h 刊。加工调度优化主要解决 具有如图1 1 所示产品加工工序次序图的产品加工问题，即每个工件由一串工 序加工而成，且工件间无约束的纯加工问题，属于简单产品加工调度优化问 题，即车间调度问题；装配调度优化主要解决具有如图1 2 所示产品装配工序 次序图的产品装配问题，即只存在零件( 工件) 间有约束的纯装配问题，属于 装配调度优化问题。 富寓二富 工件1工件2工件n 图1 - 1 简单产品工艺图图l - 2 产品装配工艺图 f i g 1 - 1p r o c e s s i n gt e c h n o l o g yc h a r to ff i g 1 - 2a s s e m b l yt e c h n o l o g yc h a r to f s i m p l ep r o d u c tp r o d u c t 多品种、小批量简单产品加工调度优化问题可被归结为种工序( 各项任 哈尔滨理 二人学t 学硕i ：学位论文 务的工艺流程不同) 需经m 类设备加工的复杂非流水型作业系统的排序问题 ( 即m x n 排序问题) ，它是b a k e r ( 1 9 7 4 ) 提出的调度问题的推广。该问题是工 件无约束问题，已经被证明是n p c 问题 1 。 多品种、小批量简单产品装配调度优化问题只涉及装配，不存在工件装配 以后产生的工件继续加工问题旧1 ，如装配自行车。 但是，工件装配以后产生的工件继续加工也是普遍存在的。例如，钻头的 生产过程，考虑钻头的切削部分与钻柄材质不同，所以对切削部分与钻柄分别 取料，进行下料、成型等加工处理产生切削部分与钻柄的毛坯，将切削部分与 钻柄的毛坯( 工件) 焊接( 装配) 成钻头的毛坯，对钻头的毛坯( 产生的新工 件) 进行开槽、磨削等加工处理，完成钻的加工。 所以多品种、小批量简单产品加工、装配调度研究有一定的局限性，有必 要进行更广泛应用领域的调度研究，如考虑同时存在加工、装配的复杂产品调 度优化问题。复杂产品制造的特点是工件加工、工件与工件装配以及装配以后 成为新工件再加工，形成工件间有约束的加工、装配，直到产品制造完成。简 单地说，复杂产品制造工序次序图中同时存在加工和装配，例如旋转分配集箱 的制造、大电机的转子轴承、飞机轴承和复杂的汽车轴承等。 现有的单件产品的加工调度算法和装配调度算法是解决纯加工或纯装配调 度问题。随着社会的进步，对产品多元化的需求促使产品生产趋向多品种小批 量，当制造产品品种单一，制造过程是工件间有约束加工、装配，单件复杂产 品制造，此时如果分别考虑加工任务调度算法和装配任务调度算法必然要割裂 单一产品的制造过程，破坏制造过程中内在的并行关系，如加工和装配之间的 并行，影响产品制造效率，因此有必要进行工件间存在约束关系的复杂产品调 度优化研究，进行复杂产品加工和装配的优化调度研究不仅有理论意义，还具 有广泛的应用领域。 1 2 国内外研究现状及分析 自从1 9 5 4 年j o h n s o n 对两台机床的流水型调度问题进行研究后，学术界和 实务界对生产调度问题展开了广泛的探讨，并取得了丰硕的成果。但是这些调 度理论对现实情况设定了很多假设，很难用于生产实践中旧1 。因此，探讨更少 假设、能真正体现实际生产的调度理论和方法具有非常重要的现实意义。柔性 调度问题就是在这种形势下产生的。它是对经典调度问题的扩展，不但继承了 传统调度问题的所有特征，而且增加了新的求解难度：允许某道工序在多台机 哈尔滨理t 大学工学硕上学位论文 器上加工，一台机器可以加工多种类型的工序。首先研究柔性调度问题的是 b r u k e r 和s c h l i e 0 1 ，他们开发出了一个多项式的机器的加工时间是相同 的。在此以后，学者们逐渐展开了对柔性调度的研究，寻找解决这类问题的有 效的优化方法。 2 0 0 1 年，m a t i 等提出了用贪婪式启发式规则同时解决柔性调度的分配 和工序调度两个子问题。同年，孙志峻等人23 用遗传算法研究了具有柔性加工 路径的智能优化调度问题，提出一种将遗传算法和分派规则相结合的调度算 法，将加工计划与生产调度同时考虑，避免了加工计划和生产调度相脱节的弊 端。 2 0 0 2 年，k a c e m 等n 3 1 用g a 解决柔性调度问题，并且采用两个方法分别解 决机器分配问题和工序调度问题：局部搜索法，建立理想的资源分配模式；分 配模型控制的遗传算法，用它求解单目标和多目标的柔性调度问题。 2 0 0 4 年，s c 对c hn 引采用禁忌搜索分步求解柔性调度问题，其优化目标是 延迟目标和设备总负荷。h o 和t a y 等n 5 1 认为求解f j s p 的g a 染色体需要特殊设 计，并给出两个标准评估染色体性能：计算的时间和空间复杂性；保持解的可 行性需要，提出了一种解决机器可以反复使用的f j s p 的有效方法。卢冰原等n 刚 对模糊环境下的f j s p 进行了研究，模糊加工时间用三角模糊数表示，优化目标 是m a k e s p a n ，采用遗传算法进行求解；实行双染色体机制，一个染色体表示工 序的机器分配，另外一个染色体表示机器上的工序加工顺序。 2 0 0 5 年，夏蔚军等n 7 1 研究了基于微粒群优化和模拟退火集成的方法解决多 目标f s j p 。多目标的处理方法是采用加权和的方法将多目标问题转换为单目标 问题。求解思路是分别求两个子问题，即微粒群优化求解机器分配问题和模拟 退火求解排序问题。同年，l o u k i l 等n 踟利用模拟退火求解多目标生产调度问 题。 2 0 0 6 年，卫忠等n 们采用演化多目标优化方法对多目标混合流水车间调度进 行了求解。同年，吴秀丽等心刚采用混合遗传算法对多目标柔性作业车间调度优 化方法进行了研究。 2 0 0 7 年，张超勇等幢设计了基于工序编码和基于机器分配编码的两种交叉 和变异算子，并提出一种双层子代产生模式的改进遗传算法应用于该调度问 题，以使子代更好地继承父代的优良特征。同年，席卫东等心引提出了一种新颖 直观的双子串基因编码方法，并设计了独特的交叉和变异算子，从而取消运用 遗传算法求解作业车间调度问题时为使基因合法化而进行的基因修复和重建过 程。同年，鞠全勇等心3 1 提出批量生产优化调度策略，建立多目标优化调度模 哈尔滨理t 人学丁学硕l ：学位论文 型，结合多种群粒子群搜索与遗传算法的优点提出具有倾向性粒子群搜索的多 种群混合算法，以提高搜索效率和搜索质量。 2 0 0 8 年，陈亮等心4 1 提出基于过滤定向搜索的集成启发式算法，设计改进了 节点分枝策略和局部全局评价函数，能同时解决柔性车间调度两大子问题。 具有相同设备的调度问题是指能够加工同一道工序的设备不唯一，即存在 一设备子集，其上的任意一台设备都能加工该道工序，加工同一道工序的所有 设备的加工时间是相同的。对于这类问题国外的相关研究把这类问题归类于多 用途机器的调度问题，并根据所研究具体问题的特点，提出了一些解决方法， 如分枝定届法，蚁群算法等；陈冬雪等乜引提出了用剩余率求解非标准作业车间 调度问题的逆序算法，引入剩余率作为一种排序的优先规则来确定各个作业的 各道工序的先后加工顺序及机器的选择，取得了令人满意的调度结果。清华大 学吴澄等呛6 1 给出了一种解决此类问题的遗传算法，改善了单纯依赖调度规则的 不完备优化过程。谢志强等幢7 1 通过对工序进行分类，对相同设备上加工的工序 提出了二次优化比较算法，而对独立工序采用最优适应调度算法，取得了较好 的效果。 具有相同设备的调度问题是柔性调度问题的一个特例，仅考虑的是工序在 设备集上加工时间相同的情况。而以上用来解决柔性调度问题的优化算法，也 只能解决工件间无约束的简单产品的柔性调度问题，而针对工件间存在约束关 系的复杂产品的柔性调度问题很少有人研究。熊禾根位剐提出了一类考虑工序相 关性的j o bs h o p 调度问题，对工序相关性从代数描述、甘特图表示和类型转 换等方面进行了较为系统的数学描述，但他仅在标准调度中考虑了工序相关 性，没有把它和柔性调度相结合。因此对复杂产品柔性调度优化研究，既考虑 了工序在设备集上加工时间不同的情况，也考虑了工件间存在约束关系的情 况，是排序理论的前沿课题，同时也是生产实践中必须加以解决的实际课题。 无论从理论上还是实践上来说，研究复杂产品的柔性调度问题，对于在大中型 企业推广c i m s 技术、实现生产自动化管理，一定会起到积极作用。 1 3 课题研究的意义 目前在我国一般企业中，生产调度的工作主要还是由老技工来完成，他们 完全靠经验来安排。如今，随着企业之间的竞争越来越激烈，产品的寿命周期 变得越来越短，产品的品种变得越来越复杂多样，以往的小品种大批量的生产 模式渐渐变成了多品种小批量的生产模式不仅每天的生产品种在不断地改变， 哈尔滨理t 大学t 学硕士学位论文 而且在客户就是上帝的口号下，已经安排好的调度计划会突然由于客户需求的 改变而改变，于是调度工作也逐渐变成一项纷繁复杂的日常性工作。面对着这 些变化和随时可能发生的生产加工环境的改变，如机床设备的突然损坏等等情 况，要使企业的生产能力和效率始终保持较高的水平，仅仅依靠经验是不能胜 任的。在技术装备较为先进的企业中，它们一般拥有企业资源规划生产管理软 件，但这些软件都不具备对生产车间级的调控管理功能，所以同样面临着与一 般企业相同的问题。如何较好地解决这一问题是当前企业界与学术界都十分紧 迫的任务之一。因此，对调度问题的研究，吸引了国内外许多学者和实际生产 调度人员的关注。 产品加工和装配是产品制造的主要任务，加工和装配任务调度对产品质 量、生产率和经济性都有很大的影响。产品加工和装配任务调度算法是当前调 度理论中所研究的重要问题之一，此项研究既可以促使调度问题的发展及其相 关问题的研究，又可以使企业实现产品加工和装配计划的合理编排，从而减少 人们的繁杂劳动，合理优化地组织生产，缩短生产周期，降低成本，提高生产 效率。 进行产品加工和装配任务调度算法的研究并实现，会大大缩短生产计划的 编排周期，提高生产计划准确度。不仅会提高企业的生产效率，判断交货期的 可行性，避免企业的生产风险，便于企业做出更合理的生产计划，促进加工制 造业的发展。 由于现有的单件产品的力n - t - 调度算法和装配调度算法是解决简单产品调度 问题的，即纯加工或纯装配调度问题。随着社会的进步，对产品多元化的需求 促使产品生产趋向多品种小批量，当制造产品复杂单一，制造过程是工件加 工、工件与工件装配以及装配以后成为新工件再加工，形成工件间有约束加 工、装配，直到产品制造完成。此时如果分别考虑产品加工任务调度算法和产 品装配任务调度算法必然要割裂单一产品的制造过程，破坏制造过程中的并行 处理，如加工和装配之间的并行，影响产品制造效率，因此有必要进行工件间 存在约束关系的复杂产品调度优化研究。本文对复杂产品柔性调度进行了研究 探讨。工件间存在约束关系的复杂产品调度优化研究以解决复杂产品加工、装 配过程综合调度优化问题为目的，可从全局( 总体) 的角度给出使产品制造时 间更短的工序安排，实现装备制造业加工、装配过程更加有效的优化控制。柔 性调度问题由于减少了机器约束，扩大了可行解的搜索范围，提高了问题的复 杂性，所以比传统的调度问题更接近实际生产环境的模拟。因此该课题的研究 与实现不仅符合当前国家大力发展装备制造业的国情，有重要的理论和社会意 哈尔滨理工人学工学硕上学位论文 义，还会产生可观的经济效益。 1 4 课题来源及本文主要内容 1 4 1 课题来源 国家自然科学基金( n o 5 0 5 7 5 0 6 2 和n o 6 0 8 7 3 0 1 9 ) ，黑龙江省自然科学 基金项目( n o f 2 0 0 6 0 8 ) ，黑龙江省教育厅海外学人科研资助重点项目( n o 1 1 5 2 h q 0 8 ) 。 1 4 2 本文研究的主要内容 关于柔性调度问题，已经有很多学者提出了有效的优化算法，但他们只考 虑了工件间无约束关系的情况，对工件间存在约束关系的复杂产品柔性调度问 题，没有相应的解决算法。本文在简单产品柔性调度的基础上，对工件间存在 约束关系的复杂产品柔性调度问题进行研究，设计两种求解复杂产品柔性调度 的优化算法。一种是分步式算法，把此问题分解为工序优化分配和工序优化调 度两个子问题，对这两个子问题分别提出相应的算法；一种是集成式算法，同 时解决这两个子问题。两种算法都采用加工工艺树模型进行调度分析，根据工 序的不同特点把加工工序分解为相关工序和独立工序，不同类型的工序采用不 同的算法进行调度。本文的研究内容是这样安排的： 第1 章介绍了本课题研究的背景，国内外研究现状，课题研究的意义、课 题来源及论文的主要研究内容。 第2 章介绍了柔性调度问题的含义，柔性调度中用到的基本概念及建模方 法，然后给出了现有的求解柔性调度问题的求解方法，最后阐述了柔性调度存 在的问题及其发展趋势。 第3 章对复杂单产品柔性调度问题进行分析，提出了一种分步式求解该问 题的算法，首先采用短用时策略和设备均衡策略把柔性调度转化为标准调度问 题；然后根据工序的不同特点，把加工工序分解为相关工序和独立工序，对相 关工序采用前沿贪心规则来进行调度，对独立工序采用缩短空闲时间算法。 第4 章对复杂多产品柔性调度问题进行分析，通过构造虚拟加工工艺树， 提出一种集成式求解问题的算法，同时解决工序优化分配和工序优化调度两个 子问题，并通过实例进行验证比较。 哈尔滨理t 大学t 学硕 = 学位论文 第5 章在前两章研究的基础上对复杂多产品动态柔性调度问题进行建模， 将不同时刻到来的产品所对应的改进加工工艺树和原来产品的剩余工序所构造 的改进加工工艺树虚拟成一棵新的改进加工工艺树，通过添加虚拟根节点将复 杂多产品动态柔性调度问题简化成复杂单产品柔性调度问题进行考虑。 最后对本文进行了总结，并对进一步的研究做出了展望。 哈尔演理t 大学t 学顾卜学位论文 第2 章柔性调度问题概述 2 1 柔性调度问题描述 车间调度问题就是在时间上合理配置系统的有限资源，以满足特定目标的 要求。传统的车间调度问题包括一个待加工工件集合，每个工件包含一个工序 集合，各工序需要采用机器等生产资源，并且要按照一定的工艺路线进行加 工；不同机器加工的工序可以不同；调度的目的就是为工件合理地分配机器等 资源，并合理地安排加工时间，在满足条件的同时，使一些指标最优。 柔性调度问题是在生产调度领域发展过程中，顺应实际生产的发展，在 传统调度基础上提出来的调度模型。它取消了传统调度中每道工序只能在一台 机器上加工的限制，即每道工序可以由多台不同的机器加工，并且在不同的机 器上加工所需的时间也不同。 柔性调度问题可以描述成：假设m 台机器，需要完成聆个工件的加工任 务，每台机器同一时刻只能加工一个工件，而且每台机器必须在当前加工的工 件处理完之后才能加工其他工件；每个工件的加工由多道工序组成，工件的加 工工艺预先确定了其内部各工序的先后顺序，加工过程中同一工件的工序严格 按照先后顺序约束逐一加工；每道工序可以在多台机器上加工，加工时间长短 随机器的性能不同而变化；调度目标是为每道工序分配最合适的机器，并确定 每台机器上各工件的最优加工顺序，以及各工序的加工开始时间，使得既定的 性能指标达到最优。 2 2 柔性调度问题中的概念和建模方法 2 2 1 柔- 生调度问题中的基本概念 调度问题的主要概念有以下几种： 1 生产周期( m a k e s p a n ) 生产周期是调度开始时间与终止时间之间的间 隔。一个调度的生产周期就是该调度中所有作业的最大完成时间，即 m a k e s p a n - - m a x ( c i ) ，f _ 1 ，2 m ，c i 为作业f 的完成时间，生产周期代表资源利 用率。较短生产周期意味着较高资源利用率，常作为作业调度优化目标。 哈尔滨理工人学t 学硕i j 学位论文 2 关键路径( c r i t i c a lp a t h ) 关键路径就是最重要的路径，其对全部工程 完工所需时间影响最大。 3 甘特图( g a n t tc h a r t ) 甘特图利用长条图来显示所有任务，将任务画 在表上，并显示开始日期与完成日期以及持续时间。 2 2 2 柔性调度问题中的建模方法 调度问题的建模方法有数学模型和析取图模型。 1 数学模型一些学者从整数规划的角度建立了多目标柔性调度的数学模 型。庞哈利1 从集成化的角度研究了柔性车间计划和调度问题，建立了两层混 合整数规划模型，并用遗传算法求解最佳加工路径，用启发式规则求解调度问 题。 2 析取图模型j s s p 的非连接图模型g = ( m 彳，d 由b a l a s b 州提出，包 含代表所有工序的节点，么包含连接同一工件的邻接工序的边，e 包含连接同 一机器上加工工序的非连接边，非连接边可以有两个可能方向。调度过程将固 定所有非连接边的方向，以确定同一机器上工序的顺序，并采用带有优先箭头 的连接边取代非连接边。d a u z e r e p e r e s b 用非连接图建模了调度问题，并 建立了邻域结构，进而采用基于邻域结构的禁忌搜索进行求解。 2 3 柔性调度问题的求解方法 简单产品的加工、装配调度问题都是对于具体生产环境中复杂的、动态 的、多目标的调度问题的一种抽象和简化。一个调度算法可以通过其如何表述 这些复杂性进行分类，由于实际生产环境是千差万别的，那么一个调度算法就 应该根据其是否适合对应的生产环境特征进行评估。对调度问题进行研究的方 法，最初是集中在整数规划、仿真和简单的规则上，这些方法不是调度结果不 理想就是难以解决复杂的问题。随着各种新的相关学科与优化技术的建立与发 展，在调度领域也出现了许多新的优化方法，比如神经网络、模拟退火法、遗 传算法、禁忌搜索法、微粒群法、蚁群算法和工艺图分解法等，使得调度问题 的研究方法向多元化方向发展。下面仅对这些方法进行归纳。 1 运筹学方法运筹学方法是将生产调度问题简化为数学规划模型，采用 基于枚举思想的分枝定界法或动态规划算法进行解决调度最优化或近优化问 题，属于精确方法3 2 1 。针对不同的分枝定界法，其不同点主要体现在分析规 则、定界机制和上界的产生三个方面旧引。这类方法虽然从理论上能求得最优 哈尔滨理丁大学t 学硕土学位论文 解，但由于其计算复杂性的原因、因而不能获得真正的实用，对于生产环境中 的动态调度实现复杂，不能解决动态及快速响应市场的问题。 2 系统仿真的方法仿真方法通过对实际生产环境的建模来模拟实际生产 环境，避开了对调度问题进行理论分析的困难，从而对一种调度方案的实施进 行计算机模拟仿真，用户可以使用仿真手段对某些调度方案进行测试、比较、 监控，而从改变和挑选调度方案。仿真方法可以建立在纯仿真模型基础上，也 可以运用各种分析模型和方法，例如排队网络、p e t r i 网、极大代数模型等。通 过仿真可以分析在不同的调度方法下系统的性能，从而调整调度规则。这种基 于仿真的方法不需对实际系统作任何不必要的简化假设，所得调度结果不存在 可行性问题，仿真模型可以尽可能按需要逼近实际情况。当需要对不同的调度 方案进行选择时，仿真系统可以作为决策支持工具。 3 基于规则的方法对生产加工任务进行调度的传统的方法是使用调度规 则( d i s p a t c h i n gr u l e s ) ，已经有许多调度规则被应用m 崩1 ，因其调度规则简 单、易于实现、计算复杂度低等原因，能够用于动态实时调度系统中汹1 ，多年 来一直受到学者们的广泛研究，并不断涌现出新的调度规则。如研究与制定较 优的单元零件加工调度算法，在减少等待时间、提高生产率等诸多约束条件下 达到了一种较为科学有效的调度效果，并将它们按形式分为了三类：简单规 则、复合规则、启发式规则。随着计算机运算速度的迅速提高，人们希望寻找 新的近似调度方法，它以合理的额外计算时间为代价，换得比单纯启发式规则 所得到的调度更好的调度。在这方面比较有代表性的有移动瓶颈方法( b o t t l e n e c kp r o c e d u r e ) ，用来解决以最小化为目标的j o b s h o p 调度问题嘧7 矧，它通 过不断地对移动的瓶颈设备进行单机调度，来获取更好的次优解。总的说来， 启发式规则直观、简单、易于实现。但是近十年的研究表明并不存在一个全局 最优的调度规则，它们的有效性依赖于对特殊性能需求的标准及生产条件。它 是局部优化方法，难以得到全局优化结果。 4 基于模糊的方法客观现象具有确定性和不确定性两个基本方面，经典 数学表达的是现象的确定性；不确定性一方面表现的是随机性，另一方面表现 为模糊性。正是利用这个特点，许多专家学者把它引入到调度领域。 模糊控制技术就是采用模糊数学开发出模糊控制器，通过将不同的调度规 则对加工系统性能的影响描述成模糊数学形式，根据对其性能的影响程度将不 同的规则进行组合，通过模糊推理确定不同加工环境下使用的规则或者组合规 则，其试验结果明显好于简单的规则或者加权规则组合。用这种思路开发出的 高性能模糊控制器具有自学习功能，可在控制过程中不断获取新的信息并自动 哈尔滨理工人学工学硕i ：学位论文 地对控制量作调整，使系统性能大为改善，从而可使调度具有很高的柔性。但 是这种方法同样具有开发周期长、需要丰富的调度经验和知识等，而且这种方 法的不足之处还有开发出一个高性能的模糊控制器是相当不易的。 5 人工智能的调度方法人工智能在6 0 年代就将计划问题作为其应用领域 之一，但直到8 0 年代，人工智能才真正开始应用于调度问题。智能调度主要包 括智能调度专家系统、基于智能搜索的方法及基于多代理技术( m u l t i a g e n t s y s t e m ，m a s ) 的合作求解的方法等。其中，智能调度专家系统是人工智能应 用的体现，由于专家系统中知识获取和推理速度这两个瓶颈，使得神经网络逐 渐被采用，但还存在训练速度慢、探索能力弱等缺点。基于多代理技术的合作 求解方法是较新的智能调度方法，它提供了一种动态灵活、快速响应市场的生 产调度机制，它以分布式人工智能( d i s t r i b u t e da r t i f i c i a li n t e l l i g e n c e ，d a i ) 中 的多代理机制作为新的生产组织与运行模式，通过代理( a g e n t ) 之间的合作 以及m a s 系统协调来完成生产任务的调度，并达到预先规定的生产目标及生产 状态悟引1 。 6 启发式图搜索法对于表述为整数规划的调度问题，最初采用分枝定界 法来解决，而后其他的启发式图搜索法也被应用于解决调度问题如：采用基于 枚举的搜索方法不断提高解的次优性：采用束搜索法( b e a ms e a r c h ) 来识别 瓶颈设备，进行调度；为了解决搜索空间太大的问题，采用一种过滤束搜索法 ( f i l t e rb e a ms e a r c h ) m 4 引，解决单台设备提前延期问题和加权延期的 f l o w s h o p 问题；研究了基于a 木的优先树搜索法的优化作业排序问题；为解决 j o b s h o p 调度问题对a 宰算法作了两点改进：在搜索过程中只展开有限结点； 采用加权的评价函数。对于图搜索算法，如何提高搜索效率并减少内存使用以 解决规模较大的问题，还需要进一步探索。 7 模拟退火法( s i m u l a t e da n n e a l i n g )模拟退火算法将组合优化问题与 统计力学中的热平衡问题类比，另辟了求解组合优化问题的新途径。它通过模 拟退火过程，可找到全局( 或近似) 最优解。其基本思想为：把每种组合状态 研看成某一物质系统的微观状态，而将其对应的目标函数c ( s i ) 看成该物质系 统在状态研下的内能；用控制参数r 类比温度，让丁从一个足够高的值慢慢 下降，对每个丁，用m e t r o p o l i s 抽样法在计算机上模拟该体系在此丁下的热平 衡态，即对当前状态作随机扰动以产生一个新状态s ，如果c o j ) c 0 ) 则接 受s i 为下一状态，否则以概率e ( c ( s 3 c ( s ) ) 接受。经过一定次数的搜索，认为系 统在此温度下达到平衡，则降低温度t 再进行搜索，直到满足结束条件。可单 独或与其他算法相结合使用模拟退火法解决f l o w s h o p 排序问题和j o b s h o p 调 哈尔滨理t 大学t 学硕f j 学位论文 度问题h 引。由于模拟退火法能以一定的概率接受差的能量值，因而有可能跳出 局部极小，但它的收敛速度较慢，很难用于实时动态调度环境h 5 1 。 8 禁忌搜索法( t a b us e a r c h ) 对于复杂的组合优化问题，禁忌搜索也是 种通过领域搜索以获取最优解的方法。禁忌搜索是一种迭代方法，它开始于 一个初始可行解s ，然后移动到邻域( 研中最好的解s ，即s 对于目标函数 只研在领域( $ 中是最优的。然后，从新的开始点重复此法n 引。为了避免死循 环，禁忌搜索把最近进行的丁个移动( 丁可固定也可变化) 放在一个称作t a b u l i s t 的表中，在目前的迭代中这些移动是被禁止的，在一定数目的迭代之后它 们又被释放出来。这样的t a b ul i s t 是一个循环表，它被循环地修改，其长度r 称作t a b us i z e 。最后，还须定义一个停止准则来终止整个算法。禁忌搜索算法 已被用于解决f l o w s h o p 调度问题如：求解公共交货期下带有等待时间惩罚的 提前拖期单机调度问题。为了更有效地搜索解空间，引入了插入和移动相结 合的机制提高了搜索效率：采用了并行禁忌搜索法以加快搜索速度。由于t a b u l i s t 的限制，使禁忌搜索法在搜索中有可能跳出局部极小 。 9 遗传算法( g e n e t i ca l g o r i t h m s ) 美国m i c h i g a n 大学的j h h o l l a n d 于 本世纪末提出了一种新的并行优化搜索方法：遗传算法( g e n e t i ca l g o r i t h m ) ， 它是一种基于进化