（管理科学与工程专业论文）基于成本的集成协作计划与调度模型及其进化算法研究.pdf

王伟业：基于成本的集成协作计划与调度模型及其进化算法研究 摘要 在实际的生产过程中，生产形式是多种多样的，工件的调度受到加工路线和加 工能力的的制约，因此必须将部分工件外包给合作伙伴协作加工。为此，建立一个 集成协作计划与调度的模型，在实现工艺路线决策的同时，给出在规定的生产周期 里规划出生产成本最低的工件调度组合变得尤为重要。 随着各种相关学科与优化技术的建立与发展，在调度领域也出现了许多新的优 化方法。利用不同优化机制、优化行为和优化结构的互补性来提高求解性能，将多 种算法混合使用成为求解调度问题的重要手段。本文采用群集智能算法，研究调度 对象、生产资源和工艺路线之间的制约关系，探索科学的多目标决策和评价体系， 结合生产过程的动态实时性以及环境影响，建立集成协作计划与调度模型。本文的 主要研究工作如下： l 、构建基于成本的集成计划与调度模型。解决了部分工件可以外包，部分工 件无法外包的不固定调度集的调度问题，在给定的生产周期旱规划出制造工件最多 的工件调度组合：综合运用遗传算法和启发式规则求解模型，在实现工艺路线决策 的同时，保证了计划的可行性和调度的一致性。 2 、研究定单可分的协作计划模型及其进化算法。针对部分定单可拆分，部分 定单不可拆分的协作规划问题，建立定单可拆分的协作计划模型，提高了供应链的 资源利用效率，并进一步降低协作成本，扩大供应链的协作优化的空间：应用差分 进化算法在连续性求解最优化问题方面的优势，设计了一种改进的差分进化算法对 模型进行优化，实现了多工艺路线选择、协作任务决策以及协作伙伴选择的同步决 策。 3 、研究定单可分的集成协作计划与调度模型及其混合进化算法。结合集成计 划与调度模型和定单可分的协作计划模型，建立定单可分的集成协作计划与调度模 型；综合运用遗传算法和差分进化算法，设计出一种新型的混合进化算法，实现在 协作生产、生产计划、工艺路线选择以及调度这四个方面的协同寻优，并提出适应 于模型的混合进化流程。 关键词：计划与调度；协作计划；定单可分；差分进化；混合进化；集成模型 千伟业：基于成本的集成协作计划与调度模型及j e 进化算法研究 i i i a b s t r a c t i np r a c t i c e ，t h e r ea r ev a r i e t yf o r m so ft h ep r o d u c t i o n , a n dt h ew o r k p i e c es c h e d u l i n g i se n s l a v e dn o to n l yb yt h ep r o c e s s i n gr o u t e ，b u ta l s ob yt h ew o r k i n ga b i l i t y s oi t i s i m p o r t a n t t oc o n s t r u c tam o d e lf o ri n t e g r a t i o no fc o l l a b o r a t i v ep l a n n i n ga n ds c h e d u l i n gt o g i v et h eb e s tp r o d u c tl i n e a n dt h es c h e d u l i n gc o m p o u n d i n go fp r o d u c i n gt h em o s t w o r k p i e c ei nt h es t a t e dp r o d u c t i o nc y c l e w i t ht h ed e v e l o p m e n to fr e l e v a n td i s c i p l i n e sa n do p t i m i z a t i o n ，t h e r ea l em a n yn e w o p t i m i z a t i o nm e t h o d sa p p e a r e di n t h es c h e d u l i n ga r e a u s i n gd i f f e r e n to p t i m i z a t i o n m e c h a n i s m s ，o p t i m i z a t i o nb e h a v i o r sa n do p t i m i z a t i o ns t r u c t u r e st oi m p r o v et h es o l v i n g p e r f o r m a n c ea n dm i x i n gt h ea l g o r i t h m sb e c o m ea ni m p o r t a n tm e a n so fs o l v i n gt h e s c h e d u l i n gp r o b l e m i nt h i sp a p e r , s w a r mi n t e l l i g e n c ea l g o r i t h m sa l ec o n s t r u c t e dt os t u d y t h ec o n s t r a i n t sb e t w e e ns c h e d u l i n go b j e c t ，p r o d u c i n gr e s o u r c e sa n dt h ep r o d u c tl i n e ， e x p l o r em u l t i o b j e c t i v ed e c i s i o n m a k i n g a n de v a l u a t i o ns y s t e m ，a n de s t a b l i s ha n i n t e g r a t e dc o l l a b o r a t i v ep l a n n i n ga n ds c h e d u l i n gm o d e lc o m b i n e dw i t ht h ed y n a m i c r e a l t i m e p r o d u c t i o np r o c e s s a n de n v i r o n m e n t a l i m p a c t ，n l e m a i nc o n t e n t sa n d a c h i e v e m e n t so ft h ed i s s e r t a t i o na l ea sf o l l o w s ： 1 am o d e lf o ri n t e g r a t i o no fc o l l a b o r a t i v ep l a n n i n ga n ds c h e d u l i n gi sc o n s t r u c t e d b a s e do nj o bc o s t s o l v et h es c h e d u l i n gp r o b l e ml a c ko ft h ew o r k i n ga b i l i t ya n dt h e p r o b l e mo ft h eu n f i x e ds c h e d u l i n gs e ti nw h i c hp a r to f t h ej o b sc a nb eo u t s o u r c e db u t p a r to ft h ei o b sc a n n o tb eo u t s o u r c e d ，a n das c h e d u l i n gw i t ht h em o s tj o b si nt h es t a t e d p r o d u c t i o nc y c l ei sg i v e n ah y b r i dg e n e t i ca l g o r i t h mw i t hh e u r i s t i c sr u l e s i sp u tf o r w a r d t ob ea p p l i e di nt h em o d e l t h ed e c i s i o no fp r o c e s sr o u t ei sm a d ea n dm e a n t i m et h e f e a s i b i l i t yo fp l a n n i n ga n dt h ec o n s i s t e n c yo fs c h e d u l i n ga l ee n s u r e d 2 ac o l l a b o r a t i v ep l a n n i n gm o d e lb a s e do nd i v i s i b l eo r d e ra n di t se v o l u t i o n a l g o r i t h mi ss t u d i e d a i m i n ga tt h ec o l l a b o r a t i v ep l a n n i n gp r o b l e mi nw h i c hp a r to f t h e o r d e r sc a nb ed i v i s i b l eb u tp a r to ft h eo r d e r sc a n n o tb ed i v i s i b l e ，ac o l l a b o r a t i v ep l a n n i n g m o d e lb a s e do nd i v i s i b l ep a r t l yo r d e r si sc o n s t r u c t e dt om a k ef u l lu s eo ft h es u p p l yc h a i n ， r e s o u r c e sr e d u c ec o l l a b o r a t i v ec o s ta n de x t e n dt h es p a c eo ft h ec o l l a b o r a t i v eo p t i m i z ei n t h es u p p l yc h a i n b yt a k i n gt h ea d v a n t a g eo fd i f f e r e n t i a le v o l u t i o n ( d e ) i ns o l v i n g p r o b l e m so fc o n t i n u o u so p t i m i z a t i o n ，ad i f f e r e n t i a le v o l u t i o na l g o r i t h m i sp u tf o r w a r df o r t h em o d e lt or e a l i z et h es y n c h r o n o u sd e c i s i o n - m a k i n go fc o l l a b o r a t i o nt a s k ，c o l l a b o r a t i v e p a r t n e rs e l e c t i o n ，m a n u f a c t u r i n gr o u t e 3 am o d e lf o ri n t e g r a t i o no fc o l l a b o r a t i v ep l a n n i n ga n ds c h e d u l i n gb a s e do n d i v i s i b l eo r d e ra n di t s h y b r i da l g o r i t h m i ss t u d i e d am o d e lf o r i n t e g r a t i o no f 扬州大学硕+ 学位论文 c o l l a b o r a t i v ep l a n n i n ga n ds c h e d u l i n gb a s e do nd i v i s i b l eo r d e ri sc o n s t r u c t e dw i t h i n t e g r a t e do ft h em o d e lf o ri n t e g r a t i o no fc o l l a b o r a t i v ep l a n n i n ga n ds c h e d u l i n ga n dt h e c o l l a b o r a t i v ep l a n n i n gm o d e lb a s e do nd i v i s i b l eo r d e ran o v e l h y b r i da l g o r i t h m i n t e g r a t e do fg e n e t i ca l g o r i t h ma n dd i f f e r e n t i a le v o l u t i o na l g o r i t h mi sp u tf o r w a r dt ob e a p p l i e di nt h em o d e l ，i m p l e m e n t i n gc o l l a b o r a t i v eo p t i m i z a t i o ni nt h e s ef o u ra s p e c t so f t h ec o l l a b o r a t i v ep r o d u c t i o n , p r o d u c t i o np l a n n i n g ，p r o c e s sr o u t i n ga n ds c h e d u l i n g ，a n d t h ec o - e v o l u t i o np r o c e s sa d a p t e dt h em o d e li sp r o p o s e df o rt h em o d e l k e y w o r d s ：p l a n n i n ga n ds c h e d u l i n g ：c o l l a b o r a t i v ep l a n n i n g ；d i v i s i b l eo r d e r ；e v o l u t i o n a l g o r i t h m ：h y b r i de v o l u t i o n ；i n t e g r a t i o nm o d e l 王伟业：基于成本的集成协作计划与调度模型及其进化算法研究 6 7 扬州大学学位论文原创性声明和版权使用授权书 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下独立进行研究工作所取得的研究 成果。除文中已经标明引用的内容外，本论文不包含其他个人或集体已经发表的研 究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本声 明的法律结果由本人承担。 学位论文作者签名： 书啦 ，i 签字日期：乃矽年r 月f 尸日 学位论文版权使用授权书 本人完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国 家有关部门或机构送交学位论文的复印件和电子文档，允许论文被查阅和借阅。本 人授权扬州大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以 采用影印、缩印或扫描等复制手段保存、汇编学位论文。同时授权中国科学技术信 息研究所将本学位论文收录到 - 月侈日 导师签名：锄乙 签字日期。州。年j 月l7 日 王伟业：基于成本的集成协作计划j 调度模型及j e 进化算法研究 1 1 生产计划和调度 第一章绪论 生产计划是企业为实现其生产目标所进行的一系列的预测和决策活动。它的主 要任务是确定在一定时期内企业要完成的产品和生产这些产品所需的原料、设备、 人力、财力、能源等资源，以获得更高的经济效益。 生产调度也称车间作业计划，简称为调度。它是在计划的基础上选择执行一组 可行计划，并且在满足完成时间和资源等约束条件下，为每个活动分配资源和时间。 生产计划和调度问题都是在给定的时间范围内分配资源来完成任务。其中计划 定义了必须做什么，并对怎么来做加以约束，需要综合考虑时间估计、每种行为所 需资源、行为之间的优先关系以及约束关系n q l 。调度则制定了j j n - r _ 作业的时问安排， 并按照计划实际执行要求的行为。它更偏重于时间概念，需要在工厂或者公司的范 围内将问题分解为更小的规模以利求解。同时，调度还要与企业的组织层和决策层 相关联，以实现生产的高效率、高柔性和高可靠性h 。5 1 。生产计划和调度的区别在于 生产计划主要侧重于资源的需求和粗分配，生产调度则主要关心任务的具体安排和 资源的详细分配。在生产管理领域，并没有对生产计划和生产调度进行明确的界定， 计划是较高层次上生产规划，侧重于时间上的规划，时间跨度放在整个计划期；而 调度是较低层次上的生产规划陋刮，侧重于与生产现场的结合，是对计划期内某个细 节时间的精细规划。 然而，在生产实践中，生产计划和生产调度是密不可分、高度耦合的。其中， 计划是调度的目标，同时调度对计划起约束作用。计划是建立在充分了解任务调度 约束上的对整体目标的预测和决策活动n 引，调度则负责将计划展开并分配到详细 的资源和作业队列中 1 4 - 1 7 o 计划不充分就难以得到完备的调度，调度不好将使资源 被浪费，同时会阻碍一个良好计划的实施。因此，计划与调度是一个极其复杂的问 题，需要有有效的决策支持方法和柔性、敏捷的模型，以及快速、可靠的求解技术。 1 1 1 研究现状 调度理论源于对制造车间生产计划与控制的研究，一般认为j o h n s o n 于1 9 5 4 年对流水车间两台机床作业排序问题求解，是调度理论产生的标志n 引。此后5 0 年 来，在运筹学、工业工程和计算机科学等领域，调度理论得到了理论界和工程界研 究人员的广泛关注和研究；其应用领域涉及电力调度、运输调度、水资源调度、网 2扬州大学硕士学位论文 络通信调度、人员调度、项目调度和制造系统生产调度等方面，制造系统生产调度 问题更是最为引人注目的研究热点之一。 针对生产计划与调度问题的研究主要可分为两个方面，包括生产计划与调度问 题的建模和计划调度问题算法研究。计划与调度问题的建模，是其算法设计与分析 的基础。根据理论研究的需要或根据实际生产系统的特点，提出一个或一类子问题， 并以一定的形式对其进行描述，建立计划与调度问题模型。其中描述形式主要包括： 问题的语义描述、问题中各要素的描述、问题的符号表示、问题的公式化描述、问 题的图论描述等。 在过去几十年中，人们对生产计划和调度进行了大量的研究，提出的方法需要 和当时的社会生产方式相适应。在“以产品为中心”组织生产的年代，由于是少品 种的大量生产，其假设是市场需求和供应能力无限，经济批量法与定货点法是比较 好的方法n 蚴1 。当市场需求和供应能力无限的假设不再成立，市场供过于求造成大 量的生产积压和停滞时，原先的计划和控制方法已不适应新的环境，新的生产计划 与调度方法和理念应运而生。这时的物料需求计划( m a t e r i a lr e q u i r e m e n tp l a n n i n g ， m r p ) 、最优生产技术( o p t i m i z e d p r o d u c t i o nt e c h o n o l e g y ，o p t ) 和基于准时制( j u s t i nt i m e ，j i t ) 的思想获得了巨大的成功。在生产管理步入信息化和集成化的时代， 涌现了许多更先进的生产管理理念和方法，制造资源计划( m a n u f a c t u r er e s o u r c e p l a n n i n g ，m r p i i ) 、计算机集成制造系统( c o m p m e ri n t e g r a t e dm a n u f a c t u r es y s t e m ， c i m s ) 、企业资源计划( e n t e r p r i s er e s o u r c ep l a n n i n g ，e r p ) 、制造执行系统 ( m a n u f a c t u r ee x e c u t i o ns y s t e m ，m e s ) 以及更多生产计划和调度方法及手段的出 现，使生产向更敏捷、更具有柔性，更精细的方向发展瞳 驯。 近来，在计划调度集成优化研究方面取得了较大的进展。较早对生产计划与调 度集成优化的有j b l a s s e r r e 等人，提出了一种双层的车间环境集成计划与调度模 型呦1 ：上层为分批层，可利用一个给定的下层作业排序作为约束得到一个可行计划； 下层为调度层，可利用上层得到的产品批量求得一个新的作业排序，这种方法最大 的缺点在于，它只能收敛于局部最优解。针对装配型产品制造，a n w a r m f 等口给出 了一种启发式方法，通过对产品定单进行分组，寻找网络关键路径进行调度。它以 准备时间、库存和总交付周期最小为目标确定最优批量，但没有考虑多周期加工情 况。r u h u l 等2 1 为批量生产企业提出原材料采购及生产批量同时优化方法，提出了 带三个不同的约束惩罚函数的遗传算法。w o l f g a n g 等口羽指出了d l s p 问题的复杂性， 并对一单机床多项目的生产环境d l s p 问题建立了其模型，通过带模拟退火的启发 式算法求解。k n u t 等m 1 也研究了单机床情况下的分批与调度问题。w i p 等5 3 提出 了一种提前一延迟交货生产计划与调度问题和遗传算法求解方法。 国内在车间生产计划与调度集成优化方面的研究也取得了一定进展。熊锐等哺1 伟业：基于成本的集成协作计划与调度模型及其进化算法研究 建立了一种车间集成生产计划与调度模型，同时考虑了工序加工的先后顺序约束和 作业在机床上的加工能力约束，并采用拉氏松弛法对其进行求解，但求解松弛调度 子问题算法的计算复杂性较大，难以解决规模较大的问题。文献7 瑚3 针对一类 j o b s h o p 车间的生产计划和调度的集成优化问题，提出一种非线性混合整数规划模 型，该模型利用调度约束来细化生产计划，以保证得到可行的调度解；并采用由启 发式规则和遗传算法构成的混合遗传算法进行求解。尚文利等1 针对多品种批量生 产类型，建立了一种调度约束的生产计划与调度集成优化模型。它是一基于分解方 法的、适于批量生产的车间计划调度集成优化，对计划和调度的目标函数进行综合 评价。模型的目标函数是使总调整费用、库存费用及生产费用之和最小；约束函数 包括库存平衡约束和生产能力约束，同时考虑了调度约束，即工序顺序约束和工件 在单机上的加工能力约束，保证了计划可行性。 此外，国内的其他学者林慧苹等h 们针对复杂的生产计划和调度集成问题中所面 临的建模过程复杂、求解困难等问题，使用规划方程方法和基于多代理的方法，采 用面向过程的思想，提出了一种基于工作流技术的分层调度模型；并通过实例证明， 其提出的建模方法易于直观理解，求解快速有效；但其实例中只有二个产品四个工 件。熊红云等h 针对多级、多资源约束的柔性生产线，以使总调整费用、库存费用 及加班费用之和最小为目标，建立了一种分批与调度集成的通用模型；但没有考虑 生产费用和调度约束。朱濒等h 2 1 提出了待料型生产系统的概念，并建立待料型生产 计划与调度优化的三个层次的数学模型：综合计划模型、生产调度模型和工艺优化 模型。为具有待料现象的企业提供优化生产组织的一般分析方法和建模思路，以增 进此类企业的经济效益。徐和平等h 副给出一种多阶段生产制造系统的生产计划与调 度综合模型，采取分解与交互逼近的方法来求解，得到生产计划与调度的局部最优 解。 综观上述国内外在车间生产计划与调度集成优化方面研究，出于计算的复杂 性，一般都对实际问题做了较大的简化，不考虑中间件或在制品的库存，并且计算 实例中的产品数量、工艺数量及设备数量等都非常的有限。生产实际中的生产计划 与调度集成优化，还有很多问题有待于进一步深入研究。 1 1 2 研究方法 生产计划和调度问题的研究受到应用数学、运筹学和工程技术等领域科学家的 重视，如今，经典调度理论基本成熟，但实际问题和经典问题还是有相当的距离， 经典调度理论的一些基本原则对于解决实际问题还是不够的，需要重新考虑和进一 步拓展。 从2 0 世纪8 0 年代开始，人工智能方法开始真正应用于调度问题，基于人工智 4扬州大学硕士学位论文 能的调度方法有智能调度专家系统，约束规划方法和基于多a g e n t 系统的合作求解 方法等。到了9 0 年代后期，计算智能作为人工智能新发展的主流地位被确定，这 是人工神经网络、模糊系统和进化计算的有机融合而形成的新的方法。计算智能在 调度方面的研究如火如荼，成为智能调度方法的主流，主要的方法有人工神经网络、 模拟退火、禁忌搜索、模糊逻辑和遗传算法等h 8 | 。 无论是离散事件系统还是连续过程生产系统，几乎没有一个生产系统的运行能 够维持在一个一成不变的调度上，这是因为外部有应对市场需求改变而引起定单改 变的因素，也有内部的生产故障、资源短缺以及加工时间的改变等因素。这些因素 都会使原来的调度性能变坏或者不再可行，所以再调度或者动态调度是不可避免 的。将实时技术和人工智能技术相结合，形成了一个新的技术领域，人们称之为“实 时智能 。实时智能重要应用于实时系统的调度中，其中的动态调度算法是核心部 分，也是研究的热点h 铲刚。 纵观过去几十年对生产计划和调度问题的研究，主要方向是将计划和调度问题 集成，或者分解为更小的规模以利求解，同时要与企业的组织层和决策层相关联， 实现生产高效率、高柔性和高可靠，也得出了不少成果。主要有： l 、数学规划方法 数学规划方法是将调度问题简化为数学规划模型，采用整数规划、动态规划以 及决策分析算法来解决调度最优化或者近似优化问题，属于精确调度方法，也称为 优化调度方法。 该方法的任务分配和全局性效果比较好，能够进行凸和非凸问题的全局优化， 但它对模型的要求很高，对复杂多变的调度问题来说，单一的模型不能够考虑到所 有的因素，参数的变化导致算法的重用性很差，以及求解空间大和计算困难等问题。 2 、启发式搜索方法 启发式搜索方法是利用任务无关信息来简化搜索过程，问题求解就是系统化地 构造或者查找解，搜索过程包括检查搜索空间、评估可能有解的的不同路径以及记 录已经搜索到的不同路径操作，a + 算法是一种典型的启发式搜索方法。 该方法的优点是利用了面向特定问题的知识和经验，可以较快产生比较好的解 决方案，缺点是用来评估解决方案的效果的手段还比较少，对如何提高搜索效率和 解决较大规模的问题还需要进一步探索。 3 、系统仿真方法 系统仿真方法不单纯追求系统的数学模型，它侧重于对系统中运行的逻辑关系 进行描述，为所有分配、排序和时间选择等决策的结果提供局部的分析，能够对一 个给定的调度用很低的代价进行详细和快速的分析，对各种方案进行对比，从而选 择效果最优的调度方法和系统动态参数。 千伟业：基十成本的集成协作计划与调度模型及】娃生化算法研究 由于生产系统的复杂性，很难用一个精确的模型来进行描述和分析，且仿真的 费用很高，准确性也受到人员判断和技巧的限制，所以即使是精度很高的仿真模型 也不能够保证通过实验能够找到优化的调度方案。 4 、人工智能方法 2 0 世纪8 0 年代以来，人工智能( a r t i f i c i a li n t e l l i g e n c e ，a i ) 逐渐成为调度研 究的重要方法，包括智能调度专家系统，约束规划方法和基于多代理系统 ( m u t i a g e n ts y s t e m ，m a s ) 的合作求解方法。 建立一个专家系统需要构建相关的知识库，知识源一般指人类专家或者模拟数 据，其次是面向约束的推理机制，使用约束的知识来保证调度的一致性。该方法可 以使用定量的知识也可以使用定性的知识，也能够产生比较复杂的启发式规则，可 以包括复杂的数据结构信息和操作这些数据的特定技术。但缺点也是难以克服的， 例如系统的建立、验证和后来的维护升级都非常困难，而且结果可能会严重偏离最 优解和次优解。 约束规划方法是通过限制变量选取顺序和变量赋值顺序来减小搜索空问的大 小。它可以用来实施柔性的和有效的调度系统，因为它把各种不同的算法包装起来， 对可重用的算法进行规划。这种方法的求解代价比较大，由于考虑了多种约束，求 解难度大，不能够得到最优解。 为了解决大规模的复杂的实际问题，可以采用“分而治之 的方法来开发分布 式调度系统，通过m a s 实现分解调度技术以及利用相关知识系统协作求解整个调 度问题。m a s 可以弥补调度理论的不足，增强实际应用中的灵活性，其自身在理 论上需要进一步完善，实现标准化。 5 、计算智能方法 几种常见的基于计算智能的调度方法主要有人工神经网络、模拟退火、模糊逻 辑和进化搜索算法。 人工神经网络是在对人脑组织结构和运行机制认识理解的基础上模拟其结构 和智能行为的一种工程系统，其中h o p f i e l d 人工神经网络最具代表性。人工神经网 络具有很强的分布式存储能力和很大的存储空间，具有自学习能力，能够通过学习 建立和改变知识，容错性很好。但在实际生产中应用得依然不多，主要是因为人工 神经网络学习效率差，难以表达符号知识和其他知识，计算速度慢且精度不高，需 要进一步的改进。 模拟退火是将组合优化问题与统计力学中的热平衡问题类比，通过模拟退火过 程，找到全局或者近似最优解。模拟退火算法可以突破局域搜索的限制，转移到代 价较高的解答，而且如果选择参数得当，会在很快的时间内达到收敛。但是，在实 践中一般不会产生最优结果，且参数选择很困难，如果选择不当，会使计算时间很 6扬州大学硕士学位论文 长并得不到好的结果，因此需要和其他方法综合使用。 模糊逻辑是运用数学手段来模仿人类思维，对复杂事物进行模糊处理。虽然模 糊逻辑的研究时间不是很长，但在智能模拟和智能控制等领域已经有了飞速的发 展。模糊系统的显著特点是能够直接地表示逻辑，适合高级知识表达，具有较强的 逻辑功能，当它没有本质的获取知识的能力，需要领域专家知识的指导，通常是和 其他方法结合使用。 进化计算技术是一类模拟生物界自然选择和进化机制的随机搜索算法，应用最 广泛的是遗传算法和免疫算法，都是对算法所产生的染色体( 符号串) 进行评价， 使适应性好的染色体有更多的繁殖机会，经过反复迭代，直到达到某种形式的收敛。 进化算法的优点是问题不必用数学模型的方法表示，而且能够在较短的时间内在搜 索空间的不同区域达到收敛，但局部优化的收敛还是很慢，对解决方案的评估比较 困难，收敛速度也无法保证。 1 1 3 发展趋势 对生产计划和调度的研究虽然已经有几十年的历史，但仍然未形成一整套系统 的方法和理论。由于制造企业不同的生产特点，对不同的生产周期、生产方式以及 管理方法所采用的计划和调度策略也存在很大不同。同时，理论研究和实际应用之 间也存在着很大的差距，一些在理论上能够获得最优解的方法往往忽略了很多实际 因素：理论上虽然能够响应系统的动态变化，但无法保证响应速度以及对调度结果 的优化。 进入2 1 世纪，随着i n t e m e t 技术的飞速发展和敏捷制造、虚拟制造、动态联盟 等先进制造技术哲理的提出，使得网络化制造模式下的调度研究以及企业异地生产 调度研究等成为调度领域新的研究方向。研究人员对开发更先进的计划和调度系统 的理论和方法从来没有停止，目前的研究重点主要在以下几个方面： ( 1 ) 寻求新的算法。解决大规模问题、探寻更先进的搜索策略和更快的计算 速度都是新的优化算法的研究者们迫切解决的问题。 ( 2 ) 生产计划与车间调度的集成问题。在实际的生产管理中，生产计划和车 间调度一般是分属不同层，这会导致计划与实际调度脱节而不可行的问题，如何将 生产计划层和车间调度层做到无缝连接，进行集成优化，获得整体最优的调度系统 需要进一步的研究。 ( 3 ) 动态调度问题。生产过程中，各类事件随机到达，需要调度能够实时反 应。传统的调度算法都是“开环”调度算法，调度一旦形成了，就不能够通过连续 反馈作出调整。针对实时环境不可预测的特点，提出了“闭环”控制或者基于反馈 控制的实时调度的要求，这就是动态调度方法。 王伟业：基于成本的集成协作计划与调度模型及其进化算法研究 最近十多年来，计算机技术、网络技术以及数据库技术的迅速发展和各种新思 想的提出，也极大的促进了生产计划与调度系统的应用与发展。主要体现在以下两 个方面： ( 1 ) 从功能上看，正在向功能集成化、信息化和智能化阶段发展。一方面， 在网络和数据库技术支持的基础上，计划调度系统与其它系统如库存、采购、销售 等信息管理系统相互集成，实现数据和信息共享，适应用户多层次与多方位的需求； 另一方面，将人工智能的概念、方法和技术( 如：专家系统、模式识别、神经网络 等) 应用于计划调度系统，提高了系统的智能水平。 ( 2 ) 从技术上看，转向网络化、组件化、标准化。随着w e b 技术和组件开发 技术的日趋成熟和推广，计划调度系统软件开始由c s ( c l i e n t s e r v e r ) 模式向 b s ( b r o w s e r s e r v e r ) 模式转变：程序开发方法也由传统的开发方法向基于组件的开 发方法( c o m p o n e n t b a s e dd e v e l o p m e n t ，c b d ) 过渡。同时，软件生产更加标准化， 从需求分析、详细设计到开发测试，形成统一的标准。 在现代经济生活中，由于科技和信息的发展，市场环境也发生了巨大的变化， 确保定单任务的完成、生产过程的正常运行和最佳利润等传统目标已经不能够满足 现代企业的要求。作为企业生产管理的重要手段和工具，计划和调度系统已经成为 一个多要求、多目标的生产规划体系，它接受来自企业内外的各类信息，动态地调 整企业的生产运作，满足生产目标多元化的要求。 1 2 生产协作 1 2 1 生产协作的含义 生产协作是指将具有相互依赖关系的分散的生产实体，通过“竞争一合作一协 调”的自组织运行机制组织在一起，相互配合，协调一致地工作，以完成任何单一 生产实体不能完成或虽能完成但不经济的任务，从而实现总体效果优于各个单独效 果之和的一种生产形式1 5 引。 由上述可知，生产协作的主体是相互依赖与分散的生产实体，生产协作的目的 是要使这些生产实体协调一致地工作，以完成需共同协作才能完成的任务。为实现 其目标，生产协作需要引入“竞争一合作一协调的自组织运行机制。强调竞争， 是为了确保参与生产协作的各生产实体资源的优化配置和运行效率；强调合作，是 因为参与生产协作的各生产实体所承担的任务之间存在着各种物理上和逻辑上的 相互依赖，最终任务的实现需要各生产实体的互相配合；强调协调，则是由于各生 产实体在实现各自承担的生产任务的过程中，存在时间、资源、目标等各方面的约 8 扬州大学硕上学位论文 束或冲突，相互间需要进行信息交流，使得各自的生产行为间能够和谐一致、配合 得当。 生产协作根据协作主体的性质，可分为企业内部的生产协作和企业外部的生产 协作两大类。企业内部生产协作是指企业内部与生产相关的各职能之间或同一职能 不同层级之间为实现企业统一的生产目标而进行的生产协作。按协作主体之间的关 系又有总体协作和多厂协作两种类型1 5 3 1 。总体协作是指公司不同职能如供应、生产、 仓储、销售等之间的协调。根据协调的职能组合，又分为供应一生产、生产一库存、 生产一销售、供应一生产一销售等协调类型。多厂协作主要研究多个工厂或车间之 间的生产计划、生产批量和安全库存方面的协调问题。企业外部的生产协作是指在 原材料供应、零部件生产、装配到成品形成过程的供需网络中，通过虚拟企业有组 织的成员企业之间生产协作过程，最终完成产品增值的一种管理模式。它是受j i t 、 全球制造、全球营销等先进经营观念影响，而成为供应链管理( s u p p l yc h m n m a n a g e m e n t ，s c m ) 与后勤管理( l o g i s t i c s ) 的重要研究内容。 1 2 2 生产协作研究状况 生产协作资源优化重组的前提是生产协作建模。生产协作建模是以形式化或信 息化的形式对生产企业进行抽象描述，是分析、仿真、优化生产协作功能、过程、 活动和行为的基础【5 4 1 。目前对生产协作的建模研究可以分为两大类：( 1 ) 建模方法 研究；( 2 ) 建模内容研究。由于面向敏捷的生产协作具有临时性、多企业合作性、 面向过程组织、组织动态等特性，所以传统的c i m s o s a 、g r a i 、i d e f 、r a i s e 及p u r d u e 等不能直接用生产协作模型。为此叶丹【l l 】提出一种多视图集成化的动 态联联盟企业建模方法。g u o 等【5 5 j 提出了基于a g e n t 的虚拟企业组织设计方法和 集成结构。在建模内容方面，叶丹【5 6 j 提出了过程模型。李培根、张洁【57 j 提出了基于 多a g e n t 机制的生产协作动态重构模型。 协作伙伴选择问题是生产协作的关键问题，研究成果较多。合作伙伴选择一般 分为两部分：第一，伙伴选择的评价指标体系：第二，伙伴的综合评价方法。由于 不同的学者研究的角度不同，提出的评价指标也各不相同。如马士华等【l2 j 认为选择 协作伙伴主要考虑的因素有：业绩、业务结构与生产能力、质量系统和环境。在评 价方法方面，常用的评价方法有：层次分析法( a h p ) 、模糊综合评价法、模糊优选 法、神经网络法、时序多目标决策方法、数据包络法( d e a ) 、整数规划法及遗传算 法等。 在协作关系管理方面，目前研究成果不多，且以定性分析居多。m a r i s a k o 和 千伟业：基于成本的集成协作计划与调度模型及其进化算法研究9 s u s a n h e l p e r 58 】认为促进网络企业间协作关系建立和持续的条件包括长期承诺、信息 交换、技术援助和声誉；l u o l 5 9 j 将联盟寿命、文化差距、市场不确定性、相关风险 以及互惠承诺5 个因素作为联盟协作关系建立的决定性要素；n i e l s e n t 6 0 】在对国际战 略联盟的实证研究中将合作经历、合作者的声誉、透明度、保障性措施等八个因素 视为影响协作关系产生的决定性因素。 在生产协作计划与任务分配的研究方面，目前研究成果不多。钱碧波【6 l j 等对虚 拟企业的生产协作计划与控制进行了研究，认为虚拟企业中协作计划与控制的结构 是一种分形的层次控制结构，从上到下可分为五层：a v e ( 敏捷虚拟企业) 层、e t ( 外 部项目组) 层、i t ( 内部项目组) 层、b o u ( 基本组织元) 层和e r ( 设备资源) 层。这种控 制结构既保留了一部分递阶控制的特点，同时又具有部分分形与自治的特点，强调 各级组织元之间的互相协作，具有较强的分布控制与自适应能力。苏志龙【6 2 j 提出了 一种基于协商的虚拟企业生产协作计划与控制四层模型，即项目粗规划、项目协商 规划、生产详细规划和生产作业控制。上述控制结构虽然可以较好地对协作计划过 程进行描述，但是并没有指出协作计划的具体实现方法。 面向敏捷制造的生产协作包括多种分布式生产实体，并且这些生产实体之间存 在着动态变化的和难以预测的相互作用。几乎每一个生产实体都需独立、自主地作 出局部决策。因为准确的全局的状态( 生产任务、工艺规划、车问状态、机床状态 等) 不可预先完全知道，在生产中作长期的计划或调度己成为绝对不可能的事情， 全面对制造过程预先分析的方法将失去实际意义。在不同结点，即不同生产实体上 的局部推理和决策变得尤为重要。基于此，建立一个集成协作计划与调度的模型， 在实现工艺路线决策的同时，给出在规定的生产周期里规划出生产成本最低的工件 调度组合变得尤为重要。 1 3 本文研究的背景与课题意义 目前，我国多数制造企业主要依靠经验丰富的生产管理人员手工安排生产调度 方案，在生产相对简单的情况下这是可行的，然而若生产调度的规模较大或生产环 境动态变化，单纯的手工调度就显得较为低效率，进而势必影响企业的发展壮大。 尤其随着j i t 思想的广泛采用，要求产品尽量按交货期完成，就是说，既不要过早 生产积压库存，也不要拖期生产影响企业的经济利益和信誉，若能妥善处理这一问 题，会为企业的发展提供良好的保障，因此解决车间作业调度问题就凸显特别重要。 生产计划与生产调度是企业生产过程中的两个基本问题，传统的研究方法是运 用自上而下的递阶结构分解方式，即先制定生产计划，再根据制定的生产计划安排 生产调度，因为在确定生产计划时所考虑的调度约束非常有限，而且调度情况也无 i o扬州大学硕士学位论文 法及时反馈到生产计划的制定中，从而难以保证制定的生产计划在生产调度中是可 行的。所以，生产计划与生产调度需要做到高度耦合、密不可分，计划为调度指引 目标，调度适应计划的安排，两者相互关联又相互约束，进而在企业决策时建立一 个有效的集成计划与调度系统是提高生产系统性能的关键因素。 对生产计划和调度的研究虽然已经有几十年的历史，但仍然未形成一整套系统 的方法和理论。由于制造企业不同的生产特点，对不同的生产周期、生产方式以及 管理方法所采用的计划和调度策略也存在很大不同。同时，理论研究和实际应用之 间也存在着很大的差距，一些在理论上能够获得最优解的方法往往忽略了很多实际 因素；理论上虽然能够响应系统的动态变化，但无法保证响应速度以及对调度结果 的优化。研究车间作业调度问题，寻求先进的车间作业调度算法具有较大的理论意 义和现实意义。其可以提供及时合适的车间作业调度方案以确保企业生产系统的高 效运行，运用先进合理的车间作业调度算法准确配置各种生产资源可以提高企业的 资源利用率、生产效率，进而增强制造企业在市场经济下的竞争力。 在生产协作中，由于其生产资源、生产时间、技术等多种因素的限制，有可能 生产部门接到的生产任务不可能全部完成，需要将生产任务的一部分委托外包给供 应链上的其他生产协作伙伴。然而，对协作计划的优化问题的研究有很大进展，但 多数协作模