（机械电子工程专业论文）多项目模具设计任务分配与调度方法研究.pdf

摘要 摘要 论文以模具企业为背景，研究多项目环境下模具设计过程中的任务分配和调度问题。 问题关键是模具设计过程中，在资源受限的情况下如何调度项目中的设计活动及如何合 理、有效配置模具设计人员从而缩短模具的设计周期、提高设计效率、降低模具生产成本， 提高企业的效益、竞争力和快速响应市场需求变化的能力。 论文分析模具设计过程及特点，对模具设计过程进行任务分解，同时描述了设计过程 中存在的各种约束，并对资源约束下多项目模具设计任务分配问题进行数学建模。目前， 对于资源约束项目调度问题的研究，大都把项目中的同一类资源作为无差别的资源来看 待，而对于人力资源这一特殊资源，每个人的知识水平和专业技能都不相同，因此每个设 计人员应该被看作不同的、有差别的资源。论文对设计人员所需模具设计技能进行分类和 描述，研究在模具设计过程中，在满足任务紧前关系约束、设计人员能力约束等约束条件 下如何进行项目规划，生成最小项目工期的计划。论文提出了一种基于遗传算法的项目规 划算法来解决此问题，并通过实例验证了该算法的有效性。 接着，论文考虑到在执行项目计划时可能遇到突发事件会使得项目无法按原计划进行 下去，根据突发事件的类型，分情况讨论了重调度的策略，重点说明了计划执行过程中因 某个任务拖期造成的局部重调度，局部重调度的目标是调整后分配受影响的任务数最少。 最后，对模具设计管理原型系统进行了总体设计和初步实现，介绍了系统的设计和各 功能模块的作用。 关键词：多项目；项目规划；资源约束；重调度；遗传算法 木本课题得到国家8 6 3 计划项目的资助( 2 0 0 6 a a 0 4 2 1 3 2 ) 和粤港招标项目( 2 0 0 5 a 1 0 2 0 7 0 0 2 ) 广东t 业大学硕i j 学位论文 a b s t r a c t c o n s i d e r i n gm o u l dd e s i g na sr e s e a r c hb a c k g r o u n d ，t h et h e s i ss t u d i e st h et a s k a s s i g n m e n t a n ds c h e d u l i n g p r o b l e m i nm o u l dd e s i g n p r o c e s s i n m u l t i p r o j e c t e n v i r o n m e n t t h ec r u xo ft h ep r o b l e mi sh o wt os c h e d u l et h ep r o j e c td e s i g na c t i v i t i e sa n d h o wt oo b t a i nar e a s o n a b l ea n de f f e c t i v ed i s t r i b u t i o no fm o u l dd e s i g ns t a f fi nt h e r e s o u r c e c o n s t r a i n e dc i r c u m s t a n c e s t h eo b j e c t i v ei st os h o r t e nt h em o u l do ft h ed e s i g n c y c l e ，t oi m p r o v ed e s i g ne f f i c i e n c y , t or e d u c ep r o d u c t i o nc o s t s ，a n d t oi m p r o v et h e c o m p e t v e n e s sa n dc a p a b i l i t i e st or e s p o n dq u i c k l y t h et h e s i sa n a l y s i sm o u l dd e s i g np r o c e s sa n di t sc h a r a c t e r i s t i c s ，a n dm o u l dd e s i g n p r o c e s st a s kd e c o m p o s i t i o na n dd e s c r i b e sv a r i o u se x i s t i n g c o n s t r a i n t sd u r i n gt h e p r o c e s so fd e s i g n i n g ：p r e c e d e n c ec o n s t r a i n t sa n dr e s o u r c ec o n s t r a i n t s e t c t h e n 。t h e t h e s i sg i v et h ep r o b l e md e f i n i t i o n 、m o d e la s s u m p t i o na n db u i l du pam a t h e m a t i c a l m o d e l i n g c u r r e n t l y , t h er e s o u 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 mh a sb e e ns t u d i e db y m a n y a c a d e m i c i a n s i nm o s to fp a p e r s ，at y p eo fr e s o u r c ew a sr e g a r d e da s n o n d i s c r i m i n a t i o n b u tf o rh u m a nr e s o u r c e ，i ti sak i n do fs p e c i a lr e s o u r c e ，b e c a u s e e a c hp e r s o n sl e v e lo fk n o w l e d g ea n dp r o f e s s i o n a ls k i l l sa r en o tt h es a m e ，s oe a c h d e s i g n e rs h o u l db es e e na sad i f f e r e n tr e s o u r c e t h et h e s i sc l a s s i f i e sa n dd e s c r i b e st h e r e q u i r e dd e s i g ns k i l l si nt h em o u l dd e s i g np r o c e s s ，a n dp r o p o s e st h em e t h o d t oc a r r y o u tt h ep r o j e c ts c h e d u l i n gw i t ht h es h o r t e s tt i m ep l a nu n d e rt h ec o n d i t i o n so fs a t i s f y i n g t h ep r e c e d e n c ec o n s t r a i n t s 、r e s o u r c ec o n s t r a i n t sa n dr e q u i r e ds k i l lc o n s t r a i n t s t h e g a b a s e dp r o j e c tp l a n n i n ga l g o r i t h mi su s e dt os o l v et h i sp r o b l e m ，a n da ne x a m p l ei s g i v e nt od e m o n s t r a t et h ev a l i d i t yo ft h ea l g o r i t h m t h e n ，c o n s i d e r i n gu n e x p e c t e d e v e n t s m i g h t b ee n c o u n t e r e d d u r i n g t h e i m p l e m e n t a t i o no fp r o j e c t s ，t h ep r o j e c ts c h e d u l e su s u a l l yc a n n o tb ee x e c u t e da s o r i g i n a l l yp l a n n e d s o ，t h er e - s c h e d u l i n gs t r a t e g yi sd i s c u s s e da c c o r d i n gt ot h e d i f f e r e n t e v e n t s ，e s p e c i a l l yf o rt a s k so ft a r d i n e s s ，t h el o c a lr e - s c h e d u l i n gs t r a t e g yi s d i s c u s s e dt o b es u b j e c t e dt ot h em i n i m u mn u m b e ro f t a s ka d j u s t m e n t s a b s t r a c t f i n a l l y , ap r o t o t y p es y s t e m o fm o u l dd e s i g nm a n a g e m e n tw a sd e s i g n e da n d d e v e l o p e d ，a n df o u rf u n c t i o nm o d u l e s o ft h es y s t e ma r ei m p l e m e n t e d g a k e y w o r d s ：m u l t i p l ep r o j e c t ；p r o j e c ts c h e d u l i n g ；r e s o u r c ec o n s t r a i n t s ；r e s c h e d u l i n g ； + t h ep r o j e c tw a ss u p p o r t e db yt h en a t i o n a lh i g h - t e c hp l a n n i n g ( n o 2 0 0 6 a a 0 4 2 13 2 ) a n ds c i e n c e a n dt e c h n o l o g yp l a n n i n go fg u a n g d o n gp r o v i n c e ( n o 2 0 0 5 a 10 2 0 7 0 0 2 ) 独创件声明 独创性声明 秉承学校严谨的学风与优良的科学道德，本人声明所呈交的论文是我个人在 导师的指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以 标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，不包 含本人或其他用途使用过的成果。与我一同工作的同志对本研究所做的任何贡献 均己在论文中作了明确的说明，并表示了谢意。 本学位论文成果是本人在广东工业大学读书期间在导师的指导下取得的，论 文成果归广东工业大学所有。 申请学位论文与资料若有不实之处，本人承担一切相关责任，特此声明。 论文作者签字：啪 舯挪酶呼铲 2 0 0 8年5月2 0日 第一章绪论 第一章绪论 1 1选题背景 1 1 1 模具行业的现状和存在的问题 近年来，中国经济的高速增长带动了模具市场的持续高速发展。随着中国加 入w t o ，在机遇与挑战并存中，中国模具工业面临的是机遇大于挑战，一方面是 模具的进出i s 高速发展；另一方面是外资大量涌入中国的模具行业。外资不仅带 来资金也带来了技术和市场。外资企业在市场中处于优势地位，但是给国内民族 工业带来了很大的竞争压力。模具材料不断涨价，工资不断上升，模具价格总体 上却是不涨反降，模具生产企业利润空间被压缩。产品质量、成本和交付周期对 企业提出了严峻的挑战。国内的企业不得不在新的市场竞争环境下，为了生存与 发展，更加注重缩短产品生命周期和满足客户多样化和个性化需求：采用多品种、 小批量的生产方式，即面向客户订单的定制生产。依靠降低产品的成本和缩短模 具交付周期来赢得市场的一席之地。总的来说，现今我国的模具制造企业存在着 以下问题： ( 1 ) 设计制造周期长，不利于市场竞争。模具是典型的开发型行业，模具设 计周期相对较长，每开发一套模具都是一个新的设计探索过程。不同于大规模生 产的一次设计，可以应付大批量的生产，每一套模具的成型产品、技术要求均不 同，使得设计结构和制造工艺不同，而且没有试制过程，通常只是单件生产。 ( 2 ) 缺乏先进的生产计划管理和控制手段。尽管模具生产属于单件模式，但 由于生产周期长，企业同时有多套模具在进行设计和生产，并且还存在由于订单 的不可知性带来经常的紧急插单，因此对于企业管理人员来说，单凭经验靠手工 来进行设计和生产的规划和调度，难以使模具的交货期和质量得到保障。 ( 3 ) 模具专业人才的稀缺。人力资源是最重要也是最稀缺的资源，企业由于 成本的考虑和资源的限制，不可能配置完全满足所有项目的人力资源。同时模具 设计水平及设计能力的形成不仅仅是一个理论学习的过程，不可能简单依靠书本 广东t 业大学硕1 j 学位论文 理论快速完成设计，更重要的是一个经验积累的过程，同样模具设计人员的培养 也是非一朝二夕能做到的。 ( 4 ) 模具企业存在人力资源配置不合理的现象。在许多模具企业和项目中都 存在这种现象，尤其人力资源配置的“大材小用”或“小材大用”问题。 1 1 2 模具设计过程和特点 一个比较详细的模具设计流程( 以某模具企业设计过程为例) ，如下图1 1 所 示： 模具的设计和制造是一个非常复杂的过程，其特点是单件小批量生产，而且 模具往往不是最终产品，其交货期的要求较为苛刻。模具的设计在整个产品生命 周期中占相当的比重，其中设计效率和质量是影响模具企业竞争能力的重要因素， 所以缩短模具设计制造周期将是提高企业竞争力的重要途径之一。总的说来，模 具设计过程有以下特点： ( 1 ) 不确定性：模具设计制造过程是一个离散化、多环节、多反复的复杂过 程，设计过程中存在的迭代与反复现象造成了设计任务总量和设计过程的不确定 性。再加上设计过程本身是一种复杂的创造性劳动，因此，具有很大的不确定性。 比如当评审未通过时，对于此阶段的工作可能要修正或者重做，这也就造成了设 计过程的不确定性。 ( 2 ) 动态性：许多影响因素表现出动态性，由于模具设计过程的不确定性， 设计任务的数量不断变化，当新的设计项目有可能在某时引入，造成任务数量的 变化，人员的动态参与和离去又造成资源数量和水平的变化。 ( 3 ) 任务分配的经验性和随机性：很多企业模具设计过程中没有充分发挥设 计者的专长，任务的分配都是设计部门主管来凭借个人经验和情绪来分配任务， 因此带有很大的随机性。 ( 4 ) 多阶段性：在设计工作流程中会有一系列的评审如：开模评审、结构评 审，修模评审等，模具设计某阶段完成后就要进行一次评审；评审通过方可继续 后续的工作。 ( 5 ) 多约束性：设计任务之间存在紧前约束关系和任务对资源存在资源约束 关系。 ( 6 ) 影响因素的多样性2 】：许多因素对设计任务的分配产生影响，如：任务 的优先度、任务的难度、任务的数量和成员的能力、工作负荷等等。 图1 1 某模具企业模具设计流程 f i g u r e 1 1m o u l dd e s i g nf l o w 广东t 业大学硕i j 学位论文 1 1 3 多项目管理 多项目管理就是一种有效利用企业资源，确保企业各项项目目标均能实现的 科学管理方法。多项目管理简单说来就是一个项目经理同时管理多个项目，并在 组织中协调所有项目的选择、评估、计划、控制等各项工作。 随着越来越多的企业面临多项目管理的挑战，多项目管理己成为项目管理研 究和实践的焦点和热点。企业在多项目同时实施的情况下，往往涉及到不同项目 在资金、时间、人力资源的竞争、共享和冲突，因此在资源受限的情况下如何进 行多项目管理和多项目人力资源配置从而缩短各项目的工期是一个重要的问题。 而面对模具企业来说，人力资源是所有资源中最宝贵、最关键的资源。因此，在 多项目环境下模具企业合理、有效地配置设计人员，缩短模具设计周期，降低模 具生产成本，才能给企业带来效益和增强企业的竞争力。 模具设计项目的工期、项目进度的安排、项目的资源分配是影响工期的关键 因素。有效的项目资源分配将可以使得模具产品设计项目工期最小，从而缩短模 具设计的周期从而尽早投入生产制造，使其能够更早的投入市场，占领市场，取 得利润最大化。其次，项目进度安排和资源分配是相互联系，不可分割的。资源 分配是项目进度安排的非常重要的一部分，项目进度安排常常需要考虑时间节奏 和资源的使用等问题。项目进度安排在一定程度上可以说也是一个项目资源分配 的问题，即将项目的资源分配到各个项目的每一项活动中，得出哪一个活动需要 的资源，在哪个时间内完成，以达到最佳的资源配置，使项目工期最短。这样， 就引出了需要解决的问题：在多项目环境下模具项目的资源分配问题，即怎样有 效地优化多个项目同时进行情况下分配资源以缩短模具设计工期的问题。 1 1 4 课题的来源 本课题来源于： ( 1 ) 8 6 3 计划项目：基于项目群动态调度的模具网络化制造系统建模、仿真与 优化( 项目号：2 0 0 6 a a 0 4 2 13 2 ) ( 2 ) 粤港关键领域招标项目：模具行业企业信息化集成与协同平台开发与应 用( 项目号：2 0 0 5 a 10 2 0 7 0 0 2 ) 4 第一章绪论 1 2 - 国内外研究现状和问题分析 资源约束项目调度问题r c p s p ( r e s o u r c e c o n s t r a i n e dp r o je c t s c h e d u l i n g p r o b l e m ) 是典型的n p ( n o n d e t e r m i n i s t i cp o l y n o m i a l b o u n d e r s ) 难题。一个r c p s p 包含一系列相关联的活动集合，这些活动之间具有紧前约束关系，必须在资源约 束和紧前关系约束下进行调度。每一个活动可以用几种模式完成，每一模式此问 题的解是在满足时序约束和资源约束的条件下产生一种使某些管理目标为最优的 方案。 多模式资源受限项目调度( m u l t i m o d er e s o u r c e c o n s t r a i n e dp r o je c t s c h e d u l i n gp r o b l e m ，m r c p s p ) 是一类非常广义的调度优化问题。它要求在满足项 目紧前约束与资源约束的前提下，确定项目中每个任务的执行模式，以及相应的 开工期和完工期，以便最小化项目的总工期。 1 2 1 基本概念 ( 1 ) 项目( p r o j e c t ) ：项目是指拥有有限资源的有限活动的集合，一个项目必 须在特定活动间的紧前关系约束下、资源约束等约束下进行调度。 ( 2 ) 活动( a c t i v i t i e s ) ：描述需要执行的具体动作，活动具有起始、终止时刻、 持续时间以及可能得到的各种资源和各种约束； ( 3 ) 模式( m o d e ) ：模式是活动所用资源数量与相关持续时间的一种组合选择。 对于一个具体的活动而言，采用不同的执行模式所消耗的资源和持续的时间是不 同的； ( 4 ) 资源( r e s o u r c e ) ：在活动执行过程中所使用和消耗的诸如电能、设备、 人力资源等有形或无形的实体，在调度中这些统称为资源。根据s l o w i n s k i 3 】等人 提出的分类方法，资源可以分为三大类：可更新资源( r e n e w a b l e ) 、不可更新资源 ( n o n r e n e w a b l e ) 和双重约束资源( d o u b l yc o n s t r a i n e d ) ； ( 5 ) 约束( c o n s t r a i n ) ：约束定义调度的可行性，对一般问题而言，约束是必须 满足的条件。一般约束包括：时序约束，活动之间相对的时序优先级关系；资源 约束，活动对资源的数量、使用时间等的要求统一称为资源约束。紧f j i 约束关系 广东工业大学硕i j 学位论文 定义项目内活动之间必须满足时序要求。最常见的紧f j 约束关系是“完成一开始 型，也就皂活动只有当其前序活动都完成后才能开始。其他类型的紧前约束关系 是“开始一完成”、“开始一开始和“完成一完成 。 1 2 2 受限资源项目调度问题常用解法 自从上世纪六十年代初k e l e y 和w i e s t 开始对该问题研究以来，资源约束项 目调度问题吸引了大量学者的注意，在过去的四十年中，有许多公开发表的文章 和专题论文从不同的角度对该问题进行了研究提出了各种各样的优化方法，概括 起来可分为以下三类： ( 1 ) 分支定界法( b r a n c ha n db o u n da p p r o a c h ) 为代表的确定性算法【4 ，5 】； ( 2 ) 基于优先规则的启发式算法( p r i o r i t yr u l eb a s e dh e u r i s t i c s ) i6 7 】 ( 3 ) 以g a ( g e n e t i ca l g o r i t h m s ) 和s a ( s i m u l a t e da n n e a l i n g ) 为代表的智能 优化算法【8 - 1 0 】。 通常用确定性算法求解资源受限的项目调度问题如：线性规划法、分支定界 法。确定性算法在理论上能求得该问题的最优解，但是用计算机求解这类问题的 c p u 时间会随着网络计划中节点数目的增多而呈指数曲线上升，会出现所谓的组 合爆炸现象j 。因此精确类算法只能求解小规模项目的资源约束项目调度问题， 但是采用此类方法等问题达到一定规模时，就会因为问题的解空间太大，而不能 在可接受的时间给出最优解。因此，近年来一些非确定性的、启发式的算法逐渐 应用到求解大规模组合优化问题上来如：蚁群算法和遗传算法。 启发式算法和智能优化算法不能保证求得问题的最优解，但在解决大规模问 题时能在求解质量和求解效率上获得一种较好的平衡。启发式算法计算简单、可 操作性强，发展的较为成熟。但是不同的启发式方法处理同一问题的效果，以及 同一启发式方法处理不同问题的效果很大的差异，它们会随着网络计划特征的不 同而有所变化。某一方法的应用，对于具有某些特征的问题效果可能很好，但对 另一问题效果则可能很差同时，随着网络计划任务数目的增加、约束关系的复杂 化，启发式方法处理问题的效果会发生明显的变化，计算精度逐渐降低【l2 1 。到目 前为止，据不完全统计，常用的启发式方法有三十多种【l3 1 ，但是，不同启发式方 法处理网络计划问题的效果差异很大，于是人们对启发式方法的分析和评价进行 6 第一章绪论 了大量的研究。早在1 9 7 5 年，d a v is 和p a t t e r s o n 就开展了启发式算法的研究工作， 他们通过考察8 3 个网络计划，对8 种启发式方法进行了分析，发现各方法所得到的 结果与理想结果的偏差为5 一10 之间【1 4 】。 1 分支定界法( b r a n c ha n db o u n da p p r o a c h ) 分支定界算法的基本思想是先用搜索树将问题的解空间按照一定的规则分割 成子空间，再利用合理的定界方法排除那些不包含最优解的子空间，从而实现缩 小有效搜索空间的目的。资源受限项目调度问题求解的分支定界法中要建立一个 枚举树，方法的基本思想是通过枚举树中的一序列决策点推导出一个调度方案， 而在每一个决策点上产生一个部分计划，不同的方法有不同的枚举策略【1 5 1 。 在分支定界算法中，采用较为有效的下界计算方法对于控制搜索树的节点个 数和提高算法的执行效率是非常重要的。传统的下界计算方法是求解原问题的松 弛问题，并将求解的目标值作为原问题目标值的下界，这种方法被称为构造性方 法。最近出现的破坏性下界计算方法为分支定界算法提供了新的思路，一些实验 表明：利用破坏性方法求解r c p s p 的下界时，可以得到比构造性方法更好的下界 【l6 1 2 启发式算法( h e u r i s t i ca l g o r i t h m s ) 基于启发式算法是应用最普遍也是最重要的一类算法。大多资源受限工程调 度问题求解的启发式方法是基于调度计划生成方案( s c h e d u l eg e n e r a t i o ns c h e m a ， 简称s g s ) ，s g s 通过逐步扩展局部进度计划来生成一个完整可行的调度计划。 下面简略介绍基于优先规则的调度方法和智能启发式方法。 ( 1 ) 基于优先规则的调度( p r i o r i t yr u l eb a s e dh e u r i s t i c s ) 基于优先规则的调度由两个要素组成s g s 和优先规则( p r i o r i t yr u l e ) 。通常 人们所使用的s g s 包括：串行调度方案( s e r i a ls c h e d u l i n gs c h e m a ，简写为s s s ) 和并行调度方案( p a r a l l e ls c h e d u l i n gs c h e m a ，简写为p s s ) 。 对一个包含n 个任务的项目来说，串行s g s 执行过程包括n 个阶段，每个阶 段从可行任务集合中按照某种优先规则选择一个活动在满足紧前约束关系和资源 约束的前提下进行调度。4 0 余年来人们先后提出了大量的优先规则，其中比较广 为使用的优先规则是：最高排列位置权重( g r p w ) 1 7 】、最迟结束时间( l f t ) 1 8 】、最 广东t 业大学硕f j 学位论文 迟开始时间( l s t ) 【19 1 、最小自由时差( m s l k ) 1 19 1 、最多紧后活动数( m t s ) 【13 】等。 以下列举了一些常见的分配规则，下表1 1 所示。 。 并行调度方案生成一个调度计划至少需要n 个步骤。每一步中首先确定当前 调度阶段的调度时间，选择已经调度的活动的最小完成时间作为当前阶段的调度 时间，这样就意味着在这个调度时间之后能有有资源约束范围内的剩余资源为待 调度活动的执行服务。然后从当前可行活动中选择一组活动进行调度，选择的依 据同样是优先规则。串行调度方案中所使用的优先规则也常常被用于并行调度方 案中，而许多学者也根据并行调度方案的特性开发了一些特殊的优先规则，例如： 资源调度方法( r s m ) 【20 1 、改进资源调度方法( i r s m ) 1 1 9 、最坏自由时差( w c s ) 1 1 9 】、 平均自由时差( a c s ) 9 】等。 表1 1 一些常见的分配规则 t a b l e1 1c o m m o na s s i g n m e n tr u l e s 序号规则名称说明 1r a n d o m 随机选择 2f i f 0 先进先出 3l i f o后进先出 4s p t处理时间最短 5l p t处理时间最长 6l o r剩余工序数最少 7m o r剩余工序数最多 8l w r剩余总加工时间最少 9m w r剩余总加工时间最多 lo m i n q下道工序服务队列最短 1 1 w i n q下道工序服务台工作量最少 12e d d交付期最早 前面所描述基于优先规则的调度过程只是单回合执行的，即每次调度过程执 行一次，并且整个调度过程使用一种优先规则。随着研究的深入开展，人们逐步 发现采用多回合的计算方法一般能够获得更好的效果。多回合的计算方法就是指 调度过程的多次执行产生多个可行的方案，并从中选择最好的调度方案，而多次 第一幸绪论 调度过程的执行可以采取两种模式：确定型多回合和随机型多回合【2 h 2 2 1 。 ( 2 ) 智能启发式方法( i n t e l l i g e n th e u r i s t i c s ) 针对r c p s p 的智能优化方法主要包括编码方式和解码规则、相邻解的定义以 及初始解产生三个要素【22 1 ，其中编码是按照某种对应规则与唯一可行调度计划相 对应的一组代码，而解码是采用一定规则将编码转换为可行调度计划的过程，初 始解是采用其它方法得到的一组编码，对应初始的可行调度计划，相邻解是一组 编码经过一步特别定义的操作所能得到的所有新的编码的集合。相邻解的定义往 往由编码方式和解码规则确定；初始解一般是随机生成或根据特定的编码方式结 合一些优先规则生成，这样既保证了初始解的多样性又保证了初始解的质量。所 以，求解r c p s p 的智能启发式方法主要区别在编码方式和解码规则上，归纳起来 可分为如下几类【z 2 】： 1 ) 紧前关系相容链表。串行调度方案每一次执行的结果对应一个活动链表， 各活动在链表中的顺序是满足紧前关系约束的。反之，如果给定一个满足紧前关 系的活动链表，那么应用串行调度方案解码可以生成一个可行调度计划。文献【2 五 2 4 2 7 1 的工作中采用了此类编码方式。 2 ) 优先权系数向量。如果给定一个i 维向量，向量中的第i 个元素代表活动 i 的优先权系数，那么针对该向量应用并行调度方案解码便可生成一个可行调度 计划。l e e 2 5 】采用了此类编码方式。 3 ) 优先规则链表。事先选定若干条优先规则构成优先规则集，再从中依次随 机选择i 条规则构成优先规则链表。解码规则既可以采用串行调度方案或并行调 度方案。解码过程如下：在调度第i 个活动时，采用编码中的第i 条优先规则计 算当前可调度活动集中各活动的优先权，并选择优先权最高的活动按照串行( 并行) 调度方案原则安排其开始时间，直至i 项活动全部调度完毕。t ) z d a m a r 采用基于 这种编码方式的改进遗传算法求解m m r c p s p t 26 1 ，得到了较好的效果。 3 遗传算法( g e n e t i ca l g o r i t h m s ) 遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全 局优化概率搜索算法。它最早是由美国密执安大学的h o l l a n d 教授提出，起源于 6 0 年代对自然和人工自适应系统的研究24 1 。它将问题的求解过程表示成“染色体” 的适者生存过程，通过染色体群( p o p u l a t i o n ) l 拘不断进化，包括复制( r e p r o d u c t i o n ) 、 9 广东t 业大学硕l j 学位论文 交叉( c r o s s o v e r ) 和变异( m u t a t i o n ) 等操作，最终收敛到“最适应环境的个体”，从而 求得问题的最优解或满意解。遗传算法是一种通用的优化算法，其编码技术和遗 传操作比较简单，优化不受限制性条件的约束，并且具有隐含并行性和搜索空间 的全局性特点。近年来，遗传算法在资源约束项目调度问题中得到了较为广泛的 应用。 遗传算法的一般流程如图1 2 所示： 图1 2 遗传算法的一般流程 f i g u r e1 - 2g a f l o wc h a r t s 4 禁忌搜索( t a b us e a r c h ) 禁忌搜索是由g l o v e r 提出的用于获取组合最优化难题近似解的一种高级启发 式方法。用这种方法，搜索从一个可行解开始逐步移向一个最优或次优解。在每 次移动前，需要根据某种与问题有关的规则确定在现行解周围的相邻解集。然后 评估每一个相邻解，并移动到该相邻解集中的一个最好解。有些移动是禁忌的， 因为它们会陷入局部最优或导致循环。这些禁忌的移动被加入禁忌表，一般地， 禁忌表的长度越长，则搜索陷入局部最优的可能性越小。但是，长禁忌表需要更多 的计算扫描时间，并且在每次迭代中限制了搜索空间。最合适的长度与问题有关， 但到目前为止还没有确定长度的规则可循。禁忌搜索己成功和应用在调度问题和 混合整数规划问题中。t a i l a r d t ”】提出了解决流水车间调度问题的禁忌搜索算法。 m a n u e l 3 0 l 为了更有效地搜索解空间，引入了插入移动和移动相结合的机制提高了 l o 第一章绪论 搜索效率。 5 模拟退火( s i m u l a t e da n n e a l i n g ) 模拟退火模仿金属中结晶体和冷却的物理过程。模拟退火算法求解的基本思 想是从一个初始可行解出发，反复迭代产生邻域解。如果邻域解的目标函数值优 于初始解，则用邻域解取代初始解继续迭代，如果邻域解的目标函数值比当前解 的目标函数值差，则依据一定的概率p 决定舍弃还是用它取代当前解，这一概率p 的值取决于冷却温度。在迭代的早期，p 的值相当大可以接受大多数邻域解，然 后随着时间的推移，p 的取值逐步减小即接受恶化解的概率越来越小，最后趋于 最优解。动态改变p 值的目的是防止迭代过程过早地落入局部最优解的范围。 j e f c o a t 和b u l f i n f3 i 】应用模拟退火法解决资源受制约的调度问题。他们的计算结果 表明与其他邻域搜索技术相比模拟退火能获得最好的解。 研究表明，在众多的启发式算法中，s a 、g a 和t a 的计算结果优于其它算法， 而对于大规模的项目来说，g a 则优于s a 和t a 。 1 2 3 调度问题 1 调度问题的分类 调度分为三类：静态调度、动态调度和重调度，如下图1 3 所示，分别描述 了设计过程中三种类型的调度： ( 1 ) 静态调度：是在理想条件下对任务优化排序，进而形成计划的过程。静 态调度不考虑生产或者设计过程中出现的意外情况。 ( 2 ) 动态调度：是由一系列以一步事件为步长的调度步共同完成的，每一次 调度步即时采样当时进行的状态，并生成一个调度方案片，所有调度方案片组合 在一起构成完整的动态调度方案。 ( 3 ) 重调度：是在模具设计执行过程中，由于模具设计过程的不确定性会存 在突发事件的发生从而容易引起当前待执行任务和资源的各种变化发生，从而使 得所获取的优化调度方案逐渐失去其优良性，甚至可行性。这时便需要对其进行 调整或重新调度，由此引出了模具设计过程的重调度问题。此时，我们运用调度 算法决定哪些任务真正投入执行，以及分配给这些任务哪类资源，任务执行后， 广东工业大学硕l 学位论文 继续监测有无触发事件集合众的事件发生，一旦监测到事件发生，执行调度算法， 直到设计过程结束。重调度问题是优化调度问题的延伸，也是优化调度理论研究 的新阶段。 ) 。 ) ，r 静态调度 静态调度 图1 3 静态调度、动态调度和重调度 f i g u r e1 3s c h e d u l i n g 、d y n a m i cs c h e d u l i n ga n dr e s c h e d u l i n g 由于模具设计过程中经常会有来自项目或者设计人员的各种变化发生，即一 些突发事件见3 1 节，从而使得所获取的优化调度方案逐渐失去其优良性，甚至 可行性。这时便需要对其进行调整或重新调度，由此引出了模具设计过程的重调 度问题。重调度问题是优化调度问题的延伸，也是优化调度理论研究的新阶段。 重调度的目标应该是对原来调度任务安排的影响最小的调度结果，并且应该 尽量保证满足原计划调度的目标和约束。 第一章绪论 预测一反应式调度对于重调度动态制造系统是一个普通策略。它有两个主要 的步骤。第一步是产生一个优化调度计划。第三步更新调度，也就是对系统破坏 或其他事件最小化它们对系统性能的影响。预测一反应式调度是一个迭代过程。 w u 【3 5 】已经描述了重调度作为一个迭代过程分3 个步骤：一是评估步骤，评估一 个突发事件的影响，二是决定重调度解的步骤，三是修改步骤，它更新一个存在 的调度计划或产生一个新的调度计划。y a m a m o t o 3 6 】已经提出了一个按照通常3 个阶段的重调度方法。第一是计划阶段，这个阶段构造一个初始调度，这个调度 要提前在一个新的工作期开始产生，它是在所有可能利用的生产要求基础上的。 第二是控制阶段，这个阶段比较每一次一个新任务开始或结束时对于当前调度计 划的实际误差。如果误差超过了一个指定的限制，则重调度阶段开始。第三是重 调度阶段。 预测一反应式调度包括三种类型的重调度策略【37 】：周期性、事件驱动和混合 式。周期性重调度【3 8 】是不考虑突发事件的触发，每隔一段时间启动一次重调度。 但是在实际应用中，很难确定最佳的重调度周期；事件驱动性重调度f 3 9j 是由扰动 即突发事件触发重调度，能够及时响应设计过程中的扰动事件，更新原调度计划 的调度：混合式重调度【4 0 】是将上述两种策略相结合，在周期性重调度的基准上， 当有突发事件发生时也会启动重调度，希望能够在有效跟踪系统变化的同时也能 控制计算量。 1 2 4 多资源约束下的项目调度与重调度过程比较 项目重调度就是在项目的执行过程中， 的调度过程相同之处是两者都是把有限的、 同之处有以下几点【4 1 1 ，如下表1 2 所示： 对资源和项目进行重新配置。与项目 受约束的资源分配给任务的过程，不 广东工业人学硕i ：学位论文 表1 2 项目调度与重调度的比较 t a b l e1 - 2c o m p a r es c h e d u l i n ga n dr e - s c h e d u l i n g 项目调度重调度 执行过程项目启动之前在按计划执行的过程中 时间范围 以项目的计划开始时间为起点从某个突发事件发生的时刻起 在资源和任务紧前约束的条件由于突发事件发生在满足约束 目标下，取得项目最短的执行时间的情况下尽量保持原来计划，使 的结果得对原计划调整最少 1 2 5 存在的问题与不足 目前研究中存在的问题有： 1 启发式算法缺乏统一的程序框架。目前许多学者针对r c p s p 提出了各种 各样的启发式算法，这些算法往往采用不同的程序框架、不同的编程语言、运行 在不同的操作系统上，所以很难准确比较它们的执行效率。 2 柔性资源限制下的工程调度问题。在实际工程实施过程中，资源的约束往 往是柔性的，如某些施工机械可以租借得到，劳动力资源可以通过适当的加班获 得增加等等。在r c p s p 的优化调度过程中，工程工期往往因为某些瓶颈资源的限 制而拖长，如果适当提高该瓶颈资源的拥有量，工程工期会缩短很多，从而大大 提高工程的经济目标。所以，在柔性资源限制下工程调度问题更符合实际应用。 虽然多执行模式资源受限项目调度问题 3 l 】考虑了各任务的执行模式的柔性，但仍 存在资源限制柔性的问题，而目前对此研究很少。 3 项目规划的稳定性问题。目前，针对r c p s p 的调度方法的静态调度方法， 调度计划一旦生成便意味着整个工程实施计划的确定。在实际工程的实施过程中 可能会遇到多种不可预见问题，这些突发事件的发生会导致原计划无法顺利实施， 需要对现有计划进行调整或重调度。一个稳定性好的计划只需较小的费用就会得 到有效的调整。 4 目前的资源受限项目调度问题的研究主要将资源分类，每类资源都看作无 差别的，比如机器、生产资料等，很少有对例如人力资源这类彼此之间有差别的 资源进行研究。 1 4 第一章绪论 1 3 选题意义 对于一个模具企业来说，设计人员作为一种非常重要的资源，其分配在模具 企业项目管理中的地位非常重要，合理、有效地分配设计人员可以使员工明确职 责，方便项目管理者统计每个人员的工作量和整个设计过程进行控制和管理。如 果缺乏有效的资源分配将会直接导致项目的失败，从而使企业面临着被淘汰的危 险。尤其是在现在这种多项目环境下，即多个产品项目同时进行的情况下，项目 与项目之间存在着资源冲突、竞争、共享的特点，在一定时期内的资源是有限的， 在各种资源约束下生成调度计划，给各设计人员安排设计任务，尽可能大的发挥 每个设计人员的设计专长和尽量缩短项目的设计时间，从而缩短交货期，这些对 模具企业的管理者判断项目的可行性和估算和缩短模具的交货期有一定的指导作 用。 1 4 本文研究的主要内容 本课题研究问题属于资源受限项目调度问题。课题的目标是建立一个多项目 模具设计过程任务分配问题的数学模型，提出一个解决该问题的算法，并开发一 个模具设计过程管理原型系统。 根据以上目标，本课题主要有以下研究内容： ( 1 ) 模具设计过程分析与模具设计任务的分解； ( 2 ) 模具设计人员设计技能的描述和评估； ( 3 ) 基于遗传算法的项目规划，生成调度计划任务分配表； ( 4 ) 当突发事件发生时，根据不同的事件分情况选择调度策略：确定是采用 整体重调度还是部分重调整； ( 5 ) 原型系统设计开发。 研究工作主要从以下几方面展开： ( 1 ) 总结国内外研究现状和理论方法； 广东丁业大学硕：卜学位论文 ( 2 ) 该问题的描述和建立数学模型； ( 3 ) 提出解决此问题的算法； ( 4 ) 模具设计管理系统的设计和初步实现。对应分布式环境下的模具设计任 务分配和控制的要求，用j s p 和j a v a 编程技术设计开发了网络环境下的模具设计 过程任务分配系统原型，并实现了部分的功能界面。 1 5 论文章节安排 全文共分四个部分，本文章节安排如下： 第一章绪论。介绍本文的研究背景，国内外研究现状和存在的问题、研究意 义、选题依据、研究内容以及论文章节安排，最后简述了论文的研究的主要内容。 第二章模具设计任务分配问题建模。该问题属于多模式资源受限项目调度问 题，并提出算法。 第三章模具设计过程调度。主要论述当突发事件发生后如何根据突发该事件 的类型及其影响确定是对原调度计划采用哪种处理方法，是局部调整还是从突发 事件发生的时刻起执行整体重调度等。 第四章模具设计管理系统的设计和开