（计算机应用技术专业论文）复杂产品调度中多设备紧凑调度算法研究.pdf

哈尔滨理工大学工学硕上学位论文 复杂产品调度中多设备紧凑调度算法研究 摘要 理论上，车间调度问题( j o bs h o ps c h e d u l i n gp r o b l e m ，j s s p ) 是最难解 决的组合优化问题之一，要求在满足约束条件的情况下尽可能保证目标函数结 果最优。实际中，大规模资源的调度优化成为制约生产发展的重要因素。可见 对调度问题的研究具有重大理论意义和实际价值。 经典j s s p 的一个缺陷就是和实际情况结合不够，缺少对调度环境、调度 对象和加工设备的充分考虑。实际生产过程中存在着复杂产品，它可由多个工 件组成，其中每个工件又可有更小的工件组成，这里把装配操作看作一种工 序，则一个复杂产品可表示为多个工件加工和装配的合成。 本文对复杂产品调度中多设备紧凑调度算法进行深入研究，主要在提高设 备利用率上进行创新。首先针对调度对象为复杂产品的情况，采用工艺树模型 对其建模，并对工艺树模型进行具体描述。其次，针对关键设备紧凑方法缺少 对非关键设备的考虑，本文充分考虑对非关键设备的紧凑处理，提出了一种基 于多设备紧凑的调度优化算法，以达到整体设备利用率的提高。关键设备紧凑 法中拉伸策略是工序的整体后移，存在对部分工序的不必要移动，本文提出了 空闲时间段拉伸条件的确定方法和预影响集的概念，对满足条件的空闲时间段 拉伸并对产生的预影响集进行递归调整，这样避免了对部分工序的不必要移 动，使得所有设备尽量紧凑。最后，在多设备紧凑算法的基础上，进一步考虑 拉伸后部分工序前移和无缝拉伸的优化调整策略。通过对多个复杂产品实例进 行验证分析，表明多设备紧凑算法在提高设备利用率上具有明显优化特性，同 时具有良好的复杂度。 关键词调度问题：复杂产品；空闲时间段；多设备紧凑；预影响集 哈尔滨理r t 大学工学硕j j 学位论文 s ! ! ! ! ! = 自= ! = = = 自_ 目自j 目= 目e ! ! ! = ! ! ! ! ! ! 自i 一| , 一m t 目e 自= s ! = = = 目e ! ! = ! = 目自 s t u d yo fm u l t i - e q u i p m e n tc o m p a c ta l g o r i t h mi n c o m p l e x p r o d u c t ss c h e d u l i n gp r o b l e m a b s t r a c t i nt h e o r y , j 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 ) i sa m o n g t h eh a r d e s t c o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s i tc a l lb ed e s c r i b e d 硒u n d e rs o m ec o n s t r a i n t s a n dt r yt o g e tt h e b e s tr e s u l to ft h ea i m f u n c t i o n i nr e a l i t y , t h es c h e d u l i n go f r e s o u r c e so nal a r g es c a l ei st ob eo n ei m p o r t a n tf a c t o rw h i c hc o n s t r a i n t st h e d e v e l o p m e n to fp r o d u c t s ot h e r e s e a r c ho nj ss ph a si m p o r t a n tt h e o r e t i c a la n d a p p l i e ds i g n i f i c a n c e af l a wo fc l a s s i cj s s pi st h a th a s n te n o u g hc o n s i d e r a t i o no fr e a ls i t u a t i o n ， i g n o r i n gt h es c h e d u l i n ge n v i r o n m e n t 、s c h e d u l i n go b j e c ta n ds c h e d u l i n ge q u i p m e n t s i nr e a lp r o d u c i n gt h e r ea r ec o m p l e x - p r o d u c t sw h i c hc a nb ea s s e m b l e db ym u l t i - j o b ， e a c hj o bc a l lb ea s s e m b l e db ym u l t i - s m a l l e r - j o b ，a s s e m b l yi sc o n s i d e r e d 邪a n o p e r a t i o nh e r e ，s ot h ec o m p l e x p r o d u c tc a nb ee x p r e s s e da st h ep r o c e s s i n ga n d a s s e m b l eo fm u l t i - j o b i nt h i s p a p e r , m u l t i - e q u i p m e n tc o m p a c ta l g o r i t h m i n c o m p l e x - p r o d u c t s s c h e d u l i n gp r o b l e mi ss t u d i e dt h o r o u g h l y ；t h ei n n o v a t i o ni sm a i n l yi ni m p r o v i n gt h e e f f i c i e n c yo fe q u i p m e n t s f i r s t l y , i nt h i sp a p e r c o n s i d e r i n gt h a tt h es c h e d u l i n go b j e c t i sc o m p l e x - p r o d u c t ，at r e em o d e lf o rc o m p l e x - p r o d u c ti sb u i l ta n dd e t a i ld e s c r i p t i o n o ft h et r e em o d e li sg i v e n s e c o n d l y , a i m i n ga tt h em e t h o dk e y - e q u i p m e n tc o m p a c t h a s n tc o n s i d e r e do t h e re q u i p m e n t s c o m p a c t ，、v i t hc o n s i d e r i n ga l le q u i p m e n t s c o m p a c t ，am e t h o db a s e do nm u l t i e q u i p m e n tc o m p a c ti sp r e s e n t e dt oi m p r o v et h e e f f i c i e n c yo f a l le q u i p m e n t s a n dt h em e t h o do fs t r e t c hi nk e y - e q u i p m e n tc o m p a c ti s m o v i n ga l l c o r r e l a t e do p e r a t i o n s ，w h i c hi n c l u d e sm o v i n gs o m en o tn e c e s s a r y o p e r a t i o n s ，am e t h o dt od e t e r m i n et h ec o n d i t i o no fs t r e t c h i n gi d l e t i m ep a r t i t i o na n d t h ed e f i n i t i o no fp r e i n f l u e n c e s e ti sp r o p o s e d ，u n d e rt h ec o n d i t i o ns t r e t c h i n gt h e i d l e - t i m ep a r t i t i o na n da d j u s t i n gt h ep r e i n f l u e n c e s e t ，s oi ta v o i d st h em o v i n go f - i i 哈尔滨理工大学丁学硕上学位论文 t h o s en o tn e c e s s a r yo p e r a t i o n s ，a n dm a k e sa l lt h ee q m p m e n t s 笛c o m p a c ta sp o s s i b l e a tl a s t , b a s e do i lt h em u l t i e q u i p m e n tc o m p a c t ，i tf u r t h e rc o n s i d e rt h ef o r w a r d m o v i n go fs o m eo p e r a t i o n sa f t e rs t r e t c h i n ga n dt h es t r e t c h i n go fn o n i d l et i m e p a r t i t i o n t h ea n a l y s i so fs o m ec o m p l e x p r o d u c te x a m p l e ss h o w st h a t m u l t i - e q u i p m e n tc o m p a c ta l g o r i t h mh a sa b s o l u t e l ya d v a n t a g ei ni m p r o v i n gt h eu t i l i z a t i o n o fe q u i p m e n t sa n dh a saf a v o r a b l ec o m p l e x i t y k e y w o r d ss c h e d u l i n gp r o b l e m ，c o m p l e x p r o d u c t ，i d l e t i m ep a r t i t i o n ，m u l t i - e q u i p m e n tc o m p a c t ，p r e i n f l u e n c e s e t i i i - 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文复杂产品调度中多设备紧凑 调度算法研究，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期间 独立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含 他人已发表或撰写过的研究成果。对本文研究工作做出贡献的个人和集体，均 已在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者虢智穿喈魄力中；月2 1 0 e t 哈尔滨理工大学硕士学位论文使用授权书 复杂产品调度中多设备紧凑调度算法研究系本人在哈尔滨理工大学攻 读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归哈尔 滨理工大学所有，本论文的研究内容不得以其它单位的名义发表。本人完全了 解哈尔滨理工大学关于保存、使用学位论文的规定，同意学校保留并向有关部 门提交论文和电子版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学可 以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部分内 容。 本学位论文属于 保密口，在年解密后适用授权书。 不保密翻。 ( 请在以上相应方框内打) 作者签名：奸窘呻日期：扩7 年弓月加日 导师签名坪币 醐仂哆铋肿日 哈尔演理t 大学t 学硕t 学位论文 第1 章绪论 1 1 课题研究的目的和意义 所谓调度( s c h e d u l i n g ) ，就是为了实现某一目的而对共同使用的资源实行 时间分配n 1 。调度问题来源于不同的领域，如生产计划、计算机设计、电力传 输、军队作战、交通运输、后勤及通信等。调度一般性的定义是在一段时间 内，为了完成一组工作，而相应地分配一套资源。调度问题的共同特性是没有 一个有效的算法能在采用多项式的有效时间内求出其最优解，它们都是n p ( n o n p o l y n o m i a lc o m p l e t e ) 完全问题。调度问题是最难解决的组合优化问题 一【2 3 - 4 】 一一 。 车间作业调度是根据产品制造需求合理分配产品制造资源，进而达到合理 利用产品制造资源、提高企业经济效益的目的。具体而言，就是针对一项可分 解的工作( 如产品制造) ，探讨在尽可能满足约束条件( 如交货期、工艺路 线、资源情况) 的前提下，通过下达生产指令，安排其组成部分( 操作) 使用 哪些资源、其加工时间及加工的先后顺序，以获得产品制造时间或成本的最优 化。随着经济全球化和信息化深入发展，为了应对瞬息万变的市场，企业对生 产管理的信息化要求越来越高。尤其是那些生产大型设备的制造企业，产品的 零部件占用资金非常大，他们的生产方式不可能是有库存的现货生产模式，只 能是按订单的生产模式，这种生产方式具有生产过程多样化、采用万能设备 多、能力负荷不均衡、生产过程不稳定和技术准备工作量大等特点，由此造成 了生产计划管理与调度工作的复杂性，而且由于设备资源的稀缺性和高额的折 旧费用，企业不希望也不可能靠盲目增加现有设备来解决阶段性的设备资源紧 张的瓶颈矛盾，关键设备的制造能力直接决定整个企业的制造能力。在这种生 产模式下如何组织管理，如何安排生产计划、如何进行调度都是我们面临的主 要问题。其中车间作业调度与控制技术是实现生产高效率、高柔性和高可靠性 的关键，有效的调度方法与优化技术的研究与应用，已成为先进制造技术实践 的基础和关键。 实际应用中的调度方法能够响应系统的动态变化，但不能保证得到好的调 度结果。而基于最优化的方法，由于其大多是建立在对可能调度的部分枚举 上，只能解决小规模的调度问题。因此，对车间调度问题的研究，在理论上和 哈尔滨理工大学工学硕上学位论文 实际应用中都有着重要意义。研究车间作业调度问题，寻求先进的车间作业调 度算法，具有较大的现实意义和理论意义，主要表现在以下几点： 1 为企业提供良好的作业生产排序方案，使企业制定出合适的作业生产计 划。 2 提供及时准确的车间作业调度方案，确保企业生产系统的高效运行。 3 应用先进合理的车间作业调度算法，合理配置各种资源，使得企业零件 的加工准备时间、等待时间减少，设备利用率与生产效率提高，在制品的资金 占用减少，生产成本降低。 4 车间作业调度问题的研究推动了遗传算法、模拟退火算法、启发式方法 等优化方法的发展与融合，也为其他领域类似问题的解决提供了条件与手段。 5 通过将优化算法与调度方法相结合，使制造系统提高运行效率，满足客 户的要求，增强企业在市场上的竞争力。 基于工艺树模型的多产品调度优化通过考虑调度对象为复杂产品的情况存 在的各种实际调度问题，理论联系实际，在关键设备紧凑法的基础上提出了基 于多设备紧凑的调度方法，充分利用了设备上的空闲时间段，提高了设备利用 率，节省了总的加工时间，具有重要的理论价值和实际意义。 1 2 国内9 1 、研究现状及分析 在过去的五十年中，人们对调度问题作了大量的研究，先后提出了选择最 优或近似最优调度的各种优化方法，如规则判定法、探索法、线形规划法、分 支定界法、蒙特卡罗法等等。早期研究主要集中在f s p 问题和简单j s p 问题 上，而对于一般调度问题还未出现最优调度算法。 车间调度问题由于系统建模方法的多样性，以及问题的侧重点不同，调度 方法和研究对象也不同。就对象而言，有确定性和随机性调度、离散事件和连 续事件调度、静态和动态调度等；就调度方法而言，有动态规划、排对论方 法、规则调度方法等等：就调度优化目标而言，有正规性能指标和非正规性能 指标，如生产成本、e t 指标等啼1 。车间调度问题的研究早在1 9 5 0 年就展开， 国内外对于车间调度问题的诸多研究可以归结为两个方面：车间调度问题的建 模和车间调度问题算法设计与分析。车间调度问题建模的主要目的是根据理论 研究的需要或根据实际生产系统的特点提出一个或一类车间调度问题的子问 题，并以一定的形式对其进行描述主要包括：问题的语义描述、问题中各要素 的描述、问题的符号表示、问题的公式化描述、问题的图论描述等，它是车间 哈尔滨理t 大学工学硕士学位论文 调度问题算法设计与分析的基础。车间调度问题算法设计的目的是对建立的模 型进行求解，获得优化的调度解。而算法分析的目的则是对算法正确性进行验 证、对调度结果进行评估与预测、对算法的时间复杂度及空间复杂度进行分析 等哺1 。近年来，车间作业调度问题的研究向更实用的方向发展，主要表现在以 下面几个方面： 1 多目标调度实际调度问题往往是多目标的，如最短生产周期、最大生 产利润，而且这些目标往往相互冲突。一般人们采用两种方法：将两目标加权 和作为目标或采用基于树扩展的双重目标梯度下降法。周亚勤等提出了调整时 间与工序顺序相关的j o bs h o p 调度优化方法研究，通过以多目标多约束的j o b s h o p 调度问题为背景，考虑工序调整、作业相似性等特点，利用成组技术和 人工智能树，提出了与工序排序有关的调整时间描述方法及其调度规则，给出 了此问题的混合整数规划模型，并构造了基于生物免疫机理的调度算法以提高 求解此类问题的效果。 2 动态调度由于实际的加工系统具有随机性和不确定性，因此生产调度 过程是一个动态过程，往往需要重新调度，特别在动态环境下，其本身就是不 断地动态重复调度的过程。武志军等提出了基于人机协同的动态车间生产调试 问题的研究与实现，通过研究三类典型动态调度事件的动态响应机制及动态调 度过程中的几个关键算法，开发了面向精密加工生产的车间调度系统。 3 人机交互调度为了考虑实际调度中存在的各种复杂因素及调度的多目 标性，以取得好的调度结果，往往需要好的人机交互策略与手段去利用和启发 调度决策者的经验知识。张晴提出了人机交互的j o bs h o p 车间动态调度方法， 指出对于离散事件的j o bs h o p 调度，采用人机交互与仿真相结合的方法，描述 了调度过程中人的行为模型，建立了一种人机交互的车间调度系统框架结构， 并探讨了适用于该框架结构的动态调度机制。 4 成组技术分解调度成组技术就是根据作业、机床之间的相似性将它们 各自分组，利用组内的相似性来提高生产率。顾擎明等提出了基于成组技术的 柔性调度的两层遗传算法，对柔性制造系统中工件的加工调度问题进行了研 究，通过对柔性制造系统中工件的加工路线和加工顺序作弱化处理来提高调度 质量，即在工艺约束条件下确定工序的成组优化，利用两层寻优的遗传算法有 效地解决这一过程的寻优问题。 5 双资源和多资源调度车间的生产能力不仅会受到机床的制约，还会受 到工人和辅助工具的制约。陈希等提出了工艺路线可变的双资源双目标车间调 度优化，将遗传算法与启发式调度规则相结合，对此问题进行了研究。在探讨 哈尔滨理工大学工学硕士学位论文 过程中，不仅考虑了每个工件有几条可行的工艺路线，而且考虑了工件的调度 受到机床、工人等资源的制约，以及在加工过程中发生的储存费用、机床的加 工费用和工人的劳动费用对工件调度的影响，设计了以生产周期和生产成本综 合优化为目标的适应度函数；刘晓霞等提出了双资源生产车间调度问题的研 究，其将遗传算法和模拟退火算法相结合对问题进行研究，该混合算法将机床 设备和工人合理地分配给加工任务，使评价性能指标获得最优。 本课题研究的是复杂产品调度中多设备紧凑调度算法，属于基于工艺树模 型的复杂产品调度优化问题。这类问题调度对象为工艺树模型和复杂产品，部 分采用a c p m ( a l l i e dc r i t i c a lp a t hm e t h o d ) 策略口1 ，与经典车间调度问题相比，此 类调度问题加强了约束条件，从而增加了和实际生产状况的结合。因此，基于 工艺树模型的多产品调度优化问题是更为复杂的组合优化问题。 针对基于工艺树模型的复杂产品调度优化问题，国内外的相关专家对此做 了一定的研究，虽已取得了一定的成果，但相对于经典车间作业调度问题来 说，研究成果并不是很明显。因此，对基于工艺树模型的复杂产品调度优化研 究，既是排序理论的前沿课题，又是生产实践中必须加以解决的实际课题。无 论从理论上还是实践上来说，研究基于工艺树模型的复杂产品调度优化问题， 对于在大中型企业推广c i m s 技术、实现生产自动化管理，一定会起到积极作 用。 1 3 课题来源及本文主要内容 1 3 1 课题来源 本课题来源于黑龙江省自然科学基金( f 2 0 0 6 0 8 ) ；黑龙江省教育厅重大科学 研究项目( 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 本文研究的主要内容 本文主要对复杂产品的调度优化问题进行研究，通过对现有的基于关键设 备紧凑的调度算法进行分析，提出了一种新的基于多设备紧凑的调度优化算 法。该算法采用递归处理预影响集的思想将拉伸空闲时间段后产生的工序交叠 情况和约束关系破坏情况调整以满足约束关系，并考虑无缝拉伸和根据拉伸后 产生的空隙，安排部分工序前移的优化策略。 哈尔滨理t 大学t 学硕 j 学位论文 本文主要研究内容如下： 1 多设备紧凑的复杂产品调度优化问题确定了多设备紧凑时空闲时间段 的拉伸条件，提出预影响集的概念和约束关系破坏后的调整策略，利用递归循 环方法对预影响集调整达到所有设备尽量紧凑，最后用实例与关键设备紧凑法 进行对比分析。 2 工序前移的复杂产品调度优化问题通过对多设备紧凑算法分析，确定 了存在工序前移时的空闲时间段拉伸条件和约束关系破坏后调整策略。根据约 束条件判断满足前移条件的工序并扩充预影响集，最后通过实例与多设备紧凑 法进行对比分析。 3 无缝拉伸的复杂产品调度优化问题在多设备紧凑基础上进一步考虑部 分工序的无缝拉伸处理，起到局部情况下的优化效果，最后通过实例分析验 证。 1 4 论文结构 第1 章介绍了本课题研究的目的和意义，国内外研究现状，课题来源及论 文主要研究内容。 第2 章介绍了车间作业调度问题的概念、应用及分类，然后给出了现有的 求解车间作业调度问题的方法，最后阐述了车间作业调度存在的问题及其发展 趋势。 第3 章对复杂产品调度中多设备紧凑调度算法进行分析，根据复杂产品工 序之间的约束关系将复杂产品构造成一棵加工树，并确定了空闲时间段拉伸条 件，制定了拉伸后约束关系破坏后调整策略和预影响集的递归调整策略，最后 通过实例与关键设备紧凑法进行比较。 第4 章在前一章的基础上考虑部分工序前移的优化调整策略，充分利用了 设备上的空闲时间段，最后通过实例进行对比分析。 第5 章在前两章研究的基础上放宽了拉伸条件，基于满足约束条件下工序 间尽量紧凑的原则，提出了无缝拉伸的优化策略，最后通过实例进行比较分 析。 最后对本文进行了总结，并对进一步的研究做出了展望。 哈尔滨理工大学工学硕i ：学位论文 第2 章车间作业调度问题概述 2 1 车间调度问题的背景 早在1 9 5 4 年，j o h n s o n 对两台机床的f l o ws h o p 型调度问题进行了研究 后，便开始了对调度问题的广泛研究m 1 。人们普遍把c o n w a y 、m a x w e l l 和 m i l l e r 三人有关调度的研究工作作为调度理论研究的正式开始饽1 ，他们三人也 被人们称为调度理论的奠基人，此后3 0 多年的调度理论和应用研究都受到他 们的影响，2 0 世纪7 0 年代，人们开始注意并重视调度复杂性问题的研究，提 出了用于研究算法有效性和问题难度的计算时间复杂性理论n 制，许多调度问题 被证明为n p 完全问题1 。 调度问题的复杂性、调度领域知识的多样性和生产环境的动态性，决定了 调度问题的解决单纯依靠人或计算机是难以完成的，必须把人、人工智能技 术、数学规划和计算机有机地结合起来去研究调度问题。由于调度问题的复杂 性，导致不同的研究者从不同的角度研究某一方面的问题，产生了许多的车间 调度问题的类型和方法，并随着对各类调度问题研究的深入及各种交叉学科的 发展，涌现出了许多新的车间调度理论与方法n 引。 2 2 车间调度问题概念和模型描述 工件车间调度问题是一个著名的n p 难度问题n3 。车间调度就是对一个可 用的加工机床集在时间上进行加工任务集分配，以满足一个性能指标集。从数 学规划的角度看，车间调度问题可表达为在等式或不等式约束下，对目标函数 的优化。典型的车间调度问题包括一个要完成的作业集，每个作业由一个操作 集所组成，各操作的加工需要占用机床或其它资源，并且必须按一些可行的工 艺次序进行加工，每台机床可加工工件的若干操作，并且在不同的机床上能加 工的操作集可以不同。调度的目标是将作业合理地安排到各机床，并合理安排 作业的加工次序和加工开始时间，使约束条件被满足，同时优化一些指标h 。 调度一般性的定义是在一段时间内，为了完成一组工作，而相应地分配一 套资源。所有调度问题的共同特性是没有一个有效的算法能在采用多项式的有 效时间内求出其最优解，它们都是n p ( n o n p o l y n o m i a lc o m p l e t e ) 完全问 题。 哈尔滨理1 = 大学丁学硕士学位论文 车间调度问题的数学描述为：设有k 个产品，每个产品的工序数为坍， ( i = l ，2 ，k ) ，总工序数n = 宇z 在m 个设备上加工，要求1 台设备在某一 智 时刻只能加工一道工序；一道工序在某一时刻只能被1 台设备加工；1 台设备 一旦加工某道工序，则直到该工序加工完毕后，这台设备才能加工其他工序； 每道工序都必须在其前续工序加工完后方可开始加工；当上一道工序完工后立 即送下一道工序加工；每道工序的加工时间已知，且与加工顺序无关；允许工 序之间等待，允许设备在工序达到之前闲置。一个工件在一台机器上的加工称 为一道“工序 ，用“加工顺序 表示各台机器上工件加工的先后次序，加工 顺序是作业调度要解决的问题。 2 2 1 车间调度问题中的基本概念 车间调度问题中常用的基本概念有：制造周期( 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 ) 制造周期是调度开始时间与终止时间之间的间 隔。制造周期代表资源利用率n 引，较短生产周期意味着较高资源利用率，常作 为作业调度优化目标。 2 关键路径( c r i t i c a lp a t h ) 关键路径就是对全部工程完工所需时间影响最 大的路径。 3 空闲时间( i d l et i m e ) 加工设备上没有安排加工工序的时间段，存在于 两个工序之间n 引。 4 目标函数( a i mf u n c t i o n ) 满足约束条件表示调度性能的函数。 2 2 2 车间调度问题中的主要模型 车间调度问题是一个非常复杂的工程问题。近年来，学者们从不同的角度 进行了研究，出现了车间调度模型大致有下面几种： 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 b s h o ps c h e d u l i n g p r o b l e m ) ； 4 动态调度( j o b s h o ps c h e d u l i n g p r o b l e mi nt h e d y n a m i c e 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 ) ； 1 0 成组调度( 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 b s h o ps c h e d u l i n g p r o b l e mi n a g i l e m 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 bs h o p s 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 mi nf r a c t a l e n t e r p r i s e ) 。 从上述调度模型可以看出，车间调度是一个非常复杂的问题，学者的研究 只集中在某一特定方面，虽然不同的研究方面存在着联系，并有可能采用相似 的研究方法，但尚未形成一套系统的理论。 2 2 3 车间调度问题中的常见图形表示方法 常见的调度模型的图形表示方法一般有两种，甘特图表示法和非连接图表 示法，对两种表示方法进行举例说明如下。 1 甘特图表示法甘特图是一种车间作业调度问题解的图示方法，以时 间为横坐标，以设备号为纵坐标n 引。一个3 作业3 设备的车间作业调度问题用 甘特图表示于图2 1 中。在此图中，o 一表示作业，在设备r 上加工，对每一项 作业j ，定义其完成时间为g ，每一个方框代表一个工序d 横坐标表示此 工序的开始时间s ，其水平方向的长度表示此工序的加工时间p 一。此调度的 总的加工时间为1 9 个时间单位。工序q 在不改变任一设备上其它工序的先后 哈尔滨理t 大学工学硕上学位论文 顺序的前提下可以被提前到以第5 个单位时间开始。 2 非连接图描述非连接图模型g = ( v ，a ，e ) 由b a l a s 提出n 毛坤1 ，v 包含 代表所有工序的节点，a 包含连接同一工件的邻接工序的边，e 包含连接同一 机器上加工工序的非连接边，非连接边可以有两个可能方向。调度过程将固定 所有非连接边的方向，以确定同一机器上工序的顺序，并采用带有优先箭头的 连接边取代非连接边。 m i 蝎 晒 口f ，o ：l 卜_ 1 1 仍， 锄如如 锄0 f j 1 02 4 5al e1 21 41 6l sl i 彘 图2 13 作业3 设备的车间作业调度问题一个解的甘特图表示 f i g 2 一l g 锄t tc h a r to f3m a c h i n e sa n d3j o b s j s s p 对n 项作业、m 台设备( 共n 个工序) 的车间作业调度问题，对应的非 连接图模型为g = ( v ，a ，e ) 。其中，v 为所有工序构成的顶点集，包括o 和 n + l 两个虚拟工序( 分别表示加工开始和终止) ；具有工艺约束偏序关系的工序 对( 作业内部工序之间的工艺要求) 的集合，称为合取弧的集合a ( 实线) ；在 机器k 上相邻工序对( 表示相邻两工序在机器k 上加工的前后顺序) 的集合， 成为析取弧的集合e ( 虚线) 。 举例说明，如图2 - 2 ，图g = ( v ，a ，e ) 表示3 作业3 设备的车间作业调 度问题的非连接图模型：现在以最大完成时间为指标，那么对车间作业调度问 题的求解就归结为找到各边( 即设备) 上作为优先决策的各操作的一组顺序 ( 即走向) ，当同一设备上有多个操作出现冲突时，上述顺序用于决定各操作 的先后，最终得到各操作间没有冲突的一个有向非循环图，而其关键路径长度 即为最大完成时间啪1 。 2 2 4 复杂产品调度中工艺树模型描述 根据产品工序加工的紧前紧后关系建立的方向由叶结点指向根结点的树型 结构称为工艺树模型，其中每个结点包含工序号，设备号，加工时间3 个元 哈尔滨理工大学工学硕上学位论文 素。包含4 个工序的工艺树模型见图2 - 3 。 o 789 图2 23 作业3 设备车间作业调度问题的非连接图表示 f i g 2 - 2d i s j u n c t i v eg r a p ho f3m a c h i n e sa n d3j o b s j s s p 图2 3 包含4 个工序的工艺树模型 f i g 2 3 t r e em o d e lw i t h4o p e r a t i o n s 图2 - 3 表示一个产品由4 个工序组成，每个工序有3 个属性：工序号机 器号加工时间。例如：工序l 由设备1 加工，加工时间为1 5 个工时。在工艺 树模型上，由于树的递归定义可以把复杂问题简单化，此外还增强了调度问题 的兼容性和扩展性，具体表现在把具体工件的加工工序和各个工件装配工序结 合起来产生一棵产品树。 复杂产品由多个工件装配组成瞳，其中每个工件具有多个加工工序，各个 工件之间装配组成产品。用工艺树模型描述就是整棵树代表一个产品，分叉结 点代表工件间的装备操作，各个连续无分叉的分支代表各个工件，分支上的结 点表示处理工件的工序。 在实际生产过程中调度和装配问题是密不可分的，多个工件装配后形成一 个大工件再继续加工时，存在装配和调度混合进行。考虑实际生产中调度问题 的多样性，本文把装配当作一种工序，具体单个工件的加工工序与普通调度中 描述一样，这样对于一个产品来说调度中就可能出现分叉结点，这与一台机器 同时只能加工一个工件并不矛盾，其中分叉结点指工件之间的装配工序。 嚣如 哈尔滨理t 大学工学硕士学位论文 2 3 车间调度问题的特点 车间调度问题有以下几个特点： 1 复杂性车间作业调度问题的复杂性主要表现在生产环境和调度的优化 计算两方面。首先，车间中工件、机器、操作人员和搬运系统之间相互影响、 相互制约。每个工件又要考虑它的加工时间、安装时间和操作顺序等因素，因 而加工环境相当复杂。 其次，在各种条件的综合影响下，车间调度实质上是一个在若干等式和不 等式约束下的组合优化问题，从计算时间复杂度看是一个n p h a r d 问题，随着 调度规模的增大，问题可行解的数量呈指数级增加，使得一些常规的方法无能 为力，因而求解非常困难。即使对于单台机床加工问题而言，如果有个工件 而每个工件只考虑加工时间以及与操作序列有关的安装时间，则这个问题就和 个城市的旅行商问题等价，因此在现有计算条件下，一般优化方法对于车间 作业调度问题是低效甚至是无能为力的。 2 多约束性通常情况下，车间调度受到工件工艺路线的约束，各道工序 的先后关系不能被颠倒。同时，车间调度问题还受到各种资源的约束，如人为 要求各机器上的负荷要均衡、加工机床、操作工人、运输小车、刀具以及其它 辅助生产工具等。 3 动态随机性在真实的车间生产环境中有很多随机和不确定性，如工件 到达时间的不确定性，实际工件的加工时间也有一定的随机性。而且系统中常 发生突发偶然事件，如紧急任务插入、交货期改变、订单被取消、设备故障或 修复等。因此生产调度过程是一个动态的随机的过程。 4 多目标性实际的车间调度问题待优化的性能指标有很多，例如生产周 期、平均流通时间、平均延误率、设备利用率等，而且这些目标之间往往会发 生冲突。研究认为所有的性能指标最终都是为了减少成本，故一个可以适应不 同的任务类型和规模的通用调度系统，应该是基于成本目标的系统。遗憾的 是，迄今为止还没有一个通用并且实用的车间调度系统。 5 离散性车间生产系统是一个典型的离散系统，工件的加工、储存和运 输发生在不同的时间和资源上，并且任务的到达、订单的更改、设备的添加和 故障等都是离散事件。这样，就有可能用数学规划、离散系统建模与仿真的方 式，通过排序理论研究车间作业调度问题。 哈尔滨理工大学工学硕士学位论文 2 4 车间调度问题的分类 车间调度问题的分类，根据研究的侧重点不同有多种分类方式。g r a v e s 依 据研究对象的复杂性对车间调度问题分类，有重要的参考价值吩2 1 。 1 调度对象车间调度问题按调度对象可分为多种类型，例如工件调度 ( 只考虑工件) 、资源( 如机床、操作人员、机器人、有轨小车、刀具和缓冲 区) 调度等；按制约车间生产能力的资源数量可分为单资源调度( 只考虑系统 中的一种调度资源) 、双资源调度( 考虑两种资源) 和多资源( 考虑三种以上 资源) 调度等1 。通常所说的车间调度大多指的是单资源工件调度，也即对工 件的处理进行排序。 2 工件按照工件加工路线是否相同，分为生产车间调度( j o b s h o p ) 和 流水车间调度( f l o w s h o p ) 。工件的数量和工艺路线是任意的，称为生产车间 调度；每个工件都有相同的加工路径，称为流水车间调度( o p e n s h o p ) 。 按照工件的加工数量分为单件调度和批量调度。单件调度指待加工的每一 种工件只有一个，而并非只有一个工件，可能有若干种不同的工件。 按照工件工序数量可分为单工艺路线车间调度和多工艺路线车间调度。每 个工件只有一道工序是单工艺路线车间调度，也叫单车间调度( s i n g l e s h o p ) ；否则为多工艺路线调度。 3 机床单机调度问题：加工系统只有一台机床，待加工的工件也都只 有一道工序，所有工件都在该机床上加工。并行机床调度问题：加工系统有一 组功能相同的机床，待加工的工件都只有一道工序，可选任一台机床来加工工 件2 钔。 多机调度问题：加工系统有若干台功能各异的机床，待加工的工件需要在 多台机床上分步加工。 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 ) 是指作业依次进入待加工状态，各 种作业不断进入系统接受加工，同时完成加工的作业又不断离开，还要考虑作 业环境中不断出现的不可预测的动态干扰口5 1 ，如作业的加工超时、设备的损坏 哈尔滨理丁大学t 学硕士学位论文 等。故此种调度方式要求调度能随时响应车间加工能力的变化，在有突发事件 出现后，能立即根据当时的车间加工能力，对待加工的工件重新展开调度，以 确保在任何时候，都能保持车间的加工性能指标处于最优或次优状态。 2 5 车间调度问题的分派规则和调度性能 2 5 1 车间调度问题的分派规则 车间调度问题的分派规则指在所有可加工的工序中，依据某一规则为每一 台机床设备和相应的生产资源选择工序，大量的仿真实验发现优先选择最短加 工时间的工序( s h o r t e s tp r o c e s s i n gt i m e ，s p t ) 对大多数性能指标来说是非 常好的分派规则乜引。 2 5 2 车间调度问题的调度性能 影响调度问题的因素很多，正常情况下有：产品的投产期，交货期( 完成 期) ，生产能力，加工顺序，