（计算数学专业论文）基于遗传算法的柔性作业车间模糊调度的研究.pdfVIP

摘要 现有的针对f s j s 问题的研究大都建立在对调度环境进行严格限 制上，强调各类限制条件和生产信息预先明确，然而在实际生产环境 中，存在机器、环境等因素的影响，致使包括时间参数和约束条件在 内的相关信息无法准确预知，存在模糊不确定性。本文将f j s p 问题 从严格限定的理想环境拓展近现实的模糊环境中，使其具有更强的灵 活性和实用性。 首先，本论文以图的形式清晰地描述作业车间调度问题、柔性 作业车间调度问题，( f j s p ) 和柔性作业车间模糊调度问题，并给出 了解决这些问题的编码、解码算法。 。 其次，本论文研究了以最小最大完成时间为目标的，具有模糊加 工时间的柔性车间调度问题( f l e x i b l ej o b s h o ps c h e d u l i n g ，f j s p ) ， 用六点模糊数来表征时间参数，本文引入可能性理论，采用可信性测 度方法解决该问题的子问题，进行了系统的阐述，确立目标函数，最 后通过遗传算法进行有效性分析。 再次，本论文研究了以最小化提前拖期惩罚为目标的，具有模 糊加工时间与模糊交货期的f j s p 问题。针对该问题，本文引入了六 点模糊数比较大小的可能度和模糊数4 大于等于豆的程度的概念。并 通过改进的遗传算法对问题进行了有效地求解。 最后，给出仿真实验结果和结论。 关键词：遗传算法，车间调度，柔性作业车间模糊调度，模糊加工 时间，模糊交货期 m o s tr e s e a r c h e sa b o u t 冈s sp r o b l e m sa r el i m i t e di n s t r i c tr e s t r i c t e de n v i r o n m e n t sm w h i c ha l lk i n d so fi n f o r m a t i o na n dr e s t r i c t i o n sa l ep r e d e f l n e d h o w e v e r , a f f e c t e db yh u m a n ， m a c h i n e sa n de n v i r m e n t a lf a c t o r s ，t h ec o r r e s p o n d i n gi n f o r m a t i o ns u c ha sr e s t r i c t i o n sa n dt e m p o r a l p a r a m e t e r sa r eu n c e r t a i na n dc a nn o tb ep r e d e f i n e dp r e c i s e l y t h i sd i s s e r t a t i o n e x t e n df j s s p r o b l e mf o r mi d e a le n v i r o n m e n tt op r a c t i c a lf u z z ye n v i r o n m e n tw h i c ha r em o r ef l e x i b l ea n d p r a c t i c a l t h ep a p e r , i n t r o d u c ec o m p l e t l yt h ec o n n e c t i o no fj o b - s h o ps c h e d u l i n gp r o b l e m ，f l e x i b l e j o b s h o ps c h e d u l i n gp r o b l e ma n df l e x i b l ej o b - s h o pf u z z ys c h e d u l i n gp r o b l e mi nt h eg r a p hv i e w f i r s t l y a n dt h ec o d ea l g o r i t h mi sg i v e na b o u tt h o s es c h e d u l i n gp r o b l e m sf i r s t l y t h i sd i s s e r t a t i o ns t u d i e st h et o t a lf l e x i b l ej o b - s h o ps c h e d u l i n gp r o b l e ma i m i n ga t m i n i m i z e dm a k e s p a nw h i c hh a sf u z z yo p e r a t i o nt i m e t e m p o r a lp a r a m e t e r si s d e n o t e db y6 - p o i n t f u z z yn u m b e r i n t r o d u c i n gt h ep o s s i b l et h e o r y , i tu s et h ec r e d i b i l i t ym e a s u r et o i l l u s t r a t ee a c h s u b - p r o b l e mo ft h i sp r o b l e ma n di tu s eg e n e t i ca l g o r i t h mt og e tp e r f e c ts c h e d u l i n gs c h e m e s r e s p e c t i v e l ys e c o n d l y t h i sd i s s e r t a t i o ns t u d i e st h ef l e x i b l ej o b s h o ps c h e d u l i n ga i m i n ga tm i n i m i z e de t p e n a l t yw h i c hh a sf u z z yo p e r a t i o nt i m ea n df u z z yd u ed a t e s 。f o rt h i sp r o b l e m ，i ti n t r o d u c et h e d e g r e eo fp o s s i b i l i t yo f6 - p o i n tf u z z yn u m b e r ，a n dt h ed e f i n i t i o no ft h ed e g r e et ow h i c hf u z z y n u m b e rai sg r e a t e rt h a no re q u a lt ob ，t h e na ni m p r o v e dg e n e t i ca l g o r i t h mi sg i v e nt og e ta p e r f e c ts c h e d u l i n gs c h e m et h i r d l y f i n a l l y ，t h ee x p e r i m e n t a lr e s u l t sa n dc o n c l u s i o na l eg i v e n k e y w o r d s ：g e n e t i ca l g o r i t h m ，j o b s h o p ，f l e x i b l ej o b s h o pf u z z ys c h e d u l i n g ，f u z z y p r o c e s s i n gt i m e ，f u z z yd u ed a t e 3 原创性声明 本人声明：所呈交的学位论文是本人在导师的指导下进行的研究工作及取得的研究成果。除本文已 经注明引用的内容外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得内墓直太堂及 其他教育机构的学位或证二传而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中 作了明确的说明并表示谢意。 学位论文作者签名：垄3 投丛 指导教师签名：互主垄 日 期：卫掣e l 期：辎灿 在学期间研究成果使用承诺书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：内蒙古大学有权将学位论文的全 部内容或部分保留并向国家有关机构、部门送交学位论文的复印件和磁盘，允许编入有关数据库进行检索， 也可以采用影印、缩印或其他复制手段保存、汇编学位论文。为保护学院和导师的知识产权，作者在学期 间取得的研究成果属于内蒙古大学。作者今后使用涉及在学期间主要研究内容或研究成果，须征得内蒙古 大学就读期间导师的同意；若用于发表论文，版权单位必须署名为内蒙古大学方可投稿或公开发表。 学位论文作者签名：茎塑煎鍪 日 飙半 指导教师签名：刍主盔 日 期一坦翌2 签： 第一章车间调度问题概述 车间调度问题是调度问题的一个子集，实际上是一个资源分配问题，这里 的资源分配主要指设备资源，问题的求解目标主要是要找到一个可以使作业能被 “最优完成的方案。通常车间调度问题约束的数目很大，使得该问题成为一个 n p - h a r d 问题。好的生产调度能提高资源的利用率和操作管理水平，生产出具有 竞争力的产品。车间的调度优化工作，因其在提高生产效率，降低生产成本等方 面所起的重要作用，正越来越受到学者们的关注。 1 1 车间调度问题的含义 典型的车间调度问题包括一个待加工工件集合，每个工件包含一个工序集 合，各工序需要占用机器等生产资源，并且要按照一定的加工顺序进行加工：不 同机器加工的工序可以不同：调度的目的就是为工件合理地分配机器，并合理地 安排加工时间，在满足约束条件的同时，使一些指标最优。 总的说来，车间调度问题就是在时间上合理配置系统的有限资源，以满足 特定目标的要求。对于所台机器 m 。，m 2 ，m 。 对厅个工件 ，。，j 2 ，。 的加工 过程，所谓调度就是分配各工件在各机器上的加工时间。 1 2 车间调度问题的研究现状 近年来，车间调度问题的研究向更实用的方向发展，主要表现在以下面几个 方面： 1 、多目标调度 多目标调度问题引起了越来越多学者的关注。他们的研究方法有三种： ( 1 ) 验偏好信息的方法，即在求解问题之前，获取决策者的偏好信息。譬如， 先通过调查，得到了综合目标与生产周期和平均延误时间之间的函数关系，然后 按综合目标搜索最优调度。 ( 2 ) 验偏好信息的方法，即直接根据问题的性质和结构求出部分以至全部非 劣解，再由决策者选择一个最满意解。 ( 3 ) 逐步取得偏好信息的方法，即决策者通过与辅助决策系统对话，来加深 自己的认识，辅助决策系统则根据决策者新的认识重新搜索解空间，对话和搜索 过程不断进行，直到找到最优解。 6 2 、动态调度 生产调度过程是一个动态过程。研究都认为动态调度方法得到的结果要优于 静态调度得到的结果。 3 、工艺路线规划与作业调度的集成 把工艺路线规划与作业调度集成在一起的工作方法，即为工件保留尽可能多 的工艺路线，调度时根据车间的动态情况来选择一条最佳的路线来加工，通过调 查认为这种方法能使生产周期、机床设备利用率等指标得到重大改善，也证实这 种方法能提高车间的生产能力。 4 、多资源调度 车间的生产能力不仅会受到机床的制约，还会受到工人和辅助工具的制约。 t r e l e v e n 和e 1 v e r s 1 研究了受工人和机床限制的调度问题，认为当工人与机床 设备的比率在5 0 - 7 5 之间时，系统的生产率最高。 5 以经济利益为目标的调度 管理人员最关心的是收益、总生产成本、在线库存费用、工件拖期损失等。 采用经济指标研究调度问题，就是选择一个能给生产车间带来最大经济利益的调 度方案。 6 批量生产调度 由于订货、运输、包装和车间管理等原因，零件往往是成批生产的。注意到， 如果一批零件加工一部分后，就运往后续加工机床，可使后续工序提前进行。 7 模糊调度 受多种因素的影响，零件的加工时间和交货期并不是非常准确的数值，这些 不确定性可以用模糊数表达。文献【2 - 6 j 研究了具有模糊属性的调度问题。 t s u j i m u r a 【3 】等研究了模糊加工时间的流水车间调度问题。m u r a t a 【4 】等研究了具 有模糊交货期的流水车间调度问题。s a k a w a 和m o r i 【5 j 建立了作业车间模糊加工 时间与模糊交货期的调度问题模型，并用遗传算法对完工时间和交货期双目标进 行了优化。 8 基于j i t 的调度 随着j i t 的成功应用，人们越来越注重盯生产调度问题。r o a c h 【7 研究了装配 线上的调度问题，提出了模拟退火与遗传算法相结合的调度算法。陈伟达【8 j 提出 了模拟退火方法与启发式式规则相结合的调度算法。李霄锋【9 j 采用反向仿真的方 法研究了j i t 生产调度问题。陈志龙l l o j 对研究情况进行了总结，认为j i t 调度 的研究模型过于简单，应向更实用的方向发展。 9 智能制造系统多目标车间调度研究 用成组技术分解调度成组技术的就是根据作业、机床之间的相似性将它们各 自分组，利用组内的相似性来提高生产率。已有文献研究了成组调度问题。提出 一种分解策略，先将作业进行分批，然后再通过随机组合每批作业的子调度来构 7 成整体调度。 1 0 人机交互调度 人机协同的交互策略为解决调度问题提供了一个新的手段。提出了一种用于 作业调度的交互工具。 1 1 多制造单元协同调度 多制造单元协同是先进制造领域的关键技术之一。多制造单元协同调度已成 为近期研究的热点。 1 3 车间调度问题的研究方法 经过5 0 多年的发展，车间调度问题出现了多种研究方法，总结如下： l 、基于启发式规则的方法 由于启发式规则计算复杂度低、易于实现，故在生产中得到了广泛的应用。 但启发式规则一般不具备全局优化的特点。常用的启发式规则可分为简单规则、 复合规则、启发式规则三类。 2 、基于运筹学的方法 运筹学方法是将生产调度问题简化成为数学规划模型，采用基于枚举思想的 分枝定界法或动态规划法进行求解。这类方法通常是一种解决较小规模调度问题 的有效算法。随着问题规模的扩大，有其自身的局限性。 3 、拉格郎日松弛算法 拉式松弛算法能为复杂的规划问题提供好的次优解，并对解的次优性进行定 量评估，所以成为解决调度问题的一种重要方法。但与分枝定界法相比，拉式算 法更耗时。 4 、动态规划 动态规划是求解小规模调度问题的有效算法，但它对组合的需要随问题规模 的扩大呈指数增长，以至不能求解大规模调度问题。 5 、基于人工智能的方法 人工智能的方法就是利用模型和知识，通过模拟和推理等手段为人的决策行 为提供支持，从而使人们可以根据车间的不同情况做出相应的更符合实际的决 策。 6 、人工神经网络法 h o f i e l d 神经网络模型的出现为解决调度问题开辟了一条新的途径，其应用 于生产调度问题的方式主要有三种：一是利用其并行计算能力，求解优化调度， 以克服调度的n p 完全问题：二是利用其自学习能力，从优化轨迹中提取调度知识： 三是用神经网络来描述调度约束或是调度策略，以实现对生产过程的可行或次优 调度。但神经网络法也存在着许多的缺陷，如涉及的变量太多，计算效率低，很 难解决实际的调度问题。 7 、基于离散事件动态系统的解析模型法 由于制造系统是一类典型的离散事件系统，因此，可以用研究离散事件系统 的方法和解析模型来探讨生产调度问题。诸如q n 、极大代数法、动态规划法、 p e r t i 网等。 8 、局域搜索法 a ) 模拟退火法 8 模拟退火方法将组合优化问题与统计力学的热平衡问题类比，通过模拟退火 过程，可找到全局最优解。文献【1 1 j 用模拟退火的方法解决了流水车间的排序问 题，但它的收敛速度慢，很难用于实时动态调度环境。 b ) 禁忌搜索法 禁忌搜索是由g l o v e r 提出的用于解决组合优化问题的一种高级启发式方法。 t a i r i d 提出了解决流水车间调度问题的禁忌搜索算法t l 纠。 c ) 遗传算法 遗传算法成为近年来解决作业调度问题的最主要方法。与其它方法相比，遗 传算法的优越性主要表现在：搜索过程中能以较大的概率找到全局最优解：具有 并行性，非常适合于大规模并行分布处理：易于和别的技术( 如神经网络，启发式 规则等) 相结合，形成性能更优的算法。但遗传算法的搜索效率低，易过早收敛 【1 9 i 。 9 、组合算法 由于每一种调度方法都有各自的优缺点，将两种算法相结合取长补短是一种 很好的思路。近年来人们开始把各种近似算法的组合应用研究作为热点，各种各 样的混合算法层出不穷，诸如将启发式规则和遗传算法相结合，提高了遗传算法 盲目随机操作的概率，加速了算法的收敛：反过来说，遗传算法本身所具有的随 机特性又能在一定程度上弥补启发式算法的强偏差性。 1 0 、仿真调度方法 仿真模型可以描述和定量评估复杂的制造系统，为实际调度采用合适的调度 算法提供依据。但高精度的仿真模型也不能保证得到最优甚至较优的调度方案。 1 4 车间调度问题的发展趋势 综上所述，我们不难看出，虽然对车间调度领域的研究已有很长的历史，但 是至今尚未形成一套系统的理论与方法，理论研究和实际应用之间还存在着很大 的差距。今后调度问题的研究应该向下面几个方向发展： ( 1 ) 实用化 一些理论上的最优调度方法能够提供最优调度，但由于计算复杂性大，并且 忽略了很多实际的因素，离应用还有很大的差距。因此如何综合运用现有优化算 法，真正提高车间调度的信息化水平有待进一步的研究。 ( 2 ) 集成化 探索车间计划与调度的集成。集合回答应该生产什么，而调度则回答怎样生 产。两者是相互联系的，应该建立一个集成系统。 ( 3 ) 高效智能化 寻找新的调度算法，该算法应该能够快速、高效的找到大规模调度问题的最优 解或次优解，并能对找到的解进行评估。 ( 4 ) 柔性化 在传统的车间调度问题的研究中，仅考虑每一工件具有唯一确定加工工艺路 线的情况。随着加工技术、自动化技术的发展，特别是柔性加工系统( f m s ) 的出 现，工件加工工艺路线必须唯一确定的传统限制己被突破，工件具有多个可选择 9 的加工路线，即路径柔性己成为生产的实际需求。 总之，对于生产调度问题的研究，随着应用数学理论的进一步发展，必然朝 着实用化、集成化、高效智能化、柔性化的方向发展。 1 5 作业车间调度问题的描述( j o b - s h o ps c h e d u i in gp r o bie m ，j s p ) j s p 调度问题是具有特殊工件特性和加工环境的典型和重要的调度问题，通 常是特殊的开环调度问题。它研究聆个工件在m 台机器上加工过程，q ；表示第f 个工件在第j 台机器上的操作，相应的操作时间岛为已知，事先给定各工件在各 机器上加工次序( 称为技术约束条件) ，要求确定与技术约束条件相容的各机器上 所有工件的加工次序，使加工性能指标达到最优。若各工件的技术约束条件相同， 一个j s p 调度就转化为较为简单的f l o w - s h o p 调度问题。 在典型的j s p 调度问题中，除技术约束条件之外，通常还假定以下条件： 各工件经过其准备时间后即可开始加工： 每一时刻每台机器只能加工一个工件，且每个工件只能被一台机器所加 工同时加工过程为不间断，整个加工过程中机器数均有效； 整个加工过程中每个工件不能在同一台机器上加工多次： 各工件必须按工艺路线以指定的次序在机器上加工； 不考虑工件加工优先权： 操作允许等待，即前一个操作未完成，则后面的操作需要等待： 所有机器处理的加工类型均不同： 除非特殊说明，工件的加工时间事先给定，且在整个加工过程中保持不 变： 除非特殊说明，工件加工时间内包含加工设置时间： 除非特殊说明，缓冲区容量为无限大 车间调度基本约束条件是进行调度理论研究的主要约束条件，能否有效地 解决j s p 基本约束条件满足问题是调度理论研究的关键。 j s p 调度的整数规划模型由b a k e r 提出，下面简单给出一个n m g c = 调度 问题的常用数学描述1 1 引。 1 0 m i nm a x m a x ( 1 1 ) s j & 一既+ m ( 1 一口i 破) 乏c 厶，i = 1 2 ，n ，h ，k = 1 ，2 ，m c 肚一c k + m ( 1 一再让) p 弘，f ，j = l 2 ，刀，七一l 2 ，m c k 苫0 , i = l 2 ，甩，七；1 , 2 ，m 五征；o 或l , i , j = 1 , 2 ，m ，k 2 1 ，2 ，肌 ( 1 2 ) 其中，式( 1 1 ) 表示目标函数，且p m a k e s p a n 。式( 1 2 ) 表示工艺约束条件 决定的各工件的各操作的先后加工顺序以及加工各个工件的各机器的先后顺序。 式中，符号气和p 捕分别为i i 件在机器k 上的完成时间和加工时问：m 是一个 足够大的正数；a m 。和分别为指示系数和指示变量，其意义为 阻若机器h 先于机器七加工工件f 口i h k2 i o ， 非上述情况0 3 ) 而衙；e 孽 箕查三工衔在机器七上加工 ( 1 4 ) 惭。1 0 ，非上述情况 u 一7 1 6 柔性车间调度问题( fie xibiej o b - s h o ps c h e d ui in gp r o bie m ， f j s p ) 在作业车间调度中，厅个工件在所设备上进行加工，工件f 都包含了嘞个顺序 化的工序 1 ，q 2 ，) 。工序d f ( 工件f 的第j 个工序) 所指定的设备为m f ， 作业时间为白，每个工序在加i 过程不能被打断，同一工件上的工序 1 ，q 2 ，；) 必须按顺序执行，每台设备同时只能处理一个工序。在柔性车 间调度中，每个工件f 包含了吃个顺序化的工序 l ，q 2 ，；) 。柔性车间调度 问题不在指定工序q 的处理设备，而是允许它从可行设备集4 中任选一台进行 处理。工序d 在设备七上的处理时间为t 驰 0 。柔性车间调度问题为每一个工序 选择一台设备m ( ) 呜，并为该工序确定开始加工时间。柔性车间调度问 题包含了两类决策：设备分配决策和工序调度决策。一旦为工序分配好了设备， f j s p 问题就转化成传统的j s p 问题了。柔性车间调度问题突破了资源唯一性限 制，减少了机器的约束，每道工序可由多个不同的机器完成，从而使车间调度问 题更加符合生产实践。f j s p 相对经典车间调度问题( j s p ) 而言提高了问题的复 杂性，所以与经典车间调度问题相比更加接近实际生产环境。 1 6 1 柔性车间调度问题的分类 柔性车间调度问题根据资源限制条件不同，可分为完全柔性车间调度( t o t a l f l e x i b l ej o b s h o ps c h e d u l i n gt - f j s p ) 问题和部分柔性车间调度( p a r t i a l f l e x i b l ej o bs h o ps c h e d u l i n gp - f j s p ) 问题，在完全柔性车间调度中，每一 个作业都可以选择任何一台机器来加工：而在部分柔性车间调度中，某些作业可 以选择在任何一台机器上进行加工，某些作业只能选择部分机器进行加工。实际 生产系统中的调度问题在机器选择方面具有柔性同时也可能具有限制，因此部分 柔性作业车间调度( p f j s p ) 问题比完全柔性车间调度( t f j s p ) 问题更具有普遍 意义，而后者的调度算法更为复杂。 1 6 2 柔性车间调度问题的求解方法 己有文献中研究j s p 问题的很多，却很少研究f j s p 。近年来对f j s p 问题的 研究日益增多，目前此类问题的求解方法归纳为分步法和集成法两类。分步法由 b r a n d i m a r t e b 4 j 首先提出，其基本思想是将复杂问题分解为几个子问题，以降低 其复杂性，在f i s p 调度中，将机器分配问题和调度问题分开考虑；集成法是将 机器分配问题和调度问题同时解决，如采用贪婪算法，采用模拟退火算法，采用 禁忌搜索法，采用局部搜索法都属此类。研究证明，两个工件以上的j s p 问题是 n p - h a r d 问题，f j s p 问题更是如此，它是典型的组合优化问题，优化极其复杂。 经典的车间调度问题导致加工计划与生产调度相脱节，不能应对实际的变 化，而柔性车问调度能充分发挥j s p 的灵活性，不仅能避免j s p 正常运行过程中 的阻塞和拥挤，而且在系统出现异常状态( 如设备故障) 时，仍能维持生产顺利进 行，因此对于它的研究具有重要的现实意义。 1 2 1 6 3 柔性车间调度问题的数学模型 假定一个加工系统有1 1 1 台机器和n 个待加工工件，每个工件包含一道或多道 工序，工件的工序顺序是预先确定的，每道工序可以在多台不同的机床上加工， 工序的加工时间随机床的性能不同而变化。调度目标是为每道工序选择最合适的 机器，以及确定每台机器上各工件工序的最佳加工顺序及开工时间，使所有工件 在系统中的流通时间最短。 下面是针对该调度模型的假设： ( 1 ) 每台机床一次只f i 勘n i - - 个工件。 ( 2 ) 工序一旦进行不能中断。 ( 3 ) 假定工件之间具备相同的优先级。 ( 4 ) 每个工件在固定时刻只能在一台机器上加工。 ( 5 ) 在零时刻，所有的工件都可被加工。 ( 6 ) 工序在可选择的若干机器上加工的时问已经确定。 描述f j s p 调度问题的变量 n 一工件数量；m - 机器数量；j i - 工件i 所包含的工序数；t 溉一工件i 的第j 道工序在机器k 上的加工时间；s 糯一工件i 的第j 道工序在机器k 上的开始 时间；e 独一工件i 的第j 道工序在机器k 上的完工时间；c 耻一所有工件仉 在机器k 上的完工时间；c 一一所有工件的最后完工时间。 f 1 r 鳓一 【0 r 1 瓢2 t o 工件f 的第f 道工序和工件e 的第g 道工序在同一台 机器足上执行，若工序可先于工序g ( 1 ) 其他 若工件f 的第f 道工序在机器尼上执行 其他 f j s p 调度问题的数学描述【1 5 】 目标函数伎所有工件在系统中的流通时间最短； ( 2 ) c 。群k m a x 础魄m a 刀x ，( c 耻) ) ( 3 ) 约束条件： ( 1 ) 顺序约束工艺要求的同一工件相邻工序间的加工顺序。 e 独一e f ( 卜1 ) ，丁班其中l j a j 为彳的“a 强截集 ，相应地称彳 为彳的“a 弱截集 。 2 1 a 截集的特征函数为：砀。g ，。 竺三苎；二三 它表示论域x 中的元素，凡对模糊集a 的隶属度不小于a 的就属于a 工，否则不 属于a 工，因此彳 是一个普通