（机械电子工程专业论文）遗传算法在车间优化调度中的应用研究.pdf

遗传算法在车间优化调度中的应用研究 摘要 车间调度是调度问题的一个重要内容，它是指在生产过程中对共同使用的 资源实行时间分配从而达到某一最优目的。在调度问题中，存在许多优化决策 问题，车间调度作为制造型企业必不可少的环节之一，其合理的车间调度方案 对提高企业的生产效率具有重要意义，不仅能够有效地降低设备的空置率，缩 短产品生产周期，并且还能降低生产成本和增加经济效益。根据车间调度中工 件的工艺路线，车间调度有作业车间调度和流水车间调度之分。在大量的制造 型企业中，往往存在着大量的生产车间，因此，对车间优化调度配置问题的研 究具有重要的现实意义。 同时车间调度问题作为一个n p ( n o n d e t e r m i n i s t i cp o l y n o m i a l 多项式复杂 程度的非确定性问题) 难题，随着需要加工的工件数和机器数量的增加，可选 调度方案数量将以指数速度急剧增长。因此，用遗传算法求解该问题就成为人 们研究的一个重要方向。本文将在建立车间调度问题数学模型的基础上，研究 采用遗传算法对其求解。 本文围绕基于最大完成时间为目标的车间调度问题开展研究，主要做了以 下工作： ( 1 ) 本文分析了作业车间调度问题的数学模型，并在此基础上对作业车 间调度问题的特例流水车间调度问题也建立了数学模型； ( 2 ) 本文采用遗传算法来解决车间优化调度问题，同时针对作业车间和 流水车间两种调度问题分别给出了采用遗传算法解决车间优化调度问题的算 法模型和实现过程； ( 3 ) 对遗传算法的优化特性进行了分析，并在s g a ( s i m p l eg e n e t i c a l g o r i t h m s ，基本遗传算法) 的基础上对遗传算法进行了一定的改进； ( 4 ) 对本文提出的解决方法进行了试验计算，并分析了基本遗传算法和 改进后遗传算法各自的特点。 关键词：作业车间调度，流水车间调度，遗传算法，优化问题 t h er e s e a r c ha n da p p l i a n c eo fg e n e f i ca l g o r i t h mi ns o l v i n g t h ew o r k s h o ps c h e d u l i n gp r o b l e m a b s t r a c t w o r k s h o ps c h e d u l i n gi sa ni m p o r t a n tc o n t e n ti nm o d e ms c h e d u l i n gp r o b l e m i tm e a n st oa c h i e v eab e s tg o a lo ft h ed i s t r i b u t i o nw h i c hs i l f f i e e st h ec o m m o n r e s o u r c et of i tt i m er e q u e s ti nt h em a n u f a c t u r e p r o c e s s e s t h e r o a r e m a n y d e c i s i o n - m a k i n go p t i m i z a t i o n si nt h es c h e d u l i n gp r o b l e m ；q u ao n eo fn e c e s s a r yp a r t , a n i c e rw o r k s h o ps c h e d u l i n gs y s t e mh a sa l li m p o r t a n ts i g n i f i c a n c et oi m p r o v ep r o d u c t e f f i c i c i l c y s c h e d u l i n gs y s t e mi sn o to n l yr e d u c i n gv a c a n c ya n dc o s to fe q u i p m e n tb u ta l s o s h o r t e nl i f e c y c l eo fp r o d u c ta n de n h a n c i n gb e n e f i t b a s e do nt e c h n i c a lr o u t e ，w o r k s h o p s c h e d u l i n gp r o b l e md i v i d ei n t ot w op a r t s ：j o bs h o ps c h e d u l i n ga n df l o ws h o ps c h e d u l i n g p r o b l e m a m o n gt h el a r g e s c a l em a n u f a c t u r i n ge n t e r p r i s e ，t h e r ee x i s t sm a n ys h o p s ，a n d t h e r e f o r et h i sp a p e rh a sb o t ht h e o r e t i c a la n dp r a c t i c a lv a l u e a san p - h a r dp r o b l e m , t h ej o bs h o ps c h e d u l i n ga n df l o ws h o ps c h e d u l i n gp r o b l e m w i ui n c r e a s ee x p o n e n t i a l l ya l o n gw i t ht h ea d d i n go fj o ba n dm a c h i n en u m b e r s s oi t b e c o m e sa l li m p o r t a n ts t u d y i n gt r e n dt os o l v et h ew o r k s h o ps c h e d u l i n gp r o b l e mw i t h g e n e t i ca l g o r i t h m o nt h eb a s i so f b u i l d i n gt h em o d e lo f j o bs h o ps c h e d u l i n ga n df l o ws h o p s c h e d u l i n gp r o b l e m , t h i sp a p e r s t u d i e st os o l v et h ep r o b l e mw i t hg e n e t i ca l g o r i t h m f o c u s i n go nw o r k s h o ps c h e d u l i n gp r o b l e m ，t h i sp a p e rm a i n l yi n c l u d e st h en e x t c o n t e n t s ： ( 1 ) t h i sp a p e ra n a l y s e st h em o d e lo fj o bs h o ps c h e d u l i n gp r o b l e m , b a s e do nt h i s a n a l y s i sa n dc o m b i n e se s p e c i a l l ye x a m p l eo fj o bs h o ps c h e d u l i n gp r o b l e m , t h i sp a p e r i n t r o d u c e st h em o d e lo ff l o ws h o ps c h e d u l i n gp r o b l e ms o l v i n gw i m g e n e t i ca l g o r i t h m ； ( 2 ) t h i sp a p e ra d o p t sg e n e t i ca l g o r i t h mt os o l v ej o bs h o ps c h e d u l i n gp r o b l e m a tt h e 韶l n l et i m ec o m p a r i n gt h et w op r o b l e m s ，t h i sp a p e ri n t r o d u c e st h ee a c hm o d e lo f j o bs h o p s c h e d u l i n ga n df l o ws h o ps c h e d u l i n gp r o b l e ms o l v i n gt h eg e n e t i ca l g o r i t h m ( 3 ) a l s ot h i sp a p e ra n a l y s e st h ef u n c t i o no fg e n e t i ca l g o r i t h m ，a n di m p r o v e st h e g e n e t i ca l g o r i t h mb a s e do ns i m p l eg e n e t i ca l g o r i t h m ( 4 ) d or e s e a r c ho nt h em o d e l si n t r o d u c e db yt h i sp a p e r , a n da n a l y s e st h es i m p l e g e n e t i ca l g o r i t h ma n dm o d i f i e dg e n e t i ca l g o r i t l u n k e y w o r d s ：j o bs h o ps c h e d u l i n g ，f l o w s h o ps c h e d u l i n g ，g e n e t i ca l g o r i t h m , o p t i m i z a t i o np r o b l e m 插图清单 图卜l 调度算法的分类2 图2 13 3 机器调度g a n t t 图7 图3 - 1 标准算法框图1 8 图4 1 基于工序的活动调度g a n t t 图3 0 图4 2 基于工序的半活动调度g a n t t 图3 0 图4 3 基本遗传算法的运算过程3 6 图4 - 4 双倍体自适应遗传算法流程图4 2 图4 56 6 g c b l a x 基本遗传算法活动调度图4 4 图4 66 6 g c m a x 双倍体自适应遗传算法活动调度图4 5 图5 1 多种群遗传算法求解f l o ws h o p 调度流程图5 l 图5 2c a r 7 类调度问题的甘特图5 3 表格清单 表2 - 13 3 j c m a x 加工数据描述7 表4 - 1 染色体解释表2 9 表4 26 6 g ，c m a x 基本遗传算法加工过程表4 4 表4 - 36 6 g c m a x 双倍体自适应遗传算法加工过程表4 6 表5 - ic a r 7 类调度问题加工时间表5 2 表5 2c a r 7 类调度问题加工过程表5 4 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果。也不包含为获得 金照王些去堂 或其他教育机构的学位 或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示谢意。 学位论文作者签名：乍参兹白 签字日期：6 7 年月2 ，日 学位论文版权使用授权书 本学位论文作者完全了解金匹王些盔堂有关保留、使用学位论文的规定，有 权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借 阅。本人授权金胆王些盔堂可以将学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位- 砖套 签字日期：回年丘月8 日 i 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签名：亏长矗 签字日期：7 年月谚日 | 电话： 邮编： 致谢 本论文是在导师张建军教授的悉心指导下完成的。论文的选题、架构以及 写作等方面无不凝聚着张老师的心血。两年多来不论是学习上还是生活上张老 师都给予我了极大的关怀和帮助，使我顺利完成了硕士研究生阶段的学习。我 所取得的每一点成绩都倾注了张老师的大量心血。张老师渊博的知识、严谨的 治学态度、敏锐的学术洞察力以及实事求是、勇于创新的科研精神是我终生学 习的楷模。在此，谨向张老师致以最衷心的感谢和最崇高的敬意! 衷心感谢两年多来一直给予我帮助的张利教授，她有真诚待人的胸怀，两 年多来一直给予我关心、理解和支持；衷心感谢洛阳轴研所吴宗彦教授、王景 华教授在课题研究上给予的支持与帮助；衷心感谢王跃飞、刘征宇、毕翔师兄， 感谢他们对我研究生期间的工作给予的支持和鼓励；衷心感谢和我共同奋斗将 近三年的同学：徐娟、韩煜、张建昌、吴健、赵斌、姚奋超、陆军、任启乐、 毛忠军，他们真诚友善、在我需要帮助的时候都无私的伸出了友谊之手，和他 们愉快的相处和合作令我终身难忘。 我要特别感谢我的父母，感谢父母双亲给我的支持和鼓励，但愿此文能够 给他们送上一份欣慰。 最后，向百忙之中评阅拙文的各位专家、教授致以衷心的感谢，并诚挚地 希望各位专家、教授给予批评指正! 再次向所有教导我、关心我、帮助我、鼓励我的老师、亲人和朋友致以深 深的谢意! 作者：段培勇 2 0 0 7 年4 月 第一章绪论 i i 研究背景和意义 在当代经济环境下，市场的发展与变化促使了传统生产方式的变革，制造 业面临着巨大的压力，以较低的生产成本和较短的生产周期开发更多的新产品 才能满足激烈的市场竞争需要。与此同时，随着科学技术的发展，生产规模越 来越大，复杂程度越来越高，对企业管理和生产过程的合理安排有了更高的要 求。车间作为生产过程的最基本单元，车间调度利用已有的资源，通过实现满 足某种约束条件( 如加工工序、所需机器等) 从而达到某一最优目的。 车间调度是制造系统的一个研究热点，他不仅是一个典型的n p 难题，也 是至今为止所有组合优化问题中最难问题之一，所以得到了广泛的关注。车间 调度是生产管理的核心内容和关键技术，科学制定车间调度方案对提高企业的 生产效率具有重要意义，不仅能够有效地降低设备的空置率，缩短产品生产周 期，并且还能降低生产成本和增加经济效益。 早在2 0 世纪5 0 年代初就有很多关于调度问题的研究文献。在计算机出现 以前，作业车间调度问题( j o bs h o ps c h e d u l i n gp r o b l e m ，简称为j s p ) 是用手工 计算完成的。但是由于问题本身复杂、计算量大、手工操作可靠性差、调度方 案优化性能不好，跟不上产品的多变性要求又容易受随机因素的干扰，使资源 和生产能力得不到充分的发挥和利用，车间生产效率不高。 随着计算机信息技术的发展，车间调度问题也没有得到很好的解决，因为 问题的规模和实时性要求也在不断提高。现在大多数学者和研究人员把研究重 点放到了“近似方法”上，如随机局部搜索方法。尤其是对于大规模的问题， 在有限的时间内找到一个可以接受的近似最优解成为当前调度问题研究的一 个焦点。 1 2 车间调度问题研究进展 调度问题最早出现在2 0 世纪5 0 年代，由于该问题的实用性和重要性，随 之在运筹学和工业工程学等学科中形成一个独立的分支方向。调度问题的核心 是模型和算法，前者涉及到问题建模、调度规则和目标函数等，后者则包括问 题可解性、计算复杂性和有效算法等【9 1 。 在6 0 年代，人们就开始对j s p 进行研究。g i f n e r 和t h o m p s o n 6 】在1 9 6 0 年提出了用于生产调度的优先分派规则方法。o e r ew s 【7 i 在1 9 6 6 年提出了用 于作业调度问题的一组基于优先分派规则的启发式算法。b a l a s s 】在1 9 6 9 年第 一个使用基于析取图( d i s j u n c t i v eg r a p h ) 的枚举方法来处理机器的调度问题。 通常，车间调度问题的约束条件数目很大，使j s p 成为一个非常难解的组合问 题。流水车间调度问题( f l o ws h o ps c h e d u l i n gp r o b l e m ，以下简称f s p ) 贝o 是具有 更严格条件的j s p 特例。尽管相对j o bs h o p 调度而言，f l o ws h o p 的工艺约束 条件比较简单，但它仍然是一个非常复杂和困难的组合优化问题，其中n p 难 题特性和强大的工程背景使其一直成为理论界和工程领域研究的热点问题。 j o h n s o n 在1 9 5 4 年的文献中 5 1 ，研究了n 个工件两台机器的f l o ws h o p 调度问 题，提出了工件排序的j o h n s o n 规则，在此基础上，其它研究人员探讨了所3 的f l o ws h o p 调度问题，并证明了f l o ws h o p 调度问题是n p 难题，人们为了得 到一个理想解决该问题的方法，就一直不断地对该问题进行研究，从而产生了 各种各样的用于求解该问题的方法。现在已有许多用于求解车间调度的最优化 方法被提出，包括分支定界法、枚举方法、构造性方法、邻域搜索方法、人工 智能方法等。图1 一l 归纳了求解调度问题算法的分类。但由于问题本身难度 很大，多数现有的最优化算法只适应于规模较小的问题。 分 支 定 界 作业车间调度问题( j o bs h o ps c h e d u l i n gp r o b l e m ) 枚 卷 方 法 数 学 方 法 优 先 分 配 规 则 构 造 性 方 法 插 入 方 法 领 域 搜 索 算 法 迭 代 改 进 法 遗 传 算 法 禁 忌 搜 索 巢 分 区 变 邻 域 搜 索 噪 吉 方 法 神 经 网 络 专 家 系 统 图1 1 调度算法的分类 工业界依靠经验或者计算机模拟生成可行调度，这样得到的可行调度不能 保证最好的性能。从根本上说，评价调度算法的性能很困难，因为获取规模很 大且最优调度已知的测试问题本身就很困难，遗传算法( g e n e t i ca l g o r i t h m ) 在车间调度上的应用，是近年来才发展起来的研究方向，对复杂工业过程的建 模、控制和优化领域的研究有十分重要的意义，f l o r i d a 大学的j e b i e g e l 和 2 人工智能方法王 蚁群系统 j j d a v e r n 最早于1 9 9 2 年提出了“用于车间作业调度的遗传算法”，此后， 越 来越多的人把目光投向这一领域。 1 3 本论文的研究意义及内容 产品生产周期一般包括概念设计、制造、销售以及回收几个阶段，制造作 为产品生命周期的一个重要阶段，完成了从概念设计到真正产品的一个重要转 变。车间调度作为协调、管理产品制造这一过程的一个重要手段，对于提高企 业的生产效率具有重要的作用，一个优良的车间调度方案，不仅能够缩短生产 周期，提高设备的利用率，而且能降低生产成本和库存，使产品能够按照计划 的要求准时、按质加工，并以经济的成本生产出来，实现生产管理的科学化和 规范化，从而提高了其快速响应对市场需求的能力。上世纪九十年代以来，计 算机通信技术及市场经济的发展使得市场需求的变化日趋频繁，因而寻求一种 有效的车间调度建模方式对其进行建模，并进行车间调度显得尤为必要和重 要。 因此，本文把研究重点放在了利用改进的遗传算法来求解作业车间调度和 流水车间调度问题上，并着重于遗传算法的应用和对车间调度问题效率上的提 高。在遗传算法和车间调度知识掌握的基础上，提出了基于遗传算法的车间调 度问题模型。 本文提出的求解模型针对遗传算法经常出现的“早熟”和“近亲繁殖”现 象，进行了一定的改进，通过这种改进，能够提高算法的收敛性，并且提高了 解的质量和算法获得全局最优解的能力。在算法的操作算子选择上，本文除了 对利用基本遗传算法求解车间调度问题进行了详细分析外，还针对操作采用了 演化策略，即采用了双倍体和多种群的概念，使得算法的遗传操作尽量贴近实 际问题的表示。同时，针对遗传操作算子的缺陷改进了操作算子，当出现早熟 时，即种群中各个体趋于一致或者局部最优解时，能够自动增大交叉和变异概 率，使其避免早熟现象，在各个体较分散的情况下，自动减小交叉和变异概率， 选择适应度较高的个体优先进入下一代，以有利于较优个体的生存。 在车间调度具体问题上，本文抽象成了比较常见的数学模型，该模型符合 一般的工艺约束条件。在本文的最后给出了算法针对实际问题的计算机模拟结 果。 1 4 论文的结构框架 遗传算法是一种仿生的随机搜索寻优方法，模仿生物界的优胜劣汰、适者 生存的进化规则，现已陆续应用到组合优化、人工智能等多个领域。本文研究 了采用遗传算法来解决车间优化调度问题。 第一章：介绍了本文的研究背景和意义，同时对车间调度的研究进展和基本内 容进行了简单的概括； 第二章：详细介绍车间调度问题。主要论述了车间调度的分类及特点，并 对工件加工数据和调度特性进行了描述，以及现阶段调度问题研究方法的介 绍： 第三章：介绍了遗传算法。论述了遗传算法的原理、数学模型、特点和算 法步骤；对算法的优缺点进行了分析，最后介绍了算法的研究进展； 第四章：该章是本文的一个重点，主要介绍了遗传算法求解作业车间调度 问题。本章首先建立了作业车间调度的数学模型，并对作业车间调度问题进行 了编码设计、遗传操作设计以及适应度函数确定。分析了基本遗传算法求解和 改进的遗传算法一一双倍体自适应遗传算法求解的模型，并进行了试验计算； 第五章：本章对流水车间调度问题建立了数学模型，采用了多种群遗传算 法求解流水车间调度问题，对该算法进行了编码设计，遗传操作等，最后对该 算法进行了试验计算； 第六章：主要对研究工作的总结以及对研究趋势的展望。 4 第二章车间调度问题模型及其描述 2 1 调度问题及其分类 2 1 1 调度问题基本描述 调度就是在产品过程中对共同使用的资源实行时间分配从而达到某一最 优目的。调度任务的产生在于多项任务共享特定的资源，而有限的资源却无法 以相对各个单独任务的最优状态同时满足所有任务的处理需求，同时需要寻求 一种优化其中一部分或者整批任务的某种处理性能指标。 调度问题的核心问题之一就是对其进行建模，由于系统建模方法的多样 性，以及问题的侧重点不同，调度方法和研究对象也有明显不同，就对象而言， 有确定性和随机性调度、离散事件和连续事件调度、静态和动态调度等。就调 度方法而论，有g a n t t 图法、构造型方法、动态规划、分支定界法、排队论方 法、规则调度方法和仿真方法等。调度的优化指标包括正规性能指标和非正规 性能指标，常用的指标由最大完成时间、平均加工时间、平均延迟时间、生产 成本等。 车间优化调度问题则是调度问题的一个子集，具体说就是为了处理多项不 同的作业而决定如何分配作为各作业共同资源的生产设备，并使生产系统的某 些性能指标达到最优或较优，从而帮助企业最大限度地实现生产效益。 一般情况下，车间调度问题是一类n p 完备的组合优化问题，因而实际研 究时必须做适当的抽象与简化，从而把复杂问题分解为多个简单问题以便于研 究。 2 1 2 调度问题分类 目前在实际的车间调度系统中，没有考虑资源的分配，一般都直接将资源 作为约束处理。因此对车间调度问题的研究，不仅要考虑工件的最大完成时间 c 峨( m a k e s p a n ) 、最大拖后时间k 、还应该使机器设备的平均空闲时间，最短 等性能指标。所以，车间调度问题是一个典型的多目标、多约束的组合优化问 题。 车间优化调度问题按生产方式、机器、工件和目标函数等的不同分类标准， 可分为如下几类。 1 从生产方式上来说，车间优化调度问题可分为开环车间( o p e ns h o p ) 型和闭 环车间( c l o s e ds h o p ) 型。开环车间调度问题也称加工排序问题，它只研究工 件的加工顺序，也即来自客户的订单上所要求的产品在所有机器上的加工 顺序，不考虑库存的设立i 而闭环车间调度问题则较开环车间调度问题来 说更为复杂，它除了研究工件的加工顺序之外，还涉及产品批量大小的设 置，也即在满足工艺约束的条件下寻找一个调度策略，使所确定的生产批 量和相应的加工顺序下的生产性能指标达到最优。 2 按加工系统的复杂程度，可以分成单台机器的调度问题、多台机器的调度 问题、作业车间( j o bs h o p ) 调度问题和流水车间( f l o ws h o p ) 调度问题。单台 机器调度问题是所有的操作任务都在单台机器上完成，因此存在任务的优 化排队问题。多台机器调度问题更为复杂，因而优化问题更为突出。对于 多台机器的调度问题，按工件加工路线的特征，可以分成j o bs h o p 调度问 题和f l o ws h o p 调度问题。若按照工艺要求，不同工件具有不同的加工顺 序，则称其为作业车间( j o bs h o p ) 调度问题；若按工艺要求，每个工件都有 相同的加工顺序，则称其为流水车间( f l o ws h o p ) 调度问题。 3 根据调度的性能指标来分，有基于调度费用和调度性能的指标两大类型。 调度费用包括为了实现调度方案所消耗的各种费用和所造成的损失，比如 运输费用、存储费用以及延期交货损失等。调度性能主要包括设备利用率、 最大完成时间、拖延加工任务的百分比等。虽然在理论分析上，大部分只 注意了调度的性能，但在实际生产中，通常要综合考虑费用和性能两方面 因素。 4 按照生产环境特点，可以将调度问题分为确定性调度和随机性调度。确定 性调度是指加工时间和其它参数是已知的和确定的量，而随机性调度则是 加工时间和有关参数是随机的变量。 5 根据作业的加工特点，可以将调度问题分为静态调度和动态调度。静态调 度是指所有待安排加工的工件在处于待加工状态时，经过一次调度后各作 业的加工时间即被确定，并且在以后的加工过程中也不再更改。而动态调 度是指各作业依次进入系统进行加工，同时完成加工的作业依次离开，考 虑到作业环境中动态扰动的出现，如作业加工超时、设备损坏等。因此动 态调度要根据系统中作业、设备的状况，不断的进行调整。在实际当中调 度的类型一般为j o bs h o p 调度问题型且为动态的 2 6 l 。 在大多数制造型企业中，车间加工系统为复杂的多台机器并行调度系统， 从其加工工艺路线上来考虑，j o bs h o p 调度问题和f l o ws h o p 调度问题均为研 究一个要完成的厅个工件0 0 b ) 力， ，每个工件以包含吩个操作 ( o p e r a t i o n ) q t ，”二q 抽f ，研究对象是由n 台机器( m a c h i n e ) 尬，”二 磊 加 工一个工件的一个加工次序。其中d l ，表示第，个工件在第，台机器上的操作，相 应的加工时间p f ，为已知。工件基于加工工艺所决定的限制在机器吖上的加工 顺序为约束条件，要求确定与技术约束条件兼容的各机器上所有工件的加工次 序，使加工性能指标达到最优。若各工件的技术约束条件相同，一个j o bs h o p 调度问题就转化为较简单的f l o ws h o p 调度问题。进一步，如果各机器上各工 件的加工次序也相同，则问题可进一步转化为置换f l o ws h o p 调度问题。 6 此外，j o bs h o p 调度性能指标中还经常涉及两种调度，即活动调度和半活 动调度。 称一个调度为活动调度，如果在不推迟其它操作或破坏优先顺序的条件 下，其中没有一个操作可以提前。 称一个调度为半活动调度，如果在不改变机器上的加工顺序的条件下，其 中没有操作可以提前。 通常用r d m a b 来表示基本调度问题，其中i , 表示工件数，m 表示机器数， 彳表示工件流经机器的类型( j o bs h o p 用g 来表示，f l o ws h o p 用f 来表示，置 换f l o ws h o p 用p 来表示) ，b 表示性能指标( 如最大完成时间c 螂、最多拖后 时间乙、平均空闲时间，等) 。 调度问题有多种描述形式，常见的有1 9 1 9 年由g a n g 提出的g a n t t 图表示法和 r o y e t a l 有向图模型，本文采用g a n t t 图描述车间调度问题。g a n t t 图是表示调度问题解 的常用方法，纵向表示机器或工件、横向表示时间，图中的方块用以表示工件的加工 工序。如表2 1 为3 个工件3 台机器的j o bs h o p 实例即，i 彤c 幺。该问题的一个可行 调度如图2 - 1 所示一个3 3 机器调度的甘特图。其中表中对应的每个工件的第一行表示 该工件每个工序加工所用的机器，第二行表示该工序在机器上的加工时间。 工序 工件 l2 3 m im 2m 3 j 1 3 32 m im ， m 2 j 2 153 m 2m lm 3 j 3 321 表2 - 13 3 j c 。加工数据描述 m l + 臣二二 二丁二互 14 6 t m ：+ 二三二二 丁二二 二1 二二口 图2 13 3 机器调度g a n t t 图 7 2 2 车间调度问题 2 2 1 工件加工数据和特性描述 在车间调度问题中，如果同一机器上既没有任意两个时间区间重叠，也没 有分配给同一个工件的任意两个时间区间重叠。且满足调度问题的一些特殊技 术约束，则称一个调度为可行( f e a s i b l e ) 调度。进一步则称使得满足调度准则或 指标最优的可行调度为最优调度。 通常，工件加工特性可用六元组p = p l ，p 2 ，p 3 ，p 4 ，p 5 ，1 3 6 ) 来表示，其中 d 2 ； 1 b l 用来表示加工方式，包括抢占式( p r e e m p t i o n ) 或非抢占式 ( n o n p r e e m p t i o n ) 。其中，抢占式加工中操作在加工过程中可以被打断。再 在原机器或别的机器上重新开始；非抢占式加工则一旦操作开始，直到加 工完毕，不能被其它加工打断，通常，记抢占式加工为p l = p m t n ，而非抢 占式加工则不在p 中出现p i 。 2 b 2 用来表示工件间的加工优先关系( p r e c e d e n c er e l a t i o n ) 。若调度问题不考虑 工件加工的优先权，则b 中不出现p 2 。 3 p 3 用来表示工件的准备加工时阊，如果= o ，贝i jp 中不出现p 3 ；妊果0 ， 则8 3 = 吒。 4 p 4 用来表示加工时间或者操作数量的限制。如果p 4 记作只= 1 ，则每个工件 有一次操作需求。 5 p 5 表示交货期信息。如果工件有交货期要求，则i b s = 碣，否则p 中不出现 b 5 。 6 d 6 用来表示批量信息，即工件是否成批联合进行加工。批量调度中，同批 的各工件的完成时间等于该批量的完成时间，假定各批量的加工设置时间 相同与加工顺序无关。若不考虑批量调度，则p 中不出现艮。 由于本文所讨论的j o bs h o p 和f l o ws h o p 调度问题具有特殊工件特性和加 工环境的最典型和最重要的调度问题，且是特殊的开环调度问题，鉴于这种重 要性、典型性和特殊性，通常将其称为基本调度问题，因此由n m a b 将其简 明表示，其中n 表示工件数，m 表示机器数，彳表示工件流经机器的类型( j o b s h o p 用g 表示，f l o ws h o p 用f 表示) ，b 表示下面介绍的性能指标。 2 2 2 调度问题的性能指标描述 由于j o bs h o p 具有代表性，以n 个工件、m 台机器的j o bs h o p 为例( 约定 调度问题为非抢占式，每个工件或者操作不能在同一台机器上多次加工，不考 虑工件加工优先权和批量) 给出调度性能指标。引入一些相关变m - t m + 合t 1 2 】。 工件以进行第，个操作的等待时问a m 工件以的总加工等待时间，即嵋= 坳。 j f f i ! m q 工件以加工完毕时间，则g = ，f + ( + 岛) 。 j = l e 工件z 的流经时间( f l o ws h o p ) ，即f = e 一。 厶工件以的推迟完成时间( 1 a t e n e s s ) ，即= q 一矾。 z 工件以完成的拖后时间( t a r d i n e s s ) ，即z = m a x l , ，o ) 。 e 工件完成的提前时间( e a r l i n e s s ) ，即目= m a x - 厶，0 。 胤 机器m 。的空闲时间，即= c 黼一，其 j = l c n = m a x c l ，c 2 ，“g ) ，m ，为机器鸩上加工的总数。 虬_ t 时刻处于等待状态的待加工工件数。 ，( f ) 一时刻正在加工的工件数。 札( ，) t 时刻已加工完毕的工件数。 虬( ，) t 时刻未加工完毕的工件数。 针对上述的相关参数，下面给出了调度问题的一些典型性能指标。 1 基于加工完成时间的性能指标： n 月 最大流经时间，总流经时间e ，加权流经时间m e ，平均流经 i f f i l，i l 时间f 。 最大完成时间c 一( m a k e s p a n ) ，平均完成时间石。 2 基于交货期的性能指标： 平均推迟完成时间z ，最大推迟完成时间l f f i , 。 平均拖后时间亍，最大拖后时间k ，总拖后时间n 巧。 i i 拖后工件个数唧( 完成时间晚于交货期的工件个数) 或拖后工件比例 9 n r n 。 3 基于库存的性能指标： 平均待加工工件数，。 平均未完成工件数。 平均已完成工件数。 平均正在加工工件数，。 平均机器空闲时间，。 最大机器空闲时间i m p , 。 4 多目标综合性能指标： 流经时间与总拖后时间的综合，如：i + 旯l ，其中五为权重。 m a k e s p a n 与总拖后时间的综合，即+ 五e t , 。 i - l 2 2 3 车间调度问题的特点 1 复杂性：车间中工件、机器和搬运系统之间相互影响、相互作用。每个工件 又要考虑它的加工时间、安装时间和操作顺序等因素，因而相当复杂。调 度问题是在等式或不等式约束下求得性能指标的最优化，在计算量上往往 是n p 完全问题，随着问题规模的增大，其计算量急剧增加，使得一些常规 的方法无能为力，对于这一点己经证明，即使对于单台机床加工问题，如 果有7 个工件而每个工件只考虑加工时间以及与操作序列有关的安装时间， 则这个问题就和月个城市的t s p 问题等价。对于一般加工系统，问题更复 杂。 2 随机性：车间调度中有很多随机和不确定因素，如工件到达时间的不确定 性，实际工件的加工时间也有一定的随机性。而且系统中常有突发偶然事 件，如机器发生故障、紧急加工任务下达、加工任务的改变等等。 3 约束性：车间调度问题中可用资源的数量、工件到期时间以及工件的操作顺 序等都是约束。此外还有一些人为的因素，如要求各机器上的负荷要平衡 等。 4 多目标性：调度问题涉及到了产品的交货期和成本等诸多因素，因此是一个 多目标决策问题，一般可以归结为两大类：第一类是基于时间的目标，主要 i o 包括任务的生产周期最短，完成日期与交货期最接近，任务在制造系统中 的总等待时间最短等；第二类是基于成本的目标，它主要考虑如何减少生 产过程中的资金占用和怎样合理利用资源，使各个生产环节负荷均匀，保 证生产的稳定性。 2 3 车间调度研究方法 车间调度问题一般来说都是对于具有生产环境中动态的、多目标的、复杂的调度 问题的简化和抽象，即使这样，该问题仍属于n p 完备问题中最困难的一种，难于求 得其精确解。因此人们一般研究其近似解，一个好的近似解也能满足实际使用要求。 车间调度问题的研究最初集中在仿真和简单规则上，但这些方法难于解决复杂的问 题。近年来，计算机信息技术与优化技术的发展，在车间调度领域出现了许多新的优 化方法，比如1 9 7 4 年g i l e t 和m i l l e r 2 0 1 提出的扫描法( s w e e pm e t h o d ) ：g l o v e r 在1 9 8 6 年提出了禁忌搜索算法这一概念 2 h ，进而形成一套完整算法； m e t r o p o l i s 在1 9 5 3 年 提出了模拟退火算法【2 3 】；意大利学者m d o d g o 等人首先提出了蚁群系统，并用于求 解t s p 问题【1 6 】；7 0 年代美国j h o l l a n d 教授和他的学生建立发展起来了遗传算法 2 2 1 。 这些算法的提出，使得车间调度问题的研究方法向多元化方向发展。总的来说，求解 车间调度问题的方法可区分为精确求解方法和近似求解方法。其中精确求解的方法包 括穷举方法、解析方法、数学规划法等；而近似求解的方法主要包括基于规则的构造 方法、智能搜索法等。 1 数学规划法 数学规划法是调度问题的精确算法，它通过对车间调度问题建立一个整数 规划模型，然后采用枚举方法寻求调度问题的最优解。 在枚举方法中，主要的枚举策略是分枝定界( b o u n da n db r a n c h ) 法，它的基 本思想是先求出对调度整数规划模型所对应的线性规划问题的最优解，如果该 解不满足调度问题的整数条件，则对应的线性规划问题的最优解必是调度问题 的目标函数值的上界，而调度问题的任意可行解的目标函数值则是其最优解的 下界，然后将对应的线性规划问题的可行域分成子域( 分枝) ，通过不断减少上 界和增大下界，最终寻找到最优解。分枝定界法的实现方法是动态构造一个表 示调度问题所有可行解的树，通过对树的搜索寻找调度问题的最优解。目前分 枝定界法的研究重点在提高分枝和定界的策略，各种不同的分枝定界方法的不 同点主要在于分枝规则、定界机制和上界产生三方面的差异。分枝定界法只适 合于小规模的调度问题，并且对实际问题比较敏感，因此限制了它在调度问题 上的应用。 此外，动态规划也广泛应用调度问题，它与分枝定界法一样，动态规划也 是只适用于小规模的调度问题【l 引。 2 启发式方法 该类方法能够快速建立问题的解，但是通常求出的解的质量比较差，否则 l l 的话需要建立复杂的启发式规则。 启发式算法( h e u r i s t i c s ) 是指一种基于直观或经验构造的算法，目标是在可 接受的花费( 计算时间、占用空间等) 下得出待解决问题的满意解，而不一定是 最优解。启发式方法中最具代表性的就是由c l a r c k 和w r i g h t 1 7 l 提出的节约法 ( s a v i n g m e t h o d ) ：典型启发式算法中还包括由l i n 和k e r n i g h a n ! ”l 提出的，并由 c h r i s t o f i d e s l l 9 】等人所推广的分支交换探索法。启发式算法主要有：启发式图搜 索法、基于启发式规则的调度算法和拉格朗日松弛算法。 基于启发式规则的调度算法是最早的近似算法，通过对每一个生产任务和 操作赋予优先等级，使得优先级高的生产任务和操作可以优先进行考虑。也是 基于其具有简单、易于实现和计算复杂程度比较低的特点，该调度规则在调度 问题上得到了广泛的应用，并且不断有新的调度规则产生。大体上分为三类， 分别为简单规则，复合规则和启发式规则，其中简单规则有三十多条，例如先 进先出规$ 1 ( f i r s ti nf i r s to u t ，f i f o ) 、最短处理时间( s h o r t e s tp r o c e s s i n gt i m e ， s p t ) 、交付期最早( e a r l i e s td u ed a t e ，e d d ) 等经常使用的规则，其它规则基本 上都是简单规则的组合或者说加权组合。该调度规则的缺点在于精度不够高， 尤其是在单纯使用简单规则的情况下。 拉格朗日算法由于它在可行的时间内能对复杂的规划问题提供较好的次 优解，并能对解的次优性进行定量评估，这是近年来解决复杂调度问题的一种 重要方法。但是拉格朗日算法对偶问题存在搜索效率低的缺点。 3 智能搜索方法 o l o v e r 在1 9 8 6 年提出的禁忌搜索算法、m e t r o p o l i s 在1 9 5 3 年提出的模拟退火算 法、意大利学者m d o f i g o 等人提出的蚁群系统、7 0 年代美国j h o l l a n d 教授和他的学 生建立发展起来了遗传算法以及神经元网络算法等被广泛应用于生产调度问题，并且 取得了良好的效果，这些算法原理都是在模拟自然界的某些演化机制的基础上建立 的。 3 1 遗传算法 遗传算法( g e n e t i ca l g o r i t h m ，以下简称o a ) ，它是1 9 7 5 年j h o l l a n d 教授 受生物进化论的启发提出的一种算法。遗传算法基于“优胜劣汰、适者生存” 策略，通过其“染色体”种群一代代的不断进化，包括选择、交叉、变异操作， 最终收敛到“最适应环境中”的个体。g a 作为一种通用的优化算法，其编码 技术和遗传操作较为简单，优化过程不受限制性约束条件