（管理科学与工程专业论文）具有柔性资源约束的优化调度问题研究.pdf

摘要柔性资源客观地存在于企业经营运作的各个环节。产品开发和生产是制造型企业运营的两个关键环节，产品开发项目调度和车间调度问题是这两个关键环节中的核心问题。本文主要对具有柔性资源约束的产品开发项目调度和流水车间调度相关问题展开研究。具有柔性资源约束的调度问题比经典调度问题更为复杂，都是强n p - h a r d 问题。解决问题的核心是模型和算法，有效的调度算法，可以大大提高资源的利用率和生产效益。因此，研究具有柔性资源约束的调度问题不仅具有较大的理论意义，而且具有相当高的实用价值。本文的研究以国内外已有的关于项目调度和车间调度等问题的最新研究成果为基础，采取系统建模方法、优化理论、人工智能和m a r l 曲6 5 编程与仿真等手段进行研究，提出问题的数学表示方法、构建有效的求解算法，得出有利于企业生产发展的参考性建议。本文主要围绕下述几个方面展开研究工作并取得了以下成果：( 1 ) 分析柔性的基本概念，给出了柔性资源的定义，并提出采用资源一能力矩阵对资源柔性分布进行表示的方法和资源柔性程度的度量方法。( 2 ) 讨沧了经典资源约束项目调度问题和流水车间调度问题的基本理论和研究现状，通过对经典调度问题基本假设的分析，提出了突破这些假设的本文所要研究的3 个主要问题：具有柔性资源约束的产品开发项目调度问题，具有柔性资源约束的流水车问调度问题和具有学习效应的柔性资源约束流水车阃调度问题。( 3 ) 对具有柔性资源约束的产品开发项目调度问题进行深入研究：提出了具有柔性资源约束项目调度问题( f r c p s p ) 的数学表示方法；设计了问题求解的改进遗传算法，采用基于优先权的自然数编码方法，提出了采用拓扑排序和最大流理论相结合的解码方法，并设计了适用于该问题的遗传算于；通过计算机数据实验验证了算法求解问题的性能，说明了不i 司资源柔性程度和资源的技能分布对项目总工期的影晌，指出合理的柔性资源调度方案对提高产品开发系统效率的作用。( 4 ) 对最小化调度时日j 表长为目标函数的具有柔性资源约束的流水车间调度( f r c f s s ) i u j 题进行了研究：阐述了问题的假设条件，建立了整数规划模型；分析了问题的强n p - h a r d 特性；提出了有机结合启发式算法、遗传算法和禁忌搜索算法的问题求解的改进算法( m a ) ，该算法由3 个模块构成，分别用于求解作业排序、柔性资源分配和工序开始时间3 个子问题；大量的计算机数据实验说明该算法具有较好的鲁棒性和收敛性；通过比较经典流水车间调度问题和f r c f s s问题的求解结果，说明了对柔性资源合理调度，改进了流水车间的生产绩效。( 5 ) 对具有学习效应的柔性资源约束流水车间调度( f r c f s s l e ) 问题进行了探讨：对问题进行了描述，分析了问题的复杂性；提出了求解f r c f s s l e 问题的启发式算法，该算法由作业排序和资源配置与开工时间计算2 个模块组成：经过小规模数据实验和大规模数据实验说明了最优柔性资源配置的原则，证明了该启发式算法的有效性，并说明了考虑柔性资源的学习效应对流水车间进行优化调度可以更有效地利用柔性资源、提高车间的生产效率。关键词：柔性资源，产品开发，项目调度，流水车间调度，优化算法i la b s t r a c tf l e x i b l er e s o u r c ei sp o p u l a r l ye x i s t i n gi nt h ep r o c e s so fe n t e r p r i s eo p e r a t i o n p r o d u c t i o nd e v e l o p m e n ta n dm a n u f a c t u r i n ga r ep l a y i n gi m p o r t a n tp a r t si nt h i sp r o c e s s , a n dt h ep r o b l e m so fp r o d u c t i o nd e v e l o p m e n tp r o j e c ts c h e d u l i n ga n ds h o ps c h e d u l i n ga r et h ek e r n e lo f t b e m p r o b l e m sr e l a t e dw i t hf l e x i b l ei e s o u i v 七c o n s t r a i n e dp r o d u c t i o nd e v e l o p m e n tp r o j e c ts 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 ga r es t u d i e di nt h i sd i s s e r t a t i o n t h ef l e x i b l el e s o n r c ec o n s t r a i n e ds c h e d u l i n gp r o b l e mi sm o r ec o m p l e xt h a nt r a d i t i o n a lo n e s ，a n di sn p - h a r di ns t r o n gs e n s e t h em o s ti m p o r t a n tt h i n gt os o l v et h es c h e d u l i n gp r o b l e mi sm a t h e m a t i c a lm o d e l i n ga n da l g o r i t h me o n s t m _ c t i o n b e c a u s ee f f e c t i v es c h e d u l i n ga l g o r i t h mc 锄o b s e r v a b l yi m p r o v et h eu t i l i z a t i o no fr e s o u r c ga n dp r o d u c t i v i t y s t u d yo nf l e x i b l el 呛s o u l - c ec o n s t r a i n e ds c h e d u l i n gp r o b l e mi sb o l l li m p o r t a n tf o rt h e o r e t i c a la n de m p i r i c a lp e r s p e c t i v e s s t u d yi sc a r r i e do u to nt h eb a s i so fm o s tc u r r e n t l yl i t e r a t u r ea b o u tp r o j e c ts c h e d u l i n ga n ds h o ps c h e d u l i n g s y s t e m a t i cm o d e l i n gm e t h o d s ，o p t i m i z a t i o nt h e o r y , a r t i f i c i a li n t e l l i g e n c et h e o r ya n dc o m p u t a t i o n a ls i m u l m i o nb a s e do nm a t l a b 6 5a r ea p p l i e di nt h i sr e s e a r c h , m a t h e m a t i c a lf o r m u l a t i o na n de f f e c t i v ea l g o r i t h ma r ep r o p o s e df o rt h ep r o b l e m s ，v a l u a b l es u g g e s t i o n sf o re n t e r p r i s em a n u f a c t u r i n ga n dd e v e l o p m e n ta r er a i s e de v e n t u a l l y p r i m a r yc o n t e n t sa n dr e s u l t sa r ea sf o l l o w s ( 1 ) c o n c e p to ff l e x i b l er g s o n r c ei sp r o p o s e db a s e do nt h er e v i e wo fd e f i n i t i o na n dc l a s s i f i c a t i o n , r e s o u r c e - a b i l i t ym a t r i xi sd e v e l o pt od e s c r i b et h ef l e x i b i l i t yd i s t r i b u t i o no f r e s o u r c e 。m e t r i c sf o rr e s o u r c ef l e x i b i l i t ya d i s c u s s e d ( 2 ) b a s i ct h e o r ya n dl i t e r a t u r er e v i e wa b o u tt r a d i t i o n a lp r o j e c ts c h e d u l i n gp r o b l e ma n df l o ws h o pp r o b l e ma r ed i s c u s s e d p r o b l e m sa b o u tf l e x i b l el e s o u r r 曰ec o n s t r a i n e dp r o d u c t i o nd e v e l o p m e n tp r o j e c ts c h e d u l i n g , f l o ws 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 gw i t hl e a r n i n ge f f e c tt ob es t u d i e di nt h i sd i s s e r t a t i o ni sp r o p o s e db ya n a l y z i n gb a s i ca s s u m p t i o n so f t r a d i t i o n a ls c h e d u l i n gp r o b l e m ( 3 ) f l e x i b l er e s o u r c ec o n s t r a i n e dp r o d u c t i o np r o j e c ts c h e d u l i n gp r o b l e mi ss t u d i e d m a t h e m a t i c a lf o r m u l a t i o ni sp r e s e n t e df o rf l e x i b l er e s o n r c ec o n s t r a i n e dp r o j e c ts c h e d u l i n gp r o b l e m ( f r c p s p ) i m p r o v e dg e n e t i ca l g o r i t h mi sd e v e l o p e d ，i nw h i c hp r i o r i t y b a s e de n c o d i n gi su s e d ，m e t h o dc o m b i n i n gt o p o l o g i c a ls o r ta n d1 1 1m a x i m u mf l o wt h e o r yi sc a r r i e do u ti nd e c o d i n g ，a n ds p e c i f i cg e n e t i co p e r a t o r sa r ed e s i g n e d t h ea l g o r i t h mi sc o d e di nm a t l a b 6 5a n dc o m p u t a t i o n a lr e s u l t si m p r o v et h ee f f e c t i v e n e s so ft h ea l g o r i t h m ，d e m o n s t r a t ei m p a c to fd i f f e r e n tl e v e l so fr e s o u r c ef l e x i b i l i t ya n ds k i l ld i s t r i b u t i o no fr e s o u r c eo np r o j e c tm a k e s p a n ，a n ds u g g e s tt h a tr e a s o n a b l es c h e d u l i n gs t r a t e g yc a ni m p r o v ep e r f o r m a n c eo fp r o d u c t i o nd e v e l o p m e n ts y s t e m ( 4 ) f l e x i b l er e s o u r c ec o n s t r a i n e df l o ws h o ps c h e d u l i n g ( f r c f s s ) p r o b l e mm m l m 1 。7 a n gm a k e s p a ni se x p l o r e d p r o b l e ms e a i n go ff r c f s si sd e s c r i b e da n di n t e g r a t e dp r o g r a m m i n gm o d e lw a sc o n s t r u c t e d b e c a u s et h ef r c f s sp r o b l e mi sn p - h a r di nt h es t r o n gs e n s e ，t h em o d i f i e da l g o r i t h m ( m a ) r e a s o n a b l yc o m b i n e sh e u r i s t i ca l g o r i t h mw i t hg e n e t i ca l g o r i t h ma n dt a b us e a r c ha l g o r i t h ma n dc o n s i s t so f3m o d u l e s ，i e h y b r i dg e n e t i ca l g o r i t h mb a s e dj o bs e q u e n c i n gm o d u l e ，c r i t i c a lo p e r a t i o nb a s e df l e x i b l er e s o u r c ea l l o c a t i o nm o d u l ea n dp r i o r i t yr u l e sb a s e do p e r a t i o n ss t a r tt i m e sd e c i s i o nm o d u l e e x t e n s i v es i m u l a t i o ne x p e r i m e n t sd e m o n s t r a t et h ee f f e c t i v e n e s sa n dr o b u s t n e s so ft h em af o rf r c f s sp r o b l e m c o m p a r i s o nb e t w e e nt r a d i t i o n a lf l o ws h o ps c h e d u l i n ga n df r c f s si m p l i e st h a tp e r f o r m a n c ei m p r o v e m e n t sa s s o c i a t e dw i t l lf l e x i b l er e s o u r c es c h e d u l i n ga f es u b s t a n t i a l ( 5 ) f l e x i b l er e s o u r c ec o n s t r a i n e df l o ws h o ps c h e d u l i n g 晰t l ll e a r n i n ge f f e c t( f r c f s s l e ) p r o b l e mi ss t u d i e d f o r m u l a t i o na n dc o m p l e x i t yo fp r o b l e ma r ea n a l y z e d h e u r i s t i ca l g o r i t h mf o rf r c f s s l ei sc o n s t r u c t e d w h i c hc o n s i s t so f2m o d u l e st h a tr e s p e c t i v e l ys o l v ej o bs e q u e n c i n g ，r e s o u r c ea s s i g n m e n ta n ds t a r tt i m ed e t e r m i n a t i o ns u b p r o b l e m s c o m p u t a t i o n a la n a l y s i si m p r o v e sp r o p e r t i e sf o ro p t i m a lr e s o u r c ea s s i g n m e n tp o l i c y , i m p r o v e se f f e c t i v e n e s so ft h ep r o p o s e da l g o r i t h m ，a n dd e m o n s t r a t e st h ep e r f o r m a n c ei m p r o v e m e n t so b t a i n e db yc o n s i d e r i n gr e s o u r c ef l e x i b i l i t ya n dl e a r n i n ge f f e c ti nf l o ws h o ps c h e d u l i n g k e yw o r d s ：f l e x i b l er e s o u r c e ；p r o d u c t i o nd e v e l o p m e n t ；p r o j e c ts c h e d u l i n g ；f l o ws h 叩s c h e d u l i n g ；o p t i m i z a t i o na l g o r i t h mi v此页若属实，请申请人及导师签名。独创性声明本人声明，所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。研究生( 签名) ：越日关于论文使用授权的说明期：竺垡二本人完全了解武汉理工大学有关保留、使用学位论文的规定，即：学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部内容，可以采用影印、缩印或其他复制手段保存论文。( 保密的论文在解密后应遵守此规定)研究生( 签名) ：童堡遂导师( 签名)武汉理工大学博士学位论文第1 章绪论1 1 研究的目的、意义本研究来源于导师罗荣桂教授负责的两项国家自然科学基金项目“面向复杂产品协同开发过程的柔性资源智能调度研究”( 课题编号：6 0 5 7 4 0 7 0 ) 和“企业柔性资源的最优分配与使用研究”( 课题编号：7 0 2 7 1 0 3 3 ) 。随着现代制造技术、信息技术和自动化技术的迅速发展，全球性的竞争给制造业企业提出了新的挑战：产品生命周期日益缩短，顾客需求日益多样化和对时间的敏感性日益增强，变化和不确定性是新的竞争环境的标志。企业要想在激烈的竞争中立于不败之地，必须以最快的速度、最好的质量、最低的成本和最优的服务来响应市场。产品是一切制造业企业生产经营活动的主体，产品开发是这一活动主体的源头。国内外企业的分析表明，产品生命周期成本中大部分是在产品开发期间决定的。产品快速开发能力在很大程度上决定了企业的竞争能力，而这种竞争力一方面表现为企业的定义和设计能力，另一方面也表现为企业在产品设计过程的管理能力。因此研究资源在产品开发项目中的最优调度对企业缩短开发时间、节约开发成本、提高开发效率具有极其重要的作用。生产调度是决定企业生产能力的关键因素之一。随着市场经济的建立与发展，企业间的竞争越来越激烈。目前，企业中车间一级的生产调度控制依然处于传统管理方式，这种管理方式不能综合考虑整个生产过程，导致等待时间长、在制品占用量大、信息反馈慢、资源浪费、生产不均衡。因此，在车间作业控制中及时准确地进行调度，对于生产系统的高效运行有着重要影响。研究生产车间调度问题，合理地安排工件和工序的加工顺序、高效地分配企业资源，对提高生产率，促进企业生产管理的现代化，提高企业的竞争力具有重要的意义。产品开发项目调度和生产调度两类调度问题是关系企业生产运营取得成功的重要问题。在实际调度过程中都涉及到有效分配有限的资源、合理安排活动或作业的顺序和活动的开始加工时问。这些调度问题中的一些资源，如人员、机器等，是具有柔性的( 具有应对变化的多有加工不同工件的能力等) ，而现有的对具有柔性资源的调度问题的研究却十分有限。本研究以具有柔性资源约束的产品开发项目和流水车间为研究对象；以现武汉理工大学博士学位论文有国内外在该领域中的研究成果为基础；试图从系统的角度对具有柔性资源约束的产品开发项目和流水车间的优化调度问题进行探讨；并借助优化方法、人工智能、计算机仿真等设计和分析问题的求解方法，探索求解问题的性能优良的算法，分析柔性资源对系统绩效的影响，提出配置柔性资源有效策略；力争为产品开发项目管理和车间调度的最优决策和实施提供理论依据，为优化调度软件的开发提供研究基础。1 2 相关问题的国内外研究评述调度( s c h e d u l i n g ) 在编制作业计划、企业管理、交通运输、航空航天、医疗卫生、现代化制造系统等众多领域都有广泛的应用。一般地说，凡是有多个不同的任务要完成，就有作业排序与作业计划问题。调度一般性的定义是在一段时问内，为了完成一组工作，而相应地分配一套资源，使预定目标达到最优。调度问题是运筹学的一个较年轻的分支，同时也是在实际中应用最广的运筹学分支之一。研究它对于在现有资源条件下提高工作效率和经济效益有重要作用，因而成为了国内外众多学者的研究焦点之一。目前对调度问题的研究在资源约束项目调度、车问调度、运输调度等方面取得了丰富的研究成果。本节主要对与本研究相关的两类调度问题，即产品开发项目调度问题和车间调度问题进行概要性的回顾，从而引出本文所要研究的问题。1 2 1 产品开发项目调度问题的研究现状产品的开发与设计是一个非常复杂、广泛的过程和系统，涉及市场开发、消费者调查、产品概念的生成与评价、工业设计、工程设计与制造、产品营销等许多不同领域，有各种专业不同的专家参与。为了保证产品设计与开发的成功，需要建立一套科学、完整的设计与开发流程，并在不同专业的设计与开发人员之间建立起有效的交流，形成一种互相理解、互相沟通、协调一致的团队。随着产品更新换代速度加快，如何适应市场需求，提高研发生产率、降低成本和缩短开发周期，成为企业在信息时代面临的新问题。基于“资源+ 时间”的产品开发将形成一个新的研发管理范式l l 】。即使是最简单的产品，其开发过程涉及到许多不同专业的人员完成各种各样的任务。成功的产品开发项目应该是通过高效地利用时间、金钱和其他资源以开发出高质量、低成本的产品。产品开发项目管理是关于计划和协调资源和任务达到这些目标的一系列活动，这些活动出现在项目调度( 项目计划) 和项目执行( 项目控制) 过程中。产品开发项目调度武汉理工大学博士学位论文主要考虑如何对任务进行排序并确定相应的资源需求量，贯穿整个产品开发过程，是一个动态的过程，对产品开发成败起着至关重要的作用。作为调度问题中一类与实践具有紧密联系的调度问题，产品开发项目调度的研究成为继车间调度后被人们广泛关注的问题。国内外一些学者对产品开发项目调度展开研究。对产品开发项目调度的研究主要借鉴项目管理中的网络计划方法，包括甘特图、关键路线法 r i t i c a lp a t hm e t h o d ，c p m ) 、计划评审技术( p g r a me v a l u a t i o na n dr e v i e wt e c h n i q u e ，p e r t ) 等 2 , a i 。应用p e r t 图网络法，能指示出项目中一些活动必须结束以后，另一些活动才能开始；还能指示出一些能并行执行的活动；减少关键路径的策略能减少过程的持续时间。但这些方法只能应用在串行活动并且无法解决过程中的迭代。s t e w a r d 在1 9 5 1 年引入d s m ( d c s i g ns t r u c t u r em a t r i x ) 作为基于矩阵的信息流分析框架。目前，d s m 已发展为三种类型：( 1 ) 基于参数的模型；( 2 ) 基于任务的模型；( 3 ) 基于团队的模型。徐晓刚在已有研究的基础上，提出了d s m 模型的建立及模型的合成方法，从整体上认识产品的设计结构，详细讨论了基于d s m 的层次划分、环路识别等相关计算，提出了新的基于反向层次的d s m 排序方法1 4 1 。但是传统的产品开发项目调度都假设所需的资源种类和数量都是无限可供的，因此资源能力不会影响调度决策。然而事实上产品开发项目涉及资源种类繁多、每种资源数量都是有限的，许多研究者对单资源约束和多资源约束项目调度问题的精确算法和启发式算法进行研究，并取得理想的成果。对于每个任务能以至少一种模式进行加工的项目调度问题，为了更有效地进行调度，j i r a c h a i ( 2 0 0 3 ) 以o m 公司的汽车车身开发为例对多模式资源约束项目调度进行研究，提出求解问题的启发式算法，通过实例证明算法的有效性1 5 】。刘士新等提出了求解多模式资源水平项目调度问题的遗传算法嘲。下面将回顾资源约束项目调度问题( r c p s p ：r c s o t l r o 。c o n s t r a i n e dp 巧e c ts c h e d u l i n gp r o b l e m ) 的相关求解算法，为后文采用项目调度求解方法解决具有柔性资源约束的产品开发项目调度问题提供参考。多数r c p s p 属于n p h a r d 优化问题，该问题成为运筹学中研究的热点问题之一。3 0 多年来，求解的算法不断推陈出新，概括起来可以分为精确算法、启发式算法和智能优化算法三类。( 1 ) 精确算法( e x a c ts o l u t i o nt e c h n i q u e )精确算法以分枝定界法为主【7 】。分枝定界( b r a n c ha n db o u n d ) 法是求解n p h a r d 问题的一种有效的精确算法，分技定界法由分枝和定界两个部分构成。武汉理工大学博士学位论文其基本思想是：先利用搜索树将问题的解空间按照一定的规则分割成子空间，即分枝过程；然后通过合理的定界方法去除不必再进行搜索的子空间，即定界过程；不断重复这两个步骤缩小有效搜索空间，直到找到最优解。为了提高分枝定界法的求解效率，许多学者进行了不断的改进：c h r i s t o f i d e s ，a l v a r e z - v a l d e s 和t a m a r i t 提出了求解s m r c p s p 的基于分离弧的分枝定界算法蝉j 和4 种定界方法，通过实验证明该算法的有效性。p a t t e r s o n 等针对s m r c p s p提出了基于紧前关系树的分枝定界法【9 】：并在此基础上提出求解m m r c p s p 的基于回溯算法的两阶段分枝定界法1 1 0 】。d e m e u l e m e e s t e r 和h e r r o e l e n “l 为解决s m r c p s p 时的资源冲突问题提出了最小延迟替代集的概念，对最小延迟替代集中的活动进行延迟，形成不同的分枝，解决资源冲突；以定理的形式给出了4种定界方法和相关的理论依据，对p a t t e r s o n 提出的1 1 0 个实例进行求解，验证了算法的有效性。m i n g o z z i 等建立了问题的o 一1 整数规划模型【1 2 i ，模型中的变量表示一个可行活动集，该可行活动集中的活动既满足时序约束也满足资源约束，可以同时执行；并提出了5 种下界的计算方法，通过实例验证了算法的有效性。n a z a r e t h 等提出了基于最大资源满足集的宽度优先的分枝定界算法【1 3 】，采用3 种定界方法控制搜索树节点的数量，并验证了算法的性能。s p r e c h e r 等对d e m e u l e m e e s t e r ，p a t t e r s o n 等提出的求解s m r c p s p 的分枝定界法进行改进( 1 ，提出了8 种定界方法，通过与文献中算法的比较，证明所提出的算法是效果最好的算法；并进行了扩展用于求解m m r c p s p i i s 3 6 ，通过对p s p l i b 中的基准实例的计算验证了算法的优越性。h a r t m a n n 和d r e x l l 为解决m m r c p s p 问题在分枝过程中提出了扩展选择集合的概念，应用l o 种定界方法进行剪枝，采用深度优先搜索直到得到完整调度方案。对k l e i n 等【1 8 l ，b m c k c r 和k n u s t 1 9 1 对下界的计算方法进行了研究，提出了有效的下界计算方法。分枝定界算法可以求得问题的最优解，但由于占用的计算机内存空间大，求解时间长，因此可求解的问题规模小，不利于大规模问题的求解。( 2 ) 启发式算法( h e u r i s t i ca p p r o a c h e s )采用启发式算法求解r c p s p 问题有时不能保证求得问题的最优解，但可以在较短的时间内求得大规模问题的近似最优解。基于优先规则的启发式算法( p r i o r i t yr u l eb a s e ds c h e d u l i n gh e u r i s t i c ) 是求解r c p s p 的主要启发式方法。基于优先规则的启发式算法是由调度生成方案( s g s ：s c h e d u l eg e n e r a t i o ns c h e m e ) 和优先规卿j ( p r i o r i t yr u l e ) 构成。调度生成方案s g s 由k e l l e y l 2 0 1 提出，分为串行调度方案( s s s ：s e r i a ls c h e d u l i n gs c h e m e ) 和并行调度方案( p s s ：p a r a l l e ls c h e d u l i n gs c h e m e ) 。4武汉理工大学博士学位论文s g s 通过对部分调度进行扩展，直至得到完整的可行调度方案。k o l i s c h 2 1 l 证明了基于任何优先规则并采用串行调度方案生成的s r c p s p 调度方案均为积极调度( a c t i v es c h e d u l e ) ：基于任何优先规则并采用并行调度方案生成的s r c p s p 调度方案均为非延迟调度( n o n - d e l a ys c h e d u l e ) 。采用优先规则可以计算可行活动集中选择活动的优先权系数，表l l 列出了文献中出现的一些优先规则毗札1 。表1 一l 求解r c p s p 的优先规则求解m m r c p s p 的基于优先规则的启发式算法把每个决策时刻的可行活动集合和执行模式按照一定的优先规则进行排序，然后利用s g s 对一个部分调度进行扩展，直到生成一个完整的调度。b o c t o r l 2 a ，o z d a m a r 和u l u s o y 等1 2 8 瑚】对基于优先规则的启发式算法进行了改进提出了解决资源冲突的活动一模式组合的处理方法对m m r c p s p 进行寻优，取得了良好的效果。( 3 ) 智能优化算法许多智能优化算法具有描述简单、鲁棒性强的特点，如遗传算法( g a ：g e n e t i ca l g o r i t h m ) 、禁忌搜索( t s ：t a b us e a r c h ) ，模拟退火( s a ：s i m u l a t e da n n e a l i n g ) 算法和蚁群( a n ts y s t e m ) 算法等已经被广泛应用于求解组合优化问题。许多学者采用智能优化方法对r c p s p 进行求解，并取得了较好的研究成果，如表l 一2 所示。为了测试求解r c p s p 的各种优化算法的寻优性能，需要大量的问题实例。早期对r c p s p 的研究中采用的问题实例除了由作者自己生成外，多数来自p a t t e r s o n 编辑的1 1 0 个典型问题【5 3 1 。随着研究的深入和丰富化，要求有更具代表性的问题实例作为检验算法性能的标准。为此，学者们设计了r c p s p 问题的生成器，其中k o l i s c h 和s p r e c h e r 5 4 】根据标准项目生成器( p r o g e n ：t h es t a n d a r d武汉理工大学博士学位论文p r o j e c tg e n e r a t o r ) 系统地产生单执行模式和多执行模式资源约束项目调度典型问题( b e n c h m a r k s ) 形成问题库p s p l i b ，并提供到目前为止已知的最优解或近似最优解，以及一些问题的最优解的上界下界。此后k o l i s c h 和h a r t m a n n p “，h a r t m a r mk o l i s c h 【5 6 j ，k o l i s c h 和h a r t m a n n l 5 7 】等进一步对p s p l i b 进行补充。研究人员可以通过网址：h t t p ：w w w b w l u n i - k i e l d e p r o d p s p l i b 下载所有的问题实例作为基准以评价他们提出的优化算法的求解效果和执行效率，同时可以把自己得到的最新解根据问题库的格式进行编辑并发送到p s p l i b 中以不断补充和更新问题库的信息，推进r c p s p 问题的研究。表1 2 求解r c p s p 的智能优化算法智能优化算法文献遗传算法h a r t m a n n l 3 0 - 3 2 ，刘十新等 3 3 , 3 4 ，o z d a m a r l 3 ”，m o r i 和t s e n g ，a l c a r a z 和m a r o t o p 7 ，3 引，g o n c a l v e s 和m e n d e s 【3 们，t o k l u ”i ，v a i l s 等【4 1 i禁忌搜索b a a 一4 2 i ，n o n o b e 和i b a r a k i 【4 引，p i n s o n 等f 州，t h o m a s 和s a l h i 4 5 】模拟退火算法b o u l e i m e n 和l e c o c q l 4 “，b o c t o r i ”1 ，c h o 和k i m y 8 i其它智能优化算法h s c i n h d i h n e i , 等5 1 2 4 9 1 1 ，黼咖和s t o l y 拱m e r k l e 等5产品开发过程中许多资源是具有柔性的，其中最典型的是产品开发人员，每个人员可能具有用以完成不同设计任务的多种不同的技术。现有研究仍缺乏从系统的角度对产品开发过程中的柔性资源优化调度问题进行研究。1 2 2 车间调度问题的研究概述车间生产调度是制造系统的基础，生产调度的优化是先进制造技术和现代管理技术的核心技术。制造过程的调度技术，将在很大程度上影响制造的成本和效率。有效的调度方法与优化技术的研究，对于提高生产效率和资源利用率，进而实现先进制造企业的现代化具有重要参考作用。1 9 5 4 年s m j o h n s o n 6 1 提出了两台机器多个作业流水车间调度的多项式算法，揭开了研究调度问题的序幕。从此调度问题成为运筹学、系统工程及自动化管理领域里的一个十分活跃的研究课题，人们一直致力于调度问题的理论与实践的研究。6武汉理工大学博士学位论文1 2 2 1 车间调度问题的求解算法根据研究对象的复杂性，把生产调度问题分为：单机调度问题，并行机调度问题，流水车间调度问题，作业车间调度问题和柔性流水车间作业调度问题。g a r e y 和j o h n s o n 5 8 】证明除了少数小规模问题存在多项式算法外，大量调度问题属n p - h a r d 问题。鉴于精确求解方法仅适合于小规模问题，人们提出了构造性算法、领域搜索算法和人工智能方法等求解大规模问题：( 1 ) 枚举方法( e n u m e r a t i v em e t h o d s ) ，包括：分枝定界法( b r a n c h & b o u n d ) 和数学方法( m a t h e m a t i c a lm e t h o d ) ，如整数规划、分解方法、拉格朗日松弛方法等 5 9 , 6 0 。该类方法对小规模问题求解比较有效，但对大规模问题求解的难度大。( 2 ) 启发式方法( h e u r i s t cm e t h o d ) ，包括：优先分配规则( p r i o r i t yd i s p a t c hr u l e ) 6 1 1 ，如s p 蚓等；插入方法( i n s e r t i o na l g o r i t h m ) 6 3 ，如n e h 等州。该类方法能快速建立问题的解，但解的质量不高，如果要求得较高质量的解需要建立复杂的启发式规则。( 3 ) 人工智能方法( a r t i f i c i a li n t e l l i g e n c e ) ，利用人工智能的原理和技术进行搜索。包括：模拟退火算法( s i m u l a t e da n n e a l i n g ，s a ) 1 6 5 】、禁忌搜索算法( t a b u 蚓玎c 札t s ) 【删、神经网络( n e u r a ln e t w o r k ，n n ) 【6 7 1 、进化计算( e v o l u t i o n a r yc o m p u t a t i o n ,e c ) 【强7 0 】、蚁群算法( a n ts y s t e m ) 7 ”和免疫算法( i m m u m 锣a l g o r i t h m ) 1 7 2 1 。随着调度研究的深入，调度算法必然进一步与实践相结合，向着集成化、动态化、高效化、智能化、实用化的方向发展。近年来，针对实际生产调度问题，学者们提出了一些更好地拟合实际问题的流水车间调度问题，其中包括具有柔性资源约束的流水车间调度和具有学习效应的流水车阃调度问题，对这两个问题的研究成果为本文的研究提供了重要启示。1 2 2 2 具有柔性资源约束的车间调度问题研究现状传统车间调度模型将作业加工时间作为问题的固定且已知的参数，通过确定作业在每台机器上的加工顺序来优化时间表长( m a k e s p a n ) 或总完工时间( f l o w t i m e ) 等系统绩效。在这一系统中，假设作业加工所需的资源是不可再生、不具备柔性的资源，一旦被某个工序使用后，在任何时刻都不能分配给其它工序；并假设作业加工所需的资源无论何时都能以所需的数量得到满足。实践中，作业加工时间往往是分配到工序上资源的函数，随着资源分配的情况而改变；而且许多资源是具备柔性的，这种柔性资源的调度是动态的，随着加工时间的推移动态地进行分配，极大地影响了流水车间的生产效率。近年7武汉理工大学博士学位论文来，国内外一些学者对具有柔性资源的平行机系统、流水车间进行了研究：d a n i e l s ，h o o p e s 和m a z z o l a ( 1 9 9 6 ) 1 7 3 对具有柔性资源的平行机静态调度和动态调度问题进行研究，提出了问题求解的最优算法和启发式算法，通过实验证明通过有效地利用资源的柔性能够大大提高平行机系统的运作效率。o l a f s s o n和s h i ( 2 0 0 0 ) 17 4 】对d a n i e l s ，h o o p e s 和m a z z o l a 提出的具有柔性资源的平行机调度问题进行重构，并采用具有全局枚举和局部启发式搜索性能的巢分区法( n e s t e dp a r t i t i o n ，n p ) 对该问题进行求解，仿真实验证明该算法对此问题求解的可行性和高效性。l u o 和h u a n g ( 2 0 0 5 ) 1 7 5 l 将具有柔性资源的平行机调度问题推广到具有部分柔性资源的平行机调度的研究，指出通过对工人进行一定的多功能训练，使其具备一定程度的柔性后并对其进行合理安排便能够实现全柔性资源对改进生产绩效的功能。d a n i e l s 和m a z z o l a ( 1 9 9 4