（计算机应用技术专业论文）遗传算法在车间作业调度方面的研究和应用.pdf

摘要 车间作业调度问题( j o b s h o ps c h e d u li n gp r o b l e m 简称j s s p ) 是一 种典型的调度n p 难题。这一问题的求解目标是要找到一个将一组作业 安排到机器上去，以使作业能够“最优”完成的方案。使企业生产能够 实现生产的高效率、高柔性和高可靠性。 本文通过对车间作业调度系统的描述，介绍了遗传算法的有关理 论。详细地阐述了算法的基本结构，提出了自己的遗传算法的编码方案、 适应度函数的选取、算法参数的选择、自适应变异和杂交算子的设计； 然后根据遗传算法的不足，引入了模拟退火算法，根据两者的优缺点把 两者结合起来，提出了混合遗传算法；接着根据实际车间作业调度生产 中可能出现的情况，初步讨论了如何实现车间作业的动态调度问题：最 后提出了车间作业调度系统的设计思想，并以两个实例说明了本文中提 出的混合遗传算法是可行的。 关键字： j s s p 遗传算法模拟退火算法 g a s a a b s t r a c t t h ej o b s h o p s c h e d u l i n gp r o b l e m ( j s s ni s o n ek i n d o ft y p i c a l s c h e d u l i n gn pp r o b l e m t h eg o a lo fs e t t l i n gt h i sp r o b l e mi s t of i n d s o l u t i o n st h a ta r r a n g eag r o u po fa r r a n g e m e n tt ot h em a c h i n et of i n i s ht h e m b e s t t h ee n t e r p r i s ec a nm a k et h ep r o d u c t i o nw i t h h j i g he f f i c i e n c y , h i g h f l e x i b i l i t ya n dh i g hr e l i a b l e ， f i r s t l y , b y t h ed e s c r i p t i o no ft h ej o b - s h o ps c h e d u l i n gs y s t e m ，t h e p a p e r i n t r o d u c e dt h e t h e o r y a b o u tg e n e t i c a l g o r i t h m s t h i sp a p e r e l a b o r a t e dt h e a l g o r i t h m s b a s i cs t r u c t u r ea n d p r o p o s e do w ng e n e t i c a l g o r i t h m se n c o d i n g ，a d a p t i v ef u n c t i o ns e l e c t i o n ，t h ea l g o r i t h mp a r a m e t e r s e l e c t i o n ，t h es e l f - a d a p t i v em u t a t i o na n dt h ec r o s s o v e ro p e r a t o rd e s i g n s e c o n d l y ，a c c o r d i n gt ot h ei n s u f f i c i e n c yo fg e n e t i ca l g o r i t h m st h ep a p e r i n t r o d u c e dt h es i m u l a t e da n n e a l i n ga l g o r i t h m s a n di ta l s op r o p o s e dt h e h y b r i dg e n e t i ca l g o r i t h m so nt h eb a s i so ft h ea d v a n t a g e sa n dd i s a d v a n t a g e s o ft h et w oa l g o r i t h m s t h i r d l y ，a c c o r d i n gt ot h es i t u a t i o nw h i c hi nt h eb a s i s a c t u a l w o r k s h o pw o r kd i s p a t c hp r o d u c t i o np o s s i b l ya p p e a r s ，i n i t i a l l y d i s c u s s e dh o wr e a l i z e dt h ew o r k s h o pw o r kd y n a m i cd i s p a t c h q u e s t i o n f i n a l l yp r o p o s e dt h ej o b s h o ps c h e d u l i n gs y s t e md e s i g nm e t h o d ，a n d s h o w e dt h eh y b r i dg e n e t i ca l g o r i t h m si sf e a s i b l eb yt w oe x a m p l e si nt h i s a r t i c l e k e yw o r d s ：j s s p g e n e t i ca l g o r i t h m ss i m u l a t e da n n e a l i n g a l g o r i t h m s g a s a 长春理工大学硕士学位论文原创性声明 本人郑重声明：所呈交的硕士学位论文，遗传算法在车间作业调 度方面的研究和应用是本人在指导教师的指导下，独立进行研究工作 所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他 个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律结果由本人承担。 作者签名：盘叠远q z 年主_ 月立拥 长春理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“长春理工大学硕士、博士学 位论文版权使用规定”，同意长春理工大学保留并向国家有关部门或机 构送交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权 长春理工大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名：垩叠熊垒2 年三月蛰 特锄签名孝毖【_ 斗年乡月妒 1 1 课题的提出 第一章绪论 随着科学技术的发展，生产规模越来越大，复杂性越来越高，市场 竞争也越来越激烈，因此对企业的管理和对生产过程的监控都提出了更 高的要求。近几十年来，各类生产过程都已经发生了显著变化，其主要 特征是生产规模的大型化和生产过程的连续化。在激烈的市场竞争中， 为了保证生产的高效稳定运行，以获得最大的经济效益，原来简单的、 局部的、常规的控制仅凭经验的管理已经不能满足现代生产的要求了， 企业管理者和控制工程师们面临的问题是：如何根据市场上原料供应和 产品需求的变化进行经营决策和组织生产；如何生产计划改变的情况下 对生产过程进行控制，以便最大限度地发挥生产的柔性；如何在生产工 艺不作大的改变的前提下进行管理、决策，使企业产生最大的综合经济 效益1 1 1 。 任何制造系统的优化与改造，都离不开管理模式与计划调度。无论 是以普通设备和生产线组成的传统车间还是计算机集成制造系统 c i m s ，都面临着有效运行的问题，对各种高科技的硬件设备，如果仍 然沿用传统的控制管理方法，显然不能发挥它们的技术优势，经济上还 造成大量投资的浪费。控制手段与调度策略的落后，已经成为现代制造 系统中的“瓶颈” 1 2 课题研究目的及意义 车问作业调度f 落o o b - s h o ps c h e d u l i n gp r o b l e m 简称j s s p ) 是柔性 制造系统( f l e x i b l em a n u f a c t u r es y s t e m ，简称f m s ) o 的种典型的调度 n p 难题。这一问题的求解目杯是要找到一个将一组作业安排到机器上 去，以使作业能够“最优”完成的方案。每个作业可由一些工序完成， 而每个工序则必须由指定的机器处理。一个调度是按照先后顺序条件将 所有工序安排到机器上的一种方案。 车间生产过程的作业调度问题是制造系统运筹技术，管理技术与优 化技术发展的核心。作为制造系统生产管理的核心内容的车间生产调度 系统，是实现生产计划和生产作业计划并使企业生产效率最大化的重要 手段。 车间作业调度和控制技术是实现生产高效率、高柔性和高可靠性的 关键。有关资料表明，机械制造过程中大部分的时日j 消耗在非切削过程 中，及时准确的调度可以提高资源的利用率，均衡生产，减少在制品阶 段的资金占用。 随着经济全球化，我国经济体制的转变，决定了如今影响企业的竞 争力的因素，由原来的以质量( q u a l i t y ) ，成本( c o s 0 为主，扩展为质量， 成本，时间，服务并重我国很多建设较早的企业，其设备现在看来已 无法适应生产高效率的需要，但由于规模较大，缺乏投资一时难以更新。 产品的技术含量低，也造成设备经济上的不可行性，如此又形成了一个 设备制约产品，产品阻碍设备的恶性循环。同时有些企业仍在采用传统 的手工方式编制生产作业计划，这种静态的、工作量极大的计划会因生 产过程中每一要素的变化而受到艰制，而调整一般只能通过生产调度员 的经验来进行，因此，整个生产作业计划的编制具有很大的盲目性。因 此制定满足企业资源约束( 设备，人员等) 的高效的生产计划是企业当前 面临的主要问题，该问题的解决，将解决企业发展的瓶颈，为企业快速 发展提供良好的保障。对降低生产成本、缩短制造周期、提高生产效益 均具有重要的意义。在这种情况下，研究企业生产系统的管理模式与具 体运行控制方法，对于提高生产效率具有重要的现实意义。 要想提高运行管理的质量，作业计划调度是最具伸缩性的因素之 一。随着运筹学及各种最优化理论发展逐渐完善，调度方法本质上作为 一种优化方法必然随之精益求精。在专业领域中通过应用来丰富完善并 检验优化算法和理论，对于它自身的发展，以及能把它更好的应用到其 他领域同样具有重要的理论意义。同时由于调度问题是n p 完全问题， 目前尚无有效的求解策略，故调度问题的研究具有重要的理论意义。 因此本文针对车间调度理论及其算法的研究既具有理论价值又具 有现实意义。 1 3 国内外在车间作业调度方面的研究现状 车间作业调度问题是一个古老而又传统的问题，对它的研究始于 2 0 世纪5 0 年代，早在1 9 5 4 年j o h n s o n 对两台机床f l o w s h o p 型调度问 题进行了研究后，提出了解决n 2 f c m a x 和部分特殊r e 3 f c m a x 问题 的优化算法，这代表调度理论研究的开始，以后它便开始对调度问题进 行了广泛研究【2 j o 6 0 7 0 年代建立了调度理论的主体( 经典调度理论) ，并重视调度复 2 杂性的研究。由于调度问题是制造系统中最基本，最重要而又最复杂的 问题之，国内外无数的学者对其进行了广泛的探讨和研究，也提出了 各种各样的算法，建立了不同的理论框架模型。车间调度问题的复杂性， 各种不同的具体问题往往有很多不同的解决方法，因此需要从策略上去 考虑车间调度问题，形成各种研究方法策略以指导对车间调度的研究。 七十年代，人们开始了算法复杂性的研究，多数调度问题被证明属 于n p 一完全问题或n p 难问题，难以找到多项式算法，因此开始关注 启发式算法。p a n w a l k a r 总结和归纳出了1 1 3 条调度规则，并对其进行 了分类。七十年代末期，经典调度理论趋向成熟。随着7 0 年代后期各 类调度问题与调度理论研究的深入及各种杂交学科的发展，又涌现出了 许多新的车阆调度理论与方法，如：基于运筹学方法、基于控制的方法， 基于启发式规则的调度方法、基于人工智能的方法、基于知识的调度方 法、确定性最优化方法、整数规划、仿真调度方法等( 3 1 八十年代初期，s t e p h e n 等从三个方面对调度进行了重新考察，对 未来发展做了分析和预测，认为理论与实际的结合将会成为研究热点。 这个富有挑战性的课题吸引了机械、计算机、管理等诸多领域的学者， 许多跨学科的方法被应用到研究中。其中最引人注目的就是以 c a r n e g i e m e l t o n 大学的m f o x 为代表的学者们开展的基于约束传播的 i s i s 研究，它标志了人工智能开始真正应用于调度问题。八十年代后期， r o d a r n m e r 等人总结了生产调度的理论和实践方面的最新研究进展，从 七个方面论述了生产调度的技术和方法，认为生产调度无论在理论还是 实践上都已突破了传统界限一捌。 九十年代至今，随着计算机应用技术的发展，人工智能、人工神经 网络、基因遗传算法、禁忌搜索算法、模拟退火算法等被广泛用于 j o b s h o p 调度问题的研究。基于遗传算法的车间作业调度，国外已有研 究，如f l o r i d a 大学的j j e b i e g e l 和j j d a v i s 提出的“用于车间作业调 度的遗传算法”等，但这些研究都不是直接对j s s p0 0 h s h o ps c h e d u l i n g p r o b l e m ) 应用遗传算法而是通过成组技术来对车间作业调度应用遗传 算法，这就使得j s s p 研究具有一定的局限性，即受到成组技术研究与 其适应性的限$ 1 j 1 6 ：, ，8 , 9 1 。 1 9 9 7 年，t s u j i m u r a 等对三种编码方式：基于持续的表示、随机键 表示和基于工序的表示对求解j s s p 问题进行了比较研究 2 0 0 0 年，王锡禄等给出了优化模型和遗传算法求解j s s p 的一般算 法框架，但它对遗传算法求解j s s p 的内部具体实现方法探讨很少1 1 0 l 。 2 0 0 2 年，谢胜利等采用分段结构染色体编码、可行调度判断和应 用修正算予等改进算法求解j s s p 问题。该算法具有较好的稳定性：但 遗传算子和修正算子的选取需要经验或反复试验【1 1 1 。 3 2 0 0 3 年，c h ib i n 等提出了两种改进的自适应遗传算法及相应的编 码方案；并比较了6 种不同算法求解j s s p 问题的情况。文章得出结论： 自适应遗传算法优于非自适应遗传算法【1 2 1 。 然而，与传统的启发式算法相比，遗传算法不适用于最优解的微调 结构，运算效率低。如果两种算法混合，遗传算法用于个体中的全局搜 索，而启发式在染色体中实行局部寻优，则会达到在求解性能和效率方 面具有显著的优势。 综上所述：在对车间调度问题进行研究的方法上，最初是集中在整 数规划、仿真和简单的规则上，这些方法不是调度结果不理想就是难以 解决复杂的问题。随着各种新的相关学科与优化技术的建立与发展，在 调度领域也出现了许多新的优化方法，比如神经网络、模拟退火法、遗 传算法、禁忌搜索法等，使得调度问题的研究方法向多元化方向发展。 1 4 本文主要研究内容 本论文是在国内外学者的研究基础上，基于遗传算法对车间作业调 度问题作了深入的研究。具体内容如下： 1 叙述了国内外车间作业调度研究的历史和现状，提出车间作业调 度研究可行性，以及研究现代车间作业调度的目的和意义。 2 通过对车间作业调度系统的描述，介绍了车f b j 作业调度问题的分 类，特点，描述方法，以及车间作业调度的假设条件，并重点讲述了长 久以来对车问调度闽题的建模方法，介绍了车f b j 作业调度问题的研究方 法和存在的问题。 3 介绍了遗传算法的起源和发展，遗传算法基本思想，遗传算法的 特点。重点介绍了遗传算法的编码和讨论了遗传算法的适应性函数，遗 传算法的参数和基本操作。最后介绍了遗传算法的执行策略和应用情 况。 4 重用遗传算法研究了车间作业调度问题，提出了自己的遗传算法 的编码方案，适应度函数，算法参数的选择，以及具体的遗传算子；然 后根据遗传算法的不足，引入模拟退火算法，并把两者结合起来，提出 了混合遗传算法；接着根据生产中可能出现的实际情况，初步讨论了如 何实现车间作业的动态调度问题；最后提出了车问作业调度系统的设计 思想并得到了初步的实现，并以两个实例说明了本文中提出的混合遗传 算法是可行的。 4 第二章车间作业调度问题描述 2 1 车间作业调度问题的定义 上世纪初，企业工程师和管理顾问讨论“如何分派( d i s p a t c h i n g ) 正 作以及能够胜任这种作的调度员( s c h e d u l e r ) o 随着工业化程度的深入， 人们在理论研究中将车间作业调度问题常定义为“分配一组资源来执行 一组任务”。如今，车间调度主要是针对项可分解的工作( 如产品制 造) ，探讨在尽可能满足约束条件( 如交货期、工艺路线、资源情况) 的前 提下，通过下达生产指令，安排其组成部分( 操作) 使用哪些资源、其加 工时间及加工的先后顺序，以获得产品制造时间或成本的最优化。 k i s h a nm e h r o t r a 博士有如下的定义l l i i nt h ei o bs h o ps c h e d u l i n gp r o b l e m ( j s s p ) af i n i t es e to f j o b s i sp r o c e s s e d0 1 1af m i t es e to fm a c h i n e s e a c hj o b i sc h a r a c t e r i z e db yaf i x e do r d e ro fo p e r a t i o n s ，e a c ho fw h i c hi st ob e p r o c e s s e do nas p e c i f i cm a c h i n ef o ras p e c i f i e dd u r a t i o n e a c hm a c h i n e c a l l p r o c e s sa tm o s to n ej o ba tat i m ea n do n c eaj o bi n i t i a t e sp r o c e s s i n go na g i v e nm a c h i n e i tm u s tc o m p l e t ep r o c e s s i n gu n i n t e r r u p t e d t h eo b j e c t i v eo f t h ej s s pi st of i n da ”s c h e d u l e ”t h a tm i n i m i z e st h e “m a k e s p a n ”o ft h ej o b s 。 今后，随着集成化程度的加深，人工智能，实时反馈等手段的运用，作 业车间调度将不在仅仅局限于车间一机器一工件一工序这样的关系，会 与制造企业的信息流、组织结构、决策方式关联起来。 车间作业调度问题也可以描述为：n 个工作在m 台机器上加工，一 个工件分为k 道工序，每道工序可以在若干台机器上加工。每一台机器 在每个时刻只能加工某个工件的某一道工序，只能在上道工序加工完成 后才能开始下道工序的加工，前者称为占用约束，后者称为顺序约束。 车间作业调度主要是针对一项可分解的工作( 如产品制造) ，探讨在 尽可能满足约束条件( 如交货期、工艺路线、资源情况) 的前提下，通过 下达生产指令，安排其组成部分( 操作) 使用哪些资源、其加工时间及加 工的先后顺序，以获得产品制造时间或成本的最优化。在理论研究中， 车间作业调度问题常被称为排序问题或资源分配问题或组合优化问题。 在过去的几十年晕，基于实际的及理论上的考虑，不断地激励着人们寻 找新的调度算法，其中一个重要原因是产品制造界的市场竞争性在不断 提高，好的生产调度能提高资源的利用率和操作管理水平，生产出具有 竞争力的产品。车间的调度优化工作，因其在提高生产效率，降低生产 成本等方面所起的重要作用，正越来越受到学者们的关注。 2 2 车间作业调度问题的分类和性能指标 车问作业调度问题常按生产方式的类型分为“开环车间型 ( o p e n s h o p ) ”和“闭环车间型( c l o s e d s h o p ) ”。前者可归结为工件的排 序问题，即对订单所要求的产品在每台机器上的先后加工排列次序，面 向顾客；后者既包括工件的加工顺序，也包括确定工件的批量大小，即 要确定与库存补充相关联的批量大小，面向库存1 1 4 j 。 根据工件在机器上的加工顺序的不同，车间作业调度问题也可分为 两种：非流水型0 s s p ) 和流水型( f s p ) 根据加工系统的复杂程度，可分为单机、多台并行机、f l o ws h o p ( f s p ) 和j o b s h o p ( j s s p ) 。 根据作业的加工特点，可将调度问题分为静态调度和动态调度。 车间作业调度中涉及的工厂资源包括：原料，设备( 加工、存储、 运输1 、人力、资金、能源等。资源的详细分配受到产品的生产工艺限 制。生产调度的性能指标可以使成本最低、库存费最少、生产周期最短、 生产切换最少、设备利用率最高、三废最少等。实际车间作业调度的性 能指标可以归结为三类i l 训： 1 撮大能力指标，包括最大生产率、在最短的生产周期等，他们都 可以归结为在固定或者无限的产品需求下，最大化生产熊力以提高经济 效益。在假定存在连续固定需求的前提下，工厂通过库存满足产品的需 求。因此，车间作业调度问题的主要目标是提高生产设备的利用率、缩 短产品的生产周期，使工厂生产能力最大。 2 威本指标，包括最大利润、最小的运行费用、最小投资、最大收 益等。其中收益指产品销售收入，运行费用包括库存成本，生产成本和 缺货损失。 3 客户满意度指标，包括最短的延迟，最小的提前或者拖期惩罚等。 2 3 车间作业调度问题的特点 本文通过参考相关文献【1 6 , 1 7 ，归纳出车问作业调度问题有以下八个 特点： 1 普遍性在现实应用中，尤其是中小型生产企业中是最为常见的 生产调度类型。 2 随机性车间调度中有很多随机和不确定因素，如工件到达时间 的不确定性，实际工件的加工时间也有一定的随机性。而且系统中常有 6 突发偶然事件，如机器出故障、作业交货期的改变等 3 复杂性车间中工件、机器、缓存和搬运系统之间相互影响、相 互作业。每个工件又要考虑它的加工时间、安装时间和操作顺序等因素， 因而相当复杂。调度问题是在等式或不等式约束下求指标的优化，在计 算量上往往是n p 难问题。随着问题规模的增大，其计算量急剧增加， 使得一些常规的方法无能为力。 4 动态模糊性车间环境是不断变化的，含有很多随机的和不确定 性的因素，包括工件的随机到达，交货期的变更及动态优先级和订单的 变化，生产能力的冲突和过载以及机器故障或紧急件插入，原材料的短 缺，操作人员的技能、操作熟练程度和因故缺勤等这就造成了调度的 动态性以及加工时间和交货期的模糊性。 5 多约束性车间作业调度中包含有多种约束情况。如：工艺约束、 资源能力约束、人力约束、零件交货期约束和产品齐套性约束等。车间 作业调度问题中资源的数量、缓存的容量、要求各机器上的负荷、工件 到期时间以及工件的操作顺序等都是约束 6 多目标性调度问题的目标很多，主要包括最小任务完成时间、 最小延迟时问、最小加工成本等。这些目标之间有的相互促进，有的相 互冲突，必须根据具体情况确定哪个目标优先，或者通过确定各个目标 在总目标中的权重来兼顾多个目标。k i r a r t a s e t a l ( 1 9 8 4 ) 将调度目标分 为三类：基于作业交货期的目标，基于作业完成时间的目标和基于生产 成本的目标，并列举了几十种调度目标。 7 可推广性其它的生产调度问题在某种程度上均可看作是它的 推广 8 可移植性它的研究成果对于生产领域以外的其它应用领域( 如 计算机技术、通讯技术和航天技术领域) 也常常是值得借鉴的。 正是由于车l 日j 作业调度问题具有以上的特点近年来，众多领域的 研究人员都对其产生了浓厚的兴趣，包括数学、机械、管理、计算机等 相关学科的学者，他们用不同的技术和方法对此进行了广泛、深入、细 致的研究，取得了丰硕的成果。本文就是在了解目前国内外车问作业调 度问题研究现状的基础上，综合比较分析现有的理论及方法，对车间作 业调度问题进行了进一步的研究和一些新的探索与尝试 2 4 车间作业调度问题的描述方法 法。 车间作业调度问题的描述方法主要有甘特图和析取图两种表示方 7 2 4 1 甘特图的表示 对于i l l 台机器：( m a c h i n e x m bm 2 ，m 。) ，n 个工件o o b x j l , 2 ，j n ) 的加工过程，分配各工件在各机器上的加工时间调度通常用甘特图表 示。甘特图( g a n t t c h i n ) 是在1 9 1 7 年由亨利甘特( h e n r y l a u r e n c e g a n t t ) 开发的。它基本上是一种线条图，横轴表示时间，纵轴表示要安排的活 动，线条表示在整个期间上计划的和实际的活动完成情况。甘特图直观 地表明任务计划在什么时候进行，以及实际进展与计划要求的对比。甘 特图使车间的计划安排情况一目了然，成为管理人员了解全局，安排车 间进度的有效工具。 以一个3 个工件3 个机器的j s s p 为例说明，表2 1 中每个括弧中 第一个数据表示工件在哪台机器上加工，第二个数据表示加工时间。图 2 】表示个可行调度，以甘特图表示。 表2 - 1 表示一个3 x 3j s s p 问题 m 2 m l 圈囝 田圈 o 24 6 rt 讯 b 图2 1 一个3 x 3j s s p ( 3 二i 件3 机器) 问题甘特图 8 2 4 ，2 析取图表示 析取图也是描述j s s p 的常用工具，对于n 个工件、m 台机器( 共n 个操作) 的j s s p 所对应的析取图g = ( v e ) 。其中，v 为所有操作构成 的顶点集，包括o 和n + i 两个虚拟操作( 分别表示加工开始和结束) a 为 n 条子边构成的边集，子边( 实线) 表示某工件按约束条件在所有机器上 从开始到结束的加工路径；e 为m 条子边构成的弧集，子弧( 虚线) 表示 同一机器上加工各操作的连接。表2 一l 中的3 x 3j s s p 问题的析取图表 图2 2 一个3 x 3 j s s p ( 3 工件，3 机器) 问题折取图 一实线表示加工路径 虚线表示同一机器上加工 2 5 车间作业调度问题的建模方法 在自然科学、工程技术和社会科学的许多颁域中，定量的系统分析、 系统综合己受到人们愈来愈多的重视。模型是开展这些工作的有效工 具，而模型化则是开展这些工作的前提和基础。车间调度问题的建模方 法很多，本文主要介绍数学分析的方法。 数学分析模型通常用数学关系式表达所研究系统变量之问的相互 关系。大多数分析模型是插述性的，即在一组条件下预测某一方案的各 种后果数值。有一类预测模型需要分辨出最优后果，即需求出最优解。 在车间优化调度中，就是要从多个调度方案中寻求满足约束条件和目标 的最佳调度方案寻求最优解的过程常称优化，这类数学模型称为优化 模型【l s l 。 作业车间调度( j s s p ) 研究n 个工件在m 台机器上的加工，已知各操 作的加工时i 、日j 和各工件在各机器上的加工次序约束，要求确定与工艺约 9 束条件相容的各机器上所有工件的加工开始时间或完成时间或加工次 序，使加工性能指标达到最优。下面简单给出一个调度问题常用的数学 描述。不失一般性，我们设作业调度应满足如下约束条件： 1 整个加工过程中，个工件不能在同一机器上加工多次； 2 任何一个工件的前一道工序加工完成后，方能进行后一道工序的 加工；在同一台机器上一个加工任务完成之后，方能开始另一个加工任 务； 3 各工件必须按工艺路线以指定的次序在机器上加工； 4 不考虑工件的优先权； 5 每个工件的工序一旦进行就不能中断； 6 一个工件同一时间只能在一台机器上加工，一台机器同一时间只 能加工一个工件； 7 每个工件相邻工序之间的间隔与所在加工地点有关，同一加工地 点问隔为零； 8 每个工件的每道工序的开工时间一定大于或等于零； 9 工序应尽量使用负荷低、空闲的设备； 1 0 工件的加工时间事先给定，且在整个加工过程中保持不变； 1 1 对工件进行外协加工或热处理时，属于资源无限，不考虑资源 竞争。 数学描述为： s tc i k - - t i k + m ( 1 一a i 曲 = ci h ，i = l ，2 ，n ；h ，k = l ，2 - - - , m ( 2 2 ) c i k - ti k + m ( 1 一x , j k ) = ti k ，i , j = l ，2 ，n ；k = l ，2 ，m ；( 2 3 ) c 止 = o 或者1 ，i ，j = 1 ，2 - - - , n ；k = l ，2 - - - , m ；( 2 4 ) 其中，式( 2 1 ) 表示目标函数，即要求最大完成时问最小化也叫 m a k e s p a n ：式( 2 2 ) 表示工艺约束条件决定的各种工件各操作的先后加 工顺序，保证每个工件的加工顺序满足预先的要求；公式( 2 3 ) 表示加 工各个工件的各机器的先后顺序，保证每台机器一次只能加工一个工 件。式( 2 1 ) ( 2 2 ) ( 2 3 ) ( 2 4 ) 中符号c i k 和t i k , 分别为i 件在机器k 上的完成时问和加工时间。m 是一个足够大的正数： 址和x i i k 分别 为指示系数和指示变量。其意义为： 小盛 机器h 先于k 加工工件i 其它情况 1 0 、，阻工件i 先于工件f 在机器k 上加工 “k 。1o ，其它情况 数学优化模型逻辑性强，能清楚地表示出复杂系统中的各种输入输 出变量以及较好地反映出多个变量之间的关系，并能实现系统的优化， 而且建模方便，是车间调度问题中应用较多的一种建模方法。 2 6 车间作业调度问题的研究方法和存在的问题 在对车间调度问题进行研究的方法上，最初是集中在整体规划、仿 真和简单的规则上，这些方法不是调度结果不理想就是难以解决复杂的 问题。随着各种新的相关学科与优化技术的建立与发展，在调度领域也 出现了许多新的优化方法，比如神经网络、模拟退火法、遗传算法、禁 忌搜索法等，使得调度问题的研究方法向多元化方向发展。 2 6 1 车间作业调度问题的研究方法 车间作业调度的研究方法是通过精确求解解析模型获得最优解，或 通过近似求解获得次优解。常用的研究方法主要由以下几种f 1 9 l ： 1 基于规则的研究方法 调度规则因其易于实现、计算复杂度低等原因，能够用于动态实时 调度系统中，许多年来一直受到学者们的广泛研究，并不断涌现出许多 新调度规则。m o n t a z e dm e t a l ( 1 9 9 0 ) 列举了常见的2 0 条规则，并针对一 个实际的j s s p ，分析了这些规则对系统性能如作业的平均等待时间、 机床的平均利用率、作业总加工时间等的影响。d o m d o f fu 。e t a l ( 1 9 9 5 ) 提出运用遗传算法选择规则的方法。c h a n g y , l e t a l ( 1 9 9 6 ) 使用线性规划 模型对4 2 条规则进行了评估，结果显示最短处理时间( s 啊规则性能最 好，而最长处理时问( u 田最差。p a n w a l k a r s e t a l ( 1 9 9 7 ) 总结了1 1 3 条规 则，并将它们分为了三类：简单规则、复合规则、启发式规则。a d a m s j e t a l ( 1 9 9 8 ) 提出了移动瓶颈方法。万国华( 2 0 0 1 ) 用模糊逻辑方法控制规 则的选择，表现出与人工智能结合的趋势。 2 基于知识的研究方法 近年来受实际需要的推动，基于知识的智能调度系统和方法的研究 取得了很大的进展。基于知识的调度方法是用专家系统自动产生调度或 辅助人去调度。它是将传统的调度方法与基于知识的调度评价相结合的 方法。 3 仿真研究方法 由于制造系统的复杂性，很难用个精确的解析模型来进行描述分 析。而通过对仿真模型的运行收集数据，就能对实际系统进行性能、状 态方面的分析，从而能对系统采用合适的控制调度方法。 4 基于人工智能( a i ) 的方法 人工智能的方法是通过提高调度方法的智能来解决各类生产调度 问题方法的总称。单一的数学方法和工具不足以解决实际的调度问题， 人工智能和专家系统的出现对解决调度的实时性和智能性提供了新的 辅助手段。它们用于调度可以克服数学规划和仿真方法的不足，根据系 统当前的状态和给定的优化且标，知识库进行有效的启发式搜索和并行 模糊推理机制，避开了繁琐的计算，并选择最优的调度策略，为在线决 策提供支持。在基于知识和规则的调度系统中，常用的知识表示法有产 生式规则、语义网络、框架等；常用的调度技术有生产规则、探试法搜 索、机会主义的推理、仿真和分级式的分解等。 5 具有计算智能的局域搜索法 近年来各种局部搜索算法在车间调度中得到了广泛的应用，这些局 部算法在优化机制方面存在一定的差异，但优化流程却具有较大的相似 性，均是一种“邻域搜索”框架。算法从一个( 一组) 初始解出发，在算 法参数的控制下通过邻域函数产生若干邻域解，按接受准则( 确定性、 概率性或混沌方式) 更新当前状态，然后按参数修改准则调节控制参数， 如此重复以上搜索过程直至算法终止准则满足，最终得到问题的优化 解。主要有以下几种方法： ( 1 ) 遗传算法( g a ) g o l d b e r s 首次将g a 应用到实际的工程系统的 优化当中。由于g a 原理和操作简单，通用性强，不受限制条件的约束， 且具有隐含并行性和全局解空间搜索能力，在机器学习、模式识别、控 制工程、优化等领域，尤其是在生产调度领域得到广泛的应用。如何利 用g a 高效求解调度问题，一直被认为是一个具有挑战意义的难题并成 为研究的热点，近年来涌现出大量论文并取得较大进展g a 的早熟和 搜索效率低问题是它的主要缺陷。 ， ( 2 ) 禁忌搜索( a s ) t s 是解决复杂组合优化问题的一种搜索策略 和方法，由g f o v c 等人提出、完善和发展。目前，t s 已在调度、交通 运输、t s p 问题、电子电路设计等诸多领域中得到应用。 ( 3 ) 模拟退火( s a )s a 可求得组合优化问题的最优或次最优解。 首次将s a 用于优化领域的是k i r k p a t r i c k ，他尝试了将s a 用于t s p 闯 题的求解。此外，s a 在j o bs h o p 和f l o ws h o p 问题中也得到了一定的 应用。 2 6 2 目前车间作业调度研究方法普遍存在的问题 调度领域中的大部分问题都具有n p 难问题，虽然对它的研究已有 几十年的历史，但至今尚未形成一套系统的方法和理论，理论研究与实 际应用之问还存在着很大差距。尤其随着j i t ( j u s t h 一币m c ) 思想的 广泛采用提前拖期( e f - - e a r l i n e s s t a r d i n e s s ) 调度问题，即使得工 件尽量按交货期完成，变得越来越突出。实际应用中的调度方法虽然能 够响应系统的动态变化，但不能保证得到好的调度例。 由于大多调度问题属于n p 困难组合问题，因此寻找具有多项式复 杂性的最优算法几乎是不可能的。各种近似启发式方法、诸如基于规则 的算法等，由于能在合理的时间内产生比较满意的调度，因此广泛应用 于实际调度中，但其往往对所得的调度解的次优性不能进行评估。在这 方面有必要探索更好的近似最优调度算法，可以考虑增加合理的计算时 间代价，提高解的次优性。各种基于统计优化的方法，诸如模拟退火法、 遗传算法等，提供了种解决调度优化问题的新途径，但同别的优化算 法类似，其本身也存在着一定程度的枚举，一般来说要收敛到最优解会 很慢，并且对于判断解的最优性也很困难。在这方面也需要做进一步的 研究。 大多数调度问题的理论研究还是集中在针对经典的调度问题设计 优化算法，而经典调度问题与实际相差较大。在实际车间调度中，车间 计划与车间调度往往是分层进行的，但这可能造成计划在实际调度中的 不可行问题，如何将计划与调度结合考虑，以求总体的优化也是需要进 一步研究的。另外，还有很多有待进一步研究的问题，比如实际车阃调 度的多目标性、动态随机性等。 2 7 本章小结 本章通过对车间作业调度系统的描述，介绍了车间作业调度问题的 分类，特点，描述方法，以及车间作业调度的假设条件，并重点讲述了 长久以来对车| b j 调度问题的建模方法，介绍了车间作业调度问题的研究 方法和调度策略。在所有的研究方法中遗传算法是被应用在车| 日j 作业调 度领域最多的方法。因此，本论文也重点研究遗传算法在车间作业调度 方面的应用，在本论文的后续章节中，主要将讨论如何基于遗传算法来 实现车间作业调度。 第三章遗传算法的理论研究 遗传算法( g e n e t i ca l g o r i t h m s ，简称g a ) 是一种借鉴生物界自然选 择和自然遗传机制的高度并行、随机、自适应搜索算法。它是模仿自然 界生物进化过程中“物竞天择，适者生存”的原理而进行的一种多参数， 多群体同时优化方法。 经过3 0 多年的发展，遗传算法己经在作业调度与排序、可靠性设 计、车辆路径选择与调度、成组技术、设备布置与分配、交通问题、数 据挖掘、函数优化、机器学习、图象处理等领域得到成功的应用，并显 示出其良好的性能f 2 l l 。本章将对遗传算法的形成和发展、基本原理、存 在问题、研究方向及应用进行探讨。 3 1 遗传算法的起源与发展 早在2 0 世纪5 0 年代和6 0 年代，就有几个计算机科学家独立的进 行了所谓的“人工进化系统”的研究，他们是利用进化的思想对实际的 工程问题进行优化。这些研究形成了遗传算法的雏形网。 8 0 年代，h o l l a n d 教授实现了第一个基于遗传算法的机器学习系统， 开创了遗传算法的机器学习的新概念。h o l l a n d 的学生b a 掣c y 在其博士 论文中首次提出了“遗传算法”一词，他发展了复制、杂交、变异、显 性、倒位等遗传算子，在个体编码上使用双倍体的编码方法。 1 9 7 5 年，d ej o n g 基于遗传算法的思想在计算机上进行了大量的纯 数值函数优化计算实验，树立了遗传算法的工作框架，得到了一些重要 且具有指导意义的结论。 1 9 8 9 年，g o l d b e r g 出版了 g e n e t i c a l g o r i t h mi ns e a r c h ，o p t i m i z a t i o n a n dm a c h i n el e a r n i n g ) ) - - 书，该书系统总结了遗传算法的主要研究成果， 全面完整地论述了遗传算法的基本原理及其应用。1 9 9 1 年，d a v i s 出版 了 h a n d b o o ko fg e n e t i ca l g o r i t h m s ) ) 一书，介绍了遗传算法在科学计 算、工程技术和社会经济中的大量实例。1 9 9 2 年，k o z a 将遗传算法应 用于计算机程序的优化设计及自动生成，提出了遗传编程( g e n e t i c p r o g r a n u n i n g 简称g p ) 的概念。从遗传算法的整个发展看，7 0 年代是兴 起阶段，8 0 年代是发展阶段，9 0 年代是高潮阶段。遗传算法作为一种 实用、高效、鲁棒性强的优化技术，发展极为迅速，已引起国内外学者 的高度重视【2 3 1 。 1 4 近年来，对于“遗传算法”的改进也有很多学者进行了大量研究， 不同的遗传基因表达方式，不同的遗传操作算子( 包括复制、选择和交 叉1 等等，但无论如何改进，其基本的指导思想都是来自于大自然中生 物进化的“适者主存”理论，所以可以将其归为一个“算法簇”可以 用进化计算来包容这样的遗传“算法簇”。分为遗传算法( g a ) ，进化规 划( e p ) ，进化策略( e s ) 和遗传程序设计( g p ) 。由于遗传算法研究热潮的 兴起，人工智能再次成为人们关注的焦点。有些学者甚至提出，进化计 算是人工智能的未来。目前、进化计算与人工神经网络、模糊系统理论 一起己成为新的研究方向计算智能。同样地，在车间作业调度领域， 基于遗传算法，甚至计算智能的研究也成为研究的热点。 3 2 遗传算法的基本思想 遗传算法是建立在自然选择和群体遗传学机理基础上的随机，选 代，进化，具有广泛适用性的搜索方法在遗传算法中最重要的概念是 染色体，染色体通常是一串数据( 或数组) ，用来作为优化问题的解的代 码，其本身不一定是解。这些染色体在后续迭代中不断进化，称为遗传。 在每一代中用“适值( f i t n e s s ) ”来测量染色体的好坏。生成的下一代染 色体称为后代( o f f s p r i n g ) 。后代是由前一代染色体通过杂交( c r o s s o v e r ) 或者变异( m u t a t i o n ) 运算形成的。据此，经过若干代之后，算法收敛于 最好的染色体，它很可能就是问题的最优解或次优解。 3 2 1 遗传算法的理论基础 遗传算法模拟的是自然界生物优胜劣汰的进化过程，在迭代处理过 程中，群体一代代的得以优化并逐