考虑后续工序批综合调度研究论文.pdf

国内图书分类号：t p 3 9 1 7 3 工学硕士学位论文 考虑后续工序的批综合调度研究 硕士研究生： 导师： 申请学位级别： 学科、专业： 所在单位： 答辩日期： 授予学位单位： 刘长海 谢志强 工学硕士 计算机软件与理论 计算机科学与技术学院 2 0 12 年3 月 哈尔滨理工大学 c l a s s i f i e di n d e x ：t p 3 91 7 3 d i s s e r t a t i o nf o rt h em a s t e rd e g r e ei ne n g i n e e r i n g r e s e a r c ho nb a t c hi n t e g r a t e ds c h e d u l i n g b a s e do nc o n s i d e r i n gs u c c e s s o r c a n d i d a t e ： p r o c e d u r e s s u p e r v i s o r ： a c a d e m i cd e g r e ea p p l i e df o r ： s p e c i a l t y ： d a t eo fo r a le x a m i n a t i o n ： u n i v e r s i t y ： l i uc h a n g h a i x i ez h i q i a n g m a s t e ro f e n g i n e e r i n g c o m p u t e rs o f t w a r ea n dt h e o r y m a r c h ，2 0 1 2 h a r b i nu n i v e r s i t yo fs c i e n c ea n d t e c h n o l o g y 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文考虑后续工序的批综合调度 研究，是本人在导师指导下，于哈尔滨理工大学攻读硕士学位期间独立进行 研究工作所取得的成果。据本人所知，论文中除已注明的部分外不包含他人已 发表或撰写过的研究成果。对本文研究工作做出贡献的个人和集体，均己在文 中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签名：五b ：= 越日期：2 , o r 2 年弓月闩 哈尔滨理工大学硕士学位论文使用授权书 考虑后续工序的批综合调度研究系本人在哈尔滨理工大学攻读硕士学 位期间在导师指导下完成的硕士学位论文。本论文的研究成果归哈尔滨理工大 学所有，本论文的研究内容不得以其它单位的名义发表。本人完全了解哈尔滨 理工大学关于保存、使用学位论文的规定，同意学校保留并向有关部门提交论 文和电子版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学可以采用影 印、缩印或其他复制手段保存论文，可以公布论文的全部或部分内容。 本学位论文属于 保密u ，在年解密后适用授权书。 不保密团。 ( 请在以上相应方框内打) 作者签名：玉l 煳 同期：少f 二年弓月，上同 刷磁各淞否l m 产 钟 考虑后续工序的批综合调度研究 摘要 综合调度是关注工序间存在约束关系的产品制造过程中，考虑加工和装配 之间的并行关系的调度，虽然综合调度问题的研究取得了一些成果，但是有关 综合调度中的批处理问题的研究，即批综合调度问题的研究比较少。因此对批 综合调度问题的研究具有非常重要的理论价值和现实意义。 本文在综合分析了国内外调度问题研究的基础上，针对现有的批综合调度 算法忽略了后续工序对批处理结果的制约，可能因为批处理工序的后续工序滞 后的时间过长而影响批处理效果的问题，提出了考虑后续工序且批处理数为2 的批综合调度算法。为了使批处理的调度效果更合理，充分利用加工设备的可 并行性，综合考虑了先行工序和后续工序对批处理结果的影晌，采用批处理判 断策略、提前最大化策略和并行最大化策略进行工序调度，实现了考虑后续工 序且批处理数为2 的批综合调度算法。 现有的批综合调度算法未研究加工时l a 不相同的工序的批处理问题，而且 也没有考虑后续工序中存在的组批工序时的情况，针对这些问题，本文又提出 了2 个加工时间不同工序的组批嵌套批综合调度算法。通过采用余差比较策 略、组批前移最大化策略、嵌套优化策略和前续工序优先策略对工序进行调 度，通过实例验证分析，此算法有良好的复杂度，可得到较优的调度结果。 针对批处理时只关注当前预批处理工序与可批处理工序批处理的效果，忽 略了可批处理工序可能与其它在批处理设备上的二【：序批处理时结果更优的问 题，提出了批处理时二次优化的批综合调度算法，通过比较批处理工序的批处 理可提前时间的大d , n 断是否必须选择当前预批处理工序进行批处理，最后通 过实例分析验证了该算法的可行性。 关键词后续工序：批处理判断策略；嵌套优化策略；综合调度：批综合调度 哈尔滨理工人学t 学硕j ：学位论义 r e s e a r c ho nb a t c hi n t e g r a t e ds c h e d u l i n gb a s e do n c o n s i d e r i n gs u c c e s s o r p r o c e d u r e s a b s t r a c t i n t e g r a t e ds c h e d u l i n g i sas c h e d u l i n gw h i c hc o n s i d e r sp a r a l l e lr e l a t i o no f p r o c e s sa n da s s e m b l yi n t h ep r o c e s so fp r o d u c t sm a n u f a c t u r i n gw i t hc o n s t r a i n t r e l a t i o ne x i s t e da m o n gp r o c e d u r e s a l t h o u g hr e s e a r c h e so fi n t e g r a t e ds c h e d u l i n g h a v em a d es o m ea c h i e v e m e n t s ，r e s e a r c h e so fb a t c hp r o b l e m si nt h ei n t e g r a t e d s c h e d u l i n g ，n a m e l yb a t c hi n t e g r a t e ds c h e d u l i n g h a sb e e nr a r e l ys t u d i e d t h u s r e s e a r c h e so fb a t c hi n t e g r a t e ds c h e d u l i n gh a v eb o t ht h e o r yv a l u ea n dp r a c t i c a l s i g n i f i c a n c e a i m i n g a tt h e p r o b l e m t h a tt h o s e e x i s t i n g b a t c h i n t e g r a t e ds c h e d u l i n g a l g o r i t h m si g n o r er e s t r i c t i o n sw h i c hs u c c e s s o rp r o c e d u r e sh a so nb a t c hp r o c e s s i n g r e s u l t s ，w h i c hp r o b a b l ym a ya f f e c tb a t c hp r o c e s s i n gr e s u l td u et ol a gt i m eo f s u c c e s s o rp r o c e d u r ei st o o l o n g t h ep a p e rp u tf o r w a r di n t e g r a t e ds c h e d u l i n g a l g o r i t h mw h i c hc o n s i d e r ss u c c e s s o rp r o c e d u r e sa n dw i t ht w ob a t c h e so nt h eb a s i so f a n a l y z i n gs c h e d u l i n gp r o b l e m sa t h o m ea n da b r o a d i no r d e rt om a k eb a t c h s c h e d u l i n gr e s u l t s m o r er e a s o n a b l e ，m a k ef u llu s eo ft h e p a r a l l e l i z a b i l i t y o f e q u i p m e n t s ，a n dc o n s i d e rt h e a f f e c to fp r e d e c e s s o r p r o c e d u r e a n ds u c c e s s o r p r o c e d u r eo nb a t c hp r o c e s s i n gr e s u l t st o g e t h e r ，t h ep a p e ra d o p t sb a t c hju d g m e n t s s t r a t e g y , m a x i m i z es t r a t e g ya h e a d ，a n dp a r a l l e lm a x i m i z a t i o ns t r a t e g yt os c h e d u l e p r o c e d u r e s ，a n dr e a l i z et h eb a t c hi n t e g r a t e ds c h e d u l i n ga l g o r i t h mw h i c hc o n s i d e r s u c c e s s o rp r o c e d u r e sa n dw i t ht w ob a t c h e s t h o s ee x i s t i n gb a t c h s c h e d u l i n ga l g o r i t h m s n o t o n l yd o n o ts t u d yb a t c h p r o b l e m so fp r o c e d u r e sw i t hd i f f e r e n tp r o c e s s i n gt i m e ，b u ta l s od on o tt a k ea c c o u n t o ft h ee x i s t e n c eo fb a t c hp r o c e d u r e so fs u c c e s s o rp r o c e d u r e s ，a i m i n ga tt h e s e p r o b l e m s ，t h i sp a p e rp r o p o s e dn e s t e db a t c hi n t e g r a t e ds c h e d u l i n ga l g o r i t h mo ft w o p r o c e d u r e sw i t hd i f f e r e n tp r o c e s s i n gt i m e a d p o t i n gr e s i d u a lc o m p a r i s o ns t r a t e g y , g r o u po fm a x i m i z i n gt h e f o r w a r d s t r a t e g y , n e s t e do p t i m i z a t i o ns t r a t e g y a n d p r e d e c e s s o rp r o c e d u r e so fp r i o r i t ys t r a t e g y t os c h e d u l et h ep r o c e d u r e s t h r o u g h e x a m p l eo fv a l i d a t e sa n da n a l y s i s ，t h ep r o p o s e da l g o r i t h mh a sg o o dc o m p l e x i t ya n d c a ng e tb e t t e rs c h e d u l i n gr e s u l t s a i m i n ga t t h ep r o b l e mt h a td u r i n gt h ep r o c e s so fb a t c hs c h e d u l i n g ，o n l yp r e b a t c hs c h e d u l i n gp r o c e d u r e sa n dc u r r e n tb a t c hs c h e d u l i n gp r o c e d u r eb e i n ga t t a c h e d a t t e n t i o nt o ，w h i l ec u r r e n tb a t c hp r o c e d u r e sc a n b eb a t c hp r o c e s s e dw i t hp r o c e d u r e s o no t h e rb a t c he q u i p m e n t sh a sb e e nn e g l e c t e d ，t h ep a p e rp r o p o s e das e c o n db a t c ho f a p p r o v e di n t e g r a t e ds c h e d u l i n go p t i m i z a t i o na l g o r i t h m t h r o u g hc o m p a r i s o no f t h e d e g r e e so fb a t c hp r o c e d u r e sc a n b ea h e a do ft i m et od e c i d ew h e t h e ri ti sm u s tc h o o s e t h ec u r r e n tb a t c hp r o c e d u r e s ，f i n a l l y a ne x a m p l ei si n v e s t i g a t e dt ov e r i f yt h e f e a s i b i l i t yo ft h ea l g o r i t h m k e y w o r d ss u c c e s s o rp r o c e d u r e s ，b a t c hj u d g m e n t ss t r a t e g y ，n e s t e do p t i m i z a t i o n s t r a t e g y ，i n t e g r a t e ds c h e d u l i n g ，b a t c hi n t e g r a t e ds c h e d u l i n g 哈尔滨理工人学工学硕士学位论文 目录 摘要i a b s t r a c t i i 第1 章绪论1 1 1 课题研究的背景1 1 2 国内外调度问题研究现状与分析2 1 3 课题来源及课题的研究意义5 1 3 1 课题来源5 1 3 2 课题的研究意义5 1 4 论文的主要研究内容和组织结构6 第2 章批综合调度问题的概述8 2 1 批综合调度问题的背景8 2 2 批综合调度问题的描述8 2 3 批综合调度问题的研究现状9 2 4 批综合调度中存在的问题和发展趋势的分析1 0 2 5 本章小结1 l 第3 章考虑后续工序且时间相同工序的批综合调度算法1 2 3 1 引言12 3 2 问题描述1 2 3 3 问题分析1 3 3 3 1 工序在普通设备上加工1 3 3 3 2 工序在批处理设备上加工一1 4 3 4 算法设计1 6 3 4 1 批处理判断策略1 6 3 4 2 提前最大化策略18 3 4 3 并行最大化策略19 3 5 算法设计及实现步骤19 3 6 算法复杂度分析2 3 3 7 调度实例2 4 3 8 本章小结2 9 哈尔滨理t 人学工学硕1 ：学位论文 第4 章时间不同工序的组批嵌套批综合调度算法一3 1 4 1 引言3 l 4 2 问题描述3 l 4 3 问题分析3 2 4 3 1 工序在普通设备上加工3 2 4 3 2 工序在多功能并行处理设备上加工3 2 4 4 策略分析与设计3 6 4 4 1 余差比较策略的分析与设计一3 6 4 4 2 组批前移最大化策略的分析与设计一3 7 4 4 3 嵌套优化策略的分析与设计3 8 4 4 4 前续工序优先策略的分析与设计3 8 4 5 算法设计3 9 4 6 算法复杂度分析4 3 4 7 调度实例4 4 4 8 本章小结4 7 第5 章批处理日, - i - 次优化的批综合调度算法一4 9 5 1 引言4 9 5 2 问题分析与方案设计4 9 5 - 3 算法设计5 0 5 4 实例分析5 3 5 5 本章小结5 5 结论5 6 参考文献5 7 攻读硕士学位期问所发表的学术论文6 1 致谢6 2 哈尔滨理t 人学t 学烦f j 学位论义 1 1 课题研究的背景 第1 章绪论 随着经济全球化的发展和企业竞争意识的不断增强，特别是多品种、小批 量的生产模式所占比例同益增大，如何降低产品的生产成本、提高产品的生产 效率和缩短产品的生产周期成了影响企业生存发展重要因素，因此，产品制造 的加工和装配的调度逐渐成为了企业关注的热点。加工和装配任务调度算法为 研究设计生产自动化和计算机虚拟制造提供了基础，是当前调度领域重点研究 的问题。对调度问题的研究，即可以促进调度问题的研究和相关学科的发展， 也可以指导企业合理安排产品的加工和装配计划，从而提高产品加工过程的自 动化率，优化产品的调度效果，降低产品的成本，提高产品的效率，缩短产品 的生产周期，实现利润最大化，不断提高企业的竞争力。 针对多品种、小批量产品生产过程中的加工和装配的调度问题，可以通过 两方面解决，一个是优化加工调度，一个是优化装配调度。前一方面主要解决 产品工艺图中工序次序的加工问题，即每个工件由一些相互之i 白j 没有约束关系 的工序加工而成，是一个不存在装配过程的纯加工的问题，属于常规的简单加 工问题：后一方面主要解决产品装配工序次序图中产品装配的问题，即工件之 间相互约束的装配的问题，这是一种纯装配调度问题。 多品种、小批量简单产品的加工调度优化问题可被归结为经过m 种设备 加工的个工艺流程不尽相同的工序的非流水型作业系统的排序问题，它是需 要b a k e r 于1 9 7 4 年提出调度问题的进一步推广1 。这个问题所讨论的加工是指 工件之间无约束加工的问题，已经被证明是n p c 问题尘。这个问题只涉及了装 配的问题，不存在工件装配以后产生的工件继续加工的问题。“，例如脚踏车的 生产装配。 但是，在生产过程中并不是所以的工件的处理过程都是纯加工或纯装配的 情况，某个工件装配后产生的工件继续加工的情况也是存在的。例如，在黄金 勘探中常用到的钻井装置的地下钻探部分，由于转轴和钻头的材质不同，所以 需要分别对转轴和钻头的毛坯进行去料、下料和铸型等加工的处理，然后将处 理后的毛坯( 转轴和钻头) 焊接( 装配) 在一起，再将焊接后的工件进行统一 中心穿孔、开槽、抛光等加工处理，最后完成进行整个装置的组合。 哈尔滨理工人学_ 学硕士学位论文 由于以往的调度研究多针对的是纯加工或纯装配的调度，有一定的局限 性，在实际应用中解决的问题不全面，有必要进一步拓展其应用领域的范围。 因此，对加工与装配并存的综合调度( 复杂产品) 问题的研究逐渐地引起了人 们的注意。 综合调度问题是组成产品的工件之间存在约束关系且需综合考虑加工调度 和装配调度的次序的调度问题1 。综合调度研究中的工序特点：工件单独加 工、工件与工件装配以后形成新工件的再加工、工件与加工后的新工件之i 自j 的 加工，形成了工序之间有约束的加工和装配，最终完成产品的制造。综合调度 中产品的制造次序图中的工序包含了加工工序和装配工序，即将加工工序与装 配工序视为一种工序进行统一调度。 国内外对简单产品调度的研究，即只加工和只装配产品的工序调度的研究 比较多，而对综合调度研究的比较少。随着社会的不断发展，人们对产品的需 求越来越多样化，促使产品趋向种类更加齐全，过去大批量粗犷制造的生产模 式逐渐被摒弃，多品种小批量的产品越来越受到人们的青睐。针对工件之间有 约束加工和装配的产品的综合调度，如果刻意将加工调度和装配调度分开考 虑，这必然割裂了产品生产过程中的内在联系，忽视加工与装配之间内在的并 行规律，进而延长了产品的生产周期，影响了制造效率，减少了生产效益。所 以工件之问有约束关系的综合调度问题的研究引起了学者们的关注。对综合调 度问题的研究不仅具有理论意义，而且还具有广泛的实用价值。 1 2 国内外调度问题研究现状与分析 由于生产调度问题的复杂性和实际生产过程中对调度优化的需求，推动了 调度问题的理论研究和发展。调度理论研究的正式丌始始于上世纪五十年代， 1 9 5 4 年，以j o h n s o n 针对2 台机床的f l o ws h o p 型调度提出了解决n 2 c m 默和 部分特殊的n 3 f c m 默问题的有效的优化算法为标志。人们为了生产过程中的 产品调度问题就一直在不断地进行研究，自此之后，学术界对调度问题进行了 大量的探讨研究，取得丰硕的理论成果的同时也促进了生产的进步。但同时， 学者们发现，由于在进行理论研究时，对实际的调度情况给定了许多限制条 件，很难用于生产实践中b ；同时，随着由于研究算法有效性和问题难度的时 间复杂度理论的提出m 1 ，大部分调度问题被证明是n p 完全问题盯3 ，并不存在 明确的多项式求解方法，因此开始寻找有效的近似方法来解决它们。经过学者 们的研究，许多方法被提出来了：例如，专家系统、遗传算法、人工神经网 哈尔滨理t 人学t 学硕i j 学位论义 络、禁忌搜索算法、蚁群系统、文化进化算法和基于设备和路径的综合调度算 法等等m 引。 1 运筹学方法运筹学方法在生产调度研究领域得到了广泛的应用，将调 度问题转化为数学规划理论描述，将复杂的生产调度问题简化为数学模型。采 用混合规划、启发式规则和线性规划等数学规划方法来处理调度研究中的优化 问题。该方法着眼于全局生产任务的调度安排，保证了产品的交货期。但是， 由于实际生产过程中，制约调度安排的因素多，不确定性大，导致了调度建模 不稳定，计算复杂。因此，对于这种生产调度的n p 问题，通过单一的数学模 型解决不了生产过程中的所有因素，更不能反应特定调度领域的自然结构n 0 1 。 2 基于离散系统的方法由于生产制造系统是一类离散系统，因此，可以 采用探讨诸如排队论( q u e u i n gt h e o r y ) 、g a r i 网络等离散系统的解析模型和 方法去研究调度问题。g a r i 方法是一种用于描述和分析生产管理系统的方 法。排队论，即随机服务系统理论，是研究系统聚散现象和随机服务系统工作 过程的数学理论和方法。排队论在调度中是一种随机优化方法，将作业视为客 户，将设备视为服务台，根据作业不同的属性，将每个作业的加工时间、加工 路径等属性描述成一个随机分布。从离散系统角度采用排队论描述柔性制造系 统，不能全面覆盖系统中的各个要素，得不到比较具体的输出。g a r i 网络 方法是一种描述企业决策过程的建模方法，它定义了资源或系统构件，活动构 件、状态构件，分别对应阐述了触发执行、i 0 转换和变量与结果组成的系统 状念。在描述上，诸如生产成本、加工时问、异常处理等涉及具体操作属性并 没有在模型中体现。 3 人工智能方法利用人工智能理论与技术解决生产调度问题的方法统称 为人工智能方法u 剁。在调度研究中采用人工智能技术始于八十年代，专家系统 和基于智能搜索的系统发展迅速，它们在决策中采用定性和定量知识，通过模 拟、搜索等手段产生一个较为符合实际生产调度过程的调度策略，可以在整个 生产调度信息的基础上选择最好的决策，具有一定的智能性。但是，它解决问 题的范围较小，不全面，同时在认知的建模以及知识和经验的搜集方面是很困 难的3 | 。 4 蚁群算法乱协1 蚁群算法是由意大利学者d o r i g o 等人提出来的，他们受 蚁群行为启发，利用旅行商问题与蚂蚁寻找食物的过程具有相似性，通过模拟 蚂蚁搜索食物过程中的信息互通，最终发现了蚂蚁到食物的路线最短，解决了 旅行商问题，这是一种求解组合优化问题的全新方法。蚁群算法能较快的找到 较优解，鲁棒性强。算法采用了正反馈的原理，不易陷入局部最优解，提高了 哈尔滨理t 大学工学硕十学位论文 解决问题的效率。这个算法也存在着一些不足，搜索时i 自j 较长，收敛速度慢， 算法复杂，而且当搜索进行到一定程度后，所有的个体得到的解是一样的，停 止了进一步搜索，限制了解空间的范围，不能更好地发现较优的解。 5 分派规则方法对生产计划中的任务进行调度的传统方法是使用调度规 则，因为调度规则易于实现、便于理解、算法简单等，有很强的实用价值，受 到学者们的广泛关注，许多规则被用于调度领域，并且有新的调度规则不断 被提出。分派规则最早由s m i t h 等人提出的，p a n w a l k a r 等人将分派规则归为 三类：第一类，同作业信息相关的优先级规则：第二类，优先级规则的组合： 第三类，切换以及加权规则。优先分派规则的近似优化规则。随着计算机运算 速度的不断提高和大型高端机的发展，人们通过寻找新的近似调度规则，实现 以小的成本换取利益的最大化。针对不同的实际问题，分析其属性，选择最佳 分派规则。从当自，j 的分派规则看，s p t 实现了算短任务的平均流程时问，e d d 可以优化最大延期相关的目标。但是，研究表明，分派规则不是一个全局最优 的调度规则，它的效果的发挥取决于生产条件和特殊性能的要求。 6 遗传算法遗传算法( g a ) 是美国m i c h i g a n 大学的h o l l a n d 对基于自然 遗传进化的提出的一种并行搜索机制，g a 是基于自然进化、自然选择、物竟 天择思想的随机搜索方法。遗传算法的搜索信息具有多点性和并行性的特点， 通过选择、交叉和变异等操作对上一代群体进行运算产生新一代群体，然后接 着对新一代进行搜索。这些运算都是以一定的概率进行，增加了其搜索范围的 广泛性，在特定情况下可以得到最优解。通过群体间的相互作用，可以保持所 搜索的数据，遗传算法解决f l o w s h o p 和j o b s h o p 可以得到较理想的静态调 度。遗传算法也存在一些不足，例如速度较慢n k 1 ，收敛过早以及与其他算法 进行组合优化等问题。 7 加工工艺树的方法根据复杂产品加工、装配工艺图为树状结构，将工 艺图称为工艺树3 。通过对工艺树结构特点的观察，人们从不同的角度对产品 调度问题进行研究。根据树状结构可以视为术端分支的繁衍的特点将工艺图进 行分解，把工序分成相关工序和独立工序分别进行调度：根据工艺树分层的特 点，对每层设置优先级，从纵或横的方向来对产品工序进行调度；根据工艺图 上工序a n - r _ 所需设备不同的特点，对存在相同设备、瓶颈设备、批处理设备等 不同情况下的工序综合调度进行分析瞳o 2 纠。目前主要的方法有拟关键路径法、 可动态工序生成具有优先级法、动态关键路径法、基于关键设备工序的紧凑算 法、基于调度长路径法、存在设备无关延迟约束的调度算法、非紧密衔接工序 动态的综合调度。叫”3 等。由于根据工艺树可以整体计划安排生产，能够实现加 哈尔滨埋t 人学t 学坝l j 学位论义 工任务与装配任务充分并行进行的综合调度算法，使得产品的生产周期缩短， 正越来越受到学者们的关注，引起了广泛的研究。 产品生产调度大部分问题是n p 困难组合问题，具有多项式的最优算法是 不存在的，学者们对该问题进行了几十年的研究，但是仍然没有得到一套系统 的理论体系。虽然经典的调度问题优化算法的研究取得了丰硕的成果，但是该 调度问题与实际的生产调度差距很大，有很大实际的因素影响这调度决策，例 如，设备数量、工序特点、生产环境、经营管理等，实际生产非常复杂，经典 的生产调度问题解决不了这些问题。诸如启发式方法、运筹方法、分派规则等 算法能在一定条件下得到较为满意的调度结果，但是不具有普遍性，对调度解 的次优性很难评估。如何更好的理论联系实际，探索更优的调度算法，提高解 的此优性，降低计算复杂度，促进调度理论的研究，将成为近期活跃的研究领 域。 1 3 课题来源及课题的研究意义 1 3 1 课题来源 国家自然科学基金项目：单件复杂产品加工和装配过程综合调度优化算法 ( 项目编号：6 0 8 7 3 0 1 9 ) 。黑龙江省自然科学基金项目：树状结构产品柔性综 合调度算法的研究与实现( 项目编号：f 2 0 1 1 0 1 ) 、哈尔滨市优秀学科带头人项 目：复杂产品加工和装配综合调度软件实现( n o 2 0 1 0 r f x x g 0 5 4 ) 等项目的 支持。 1 3 2 课题的研究意义 调度( s c h e d u l i n g ) 就是在有限的一段时间内，为完成某项任务而对相应 资源进行分配。调度问题涉及的应用领域非常广泛，如在安排生产、柔性制 造、供电列车编组、作战保障、卫星通信、协同作战及情报传输等。准确选择 适合的调度理论和算法，采用高效的调度方案进行任务安排，能够提高工作效 率，带来利益的最大化。调度问题是一个十分复杂的问题，不同的实际调度问 题的调度方案不同，实际生产环境的不同而调度方案也会不同。调度问题是 n p 困难组合问题。 实际的生产调度问题主要牵涉到加工与装配任务的问题，如何对加工和装 哈尔滨理t 人学t 学颁 ：学位论文 配过程进行优化控制是当前生产制造领域和生产自动化应用领域的热点研究问 题。综合调度问题是综合考虑了加工和装配调度在产品工件f 自j 有约束关系的产 品制造过程中的次序，将加工工序和装配工序进行统一进行调度的问题，这是 一类更复杂的调度问题。批综合调度作为综合调度问题中研究批处理问题的调 度，与现有的批调度问题主要解决组成产品的工件之间无约束关系的批调度不 同，它主要研究的是综合调度中工件问有约束关系的批调度问题，因此有必要 进行批综合调度的研究。随着综合调度问题的研究越来越受到人们的关注，取 得了一些研究成果，但由于批综合调度问题的复杂性，目前在这一方面研究比 较少。加大对批综合调度问题的研究，提高工序加工的并行性，保证同一设备 上工序加工的紧密衔接，可以减少工序的等待加工时间，提高设备的利用率， 充分发挥设备的性能，保持物流的一贯性，不断提高生产效率，节约生产成 本，增强产品竞争力，实现企业利润的最大化。因此，研究此类调度问题具有 重要的理论价值和现实意义。 1 4 论文的主要研究内容和组织结构 对于生产调度中的批处理问题，学者们已经有了比较深入的研究，取得了 不少的理论成果，这些研究多数考虑的是工件之间无约束的情况。无约束关系 工件的批调度算法是将产品的加工过程分解无约束工件，先进行工件的i h - r 过 程，再对加工之后的工件进行装配，不进行全局性的统一批处理调度，这种调 度方式不适合多品种小批量的产品。目前，综合考虑产品内在的加工与装配的 可并行关系的批综合调度算法研究的比较少。本文重点考虑了批处理时后续工 序对批处理调度结果的影响，从加工时i 、自j 相同工序的批处理、工序批处理时存 在嵌套和二次优化调度顺序三个方面对批综合调度进行了研究，针对不同的方 面给出了有效地解决产品加工和装配的批综合调度的算法，通过实例分析和验 证，表明算法在求解批综合调度时是较为有效的。本文的研究内容和组织结构 如下： 第1 章介绍了综合调度问题的研究背景和发展过程，对当前研究情况和发 展趋势进行简要分析，同时阐述了本课题的研究意义。 第2 章对批综合调度问题研究的意义和当前批调度的一些方法进行介绍， 并对该问题的研究进行了展望。 第3 章对现有批综合调度问题进行分析，考虑了后续工序对批处理的影 响，据此提出了相应的调度算法，采取了方案策略进行优化调度。 哈尔滨理t 人学t 学颂i j 学位论义 第4 章是针对前一章算法未考虑加工时间不同工序的批处理和后续工序中 存在组批工序的情况，通过提出余差比较策略和嵌套优化策略，将复杂问题向 简单化处理，拓宽了现有批综合调度研究解决问题的范围。 第5 章在前两章研究的基础上，对批处理判断的调度顺序进行了再次调 整，提出了二次优化策略完善了自可两章的算法，并通过调度实例进行分析比 较。 结论的部分对全文的工作进行了总结，并对批综合调度问题的进一步研究 做出了展望。 哈尔滨理t 火学_ 学硕十学位论文 第2 章批综合调度问题的概述 2 1 批综合调度问题的背景 经过学者们对调度理论的不断研究，越来越多的研究成果应用于实践当 中，而调度中的批处理加工作为一种重要的生产方式越来越受到人们的关注。 由于生产过程中采用批调度时具有设备投资小、产品加工快、产品样式多、生 产批量小、符合个性化等特点，批处理的生产模式广泛的应用于多个行业。对 产品生产过程进行有效合理的批调度可以减少人力投入、降低成本、提高设备 利用率、缩短产品生产周期，增强了企业的竞争力。 随着社会的进步，人们对个性化的产品的需求不断增加。个性化产品的需 求，使得同一种类的不同个性化产品工序需有不同的加工顺序以提高生产效 率。对于这种小批量多品种的个性化产品，以往的采取将加工工序与装配工序 分别调度处理的加工模式，忽视了产品内在的加工工序与装配工序之间的可并 行处理的关系，延迟了产品的加工时间，影响了调度效果。因此，将加工工序 和装配工序一同处理的综合调度应运而生。批综合调度作为一种存在可同时 加工多个工序的设备( 批处理设备、多功能并行处理设备) 的综合调度，结合批 调度中批处理设备所具有的特点，有必要研究一下批综合调度的问题。 2 2 批综合调度问题的描述 为了提高生产效率，减少设备投资成本，越来越多的批处理设备被运用到 现代化的生产过程中。如果在生产过程中忽视批处理设备的可批量加工工件的 特点，将其当做一般的加工设备使用，显然是一种资源浪费：如果过分关注其 可批量加工工件的特点，不合理一味将工件等待批处理加工，势必延迟了产品 的完工时间。因此有必要考虑一下在将产品的加工与装配同时进行的综合调度 问题中的批处理问题，即我们讨论的批综合调度问题。 批综合调度问题可表述为：设有加工设备m 台，加工工序门个，工序的顺序 按待加工产品的树状工艺图结构预先确定；每个工序只在一台设备上加工或装 配，加工或装配均称为加工；普通设备一次只能一个工序；批处理设备可以同 时加工不止一个工序；每个工序只有其工艺紧前工序加工完成之后才能开始加 工；每个工序只有其设备紧前工序加工完成之后爿能丌始加工。 哈尔滨理丁人学t 学硕l j 学位论文 2 3 批综合调度问题的研究现状 产品的批调度问题，以往也称同时批处理调度。国外对批处理研究起步较 早，加工分批的方式大致分两类。一类是并行批调度。“卜 ! ，这个分批方式多见 于二极管的生产力n - r _ 过程中，g i m p l e 较早的研究了这类问题。州，此时工件的批 处理加工时间等于这批工件中工件加工时间最长的时间；一类是串行批调度， 这类批调度的加工时问等于这批工件的所有加工时间的总和，文献 3 4 】等对这 类问题进行了深入的论述。 在批调度的调度策略方面，多数分两步进行，先将工序分到相关设备，然 后再在相关设备上对工序进行调度，确定工序的调度时间。 文献3 5 1 从整个；o n t _ 调度过程出发，将其分成几个阶段，对多阶段的批调 度问题进行了论述。通过采用时间轴的方式将产品的；o n - r _ 和设备的分配分别表 示为x 轴和y 轴，然后通过对这个二维时间表的分析，建立多阶段的批调度模 型。 文献 3 6 1 在文献【3 5 的基础上，通过分析二维时问表，又增加了对传输时 间和相关建立时问，提高了这个模型的求解速度，完善了这个模型表述内容的 全面性。 u z s o y 首次对工件尺寸不同的单机批调度问题进行了研究，证明这类问题 是n p 完备的，并设计了启发式算法。盯1 ；d u p o n t 针对启发式算法的制造跨度采用 分枝定界法，利用穷举方法进行了优化，在理论上取得了较好的效果，但当遇 到大规模问题时，计算效率不高，时间复杂度大。讲1 。 由于批调度在工业化生产中得到了广泛应用，国内也越来越重视对批调度 的研究。 文献f 4 0 】针对批处理调度问题提出了一种不同以往批进批出的新型批调度 问题，即连续性批调度问题。这个问题源于加热炉对管坯的加热过程，批的加 工时间不单独由批的大小和批中工件加工时间的大小决定，还考虑到了机器的 容量的因素。通过研究分析，给出了一个动态规划的算法。 文献 4 1 在模糊制造系统中引入了差异工件的单机批调度问题，建立了制 造跨度模型，这个模型主要是基于批间隔时间和批；o n t 时间。同时文献( 模糊 制造系统) 给出了一种混合算法，并设计了统一的编码，提高了算法的效率。 文献 4 2 研究了带有“扩充链”优先约束的工件的分批排序的问题，将该 问题转化为对非二部图赋权匹配的问题，以最大完工时间为目标函数，通过组 哈尔滨理工大学t 学硕：f ：学位论文 = = = = = = = ! = = = = = = ! = = = = = = = = = = = = = i i i = = = = = = = ! = = ! = = = = = = = = = = = 合优化，相应的给出了个多项式算法。这种扩充链上既有优先工序但无约束 工序，这种优先工序与无约束工序之间有时间的先后关系，无实质的约束关 系。 文献 4 3 】研究了单台批处理机上的在线排序问题，工件的加工时间只有当 工件到达之后才能知道，并证明了m h b 算法的竞争比在机器容量无穷大的条 件下大于等于2 。这种批调度的工件之间是单独成批，相互之间无约束关系。 上述调度算法中的纯加工或纯装配的批调度是传统的批调度模式，影响当 前生产形势下的小批量多品种产品的加工效率，不如批综合调度的处理效果 好。 文献【2 2 】首次提出了综合调度中的批处理问题的算法，即批综合调度问题 的算法。批综合调度是一种较复杂的综合调度问题，这种批调度的工序之间具 有实质性的约束关系，综合考虑了加工与装配的可并行的内在关系，通过采用 l 临时等待策略判断当满足预批处理被等待工序的先行工序加工时间小于当前预 批处理等待工序的加工时间的关系，这两个工序便进行批处理。但该文献未从 批处理工序的全局考虑，忽略了等待工