（机械制造及其自动化专业论文）车间生产调度性能评价理论及其应用.pdf

中文摘要 汽车零部件制造企业车间生产调度问题围绕车间生产加工过程中如何配 置资源而实现车问生产调度优化而展丌的，从数学模型的角度看，是在满足制 造系统性能指标的基础上，对可用的制造资源集按照时间要求分配为车间生产加 工任务集。表现为制造约束下对目标函数的优化，是一类广义约束优化问题，即 在满足一定生产技术条件与车间制造资源约束前提下，确定被加工零部件的加工 顺序、加工路径、加工开始与完成时间。由于车间制造系统的复杂性、制造环境 影响因素的随机性、生产加工任务和车间生产调度目标的多样性，决定了车间生 产调度问题的复杂和困难。在考虑车间调度问题的动态性、多目标性和复杂性的 基础上，文中考虑影响车间生产调度的各方面因素，针对车间生产调度性能评 价理论及其应用作了较深入研究。 首先，研究了汽车零部件制造企业车间生产类型、生产方式及其生产流程、 车间生产调度与企业管理系统关系，建立了车间生产调度的系统功能模型。就汽 牟零邮件韦0 造企业j m 吉，其车f h j $ i j 造系统一般均呈离散型生产方式，具有多资源、 多产品中小批量，并兼有面向订单和面向库存的混合型生产的特点。而车间生产 调度的系统功能模型是由生产事件集合构成，反映了车间制造资源与车间生产加 工任务之间的功能逻辑关系。 其次，从车间生产调度系统功能模型出发，建立了车间生产调度问题数学描 述及其数学模型，从建立制造车间静动态生产调度模型出发，采用p e t r i 网建 模方法，建立了一系列基础模型，并进一步扩展为车自j 静动态生产调度模型。 在考虑车间制造资源及其约束条件的基础上提出了车间生产加工作业排序优化 数学模型、最佳初始工件投入量优化数学模型和最佳转序量优化数学模型。 第三，针对制造车间生产调度中存在的不确定性因素，从车间制造资源不确 定性因素和车间外部环境不确定因素两方面进行深入研究，系统地提出车间生产 调度中卜确定性凶素的定量分析与评价数学模型。 最后，深入研究了车间生产调度可靠性问题和车间生产调度性能的可靠性仿 真评价理论方法，建立了系列相关数学模型，在此基础上，开发了车间生产调度 系统性能及可靠性仿真评价系统，采用某汽车零部件制造企业车间生产调度实际 案例进行了计算机仿真和应用验证。文中建立的车间生产调度性能及可靠性评价 方法正确可行，具有重要的实用价值。 关键词：制造系统：车间生产调度；可靠性；调度性能仿真；仿真评价：系统 a b s t r a c t t h ei s s u eo fa u t o m o b i l es p a r em a n u f a c t u r i n ge n t e r p r i s ew 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 gp r o b l e mi n v o l v e s i nh o wt oa l l o c a t er e s o u r c ea n dr e a l i z ew o r k s h o p p r o d u c t i o ns c h e d u l i n go p t i m i z a t i o ni nw o r k s h o pp r o d u c t i o nw o r kp r o c e s s f r o mt h e p o i n to fv i e wo fm a t h e m a t i cm o d e l ，o nt h e b a s i so fs a t i s f y i n gm a n u f a c t u r es y s t e m p e r f o r m a n c ei n d e x ，a v a i l a b l em a n u f a c t u r er e s o u r c e ss e ti s d i s t r i b u t e dt ow o r k s h o p p r o d u c t i o np r o c e s st a s ks e ta c c o r d i n gt o t i m ec o n s t r a i n t i tb e h a v e sa so b j e c t i v e f u n c t i o ni so p t i m i z e du n d e rm a n u f a c t u r i n gc o n s t r a i n t i ti sab r o a ds e n s ec o n s t r a i n e d o p t i m i z a t i o np r o b l e m ，n a m e l y ，u n d e rs a t i s f y i n gac e r t a i n t yp r o d u c t i o ns p e c i f i c a t i o n s a n dw o r k s h o pm a n u f a c t u r er e s o u r c ec o n s t r a i n t ，a s c e r t a i nw r o u g h tp a r t i a lp r o c e s s i n g s e q u e n c e ，p r o c e s sp a t h ，t h et i m eo fp r o c e s sb e g i n n i n ga n df i n i s h i n g o w i n gt o t h e c o m p l e x i t yo fw o r k s h o pm a n u f a c t u r i n gs y s t e m ，t h er a n d o m n e s so fm a n u f a c t u r i n g e n v i r o n m e n ti n f l u e n c i n gf a c t o r ，t h eo b j e c t i v ed i v e r s i t yo fp r o d u c t i o np r o c e s sa n d w o r k s h o pp r o d u c t i o ns c h e d u l i n g ，i tr e s u l t e d i nt h ec o m p l e x i t ya n dd i f f i c u l t yo f w o r k s h o pp r o d u c t i o ns c h e d u l i n gp r o b l e m b a s e d o nc o n s i d e r i n gt h ed y n a m i c ， m u l t i p l eo b j e c t i v ea n dc o m p l e x i t yo fw o r k s h o ps c h e d u l i n gp r o b l e m ，a l l k i n d so f e f f e c tf a c t o r sw h i c hi n f l u e n c ew o r k s h o pp r o d u c t i o ns c h e d u l i n ga r ed i s c u s s e d ，a n d w o r k s h o pp r o d u c t i o ns c h e d u l i n gp e r f o r m a n c ee v a l u a t i o nt h e o r ya n da p p l i c a t i o ni s s t u d i e dp e n e t r a t i n g l yi nt h ep a p e r f i r s to fa l l ，a u t o m o b i l es p a r em a n u f a c t u r i n ge n t e r p r i s ew o r k s h o pp r o d u c t i o ns t y l e ， m o d eo fp r o d u c t i o na n dp r o d u c t i o nf l o w ，w o r k s h o pp r o d u c t i o ns c h e d u l i n ga n d e n t e r p r i s em a n a g e m e n ts y s t e m a t i cr e l a t i o n s ，s y s t e m f u n c t i o nm o d e lo fw o r k s h o p p r o d u c t i o ns c h e d u l i n ga r ed i s c u s s e d w o r k s h o pm a n u f a c t u r i n gs y s t e mu s u a l l ya c t s l i k ed i s c r e t ep r o d u c t i o nm o d e ，h a st h ec h a r a c t e ro fm u l t i - r e s o u r c e ，m u l t i p l ep r o d u c t m i d d l eo rs m a l lb a t c h a n dc o m b i n a t i o n 、v i t l lm t o ( m a k e t oo r d e r ) a n dm t s ( m a k e t os t o r e ) m i x e dm o d ef o ra u t o m o b i l es p a r em a n u f a c t u r i n gp r o c e s s t h e s y s t e m f u n c t i o nm o d e lo fw o r k s h o pp r o d u c t i o ns c h e d u l i n gi sm a d eu po fp r o d u c t i o ne v e n t c o n c o u r s e ，r e f l e c t st h ef u n c t i o n a ll o g i cr e l a t i o n s h i pb e t w e e nw o r k s h o pm a n u f a c t u r e r e s o u r c e sa n dw o r k s h o pp r o d u c t i o np r o c e s sa s s i g n m e n t s s e c o n d l y ，f r o mt h eb e g i n n i n go fw o r k s h o pp r o d u c t i o ns c h e d u l i n gs y s t e mf u n c t i o n m o d e lm a n u f a c t u r er e s o u r c eh a r m o n ym o d e la n dw o r k s h o pp r o d u c t i o ns c h e d u l i n g p r o b l e mm a t h e m a t i c a lm o d e li s s e tu pb yc o n s i d e r i n gw o r k s h o p m a n u f a c t u r e r e s o u r c e si n t e r a c t i o na n dh a r m o n y ，a n df r o mt h e f o u n d a t i o no fc o n s t i t u t i n g m a n u f a c t u r i n gs y s t e ms t a t i c o rd y n a m i cs c h e d u l i n gm o d e l ，as e r i e so fp r e l i m i n a r y i i m o d e l sa r ee s t a b l i s h e da n da r ee x t e n d e dw o r k s h o pp r o d u c t i o ns c h e d u l i n gs t a t i ca n d d y n a m i cm o d e lo nt h eb a s i so ff o u n d a t i o nm o d e lb ya d o p t i n gp e t r in e tm o d e l i n g m e t h o d w o r k s h o pp r o d u c t i o np r o c e s so p t i m i z a t i o nm o d e l ，t h eb e s ti n i t i a lw o r k p i e c e i n p u ta m o u n to p t i m i z a t i o na n dt r a n s g e n i cf o r e w o r d a m o u n to p t i m i z a t i o ni ns h o pi s p u tf o r w a r du n d e rc o n s i d e r i n gw o r k s h o pm a n u f a c t u r er e s o u r c e sa n d c o n s t r a i n t c o n d i t i o n t h i r d l y ，i na l l u s i o nt ot h eu n c e r t a i nf a c t o r se x i s t i n gi nt h ep r o d u c t i o ns c h e d u l i n g o fm a n u f a c t u r i n gw o r k s h o p ，b o t hf r o mu n c e r t a i nf a c t o r so fm a n u f a c t u r i n gr e s o u r c e s i nt h ew o r k s h o pa n du n c e r t a i nf a c t o r so fe x t e r n a le n v i r o n m e n to fw o r k s h o p ， c o r r e l a t i v eq u a n t i t a t i v ea n a l y s i sa n de v a l u a t i o nm a t h e m a t i c a lm o d e la r ee s t a b l i s h e d a n dt h es t r a t e g yo fc o n t r o l l i n gu n c e r t a i nf a c t o r so fp r o d u c t i o ns c h e d u l i n gi nw o r k s h o p i sa l s od i s c u s s e d f i n a l l y ，t h ep e r f o r m a n c ep a r a m e t e ro fm a n u f a c t u r i n gs y s t e m ，t h ep e r f o r m a n c e e v a l u a t i o no fp r o d u c t i o ns c h e d u l i n g ，t h ee m u l a t i o ne v a l u a t i o np r o b l e mo fp r o d u c t i o n s c h e d u l i n gr e l i a b i l i t ，va n dp r o d u c t i o ns c h e d u l i n gp e r f o r m a n c ea n dr e l i a b i l i t yi ns h o p a n dr e l a t e dm a t h e m a t i c a lm o d e li se s t a b l i s h e dr e s p e c t i v e l y o nt h i sb a s i so fa b o v e t h e o r ya n a l y s i s ，a ne m u l a t i o ne v a l u a t i o ns y s t e mo fp r o d u c t i o ns c h e d u l i n gs y s t e m p e r f o r m a n c ea n dr e l i a b i l i t yi ns h o pi sd e v e l o p e da n dp r a c t i c a lc a s eo fp r o d u c t i o n s c h e d u l i n gi ns h o pi nc e r t a i na u t o m o b i l ep a r t sm a n u f a c t u r i n ge s t a b l i s h m e n ti sa d o p t e d t oc a r r yo u tc o m p u t e rs i m u l a t i o na n da p p l i c a t i o nv e r i f i c a t i o n k e yw o l d s ：m a n u f a c t u r i n gs y s t e m ；s h o ps c h e d u l i n g ；r e l i a b i l i t y ；s c h e d u l i n g p e r f o r m a n c es i m u l a t i o n ；s i m u l a t i o ne v a l u a t i o n ；s y s t e m i i i 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 武汉理工大学或其它教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说 明并表示了谢意。 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即 学校有权保留、送交论文的复印件，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段 保存论文。 ( 保密的论文在解密后应遵守此规定) e l 期：沙函夕? 武汉理工人学博十学位论文 第1 章绪论 1 1 引言 随着我国加入w t o ，国内外市场竞争越来越激烈，特别是中小型汽车零部件制 造企业，多品种、中小批量的生产形式所占比例越来越大，为了能够在竞争中立于 不败之地，降低成本，提高生产效率和生产质量成为当务之急。而汽车零部件制造 企业车间制造系统畅通的核心问题是如何有效地进行汽车零部件制造企业车间生产 调度( 文中简称车间生产调度) ，车间生产调度直接影响车间制造系统的运行性能， 是车间制造系统中最重要的一环，因此，车间生产调度成为实现先进制造的基础和 关键，从而车间生产调度问题的研究与应用，对汽车零部件制造企业缩短产品生产 周期、确保产品按期交货、降低生产成本，以适应多变的市场需求，具有重要的理 论意义和实用价值。 现代经济中日益强化的竞争趋势和不同客户定制变化的需求促使企业重新评估 生产制造战略，如更短的产品制造周期和准时化的生产，利用有限制造资源满足各 种加工任务的生产加工，确定工件在制造设备上的制造顺序和时间，保证获得最优 的系统性能指标，能够最大限度地提高企业的生产效益。因此，车间生产调度问题 具有很强的实际应用背景，有效而合理的车间生产调度是制造领域的重要研究课题 t l , 2 。 车间生产调度问题通常是指在车间制造过程中如何配置资源而实现生产调 度优化而展开的。一般的车间生产调度问题可以描述为：刀个工件在聊台机器上 进行加工，个工件有k 道加工工序，每道加工工序可以在若干台制造资源上进 行加工p l 。每一台制造资源在每一时刻只能加工某个工件的某道工序，且只能在 上道工序加工完成后才能开始下一道工序的加工。即，从数学模型的角度看，车 间生产调度是对一个可用的加工制造资源集在时间上进行加工任务集分配，以满足 制造性能指标。用数学规划的方法，车间生产调度问题可表示为等式或不等式约束 下对目标函数的优化。车间生产调度的目的是将加工作业合理地安排到各种制造资 源上、合理地安排加工作业顺序、确定加工开始时间与完成时间，并使约束得到满 足，同时使车间制造系统的性能达到最优或次优。因此，车间生产调度问题本质上 是一类广义的约束优化问题，在满足一定技术条件与制造资源( 以下简称制造资源) 约束的前提下，确定出工件的加工投放顺序、加工路径、加工开始时间与完成时间， 并尽可能满足生产管理者的生产目标。 车间生产调度主要是针对产品制造工作，探讨在尽可能满足交货期、工艺路线、 制造资源等约束条件下，通过制造资源合理安排、加工时间及加工顺序确定，获得 武汉理i ：人学博十学位论文 车间制造系统性能的最优化。在理论研究中，车间生产调度问题通常被称为加工排 序问题或制造资源调度分配问题，好的车间生产调度能够有效地提高制造资源利用 率和生产管理水平，生产出具有竞争力的产品1 1 - 4 1 。 对于车间生产调度模型来说，实际车间生产调度不是一成不变的，会随各种生 产影响因素和约束条件的变化而变化，因此，在不同制造资源、约束条件、生产规 模、生产形式和管理方法下，车间生产调度所追求的目标、策略及其数学模型均会 有所不同。由于车间生产调度问题影响因素的复杂性和生产过程与生产环境的动态 性，必须将制造资源、约束条件、生产规模和生产调度方法进行综合考虑来研究车 间生产调度问题。 在实际车间生产调度中，还必须考虑管理人员、制造人员的技术水平、刀具、 央具、量具、检验用具、物料转序等因素，即需要考虑两个方面的问题，生产作业 调度和制造资源调度。目前，在理论研究上大部分研究集中在生产作业调度上，一 般没有考虑制造资源调度，而将制造资源作为约束处理。 中小型汽车零部件制造企业车间主要活动是组织生产，生产的有效性取决于生 产计划制订和实施，即生产计划制定与生产过程调度，由于现代生产的运行与管理 十分复杂，因此，车间生产调度问题十分重要。同时顾客需求瞬息万变，技术创新 不断加速，产品生命周期不断缩短，市场竞争日趋激烈。多品种、中小批量生产方 式被越来越多的采用，因此，多品种、中小批量生产成为我国中小型汽车零部件制 造企业的最显著特征。 在车f 白j 生产调度中，生产计划调度的任务是根据生产目标和约束，为每一个加 工对象确定具体的加工路径、时间、制造设备资源和操作等，以保证车间制造系统 的某一性能指标达到最优，具有静态特性。生产过程中调度的任务是根据生产计划 调度问题的最优解，按计划组织生产，当制造人员、制造设备、工夹具等制造资源 和生产任务的不确定性出现而产生生产中断或需求变更时快速响应，柔性地调整车 问的全部或局部生产过程，具有动念特性，此时，实质上是一个制造资源的调度与 分配问题。 影响车间生产调度问题的因素很多，正常情况下有产品的投产期、交货期、制 造人员技术水平、工央具、生产能力、加工顺序、制造设备和原材料的可用性、生 产批量、加工工艺路径、成本限制等。这些都是约束条件，有些约束条件是必须要 满足的，如交货期，生产能力等，而有些达到一定的满意度即可，如生产成本，这 些约束在进行车间生产调度时有些可以作为确定性因素处理。而对于制造设备故障、 原材料供应变化，生产任务变化等是事先不可预见的，属于不确定性因素。这样一 来，在生产过程中生产计划调度问题由于不确定因素的作用，将从静态问题转化为 2 武汉理一i ：人学博+ 学位论文 生产过程中的动态调度问题。从这方面来看，车间生产调度问题具有静、动态双重 特性。 车间生产调度性能指标大致可以归结为3 大类：1 ) 最大能力指标：包括最大生 产率、最短生产周期等；2 ) 生产成本指标：包括最大利润、最小化运行费用、最 小投资、最大收益等；3 ) 客户满意度指标：包括最短延迟时间，最小提前或者最小 拖后时间等。 生产计划调度问题，根据车间制造系统的复杂程度，可分为单机、多台并行机、 f l o ws h o p 和j o bs h o p 。单机调度是指所有加工任务都在单台机器上完成，为此存在 生产任务的排队优化问题；多台并行机调度问题更复杂，因而优化问题更突出；f l o w s h o p 型问题是假设所有加工作业都在同样的设备上进行，并有一致的加工操作和加 工顺序；j o bs h o p 是混合型生产调度，不同的作业具有不同的加工操作和加工顺序， 并不限制加工作业的制造设备。一般车间生产调度的问题往往是动态的i o bs h o p 型 式。 根据加工作业特点，可将车间生产调度问题分为静态调度和动态调度。静态调 度是指所有待安排加工的工件均处于待加工状态，因而进行一次调度后，各加工作。 业的加工时间、加工顺序、制造设备等均被确定，在以后的加工过程中不再改变； 动态调度是指加工作业依次进入待加工状态、各种加工作业不断进入车间制造系统， 接受加工、同时完成加工的加工作业又不断离开，还要考虑作业环境中不断出现的 动态扰动、如作业的加工超时、制造设备的损坏等，因此，动态调度要根据车间制 造系统中加工作业、制造设备等情况，不断地进行实时变更。 ，。= 车间制造系统的复杂性、制造环境影响因素的随机性、生产任务和调度目标的 多样性，决定了车间生产调度问题的复杂和困难。车间生产调度本身受到各制造资 源、约束条件、生产规模、生产形式和管理方法的影响，在不同的制造资源、约束 条件、生产规模、生产形式和管理方法下，车间生产调度问题的目标、调度策略及 其数学模型一般不同。由于生产环境的动态性、生产领域知识的多样性、生产调度 问题的复杂性，必须将制造人员、制造资源、约束、数学方法和信息技术结合起来 研究车间生产调度问题，在此基础上对车间生产调度结果进行定量分析与评价，并 根据定量评价结果反过来指导车间生产调度，此即为本课题研究的目的和意义 之所在。 1 2 车间生产调度问题的研究方法 车间生产调度问题的复杂性和现实生产对优化调度的应用需求，促使从事现代 制造研究人员提出很多解决方法，从而推动车间生产调度理论与实践的发展。就研 武汉理1 ：大学博十学位论文 究方法而言，主要有运筹学方法、统计分析方法、极大代数法、网络方法、智能调 度方法、模糊逻辑的方法、计算机仿真方法等1 。 1 、运筹学方法 运筹学方法广泛应用于车间生产调度问题的研究，将车间生产调度问题转化为 数学规划理论问题描述。常用的数学规划方法有线性规划法、整数规划法、混合整 数规划法、启发式规则方法和动态规划法。这类方法在车间生产调度问题的研究， 从2 0 世纪5 0 年代到7 0 年代取得了一批研究成果。如：1 ) 分解技术。将车间控制 分成上下层，上层通过工件加工的最早丌始时间和最迟结束时间来考虑各子问题间 的约束关系，下层通过对工序的细致排序来考虑各子问题内的约束。2 ) 枚举方法与 拉氏松弛法。3 ) 启发式规则方法。是从尚未调度的工件中按照规则进行选择，直到 所有工件均被调度为止。采用运筹学方法虽然能从理论上求取最优解，但由于大多 数车间生产调度问题是n p 问题，计算的复杂性使得这些方法的应用受到很大的限 制。 2 、统计分析方法 统计分析法是一种随机优化方法，它是将每一个制造设备资源看成是一个服务 终端，将每个加工作业作为一个客户，将加工时间及到达时间均假设为一个随机分 布来描述各作业的可变性与复杂的路径。通过各种统计分析方法，可以求解车间制 造系统中一些常用的性能指标，如平均在制品数、平均队列长度、制造设备职员平 均利用率、零部件平均停留时自j 等。 3 、极大代数法 该方法在2 0 世纪8 0 年代成功用于离散事件动态系统的建模与分析，它是利用 双子( d i o i d ) 或极大代数中的特殊运算规则，将逻辑非线性关系转换为先行关系， 从而在离散事件动态系统理论中建立起与先行关系系统理论相类似的方法。其优点 为具有先行属性、严格的理论体系和易于处理时间因素。利用该方法可以分析车间 生产调度的稳定性、特征结构、能控性等。 4 、智能调度方法 利用人工智能理论与技术求解车间生产调度问题通称为智能调度，其主要方法 包含人工智能技术、人工神经网络优化、遗传算法、邻域搜索技术等。 1 ) 人工智能技术 8 0 年代开始了人工智能技术在调度问题中的应用研究。专家系统和基于知识的 4 武汉理1 ：人学博十学位论文 系统发展较迅速，它们有如下优点：在决策处理过程中同时采用定性和定量的知 识；能生成启发式规则，这些规则比分配规则复杂：可以在整个车间信息的基 础上选择最好的启发式规则；能敏锐地获得信息之间的复杂关系，并采用特殊的 技术来处理。 基于专家知识系统：其由两个部分组成：知识库和推理机制。知识库包括一些 规则、过程和启发式信息等；推理机制用来选择一种策略处理知识库中的知识来解 决问题。 智能体：人工智能的对策就是智能体，一个智能体有着与其它智能体完全不同 的软件处理过程，它完全依赖自己的知识库，而调度正是利用调度知识库的知识来 实现。 2 ) 人工神经网络优化 神经网络模仿人类学习和对事物的预测，根据网络拓扑结构、节点特征和训练 或学习规则的不同而变化。人工神经网络优化方法用于车间生产调度主要有3 类方 式：利用其并行计算能力，求解优化调度，来克服n p 难题；利用其学习能力， 从优化轨迹中提取调度知识；用来描述调度约束或调度策略，以实现对生产过程 的可行调度或次优调度。 3 ) 遗传算法 遗传算法是按自然进化法则、群体优化搜索的方法解决车间生产调度问题，其 基本原理是，产生若干代表问题候选解，并组成一个群体，按照某一评价函数或算 法对群体中的每个成员进行评估，评估结果为代表解。遗传算法的结构特点为： 遗传算法的工作问题是编码，对搜索问题的限制极少，对函数的一些约束条件像连 续性、可导性等不作要求，减少了所要解决问题的复杂性：遗传算法是同时搜索 解空间内的许多点，可以有效地防止搜索过程中收敛到局部最优解，并获得全局最 优解；遗传算法使用遗传操作时是按概率在解空间进行搜索，是一种有目标、有 方向的启发式搜索。 4 ) 邻域搜索技术 邻域搜索技术方法主要包含模拟退火法和禁忌搜索法，其基本思想分别为：1 ) 模拟退火法。模仿晶体结晶的冷却过程，在较高温度乃下，系统状态为s ，能量( 即 目标函数) 为e ，选择的一个邻域s 。，如果，e ( s ) e ( s ) 则接受s 为下一状态，否则 e ( s 。) 一占( s ) 以概率e z i 接受s 。经过一定次数( 称为m a r k o v 链长) 的搜索，认为系统在 此温度下达到平衡，则降低温度t s 再进行搜索，直到满足条件。2 ) 禁忌搜索法。 武汉理r 人学博士学位论文 从一个可行解s 出发，s 产生邻域s ，如果f 为目标函数，选取所有邻域中使f i s ) 为最优的状态作为下一状态，并把这一移动的反向移动存入一个称为禁忌移动( t a b u m o v e ) 的表中，列在表中的移动在以后若干步内不允许再产生，这样可避免搜索退 回去。 5 、网络方法 由于车间制造系统一般是典型的离散系统，因而可以采用g r a i 网络、p e t r i 网 等方法来研究离散系统的车间生产调度问题。 1 ) g r a i 方法 g r a i 方法是2 0 世纪7 0 年代法国波尔多第一大学g r a i 实验室提出的一种用于 描述与分析生产管理系统的方法。g r a i 网格是g r a i 方法中用于建模制造系统中决 策中心活动的一种方法，g r a i 网络是用来描述企业决策过程的建模方法，主要是 一种描述性方法，许多涉及具体执行的细节，包括时间、成本、异常处理机制并没 有包括在模型中，有关资源和信息业作为支持表示在网络上。g r a i 网络基于图形 理论，定义了三种基本的图形化的建模构件和连接弧，g r a i 网络中定义的建模构 件包括状态构件、活动构件、资源或者支持构件，它们的作用分别为：状态构件表 示了由变量和结果构成的系统状态；活动构件表示了通过变换函数6 将输入状态转 换为输出状态；资源或者支持构件定义了为完成活动的执行而必须提供的信息和物 力资源，包括一起活动执行的触发条件。 2 ) p e t r i 网方法 p e t r i 网是一种系统描述和分析工具，p e t r i 网系统结构图一般由库所、变迁、 有向弧和托肯等元素组成，各构成要素的含义为：1 ) 库所( p l a c e ) 可用于表示制 造资源的实体，用圆形节点表达：2 ) 变迁( t r a n s i t i o n ) 可用于表示生产加工任 务的流动变化，用直行符号表示；3 ) 有向弧( c o n n e c t i o n ) 用带箭头的直线或弧线 表示，是用于联结库所和变迁的符号，可用于表示生产加工任务在制造资源上的流 入与流出：4 ) 托肯( t o k e n ) 是库所中的动态对象，可以从一个库所移动到另一个 库所，可用于表示生产加工任务工作量。它用利用库所、变迁和有向弧的连接表示 系统的静态功能和结构，通过变迁和令牌的移动描述系统的动态行为。p e t r i 网可以 很方便地描述车间制造系统的框架及过程，适合于进行计算机仿真分析。但p e t r i 网 不提供决策分析功能，因而不能进行最优决策。一般一个复杂系统的p e t r i 网不仅模 型建立困难，而且对模型的性能分析和优化决策也难以进行。因而针对p e t r i 网存在 的问题进行改进，使p e t r i 网的有关理论、方法，尤其是优化决策成为一个研究热点。 6 、模糊逻辑的方法 6 武汉理t 火学博+ 学位论文 客观现象具有确定性与不确定性两个基本方面，经典数学表达的是现象的确定 性；不确定性方面一方面表现为随机性，另一方面表现为模糊性，因此可以把模糊 的概念引入调度领域。模糊逻辑主要用来解决车间生产调度问题中不确定的a n - r _ 时 间、约束和辅助时间等，将这些用模糊数据来表示。 7 、计算机仿真方法 基于仿真的方法侧重于对系统运行逻辑关系的描述，能够对车间生产调度方案 进行评价，分析系统的运行性能，并选择系统的动态结构参数。由于车间制造系统 的复杂性，很难用有精确解的数学模型对其进行描述分析。而通过运行仿真模型可 以对实际系统进行运行性能和状态方面的定量评估与分析，从而对系统采用合适的 调度方法。 计算机仿真调度为复杂的车间生产调度研究提供了一种模拟实验研究，通过建 立车问制造系统的仿真运行模型，利用离散事件仿真技术，可以从各个方面针对车 间生产调度进行研究。在应用上计算机仿真车间生产调度方法主要用于车间生产调 度的系统性能分析与评价。 1 3 车间生产调度问题国内外研究现状与发展趋势 1 3 1 车间生产调度问题国内外研究现状 车间生产调度问题研究始于2 0 世纪5 0 年代，j o h n s o n 在对两台机床的流水生产 调度问题进行研究时，提出的解决n 2 f c m 戤和部分特殊的n 1 3 f i c m 缸问题的优化算 法，代表生产调度理论研究的开始，他于1 9 5 4 年首次发表了关于f l o w s h o p 型调度 问题的文章后，众多学者便丌始对生产调度问题进行了广泛研究1 5 1 2 8 】。f l o w s h o p 型调度问题假设所有作业都在同样的设备上加工，并有一致的加工操作和加工顺序； 而j o b s h o p 是最混合型的调度类型、并不限制作业操作的加工设备，并允许每个作 业加工具有不同的加工路径和不同的加工批量。由于调度问题的复杂性，引起了无 数研究者的浓厚兴趣，在过去的近5 0 年里，大量的研究成果被发表。随着7 0 年代 后期调度理论研究的深入及各种交叉学科的发展，涌现出了许多新的车间生产调度 理论与方法。 1 、车间生产调度理论模型研究方面 最初集中在车f 自j 生产调度问题的静态理论模型，研究人员针对制造企业各种特 定的生产环境、生产资源、约束条件、调度目标等条件下，构建静态调度模型，如 7 武汉理丁大学博士学位论文 文献 9 1 1 围绕流程企业的不同生产条件下的生产问题建立相应的调度理论模型， 研究工作涉及了流程企业车间生产调度的几个重要方面，建立了较完善的车间生产 调度问题框架、选取和混合使用各种调度算法以及流程企业物料流调度优化；文献 1 2 - 1 4 对混合型企业车问生产调度问题理论调度模型进行了研究，根据混合型生产 过程的概念、特点，讨论了混合型企业车间生产调度问题研究中存在的问题及其解 决途径；文献 1 5 2 0 中提出了一种结构化集成调度系统理论并基于这个理论对实际 车间生产调度的建模进行了研究。认为应该从系统的角度来研究车间生产调度问题， 因为实际车间生产调度问题规模庞大、结构复杂、因素众多，本身就是个大系统问 题，因此调度问题的研究应该从一个新的基点开始，即把调度研究的重点从传统的 算法研究转移到系统性研究上。结构化集成调度系统理论把实际车间生产调度问题 划分为资源和任务，并以这种分析方法为核心，用大系统的观点对车间生产调度问 题涉及到的各种因素进行整体性研究：文献 2 1 - 2 5 中考虑车间生产调度问题中的各 种柔性化要求，构建柔性化的车间生产调度模型，从柔性的角度出发，分析与车间 生产调度密切相关的因素，将调度决策的求解朝着综合智能化的方向发展，给出可 行的调度问题解决方案；文献 2 6 3 0 中针对各种制造环境的不同情况，给出了与之 相适应的调度问题模型；文献 3 1 - 3 8 中给出了在不确定性条件下，车间生产调度问 题模型的构建，分析了车间生产调度中所存在的各种不确定性，阐述了不确定性的 分类，不确定性的数学描述，不确定性车间生产调度的数学模型，各种调度方法， 处理不确定性车间生产调度的优化方法等，给出了解决不确定性车间生产调度的有 关方法；文献 3 9 - 4 6 中针对车间生产调度问题中存在模糊信息的情况下，对模糊性 车间生产调度问题模型构建进行了研究，应用模糊集理论建立基于经验规则的生产 计划调度模糊模型，以基于模糊推理的模糊算法求解以语言变量描述的生产计划调 度模糊模型；文献 4 7 - 5 0 分别针对混合型车间生产调度问题的结构形式及知识表达 进行了研究，提出了一种统一结构以及知识表达方法；文献 5 卜5 3 针对协同生产、 人机协同的动态调度等方面进行了研究，探讨了车间生产调度中的协同问题。 应用这些静态生产调度模型理论方法对企业实际生产问题进行调度时，存在很 大的局限性，由于在调度模型的构建上将所有的影响因素都作为静态不变的常量， 这与实际问题的不一致使得在车间生产调度中出现严重矛盾，或者出现根本不能应 用的情况出现。近年来，随着对车间生产调度问题研究的深入与发展，将一些影响 车间生产调度问题的因素都作为动态可变量处理，从而将车间生产调度问题作为动 态问题来研究，构建出动态生产调度模型【5 4 - 6 2 】，如文献 5 6 中构建了一种多阶段动 态生产调度模型，针对紧急任务的临时插入及随之而来的已调度任务释放问题，分 析了现有的动态调度模式，提出了“资源可用性 和“上相似任务”的概念，根据 武汉理工火学博士学位论文 资源对任务的可用性与任务问对资源的需求相似性，对调度机制进行了改进，提出 了一种多阶段动态生产调度模型，以避免任务的无谓中断与释放，达到减少受影响 任务数量、降低任务调整成本的目的：文献 2 2 中对多品种批量生产的企业动态生 产计划进行了研究，介绍了多品种批量制造企业的一种动态生产调度模型，用于灵 活处理企业在实际生产中出现多变的生产情况；文献 5 5 】研究了动态生产调度方法， 在总结当日订有关多a g e n t 调度问题研究方法的基础上，描述了一种基于多a g e n t 的生 产调度框架结构以及此框架结构中代理之f b j 的信息运动规律，最后探讨了适用于该 框架结构的动态调度机制。 在这些车间生产调度模型的建模方法研究上，最初采用功能与信息建模方法、 资源建模方法、工作流建模方法、过程建模方法等构建模型1 5 4 - 6 2 ，2 0 世纪初出现了 采用网络计划建模法构建车问生产调度模型，如：g r a i 网络、p e t r i 网法等 6 3 - 6 9 l ； 近年来，向多建模方法综合应用的方向发展。 总体来讲，在研究车间生产调度问题并建立调度模型时，将车间生产调度问题 要么作为静态问题处理，要么作为动态问题来处理，在研究该问题时基本上没有将 车间生产调度的静态特性与动态特性结合起来研究。在研究车间生产调度问题中的 不确定因素时，只是作为特定条件来处理，并没有将车间生产调度问题中的不确定 冈素与车间生产调度问题静态、动态特性结合进行系统性的研究。 2 、车间生产调度问题的算法研究方面 在车间生产调度问题的算法研究方面，整数规划、多目标优化、仿真和简单规 则优化算法研究较多，发表的文献也相当丰富 7 0 - 8 2 ，这些传统的调度方法在应用中 存在很大的局限性，如难以建立准确约束条件下的数学模型，并且求最优解时是随 问题规模呈指数倍增长的n p 难题，因此只能对小规模的系统求解。随着各种新的相 关学科与优化技术的建立与发展，2 0 世纪9 0 年代开始出现了许多新的优化算法， 如神经网络、遗传算法、基于知识的方法、基于离散事件系统( r e d s ) 的解析模型和 方法等，研究较多的有模拟退火算法( s a ) 、遗传算法( g a ) 、禁忌搜索( t s ) 、进化规