（机械工程专业论文）作业车间批量生产调度研究及仿真.pdf

我 研 我 关于论文使用授权的说明 本人完全了解北京_ 丁业大学有关保留、使用学位论文的规定，即：学校有权保留送交 论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容，可以采用影 印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 躲盏鼬翩虢盏毪期： 仙io 6 s 摘要 摘要 随着市场竞争越来越激烈，企业必须能够充分利用有限的资源，提高对市场 变化的反应能力和生产效率，车间生产调度问题就变得更加重要。尤其是考虑到 大部分产品是批量生产的实际情况，必须寻找适应这一要求的解决方案，包括如 何合理分批以及如何进行生产调度。因此，车间批量生产调度的研究不仅具有重 要的理论意义而且更具有长远的实际意义。 本文研究了基于作业车间的批量生产调度与仿真问题，基于等分批的思想对 大批量生产的工件进行科学的分批，把分好的子批当作一个新的工件，重新进行 工件编号、计算加工时间、读取生产工人和设备，引入调度算法进行调度。最后， 通过多种标准调度算例验证了分批调度的可行性和优越性。 运用o p e n g l 这个强大的开放式图形软件包，借助v c 作为开发平台，绘制 了生产车间的三维图形，能够对车间的生产场景和加工设备初始化，以适应多种 生产状况；并且实现了整个生产调度过程的动画仿真，能够非常方便观测到调度 过程中可能出现的各种意外，从而降低生产成本，提高生产效率。 软件实现运用了多种工具，通过m a t c o m 编译器将m a t l a b 下编写的优化算 法集成到v c + + 6 0 中，以s q l s e r v e r2 0 0 0 作为车间调度系统的数据库，开发具 有实用性的车间生产调度软件。经过实例调度实验，结果证明系统可行，达到了 对工件分批、调度以及动画仿真的效果。 关键词车间调度； 批量生产； o p e n g l ； 动画仿真 a b s t r a c t a bs t r a c t w i t ht h ei n c r e a s i n g l yf i e r c em a r k e tc o m p e t i t i o n ，e n t e r p r i s e sm u s tb ea b l et o m a k ef u l lu s eo fl i m i t e dr e s o u r c e st oi m p r o v er e a c t i o nc a p a c i t yt om a r k e tc h a n g e sa n d p r o d u c t i o ne f f i c i e n c y , s op l a n tp r o d u c t i o ns c h e d u l i n gp r o b l e mb e c o m e se v e nm o r e i m p o r t a n t e s p e c i a l l yc o n s i d e r i n gt h em a s sp r o d u c t i o no f m o s tp r o d u c t si nt h ea c t u a l s i t u a t i o n , w em u s tf i n das o l u t i o nt om e e tt h i sr e q u i r e m e n t ，i n c l u d i n gh o w t ob a t c h w i t h i nr e a s o na n dh o wt os c h e d u l ei nb a t c h e s t h e r e f o r e ，m a s sp r o d u c t i o ns c h e d u l i n g o fs h o pn o to n l yh a si m p o r t a n tt h e o r e t i c a lm e a n i n gb u ta l s oh a sp r a c t i c a ls i g n i f i c a n c e i nal o n g - t e r m t h i sp a p e ra i m sa ta n a l y z em a s sp r o d u c t i o ns c h e d u l i n ga n ds i m u l a t i o ni s s u e si n j o bs h o p s b a t c hm e t h o di s b a s e do ns c i e n t i f i c a l l ys e p a r a t i n gw o r k p i e c e si n t ot h e e q u a lb a t c hs i z e ，a n dt a k et h i ss e p a r a t e dc h i l dl o ta san e ww o r k p i e c e ，t h e np r o c e e d w i t hn u m b e r i n gt h ew o r k p i e c e s ，c o m p u t ep r o c e s s i n gt i m e ，r e a dp r o d u c t i o nw o r k e r s a n de q u i p m e n t s ，a n du s es c h e d u l i n ga l g o r i t h mf o rs c h e d u l i n g f i n a l l y , d e m o n s t r a t e t h ef e a s i b i l i t ya n ds u p e r i o r i t yo fb a t c hs c h e d u l i n gt h r o u g hav a r i e t yo fs t a n d a r d s c h e d u l i n ge x a m p l e s u s i n gt h i sp o w e r f u lo p e n g lg r a p h i c sp a c k a g ea n dv ca s t h ed e v e l o p m e n t p l a t f o r m ，t od r a wat h r e e d i m e n s i o n a lg r a p h i c sw o r k s h o p t h i si sa b l et oi n i t i a l i z et h e p r o d u c t i o ns c e n ea n de q u i p m e n ts oa st oa c c o m m o d a t eav a r i e t yo fp r o d u c t i o ns t a t u s t h i sa l s om a k e st h ew h o l ep r o c e s so fc o m p u t e rs i m u l a t i o np o s s i b l e ，a n dc a l le a s i l y o b s e r v et h ev a r i o u sa c c i d e n t so c c u r r e dd u r i n gt h eo p e r a t i o n ，t h u sr e d u c i n gp r o d u c t i o n c o s t sa n di n c r e a s i n gp r o d u c t i v i t y a v a r i e t yo ft o o l sa r eu s e di nt h i sp a p e r , m a t c o mc o m p i l e ri n t e g r a t e so p t i m i z a t i o n a l g o r i t h mw r i t t e nb ym a t l a bi n t ov c + + 6 0 ，a n dt a k es q ls e r v e r2 0 0 0a st h e d a t a b a s eo fs h o ps c h e d u l i n gs y s t e m ，s od e v e l o pap r a c t i c a lw o r k s h o pp r o d u c t i o n s c h e d u l i n gs o , w a r e t h r o u g he x a m p l e so fs c h e d u l i n ge x p e r i m e n tr e s u l t ss h o wt h a t t h es y s t e mi sf e a s i b l et ob a t c h e so f j o b s ，s c h e d u l i n g ，a n da n i m a t i o ns i m u l a t i o nr e s u l t s k e y w o r d sj o b s h o ps c h e d u l i n g ；b a t c hp r o d u c t i o n ；o p e n g l ；a n i m a t i o n 。s i m u l a t i o n i i 2 3 分批算法实现16 2 3 1 算法基本思想1 6 2 3 2 分批算法比较l7 2 3 3 算法实现18 2 4 调度算法1 9 2 4 1 遗传算法1 9 2 4 2 禁忌搜索算法2 0 2 4 3 混合优化调度算法2l 2 5 实例仿真与分析2 3 2 5 1 加工数量为1 0 的4 x 4 调度2 4 2 5 2 加工数量为3 0 的4 x 4 调度2 5 2 5 3 加工数量为1o 的6 x 6 调度2 7 2 5 4 不同分批调度算法的比较2 9 2 5 5 实例分析3 0 1 1 1 3 4 1 计算机动画4 3 3 4 2 帧缓存技术及应用4 4 3 4 3 调度系统动画仿真4 4 3 5 本章小结4 6 第4 章系统详细设计4 7 4 1 系统总体设计4 7 4 1 1 系统问题的提出4 7 4 1 2 系统功能设定4 7 4 1 3 系统模型分析4 8 4 2 系统功能实现5 0 4 2 1 利用s q ls e r v e r 建立车间调度的数据库系统。5 0 4 2 2v c + + 6 0 环境中调用m a t l a b 程序5 2 4 2 3v c + + 6 0 下进行o p e n g l 编程5 3 4 3 系统各模块及功能实现5 3 4 3 1 安全模块- 。5 4 4 3 2 管理模块5 5 4 3 3 调度模块5 8 4 3 4 仿真显示模块6 1 4 4 本章小结6 5 结论6 6 i v 目录 i 参考文献6 8 攻读硕士期间所获得的科研成果7 1 致谢7 2 v 第1 章绪论 第1 章绪论 1 1 课题研究背景及意义 1 1 1 课题背景 随着社会需求的不断发展，生产规模越来越大，生产过程复杂性越来越高， 为了保证企业生产的高效稳定运行，以获得最大的经济效益，原来简单的、局部 的、常规的、仅凭经验的生产调度已经不能满足现代企业的要求，管理人员和工 程师们面临一些新的问题：如何根据市场上供应的有限原材料来满足产品需求的 不断变化，进行经营决策和组织生产；如何在生产计划临时改变的情况下对生产 进行重新调度，最大限度地发挥生产的柔性特点；如何在生产工艺没有大的改变 的前提下进行调度，使企业产生最大的综合经济效益【l l 。这就对企业的科学管理 和对生产过程的合理调度都提出了更高的要求。 车间的生产调度就是组织执行生产进度计划的工作，生产调度以生产进度计 划为依据，生产进度计划通过生产调度来实现。现代工业企业，生产的环节多， 合作关系复杂，生产过程连续性强，状况变化快，为了适应多变的生产环境，企 业必须充分利用已有的资源，一方面提高对市场变化的反应能力和生产效率，另 一方面调整好生产计划，及时研究分析影响生产的各种因素，根据不同情况采取 相应对策，保证生产任务按时按质按量的完成【2 1 。 车间调度问题是生产制造过程中的基本问题，但是经典的作业车间调度模型 中，假设每种加工工件只有一件，这种假设限制了经典调度问题在实际生产中的 应用，因为在实际生产过程中大部分产品都是批量生产的。批量，是指企业( 或 车问) 在一定时期内，一次出产的、在质量、结构和制造方法上完全相同产 品( 或零部件) 的数量。所以为适应实际生产需要，必须对批量生产调度进 行研究和分析。 计算机水平在逐步提高，计算机仿真技术的运用也越来越广泛。计算机仿真 是利用计算机科学和技术的成果建立被仿真的系统的模型，并在某些实验条件下 对模型进行动态实验的- - l - j 综合性技术，具有高效、安全、受环境条件的约束较 少、可改变时间比例尺等优点，已成为分析、设计、运行、评价以及培训等系统 ( 尤其是复杂系统) 的重要工具。人们利用这样的仿真模型进行试验，从中得到 所需的相关信息，然后帮助人们对现实世界的某一层次的问题做出决策，这样就 不必建立实物模型来研究分析，大大缩短了研究时间，降低了研究成本，提高了 生产效率【3 1 。 1 2 1 车间调度概述 调度是在满足某些约束( 作业的先后关系、预定的完成时间、最早开始时间 和资源能力等) 的条件下对操作( 作业) 的排序，按照排序的次序给它们分配资 源和时间，并且使某个执行目标达到最优( 如总的执行时间、拖期时间和生产费 用等) 。从数学规划的角度看，车间调度可表达为在等式或不等式约束下，对一 个或多个目标函数的优化。现代典型的车间调度问题是：将作业均衡地安排到各 处理机上，并合理的安排作业的加工次序和开始时间，使约束条件被满足，同时 优化一些性能指标【2 】。 1 2 1 1 车间调度的分类 车间调度问题的分类，根据研究的侧重点不同有多种分类方式。g r a v e s 5 1 依 据研究对象的复杂性不同，把车间调度问题分成不同种类，有重要的参考价值。 2 第1 章绪论 曼i l l 一一i 一一一一一一一, , 曼皇舅 ( 1 ) 单机调度问题 加工系统只有一台机床，待加工的零件也都只有一道工序，所有零件都在该 机床上加工。 ( 2 ) 并行机床调度问题 加工系统有一组功能相同的机床，待加工的零件都只有一道工序，可选任一 台机床来加工零件。 ( 3 ) 流水车间调度问题 加工系统有一组功能不同的机床，待加工的零件包含多道工序，每道工序在 一台机床上加工，所有零件的加工路线都是相同的。 ( 4 ) 作业车间调度问题 加工系统有一组功能不同的机床，待加工的零件包含多道工序，每道工序在 一台机床上加工，零件的加工路线互不相同。 通过以上描述不难看出，单机调度是最简单的调度问题，相对而言，作业车 间的调度问题最为复杂，通常是特殊的开环调度问题，也是研究人员关注的重点， 同时在现实的企业生产过程中，大部分生产调度也都属于作业车间的调度问题。 本论文研究也是基于作业车间的生产调度。 1 2 1 2 车间调度问题的特点 ( 1 ) 建模计算复杂性 车间中机器、工件、工人等之间关系复杂，相互影响，因而相当复杂。调度 问题往往是通过等式或不等式等约束条件柬计算的，属于典型的n p h a r d 问题。 随着问题规模的加大，计算量也急剧增加，所以调度问题往往没有精确的解，通 常是在解答过程中寻求其最优解。 ( 2 ) 动态随机性 调度中存在很多随机性和不确定性，如工件的交货期、工件的完成时问、生 产成本等。另外还有一些可能发生的突发事件，如机器故障、工人操作的失误和 生产任务的变更等。 ( 3 ) 多约束性 生产调度受到很多约束条件的限制，如加工资源、工件到期时间与工件加工 顺序等。此外，还有人为的附加因素，如机器负荷平衡等等。 ( 4 ) 多目标 调度的目标很多，目标之间往往又相互冲突，如基于作业交货期的目标、基 于作业完成时间的目标、基于生产成本的目标等【6 】。 北京下业大学下学硕十学位论文 1 2 2 调度的现状及发展趋势 1 2 2 1 车间调度研究现状 自1 9 4 5 年s m j o h n s o n 提出流水车间两台机器下排序问题的优化准则，建 立起第一个排序问题的数学模型以来，此后半个多世纪以来，很多学者进行了大 量的研究工作，并且随着f m s 和c i m s 技术的发展，生产车间的调度问题越来 越显示出其重要性，成为热门的研究领域之一。特别是计算机技术、仿真技术的 不断完善，也使一些复杂的排序实现和最优规则组合成为可能。近年来，车间调 度问题的理论研究更系统化，并进一步接近于生产实际，以下几个方面是车间调 度研究的热点领域： 。 ( 1 ) 多资源、多目标调度优化：大量的实际生产问题属于多资源、多目标 优化问题，因此成为理论界和工程界共同关注的重要研究课题。通常可采用三种 方法： a ) 采用先验偏好信息的方法，即在求解问题之前，获取决策者的偏好信息。 c a v a l i e r i 和g a i a r d e l l i 7 】先通过调查，得到了综合目标与生产周期和平均延误时间 之间的函数关系，然后按综合目标搜索最优调度。d a g h 和s i t t i s a t h a n c h a i c 8 】用神 经网络把多个目标映射成一个综合指标。由于取得准确的“先验”偏好信息是很 难的，所以得到的结果往往不能反映决策者的真正偏好。 b ) 采用后验偏好信息的方法，即直接根据问题的性质和结构求出部分以至 全部非劣解，再由决策者选择一个最满意解。m u r a t a 9 】等提出了多目标的遗传算 法，算法可得到多个非劣解。p o i l i l 锄b a l 锄【l o 】等用该方法研究了作业调度问题， 证明了该算法的有效性。但当非劣解数目较多时，如何从中选择最满意的解仍是 个有待决策的问题。 c ) 逐步取得偏好信息的方法。在决策过程中，决策者通过与辅助决策系统 对话，来加深自己的认识，辅助决策系统则根据决策者新的认识重新搜索解空间， 对话和搜索过程不断进行，直到找到最优解。 ( 2 ) 工艺计划与车间调度的集成研究：工艺加工计划确定零件制造的加工 路线，而车间调度则负责将制造资源分配给由工艺加工计划所决定的零件加工工 序，工艺加工计划与车间调度不仅相互关联还相互约束。传统的工艺计划与生产 调度是相互独立的，并假设制造环境是不变的，资源是无限的，而在实际的生产 过程中往往不是这种理想情况。因此，有些学者提出了把工艺路线规划与作业调 度集成在一起的工作方法。 ( 3 ) 作业车间的动态调度：实际生产中的大量问题是随机发生的，生产调 度过程是一个动态过程。动态调度包括：反应调度( 强调环境变化时的响应能力) 、 自适应调度、实时调度和在线调度。 4 第1 章绪论 ( 4 ) 车间作业的模糊调度：由于生产过程中诸多不确定因素的影响，很少 能获得精确的加工时间和交货期。因此，把加工时间和交货期按模糊数处理更符 合生产实际。 ( 5 ) 非正规性能指标的车间调度：在大多数研究中，评价调度方案一般都 采用生产周期、平均流动时间等时间指标。随着j r r ( j u s ti nt i m e ) 技术的成功 应用，基于公共交货期的e t 调度成为一个新的调度研究热点问题。 ( 6 ) 基于多a g e n t 的车间调度：智能体( a g e n t ) 技术的发展提供了一条解 决动态生产调度和敏捷生产调度问题的途径。基于多a g e n t 的调度方法既融合了 多种现代的理论和技术成果，如先进制造、分布式人工智能、计算机技术等，又 能够适应当前制造系统对于柔性、敏捷性和重构能力的需要。 ( 7 ) 批量调度：在现实的生产中，由于订货、运输、包装和车间管理等原 因，工件往往是成批生产的。按经典的调度理论已经不能解决此时的最优化问题， 批量调度就被提出成为了新的研究热点。研究后发现，如果一批零件加工一部分 后，就运往后续加工机床，可使后续工序提前进行，并且有些生产辅助工作如调 整工具、更换夹具等可以在零件到来前进行。如果事先就划分好合理的批次，做 好准备工作，零件到达后就能开工，就能有效地提高生产率。 ( 8 ) 人机交互调度：由于理解人的决策过程比预想要困难得多，所以调度 方法的研究目的不是取代人，而是对人的决策行为的支持。这种观点促使许多研 究者开始研究各种人机交互系统中存在的问题。采用人机交互的调度方法要充分 发挥人的认知作用，人可以通过人机交互界面下发调度命令，或根据监测数据及 自己的调度经验，对调度方案进行审查和修改，并将它们传送给人机交互系统中， 这样人就可以充分实现自动辅助功能的操作过程【1 1 1 。 1 2 2 2 车间调度发展趋势 综观车间调度问题半个多世纪来的研究、应用和发展，在取得大量成果的同 时，也显露出许多急需解决的问题。过于简化的调度模型虽然便于理论研究，却 难以用于动态性、随机性、多目标等的实际生产过程。今后的研究应以可应用的 调度系统为重点，使研究朝着真正解决实际生产问题，提高制造管理技术这一目 标发展。从这个角度来看，对调度问题的研究可从以下几个方面进行拓展： ( 1 ) 交互式在线调度 生产过程的随机性、不确定性往往要求不断进行重新调度，实际的生产环境 是动态的、具有变化的结构和目标，甚至还存在调度的中断。因此，即使用再精 准、快速的离线调度，也会使等待时间增加、设备利用率和生产效率下降。因此 具有交互功能的在线动态调度的研究将是今后的一个研究方向。 ( 2 ) 集成化 5 北京下业大学t 学硕十学何论文 随着并行工程的不断深入，生产过程中不同阶段集成的重要性和迫切性只益 突出。加工工艺计划和车间调度在功能上既有各自内在的功能特点，又存在着许 多相互联系。在工艺计划阶段如果不考虑车间的具体制造资源状态和生产能力， 就无法制定合理的作业计划、安排生产。在生产过程中，调度系统应及时反馈工 艺执行情况，当生产过程中出现问题时，及时进行资源重新分配或调整工艺计划， 提高生产计划的可执行性。因此建立一个行之有效的集成系统是提高生产系统性 能的关键之一。 ( 3 ) 优化策略的研究 寻找新的数学工具和分析方法，建立调度算法复杂性、收敛性的分析研究。 将现已有的各种调度方法的优点有机地融合，加强混合优化策略以及相应仿真环 境的开发，建立实用化的调度平台与优化技术，这无疑是一个值得关注的研究方 向。 1 2 3 车间调度问题求解方法 车间调度问题的研究受到应用数学、运筹学、自动化和人工智能等领域的科 学家的重视，既是一个古老的课题，又是一个现代的热点问题，由于其重要的理 论和应用价值，所以多年来始终是研究的热点。自从调度问题研究报告的首次发 表，至今已经提出了各种各样研究方法。从国内外的发展来看，对车间调度问题 的研究主要有以下几种方法： ( 1 ) 基于启发式规则的方法 由于启发式规则计算复杂度低、易于实现，故在生产中得到了广泛的应用。 但启发式规则一般不具备全局优化的特点。常用的启发式规则可分为简单规则、 复合规则、启发式规则三类【1 2 】。 ( 2 ) 分枝定界法 因为分枝定界法可为部分路径计算很强的下界，所以它是求解调度问题比较 有效的方法。对于较大规模的调度问题，分枝定界法需要较多的时问【1 3 】。 ( 3 ) 拉格郎日松弛算法 拉式松弛算法能为复杂的规划问题提供好的次优解，并对解的次优性进行定 量评估，所以成为解决调度问题的一种重要方法【1 4 】。但与分枝定界法相比，拉式 算法更耗时。 ( 4 ) 动态规划 动态规划是求解小规模调度问题的有效算法，但它对组合的需要会随着问题 规模的扩大呈指数增长，以至不能求解大规模调度问题【1 1 】。 ( 5 ) 专家系统和基于知识的方法 专家系统和基于知识的方法由知识库和推理机组成。知识库包括一些规则、 6 第1 章绪论 过程和启发式信息。推理机制用来选择一种策略处理知识库中的知识【1 3 】。 ( 6 ) 多智能体方法 由于单一的专家系统处理问题的能力有限，不少学者提出并行或分布策略来 解决调度问题。如文【1 5 】用多智能体结构的分布式决策方法对f m s 进行了动态 研究。 ( 7 ) 人工神经网络 h o p f i e l d 神经网络模型的出现为解决调度问题开辟了一条新途径，但由于涉 及的变量太多，计算效率低，很难解决实际调度问题【1 6 】。 ( 8 ) 模拟退火 模拟退火将组合优化问题与统计力学的热平衡问题类比，通过模拟退火过 程，可找到全局最优解。但它的收敛速度慢，很难用于实时动态调度环境1 7 】。 ( 9 ) 禁忌搜索方法 禁忌搜索是由g l o v e r 提出的用于解决组合优化问题的一种高级启发式方法。 t a i l a r d 提出了解决流水车间调度问题的禁忌搜索算法。由于禁忌搜索的应用需要 较多的技巧，故在车间调度中的应用难度较大【1 8 】。 ( 1 0 ) 仿真调度方法 仿真模型可以描述和定量评估复杂的制造系统，为实际调度采用合适的调度 算法提供依据。但应用仿真进行生产调度的费用高，仿真的准确性受程序员判断 能力和技能的限制，并且很难从特殊的试验中提炼出一般规律。 ( 1 1 ) 遗传算法 遗传算法成为近年来解决作业调度问题的最主要方法。与其它方法相比，遗 传算法的优越性主要表现在：搜索过程中不易陷入局部最优，能以极大的概率找 到全局最优解；具有并行性，非常适合于大规模并行分布处理；易于与其他的技 术( 如神经网络、启发式规则等) 相结合，形成性能更优的算法。但遗传算法的 搜索效率低、易过早收敛【9 1 。 1 3 批量生产调度概述 传统的调度研究只是针对经典的调度案例进行分析，研究的加工工件只有一 件。而在实际生产中，企业接受的订货可能不仅仅只有一件，所以车间一般都是 以一定的批量同时进行生产加工，提高生产效率，这就牵扯到批量生产调度的研 究。然而真正涉及到生产车间批量调度的文献很少，其原因主要在于车间调度的 复杂性。车间调度问题属于n p 完全问题，到目前为止，非常复杂的批量生产调 度，在实际的计算中很难得到最优解。随着批量调度在实际生产中的重要性越来 越突出，并且现代计算机技术的飞速发展，近几年来，研究批量生产调度优化问 7 c a n d i d o 和k h a t o r l n l l 2 4 1 注意到把一批工件分多次运输能缩短生产周期，但没 有考虑到一道工序可在多个机床上加工的情况，并且没有分析运输过程中批次对 生产周期的影响。台湾学者c h i n y a o l o w 等人【2 5 1 研究了生产车间分批调度的优点。 他们对等量分批和不等量分批进行了对比研究，认为对批量调度进行合理的等量 分批可以缩短生产周期、降低生产成本，但他没有解决应该如何分批的问题。 1 3 2 批量调度研究现状 目前国际上对批量问题已经开展了以下的研究【2 6 1 。d e b o d t 等人研究了在动 态需求条件下，滚动展望期的作用和需求的不确定性对批量决策的影响；f a b r i z i o 等人对一个源于食品公司的能力约束的批量调度问题进行了研究，将该问题模型 建立成一个基于混合连续生产调整方式能力约束批量问题，并提出了解决方案； b a h l 等人对能力约束的批量问题进行了研究，并且按照需求的类型、资源约束 8 第1 覃绪论 及生产计划的规模对能力约束批量问题进行了划分；k u i k 等人讨论了在一个公 司的不同的决策层中，批量问题和生产计划所起的作用，主要讨论了与实际计划 和控制相关的批量的计划与选择的区别：w o l s e y 研究了单项目无约束批量问题 的问题模型及解决算法；d r e x l 和k i m m s 对批量和排产问题中的不同类型进行了 研究，并按生产周期的不同划分为离散和连续周期批量问题；b e l v a u x 与w o l s e y 对在基本批量问题模型基础上添加不同变量的方式进行了讨论，如延迟、调整费 用等，并对不同模型的批量问题计算结果进行了研究；k a r i m i 对能力约束单级批 量问题进行了研究，并对求解方法进行了总结；b r a h i m i 等人对能力约束和无能 力约束条件下的单级批量问题的研究进行了总括；j a n s 与d e g r a e v e 对单级动态 批量问题进行了研究，并对近期的研究成果进行了总结。 1 4 计算机仿真概述 计算机系统仿真就是，以计算机为工具，以相似原理、仿真技术、系统技术 及其应用领域有关的专业技术为基础，利用系统模型对实际的或设想的系统进行 试验研究的一门综合性技术。 由于生产调度的复杂性，一般的方法很难用精确的解析模型对其进行描述分 析。但是，仿真的方法却能提供这种理想模型，且可以定量地进行评估，从而使 实际系统采用合适的调度方法。基于仿真的方法不单纯追求系统的数学模型，侧 重对系统中运行的逻辑关系进行描述，能够对生产调度方案进行比较评价，分析 系统的动态性能，并选择系统的动态结构参数。 1 4 1 仿真在调度中应用 计算机建模和仿真功能强大，应用十分广泛。在产品制造中的应用大致包括 三个方面：以产品模型为中心的仿真、以制造系统模型为中心的仿真和以产品开 发过程模型为中心的仿真。这三方面的应用随着制造企业信息化进程的发展而发 展，并更加注重可视化技术的应用及与用户之间的交互。本文需要关注的是第二 个方面的运用，以制造系统为中心建模仿真的目的在于对车间生产进行合理的调 度，包括加工路线、资源的分配、物料的供应等【27 1 。仿真在车间调度中使用的难 点在于必须建立一个有效的仿真模型，由于制造车间本身很复杂，要考虑的因素 很多，所以要建立一个完整准确而计算量又不太大的车间模型是非常困难的。 在分析制造系统模型时，调度问题是重要一环，现代产品市场的发展对生产 调度的快速反应能力和精确性都提出了更高的要求，早期的调度方法大都基于运 筹学、控制论等数学方法，由于生产车间调度问题的最优解的求解时间随着问题 规模增大呈指数增长，因此无论多先进的计算机都不可能在有限时间内求出最优 9 工条件，方便快捷。 1 4 2 调度仿真的特点 计算机仿真特点鲜明，在生产调度中使用时应全面的考虑仿真的优缺点，并 且尽可能通过与别的方法相结合来弥补其不足【2 8 】。 l o 第l 章绪论 皇量量曼曼皇甍皇曼曼曼曼曼曼曼皇曼曼曼i _ ii i i i_!舅曼曼曼曼曼量曼鼍曼皇曼皇曼曼量曼鼍 优点：克服了复杂问题不能求解析解的矛盾，转而求可行解；可对多方案进 行比较，可检验不同决策规则的作用；模型描述能力强，对多种车问都能建摸； 在一个仿真环境上可开发多个调度器；通过仿真，可以预测拟采取的生产步骤的 可行性，决策规则的合理性，还能发现生产过程的非正常状态。 缺点：仿真结果与实验条件有关，缺乏普遍性，难以在其基础上发展调度理 论：建模和运行的工作量较大，为评价一个决策规则可能要做多次仿真运行，开 发和使用成本较高；仿真的正确性受程序员的技巧及判断的限制，有时候，即使 模型是准确的，由于编程和决策的因素，也不一定能保证好的调度产生。 随着计算机仿真技术的进一步发展，其缺点的不断弥补，强大的优势越来越 明显，必将促使仿真成为解决车间运行阶段调度问题的最有效的途径之一【2 引。 1 5 本文的主要内容 本课题的研究主要针对作业车间的批量调度和仿真，主要研究包括如下内 容： 对作业车间的双资源多目标批量生产调度问题进行分析，确定分批方法，建 立数学模型，写出分批算法；把分批的结果当作一个新的待调度工件，重新计算 加工时间，读取加工工人和加工设备，引入混合优化算法，进行调度；对调度结 果进行仿真研究，基于v c 下的o p 钮g l 模拟生产车间模型并进行实时调度仿真。 论文的具体组织结构如下： 第1 章绪论介绍了车间调度问题的含义、分类及特点，分析了车间调度问 题国内外研究的历史和发展现状，总结了近年来车间调度研究的主要发展方向及 车间调度问题的主要求解方法，并详细介绍了本文的主要研究内容。 第2 章作业车间批量生产调度算法研究通过对实际生产状况的分析，针对 作业车间批量生产的问题提出了分批调度策略。首先对分批调度进行简介，论述 其在实际生产中的意义及常用的一些分批方法，然后提出本文所运用的分批算法 的研究思想和基本流程，建立双资源多目标优化调度模型，采用禁忌搜索算法和 遗传算法相结合的混合优化算法，完成调度。最后，从现实生产实际出发给出了 批量生产的调度算例，其结果可行，对生产实践起到一定的指导作用。 第3 章车间调度仿真首先介绍了o p e n g l 的相关基本知识，在v c 环境下 运用o p e n g l 绘图的准备工作；然后分析了车问调度三维场景的具体实现过程； 引入计算机动画的概念，研究把动画方式应用在调度系统中的可行性，并详细介 绍了实现的方法。 第4 章系统详细设计根据建立的车间调度系统三维场景模型研究，采用 v c 抖6 0 为编程平台，实现软件框架的搭建；通过m a t c o m 编译器，把在m a t l a b 1 2 第2 章作、j k 车间批晕生产调度算法研究 第2 章作业车间批量生产调度算法研究 2 1 批量生产调度问题的描述 在批量生产调度问题的研究中，依据适当的分批原则，把每一种工件分成若 干小批量进行加工，每一小批工件被称作子批。子批的数目、包含工件多少和加 工先后顺序是决定批量调度性能最为基本的三个要素，l o ts p l i t t i n g ( l p ) 和l o t s t r e a m i n g ( l s ) 都表示分批调度。 最简单的分批方式相对于没有分批的调度，也能够节省大量的加工时间，通 过简单的一种工件批量生产为例，假设有三台加工设备，工件加工需要三个工序， 图2 1 表示把工件等分为3 批和没有进行分批情况下的加工时间对比。当第一批 工件完成第一个工序加工之后立即到下一个设备进行第二个工序的加工，依次进 行，结果可以明显看出分批调度的优势。 加 工 设 备 加 工 设 备 加工时间 图2 - 1 加j r 时间对比 f i g u r e 2 1c o m p a r i s o no f p r o c e s s i n gt i m e 对于大批量生产的车间，通常情况下，我们可以采取四种分批策略来改进调 度性能： ( 1 ) 无间隙等量分批，即将工件分成若干个大小相等的子批，并且所有工 件的加工是连续的。 ( 2 ) 有间隙等量分批，即将工件分成若干个大小相等的子批，允许工件批 北京下业大学t 学硕十学何论文 次加工之间存在时间间隔。 ( 3 ) 无间隙不等量分批，即工件可以分为许多大小不同的批次，并且子批 在同一机床上的加工是连续的。 ( 4 ) 有间隙不等量分批，即工件可以分为许多大小不同的批次，但是允许 子批之间的操作可以不连续。 一些专家对分批调度问题进行了比较深入的研究，得出的结论认为把工件分 批加工时如果将其等分更有利于缩短最大加工完成时间。等分批( e q u a lb a t c h s i z e ) 指分批后的子批包含工件数目相同或相近，是常用的分批策略。当使用等 分批不能使结果更加优化时，才考虑用其它分批策略【2 9 】。本文分批算法核心正是 基于等分批的思想，采用有间隙的等量分批。 2 2 批量调度约束和模型 假设作业车间里有r 台机器，某段时间有x 类工件需要加工，每类工件都 有一定的数量，且每类工件都有多道加工工序，每道工序可在多台性能不同的机 床上加工，工人具有特定的加工能力。同时我们遵循分析问题的一些约束： ( 1 ) 所有工件在零时刻均可以被加工。 ( 2 ) 任何工件不允许提前加工。 ( 3 ) 每一道工序在某一台机床上的加工时间是确定的。 ( 4 ) 工件到达机床之前进行的准备时间，我们在调度时计入工件的加工时 间。 ( 5 ) 每台机床同时刻只加工一个工件。 ( 6 ) 每种工件在等分批的条件下，可分成任意批次。 ( 7 ) 不同工件的批次之间、工序之间没有先后约束。 ( 8 ) 不同工人和机床具有不同的加工能力。 不同于调度的多目标性，在研究分批算法时，目标只是将各类工件划分为合 理的加工批次，使得最终的加工时间最短，或者综合制造成本最小，或者两者的 加权值最小，本文在研究分批算法时，是以生产周期的最优化为目标。 在分析问题之前首先引入要用到的符号和函数： g 。：表示第x 种工件( x = l ，2 ，3 ，期，x 为工件种类数； 厶：表示q 的第y 个子批( 尸1 ，2 ，3 ，瓦) ，y x 为q 的子批总数； q ，：表示工件q 的y 子批包含的工件数； m ，：表示第，台机器( 产1 ，2 ，3 ，r ) ，其中r 为机器总数； 1 4 第2 苹作业t - 闸批晕生产调腰舁绫母f 冗 互( t p ) ：表示子批e j ，y 的第p 道工序的准备时间( 矿l ，2 ，3 ， b ) ，其中只为工件q 的工序总数。 互( 乓p ) ：表示子批e 工，j ，的第p 道工序的加工时间( 矿1 ，2 ，3 ， r ) 5 q ( q ) ：表示工件q 的计划加工数量； k ( e ) ：子批疋，中包含的工件数； ：所有工件最大完成时间； 建立作业车间分批调度问题的数学模型如下。 加工时间最优化约束： m l n 丁嘲x ； ( 2 一i ) 分批数量约束： q ( q ) = q ，y ： ( 2 - 2 ) 最大完成时间约束： z 。五( 丘，p ) + 互( e ，p ) k ( e ，) ，v 疋，p ： ( 2 - 3 ) 式( 2 一1 ) 中的总时间可表示成式( 2 4 ) ： 乙= 互+ 正； ( 2 - 4 ) 其中生产加工准备时间r l ： 写：鼬引岛，砒 协5 ， 写= 盔弧岛，砒 ( 2 - 5 ) 工件完成加工的时间瓦： 互= 壹圭壹伍皈，力) ；互= 乏皈，力 ； ( 2 6 ) x = ly = lp = l 以上分析的准备时间在下面计算时，全部纳入加工时间。一方面是考虑方便 计算；另一方面也是为了减少时间矩阵，限制批数，方便管理。 因为正确选择批量大小和合理确定批量的间隔生产期，对提高批量生产的经 济效益十分重要。大批量生产比小批量生产可以节约原材料，减少机器设备和工 夹具的更换时间，可以大批购进原材料，工人能够比较长期地从事一种作业，易 首先，在等分批的指导下，基于最大完工时间最小化的分批算法只考虑完全 等分的情况，比如某类工件包含1 0 个工件，它只能考虑分成2 批或者5 批的情 况； 其次，计算任务繁重，对于每一次的分批，此算法都要先确定分批数，然后 再计算子批包含的工件数，计算子批每道工序新的加工时间，再代入公式进行判 定； 本文基于对以上问题的分析，改进分批算法如下。 本文分批的核心思想：当车间只加工一类工件时，必定存在一个最优的分批 方案。先确定一定数量的某种工件单独加工时应该划分的子批数，然后计算每个 子批包含的工件数，计算子批的每道工序需要的新的加工时间。这时，新的工件 在车间中的加工方式便成了平行移动方式，基于这种情况采用确定性调度算法求 出较好的调度方案。计算某一类工件单独加工时，需要划分的批次判定公式为： 丁= + k ( 刀一1 ) t l ； 1 6 ( 2 8 ) 第2 章作业乍问批帚生产调度算法研究 式中，m 为工序数；刀为批数；为某工件第i 工序的加工时间：气为最长 工序的加工时间( 此时t 、f ，已包含准备时间) ；k 为子批中包含的工件数( 此时 为判定公式并不是求得最终结果的公式，k 根据计算的结果能取非整数) ，t 为 考虑分批的时间参数。 本文的分批算法，引入了参数k ，可以取到非整数，这样就丰富了分批的情 况，不仅仅局限于完全等分批。还是1 0 个工件，我们就可以分成4 个子批，每 个子批包含工件数为2 ，2 ，3 ，3 。这样势必更有可能得到最优解。另外，本文 的算法是确定了合理的分批数目之后再进行子批相关数据的计算，相比于计算每 次分批之后的子批数据，大大减小了计算任务。 2 3 2 分批算法比较 为验证本文算法的合理性，和文献【3 0 】中提到的“基于机器负荷角度出发的 分批算法”