（计算机应用技术专业论文）基于累计设备空闲时间段的调度算法研究.pdf

哈尔滨理工人学工学硕1 j 学位论文 基于累计设备空闲时间段的调度算法研究 摘要 由于信息技术的迅速发展、客户需求的多样化及经济的全球化，大规模资 源的调度优化成为制约生产发展的重要因素。实际中调度问题逐渐向调度对象 复杂，约束条件复杂的方向发展。复杂产品调度就是在以上发展中产生的一种 调度形式。因此，研究复杂产品调度问题具有重要的理论和实际意义。 复杂产品调度主要是指工件间有约束关系的调度问题，与传统工件间无约 束的调度问题相比，调度对象更复杂，约束条件更多。复杂产品工艺树模型中 包含装配和加工两种工序，把装配和调度结合起来调度扩展了调度研究领域。 本文通过对复杂产品调度中设备空闲时间段的分析，提出根据复杂产品调 度时设备空闲时间段累计长度的大小确定复杂多产品调度次序的调度算法。该 算法由于优先安排空闲时间段短的产品，使产品调度结果比拟关键路径法更紧 凑，提高了设备利用率，实现整体调度空闲时间的缩短。 由于复杂多产品调度是按次序进行的，如果只根据一次产品调度时设备空 闲时间段累计长度的大小确定复杂多产品调度次序，便没有考虑后调度产品的 调度环境，缺少对累计空闲时间段动态变化的考虑，为此，提出动态计算累计 空闲时间段算法。通过算法分析和实例验证，本文提出的算法不仅容易实现， 而且效果更好。 关键词复杂多产品；工艺树模型；拟关键路径法；空闲时间段；调度算法 哈尔滨理工大学- 学硕士学位论文 as c h e d u l ea l g o r i t h mb a s e do nc u m u l a t i n gi d l e - t i m e p a r t i t i o n so fm a c h i n e a b s t r a c t w i t hi n f o r m a t i o nt e c h n o l o g yd e v e l o p i n gr a p i d l y , c u s t o m e rd e m a n dc h a n g i n g r a p i d l ya n dt h ee c o n o m i cg l o b a l i z a t i o n ，h o wt os c h e d u l eh u g er e s o u r c ew e l lb e c o m e s a ni m p o r t a n tp r o b l e mt oe c o n o m yd e v e l o p m e n t i nr e a l i t y , s c h e d u l i n gp r o b l e m t r e n dt ob et h ea s p e c tw h i c hh a sc o m p l e xo b j e c t sa n dc o m p l e xc o n s t r a i n s c o m p l e x p r o d u c ts c h e d u l i n gp r o b l e mi sg e n e r a t e df r o mt h i ss i t u a t i o n s o ，r e s e a r c ho nc o m p l e x p r o d u c ts c h e d u l i n gp r o b l e mh 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 ga n dp r a c t i c a lv a l u e c o m p l e xp r o d u c ts c h e d u l i n gp r o b l e mi st h es c h e d u l i n gp r o b l e mw h i c hh a s c o n s t r a i n sb e t w e e nj o b s c o m p a r e dt ot h et r a d i t i o n a ls c h e d u l i n gp r o b l e mh a sn o c o n s t r a i n sb e t w e e nj o b s ，t h es c h e d u l i n go b j e c t sa r em o r ec o m p l e xa n dh a v em o r e c o n s t r a i n s c o m p l e xp r o d u c t st r e em o d e lc o n t a i n so p e r a t i o n sa n da s s e m b l e sw h i c h e x p a n d st h es c h e d u l i n gr e s e a r c ha r e a t h r o u g hs t u d i e dt h eu s eo fi d l e - t i m ep a r t i t i o n si nc o m p l e xp r o d u c t ss c h e d u l i n g p r o b l e m ，a s c h e d u l i n ga l g o r i t h mc o n f i r m st h ep r o c e s s i n gs e q u e n c eo fc o m p l e xm u l t i - p r o d u c tb yc a l c u l a t i n gt h ec u m u l a t i v el e n g t ho fi d l e t i m ep a r t i t i o n so nt h em a c h i n ei s p r o p o s e d t h ea l g o r i t h ma r r a n g e sc o m p l e xp r o d u c tw i t hs h o r t e ri d l e - t i m ef i r s t l yb y c o m p a r i n gt h ec u m u l a t i v el e n g t ho fi d l e - t i m ep a r t i t i o n sw h i c ha r ep r o d u c e da f t e r p r o d u c t sa r ep r o c e s s e d ，m a d et h es c h e d u l i n gr e s u l tm o r ec o m p a c tt oa l l i e dc r i t i c a l p a t hm e t h o d ，i m p r o v e dt h ee f f i c i e n c yo fe q u i p m e n t sa n ds h o r tt h ew h o l es c h e d u l i n g i d i e t i m e b e c a u s ec o m p l e xm u l t i - p r o d u c ta r es c h e d u l i n gb ys e q u e n c e ，i fd e t e r m i n et h e c o m p l e xm u l t i p r o d u c t s c h e d u l i n gs e q u e n c eb yo n l yo n et i m ec o u n tt h el e n g t ho f i d l e t i m ep a r t i t i o n so nt h em a c h i n e ，i td o e s n tc o n s i d e rt h ec h a n g eo ft h es c h e d u l i n g e n v i r o n m e n t ，a l s od o e s n t c o n s i d e rt h ed y n a m i cc h a n g eo ft h et o t a li d l e t i m e p a r t i t i o n s an e ws c h e d u l i n ga l g o r i t h mw h i c hc a l c u l a t e st h et o t a li d l e - t i m ep a r t i t i o n s - i i 哈尔滨理工人学t 学硕l ：学位论文 d y n a m i c a l l yi sp r o p o s e d i ts h o w s t h a tt h ea l g o r i t h m st h i sp a p e rp r o p o s e dn o to n l yb e e a s yt or e a l i z eb u ta l s oc a no b t a i nb e t t e rr e s u l t st h r o u g ha n a l y z ea n de x p e r i m e n t s k e y w o r d sc o m p l e xm u l t i p r o d u c t ，t r e em o d e l ，a l l i e dc r i t i c a lp a t hm e t h o d ，i d l e t i m e p a r t i t i o n ，s c h e d u l i n ga l g o r i t h m i i i 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文基于累计设备空闲时间段的 调度算法研究，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期间 独立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含 他人已发表或撰写过的研究成果。对本文研究工作做出贡献的个人和集体，均 已在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签名：胡火靶日期：研年；月归日 哈尔滨理工大学硕士学位论文使用授权书 基于累计设备空闲时间段的调度算法研究系本人在哈尔滨理工大学攻 读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归哈尔 滨理工大学所有，本论文的研究内容不得以其它单位的名义发表。本人完全了 解哈尔滨理工大学关于保存、使用学位论文的规定，同意学校保留并向有关部 门提交论文和电子版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学可 以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部分内 容。 本学位论文属于 保密口，在年解密后适用授权书。 不保密西 ( 请在以上相应方框内打4 ) 作者签名：龋、) 、搀 导师签名： 咐叫参 日期：枷1 年弓月日 日期：洌穸年岁月劢日 哈尔滨理工大学t 学硕一 = 学位论文 第1 章绪论 1 1 课题研究的目的和意义 调度问题是对生产过程的作业计划，具有很强的实际背景，它最早是在制 造业中提出来的，后来广泛应用于计算机系统、运输调度、生产管理领域。在 生产计划领域中，调度主要是用于调配资源、合理安排作业顺序，在满足现有 生产条件下，使生产成本最小。调度的质量可用不同的目标函数( 如考虑时 间、费用等目标) 来度量。所以，调度( s c h e d u l i n g ) 问题有时候也称为排序 ( s e q u e n c i n g ) 问题。而合理的调度方案能够给企业带来巨大的经济效益。调 度是一个多目标、多约束的优化问题，通常是n p 完全问题。不同的生产环 境其调度方案是不同的，不存在通用的调度方案，生产环境是动态变化的，因 此调度问题的解决不能单纯依靠人和计算机，必须把人、人工智能技术、数学 规划和计算机有机地结合起来去研究调度问题。 在过去的几十年里，人们不断地去寻找新的生产调度模型和调度算法伫3 1 ， 其中一个重要原因是产品制造界的市场竞争在不断提高，好的生产调度能提高 资源的利用率和操作管理水平，生产出具有竞争性的产品。目前，在我国的一 般生产企业的车间作业调度中，绝大多数都是依靠熟练的技术人员凭长期积累 的经验进行，企业很少运用现代企业所要求的“科学化、现代化和自动化 理 念，从而导致企业生产效率低，设备利用率低，这样的直接后果就是导致企业 生产产品成本提高，竞争力降低，这对于在当今全球日趋“一体化”的企业竞 争中处于不利地位。因此为了扭转我国生产企业的这种不利局面，必须要求生 产企业，特别是制造行业采用先进技术。对于制造行业来说，解决车间调度问 题无疑是关键环节。 现在，企业对生产管理的信息化和科学化要求越来越高。尤其是那些生产 大型设备的制造企业，产品的零部件占用资金非常大，他们的生产方式不可能 是有库存的现货生产模式，只能是按订单的生产模式，这种生产方式具有生产 过程多样化、采用万能设备多、能力负荷不均衡、生产过程不稳定和技术准备 工作量大等特点，由此造成了生产计划管理与调度工作的复杂性，而且由于设 备资源的稀缺性和高额的折旧费用，企业不希望也不可能靠盲目增加现有设备 来解决阶段性的设备资源紧张的瓶颈矛盾，设备的利用率直接决定整个企业的 哈尔滨理t 大学t 学硕十学位论文 制造能力。在这种生产模式下如何组织管理，如何安排生产计划、如何进行调 度都是我们面临的主要问题。其中车间作业调度与控制技术是实现生产高效 率、高柔性和高可靠性的关键，有效的调度方法与优化技术的研究与应用，已 成为先进制造技术实践的基础和关键。 设备空闲时间段的利用率是衡量设备利用率的重要标准。理论上，在满足 所有约束条件的情况下，显然，设备的空闲时间段的利用率越高，整体设备的 利用率就越搞。本文对此问题进行了深入的研究，在满足约束条件的前提下， 考虑设备的空闲时间段的利用率，以取得最优或次优的生产调度方案。因此， 此类算法研究，具有重要的理论意义和实际的应用价值。 1 2 国内外研究现状及分析 在对车间调度问题进行研究的方法上，最初是集中在数学规划、仿真和简 单的规则上，这些方法不是调度结果不理想就是难以解决复杂的调度问题。随 着各种新的相关学科与优化技术的建立与发展，在调度领域出现了许多新的优 化方法，比如基于人工智能、计算智能和实时智能的各种调度方法，这些方法 已经成为调度方法的主流h 1 。 1 数学方法数学规划法在车间调度中被广泛的采用。从数学规划的角 度，车间调度问题可以归结为在等式约束或者不等式约束下，对一个或者多个 目标函数进行优化。数学规划方法将车间调度问题简化为数学规划模型，采用 整数规划、动态规划以及决策分析等方法来解决调度最优化或近似最优化问 题。车间调度中广泛使用的是混合整数线性规划( m i x e di n t e g e rl i n e a r p r o g r a m m i n g ，m i l p ) 和混合整数非线性规划( m i x e di n t e g e r n o n l i n e a r p r o g r a m m i n g ，m i n l p ) 方法哺一1 。但是，数学规划方法是一种精确求解方法， 它需要对调度问题进行统一的建模，任何参数的变化会使得算法的重用性很 差。 2 基于规则的调度方法调度规则因其易于实现、计算复杂度低等原因， 能够用于动态实时调度系统中，许多年来一直受到学者们的广泛研究，并不断 涌现出许多新调度规则。p a n w a l k a rs e t a l 总结了1 1 3 条规则1 ，并将它 们分为三类：简单规则、复合规则和启发式规则。m o n t a z e r im e t a l 列举 了常见的2 0 条规则伸1 ，并针对一个实际的f m s ，分析了这些规则对系统性能 如作业的平均等待时间、机床的平均利用率、作业总加工时间等的影响。随着 计算机运算速度的飞速提高，人们希望寻找新的近似调度方法，以合理的额外 哈尔滨理t 大学下学硕十学位论文 计算时间代价，换得比单纯启发式规则所得到的调度更好的调度，a d a m s j e t a l 提出了移动瓶颈方法扫1 。c h a n gyl e t a l 使用线性规划模型对4 2 条 规则进行了评估引，结果显示最短处理时间( s p t ) 规则性能最好，而最长处 理时间( l p t ) 最差。启发式规则具有全局敏感性，利用不同的规则可产生不 同的调度方案，而且规则在不同的场合所起的作用也不同，调度系统的性能取 决于规则的选择。因此，规则的选择成为基于规则调度方法的主要障碍。 3 人工智能技术从上世纪八十年代初开始，一系列新的技术被用来求解 车间调度问题。它们无一例外地被冠以人工智能技术，这些技术包括专家系 统、基于知识的系统和一些搜索技术。它们有四大优势：第一决策处理过程中 同时采用定性和定量的知识；第二能生成启发式规则，这些规则比分配规则复 杂；第三可以在整个车间信息的基础上选择最好的启发式规则；第四能敏锐的 获得信息之间的复杂关系，并采用特殊的技术来处理这些关系。但也有不足之 处，它们需要时间去建立和验证，有时很难去维护和改变；只能产生可行解， 不能说明与最优解的接近程度；它们与系统本身紧密相联，但它们却无法管理 系统n 。例如：在专家系统和基于知识的系统中，专家系统和基于知识的系统 均由两个部分组成：知识库和推理机制。知识库包括一些规则、过程和启发式 信息等；推理机制用来选择一种策略处理知识库中的知识，以便随时解决问 题。推理机制分数据驱动和目标驱动两种。i s i s 是最早提出针对车间调度的专 家。i s i s 采用了面向约束推理的方法，把约束分成三种类型：组织目标约 束、物理限制约束和临时约束。i s i s 利用这些约束知识维护调度的一致性和 验证最低限度满足约束的调度决策。w y s k 提出了一个将专家系统和仿真集成 的调度系统n 引。而在分布式a i 中，由于一个单一的专家系统或基于知识的系 统所具有的知识有限和处理问题能力不强等原因。人工智能学者开始开发分布 式调度系统，采用的是“分而治之”的方法。对此，人工智能界的对策就是智 能体( a g e n t s ) 。一个智能体有着与其它智能体完全不同的软件处理过程，它完 全依赖自己的知识库。 4 人工神经网络神经网络模仿了人类学习和对事物的预测能力，是一种 并行处理模型。这种模型根据网络拓扑结构、节点特征和训练或学习规则的不 同而变化。r a b e l o 首先采用反向传播神经网络来处理具有各种类型的生产车 间调度问题“3 1 。通过训练使得网络能够正确地根据生产特征来选择合适的调度 策略和评价指标。网络的训练是分别采用多台机床的加工情况，训练的输入信 息有工件特征( 如工件种类、加工路径、到期时间和加工时间等等) 和车间特 征( 机床台数和加工性能等) ，训练的输出信息是对特定问题所选分配规则和 哈尔滨理t 大学t 学硕十学位论文 评价指标的评判等级。由于产生一个可行调度涉及的变量太多，所以这些方法 计算效率低，并且常常会产生不可行调度。因而，它们不能解决实际调度问 题。 5 邻域搜索技术邻域搜索技术的应用十分普遍。邻域搜索技术不仅本身 可以求得好的结果，而且如果与其它启发式方法相结合，则效果会更佳。这种 技术针对一个初始调度，在每次的迭代中加入很小的变化( “干扰) ，这些干 扰由启发式规则提供。在概念上与爬山法相类似，这种技术不断的刺探和评价 调度，直到目标方程的值没有任何进展。在这一类技术当中，应用最为普遍的 是禁忌搜索( t a b us e a r c h ) 、模拟退火( s i m u l a t e da n n e a l i n g ) 和遗传算法 ( g e n e t i ca l g o r i t h m s ) 。这些方法都有自己独特的添加干扰技术、停止搜索规则 和防止局部最优等手段，1 5 1 。 6 模糊逻辑模糊逻辑理论一般用在混合调度方法中。它主要用来解决车 间调度问题中不确定性的加工时间、约束和辅助时间。这些不确定性可以用模 糊数据来表示。t s u j i m u r a e t a l 提出了一个用模糊理论为流水车间中加工 时间建模的混合调度系统n 引，采用三角模糊数( t r i a n g u l a rf u z z yn u m b e r s ， t f n ) 来表示加工时间。每一个工件用两个三角模糊数来定义，一个是下界， 另一个是上界。用分枝定界过程来优化生产周期( m a k e s p a n ) 。 本文研究的是具有累计空闲段的设备的车间作业调度，是基于工艺树模型 的多产品调度优化问题。这类问题调度对象为工艺树模型和复杂产品，部分采 用a c p m 策略n7 1 ，与经典车间调度问题相比，此类调度问题加强了约束条 件，从而增加了和实际生产状况的结合。因此，基于工艺树模型的多产品调度 优化问题是更为复杂的组合优化问题。 因此，对设备空闲时间段利用的研究，既是排序理论的前沿课题，又是生 产实践中必须加以解决的实际课题。无论从理论上还是实践上来说，研究设备 利用问题，对于在大中型企业推广c i m s 技术、实现生产自动化管理，一定会 起到积极作用。 1 3 课题来源及本文主要内容 1 3 1 课题来源 本课题来源于黑龙江省自然科学基金( f 2 0 0 6 0 8 ) ；黑龙江省教育厅重大科 哈尔滨理工人学丁学硕 j 学位论文 学研究项目( 1 0 5 5 1 2 0 0 0 8 ) ；哈尔滨市科技攻关项目( 2 0 0 5 a a l c g 0 6 1 1 1 ) 。 1 3 2 本文研究的主要内容 本课题研究目的是对现有的用于求解非标准车间作业调度问题的方法所存 在问题进行分析，提出了一种新的求解车间作业调度问题的算法。针对复杂多 产品加工时产品调度次序影响机器利用率的问题，考虑产品调度过程中尽量提 高机器利用率，提出一种根据产品工序所在机器上空闲时间段累计长度来确定 产品加工顺序的调度方法。该方法通过比较产品加工产生空闲时间段长度，优 先安排空闲时间段短的产品，实现整体调度空闲时间的缩短。实例表明该方法 不仅提高机器利用率，而且有可能缩短总加工时间。 1 4 论文结构 第l 章介绍了本课题研究的目的和意义，国内外研究现状，课题来源及论 文主要研究内容。 第2 章介绍了车间作业调度问题的含义、特点及分类，然后给出了现有的 求解车间作业调度问题的方法，最后阐述了车间作业调度存在的问题及其发展 趋势。 第3 章对多复杂产品车间调度问题进行分析，根据产品工序之间的约束关 系将产品构造成一棵加工树，并将工序分为相关工序和独立工序，并介绍了拟 关键路径法。 第4 章在第三章基础上提出了累计设备空闲时间段的算法来确定复杂多产 品调度顺序，实现所有设备利用率的提高。并对所提出方法用实例进行验证。 第5 章在前两章研究的基础上提出了动态累计空闲时间段的调度算法，并 通过实例进行比较。 结论部分对本文进行了总结，并对进一步的研究做出了展望。 哈尔滨理工人学工学硕l j 学位论文 2 1 引言 第2 章车间作业调度理论与方法 1 9 5 4 年，j o h n s o n 开始研究2 个和3 个工序的带准备时间的流水车间 ( f l o ws h o p ) 调度问题，此后，生产调度问题的建模和求解，一直是理论界 研究的热点问题。车间调度是车间管理与控制的一个主要内容，及时、准确、 有效的调度，对于生产系统的正常运行有重大影响。调度问题来源于不同的领 域，如柔性制造系统、生产计划、计算机设计、后勤及通信等，这些问题的共 同特性是没有一个有效的算法能在多项式时间内求出其最优解n 引。 调度问题的复杂性、调度领域知识的多样性和生产环境的动态性，决定了 调度问题的解决单纯依靠人或计算机是难以完成的，必须把人、人工智能技 术、数学规划和计算机有机地结合起来去研究调度问题在现代化制造系统中， 随着企业规模的扩大，解决好企业车间调度问题，是实现生产自动化、高效率 和高柔性的关键所在；正确处理好车间调度问题，可以为企业节约大量的人 力、物力，使制造设备和资源可以得到更有效充分地利用。在敏捷制造中，面 对生产柔性化、高效化的要求，生产的计划调度及其优化成为生产控制的关 键，建立高效柔性的生产作业调度系统已成为生产控制的核心。因此，如何运 用有限的资源，降低产品的生产成本，缩短产品的制造周期，保证按时交货， 提高企业信誉，赢得更多的客户，成为制造厂商在竞争中生存的一个重要条 件。 2 2j o bs h o p 调度问题概述 2 2 1j o bs h o p 调度问题描述 设有个作业，每个作业的工序数为圻，f 1 ，2 ，。总工序数为 n 一以在聊台设备上a n - r ，其基本约束条件是： i = 1 1 每台设备每次只加工一个工序： 2 每个工序不能同时在多台设备上加工； - 6 - 哈尔滨理丁大学t 学硕= 1 ：学位论文 3 每个工序的加工顺序预先确定，满足技术要求； 4 每个工序在每台设备上只加工一次； 5 每一道工序必须在指定的设备上不间断地进行加工直到本工序完成为 止。 表2 1 描述了一个3 作业3 设备的车间作业调度问题实例，在表2 1 中不 仅给出了每一项作业在所有设备上的工艺约束，也给出了在每一个设备上加工 的时间。 表2 1 一个3 作业3 设备的车间作业调度问题的加工数据 t a b l e2 一li n f o r m a t i o no f3m a c h i n e sa n d3j o b s j s s p 作业名所在设备( 加工时间) l 1 ( 3 )2 ( 3 )3 ( 3 ) 2l ( 2 )3 ( 3 )2 ( 4 ) 3 2 ( 3 ) 1 ( 2 ) 3 ( 1 ) 总的说来，车间调度就是对一个可用的加工机床集在时间上进行加工任务 集分配，以满足一个性能指标集。从数学规划的角度看，车间调度问题可表达 为在等式或不等式约束下，对目标函数的优化n9 1 。典型的车间调度问题包括一 个要完成的作业集( 工件集) ，每个作业由一个操作集( 工序集) 组成，各操 作的加工需要占用机床或其它生产资源( 人员、刀具和辅助资源) ，并且必须 按一些可行的工艺次序进行加工。每台机床可加工工件的若干操作，并且在不 同的机床上能加工的操作集可以不同。调度的目标是将作业合理地安排到各机 床以及合理地使用其它生产资源，并合理安排作业的加工次序和加工时间，使 约束条件被满足，同时优化一些生产性能指标。 2 2 2j o bs h o p 调度问题中的基本概念 车间调度问题中常用的基本概念有：制造周期( m a k e s p a n ) ，关键路径 ( c r i t i c a lp a t h ) ，空闲时间段( i d l et i m e ) ，目标函数( a i mf u n c t i o n ) 等。 1 制造周期( m a k e s p a n ) 制造周期是调度开始时间与终止时间之间的间 隔。制造周期代表资源利用率心引，较短生产周期意味着较高资源利用率，常作 为作业调度优化目标。 2 关键路径( c r i t i c a lp a t h )关键路径就是对全部工程完工所需时间影响 哈尔滨理t 大学t 学硕十学位论文 最大的路径。 3 空闲时间( i d l et i m e ) 加工设备上没有安排加工工序的时间段，存在 于两个工序之间他。 4 目标函数( a i mf u n c t i o n ) 足约束条件表示调度性能的函数。 2 2 3j o bs h o p 调度问题中的主要模型 车间调度问题是一个非常复杂的工程问题。近年来，学者们从不同的角度 进行了研究，出现了车间调度模型大致有下面几种： 1 多目标调度( m u l t i - o b j e c t i v ej o bs h o ps c h e d u l i n gp r o b l e m ) 2 可变目标调度( a l t e r a b l e o b j e c t i v ej o bs h o ps c h e d u l i n gp r o b l e m ) 3 多资源调度( m u l t i r e s o u r c ec o n s t r a i n e dj o bs h o ps c h e d u l i n gp r o b l e m ) 4 动态调度( j o bs h o ps c h e d u l i n gp r o b l e mi nt h ed y n a m i ce n v i r o n m e n t ) 5 多工艺线路的调度( j o bs h o ps c h e d u l i n gp r o b l e mw i t ha l t e r n a t i v e m a c h i n e s ) 6 批量生产调度( j o bs h o ps c h e d u l i n gp r o b l e mi nt h eb a t c hp r o c e s s ) 7 模糊加工时间调度( j o bs h o ps c h e d u l i n gp r o b l e mw i t hf u z z yp r o c e s s i n g t i m e ) 8 模糊交货期调度( j o bs h o ps c h e d u l i n gp r o b l e mw i t hf u z z yd u e d a t e ) 9 准时生产调度( j o bs h o ps c h e d u l i n gp r o b l e mw i t hi nj u s ti nt i m e e n v i r o m e n t ) 1o 成组调度( j o bs h o ps c h e d u l i n gp r o b l e mw i t hg r o u pt e c h n o l o g y ) 1 1 协同调度( j o bs h o ps c h e d u l i n gp r o b l e mi nh o l o n i cm a n u f a c t u r i n g ) 1 2 虚拟制造调度( j o bs h o ps c h e d u l i n gp r o b l e mi nv i r t u a l m a n u f a c t u r i n g ) 1 3 敏捷制造调度( j o bs h o ps c h e d u l i n gp r o b l e mi na g i l em a n u f a c t u r i n g ) 1 4 精益生产调度( j o bs h o ps c h e d u l i n gp r o b l e mi nl e a np r o d u c t i o n ) 15 多智能体调度( j o b s h o ps c h e d u l i n g p r o b l e mi n m u l t i a g e n t m a n u f a c t u r i n g ) 1 6 分形企业生产调度( j o bs h o ps c h e d u l i n gp r o b l e m i nf r a c t a l e n t e r p r i s e ) 从上述调度模型可以看出：调度研究与制造模式的结合非常紧密，随着先 进制造模式的出现，出现了相应的调度模型，如精益生产调度、协同调度、分 - 8 一 哈尔滨理工大学工学硕l 学位论文 形企业生产调度等。但还可以看出，车间调度是一个非常复杂的问题，学者的 研究只集中在某一特定方面，虽然不同的研究方面存在着联系，并有可能采用 相似的研究方法，但尚未形成一套系统的理论。 2 2 4j o bs h o p 调度问题的特点 1 复杂性车间作业调度问题的复杂性主要表现在生产环境和调度的优化 计算两方面。首先，车间中工件、机器、操作人员和搬运系统之间相互影响、 相互制约。每个工件又要考虑它的加工时间、安装时间和操作顺序等因素，因 而加工环境相当复杂。其次，在各种条件的综合影响下，车间调度实质上是一 个在若干等式和不等式约束下的组合优化问题，从计算时间复杂度看是一个 n p h a r d 问题，随着调度规模的增大，问题可行解的数量呈指数级增加，使得 一些常规的方法无能为力，因而求解非常困难。即使对于单台机床加工问题而 言，如果有个工件而每个工件只考虑加工时间以及与操作序列有关的安装时 间，则这个问题就和个城市的旅行商问题等价，因此在现有计算条件下，一 般优化方法对于车间作业调度问题是低效甚至是无能为力的。 2 多约束性通常情况下，车间调度受到工件工艺路线的约束，各道工序 的先后关系不能被颠倒。同时，车间调度问题还受到各种资源的约束，如人为 要求各机器上的负荷要均衡、加工机床、操作工人、运输小车、刀具以及其它 辅助生产工具等。 3 不确定性车间调度中有很多随机和不确定性，如工件到达时间的不确 定性，实际工件的加工时间也有一定的不确定性。而且系统中常发生突发偶然 事件，如机器发生故障、紧急加工任务下达、加工任务的改变等等。 4 多目标性实际的车间调度问题待优化的性能指标有很多，例如生产周 期、平均流通时间、平均延误率、设备利用率等，而且这些目标之间往往会发 生冲突。研究认为所有的性能指标最终都是为了减少成本，故一个可以适应不 同的任务类型和规模的通用调度系统，应该是基于成本目标的系统。遗憾的 是，迄今为止还没有一个通用并且实用的车间调度系统。 5 离散性车间生产系统是一个典型的离散系统，工件的加工发生在不同 的时间和资源上，并且任务的到达、订单的更改、设备的添加和故障等都是离 散事件。这样，就有可能用数学规划、离散系统建模与仿真的方式，通过排序 理论研究车间作业调度问题。 哈尔滨理t 大学丁学硕_ 二学位论文 2 2 5j o bs h o p 调度问题的分类 车间调度问题的分类，根据研究的侧重点不同有多种分类方式。g r a v e s 依据研究对象的复杂性对车间调度问题分类心引，有重要的参考价值。 1 调度对象车间调度问题按调度对象可分为多种类型，例如工件调度 ( 只考虑工件) 、资源( 如机床、操作人员、机器人、有轨小车、刀具和缓冲 区) 调度等；按制约车间生产能力的资源数量可分为单资源调度( 只考虑系统 中的一种调度资源) 、双资源调度( 考虑两种资源) 和多资源( 考虑三种以上 资源) 调度等幢3 1 。通常所说的车间调度大多指的是单资源工件调度，也即对工 件的处理进行排序。 2 工件按照工件加工路线是否相同，分为生产车间调度( j o bs h o p ) 和 流水车间调度( f l o ws h o p ) 。工件的数量和工艺路线是任意的，称为生产车间 调度；每个工件都有相同的加工路径，称为流水车间调度( o p e ns h o p ) 。 按照工件的加工数量分为单件调度和批量调度。单件调度指待加工的每一 种工件只有一个，而并非只有一个工件，可能有若干种不同的工件。 按照工件工序数量可分为单工艺路线车间调度和多工艺路线车间调度。每 个工件只有一道工序是单工艺路线车间调度，也叫单车间调度( s i n g l e s h o p ) ；否则为多工艺路线调度。 3 机床单机调度问题：加工系统只有一台机床，待加工的工件也都只 有一道工序，所有工件都在该机床上加工。并行机床调度问题：加工系统有一 组功能相同的机床，待加工的工件都只有一道工序，可选任一台机床来加工工 件。 多机调度问题：加工系统有若干台功能各异的机床，待加工的工件需要在 多台机床上分步加工。 4 加工任务和特征静态车间调度( s t a t i cs c h e d u l i n g ) 是指所有待安排 加工的工件均处于待加工状态，因而进行一次调度后，各作业的加工被确定， 在以后的加工过程中就不再改变。故静态车间调度不考虑工件在加工过程中出 现的意外情况，如机床突然损坏、工件的交货期提前、有更紧迫的工件要求被 加工等等。 动态车间调度( d y n a m i cs c h e d u l i n g ) 是指作业依次进入待加工状态，各 种作业不断进入系统接受加工，同时完成加工的作业又不断离开，还要考虑作 业环境中不断出现的不可预测的动态干扰，如作业的加工超时、设备的损坏 哈尔滨理下大学丁学硕上学位论文 等。故此种调度方式要求调度能随时响应车间加工能力的变化，在有突发事件 出现后，能立即根据当时的车间加工能力，对待加工的工件重新展开调度，以 确保在任何时候，都能保持车间的加工性能指标处于最优或次优状态。 2 3j o bs h o p 调度问题的分派规则和调度性能 2 3 1j o bs h o p 调度问题的分派规则 车间调度问题的分派规则指在所有可加工的工序中，依据某一规则为每一 台机床设备和相应的生产资源选择工序，大量的仿真实验发现优先选择最短加 工时间的工序( s h o r t e s tp r o c e s s i n gt i m e ，s p t ) 对大多数性能指标来说是非常 好的分派规则心引。 2 3 2j o bs h o p 调度问题的调度性能 影响调度问题的因素很多，正常情况下有：产品的投产期，交货期( 完成 期) ，生产能力，加工顺序，加工设备和原料的可用性，批量大小，加工路 径，成本限制等，这些都是所谓的约束条件幢引。有些约束条件是必须满足的， 如交货期，生产能力等，而有些达到一定的满意度即可，如生产成本等，这些 约束在进行调度时可以作为确定性因素考虑。而对于设备故障，原料供应变 化，生产任务变化等非正常情况，都是事先不能预见的，在进行调度时大都作 为非确定性因素考虑。 调度指标是评价调度方案优劣的标准。生产调度指标可以是生产周期最 短、成本最低、拖延时间最短、生产切换最少、设备利用率最高、三废最少 等。实际生产调度指标有：调度性能的指标，包括：生产周期、平均流动时 间、机床利用率、工人利用率等，其实质是最大化生产能力以提高经济效益： 成本指标，包括：加工费用、工人工资、启动成本、延期罚款和废品损失等和 客户满意度指标，包括：延期时间、提前时间和延期工件的数量等。 2 4 国内外j o bs h o p 调度问题的研究方法 对于调度问题的研究经历了一个较长的发展时期，自5 0 年代初期开始， 哈尔滨理t 大学_ 学硕_ j j 学位论文 应用数学、运筹学、工程技术等领域学者就对调度问题进行了大量的研究。5 0 年代早期，j o h n s o n 提出了解决i l 2 c 懈和部分特殊的n 3 f c m 舣问题的有效优 化算法，标志着调度理论研究的开始。考虑到调度问题本身的复杂性，后来人 们逐渐着手开始寻找有效的求解策略。到了6 0 年代，调度理论主要围绕着线 性规划、整数规划、混合整数规划、动态规划、分支定界等方法，研究并解决 了一系列有代表性的调度问题。随着问题规模的扩大，人们越来越深刻地认识 到传统的精确算法已不能满足求解的需要，特别对于大规模的问题，采用精确 算法往往是不可能的。于是在6 0 年代中期开始，人们开始着手研究调度问题 的复杂性，并且证明了许多调度问题诸如最简单的f l o ws h o p 和j o bs h o p 都是 n p 难问题，对于这类问题，并不存在有效的多项式求解方法，因此开始寻找 有效的近似方法来解决它们，如基于优先规则的方法、基于瓶颈的启发式方 法、遗传算法、模拟退火算法、禁忌搜索算法、阀值接受算法、人工神经网 络、专家系统、蚁群系统等等把h 引。 1 解析方法解析方法是对于特定的目标，能在多项式时间内得到最优调 度的一类方法。这类方法虽然搜索效率很高，但是适用问题很少，只对特定问 题有效，对于一般问题，除了小规模的几个问题外，很难找到解析方法心引。 2 分支定界法分支定界法采用过滤机制，它并不对所有的搜索分枝进行 评估。在每一阶段的计算中，只对那些有前途的分支进行评估计算，其他分枝 被永远地删除。分支定界法只适合于小规模的问题，对于大规模的问题，往往 需要相当长的时间，因此限制了它的使用啪1 。 3 数学规划法数学规划法包括线性规划、非线性规划、整数规划、混合 整数规划、l a g r a n g i a n 松弛方法、动态规划等，此类方法通常是一种解决小规 模调度问题的有效算法，但由于生产调度是一类组合优化问题，属于n p 完全 问题，随着问题规模的扩大，会发生组合爆炸，以致很难用它来求解大规模的 调度问题。此外，就是数学规划法自身的局限性，人们在运用时，不得不附 加一些脱离实际环境的假设，这在一定程度上导致了其理论研究与实际应用之 间的差距。 4 控制理论方法它是一种比较适合定量地定义基本问题，但还没有形成 一套有效的调度模型表达、分析设计的技术。缺点是：模型描述能力有限，建 模时不得不对真实环境进行大量的简化，求得最优解的时间是随问题规模增大 而呈指数规律增长引，因此也只适合对小规模的系统求解。 5 优先分派规则法最早的分派规则由j a c k s o n 和s m i t h 等提出，j s s p 的 分配规则有最短加工时间( s h o r t e s tp r o c e s s i n gt i m e ，s p t ) 、最长加工时间 哈尔滨理工人学工学硕l j 学位论文 ( 1 0 n g e s tp r o c e s s i n gt i m e ，l p t ) 、剩余加工时间最长( m o s tw o r kr e m a i n i n g ， m w r ) 、剩余加工时间最少( l e a s tw o r kr e m a i n i n g ，l w r ) 、剩余工序数最多 ( m o s to p e r a t i o n sr e m a i n i n g ，m o r ) 、剩余工序数最少( l e a s tw o r kr e m a i n i n g l o r ) 、最早交货期( e a r l i e s td u ed a t e ，e d d ) 和先来先服务( f i r s tc o m ef i r s t s e r v e d ， f c f s ) 等b 3 1 。p