（管理科学与工程专业论文）虚拟制造组织中任务分配系统的设计与开发.pdf

华中科技大学硕士学位论文 摘要 虚拟制造组织( v m o ，v i r t u a lm a n u f a c t u r i n go r g a n i z a t i o n ) 是基于合作的全球化 制造模式。地域上分布的成员企业通过i n t e m e f f i n t r a n e t 结成联盟，实现资源共享、风 险共担、利益均分，从而达到降低生产成本、快速响应市场需求、提高市场竞争力的 目的。在v m o 中，各成员企业通过任务分配环节建立合作关系，进行资源重组完成 生产任务并进行利益分配。任务分配系统的设计与开发是v m o 项目的研究重点之 一d 本文研究了基于招投标机制的任务分配模型。基于该模型，分布在各成员企业的 子系统依据招投标协议进行多边谈判，完成任务分配过程。本论文的研究工作主要包 括系统设计实现和协议算法研究两大部分，广泛研究了系统构架及应用技术、数据处 理、模块划分，招投标协议、谈判策略、成本计算模型和生产调度算法等方面。 在系统设计中，采用了基于c o r b a 的m u l t i - a g e n t 结构，解决了分布式异构系 统间的交互问题；采用x m l 文档作为系统间数据和文档交换的标准格式，提供了用 户自定义格式与信息和文档自动解析功能，以及与数据库系统的无缝集成。整个系统 分为9 个模块：招标准备模块、招标谈判模块、招标合同模块、计时器模块、投标准 备模块、投标谈判模块、投标合同模块、成本核算模块及生产调度模块。 在协议算法研究中，本文提出了一种改迸的扩展合同网协议，定义了更为丰富的 谈判语言，实现了多边多回合的招投标谈判并解决了多种冲突问题。提出了一种以利 润为目标的谈判策略，允许各个招投标方根据其各自利润目标报价谈判保证了招投 标结果的双赢。提出了基于动态调度的成本计算模型，为投标方进行谈判提供了报价 的依据。提出了一种基于e d f ( e a r l i e s td u e , d a yf i r s t ) 的改进生产调度算法，优化了 企业的生产调度，提高了生产线豹利用率，从而降低了生产成本，保证了投标方在招 投标过程中的竞争优势。 根据系统设计及协议算法研究的结果利用j a v a 语言实际开发了跨平台、分布式 的v m o 任务分配原型系统，可以与v m o 信息系统进行集成，并通过人机交互快速 完成v m o 中的任务分配过程。 关键词：虚拟制造组织任务分配 招投标机制 i 华中科技大学硕士学位论文 a b s t r a c t v i r t u a lm a n u f a c t u r i n go r g a n i z a t i o n ( v m o ) i sa m a n u f a c t u r i n gm o d e b a s e do ng l o b a l c o l l a b o r a t i o n t h ed i s t r i b u t e de n t e r p r i s em e r e b e i sc o l l a b o r a t ew i t he a c ho t h e rv i ai n t e r a c t a n d i n t r a n e t ，s h a r i n gr e s o u r c e s ，r i s k sa n dp r o f i t s ，s oa st or e d u c ep r o d u c t i o nc o s t ，r e s p o n d t o m a r k e td e m a n d si nt i m ea n db em o r ec o m p e t i t i v e i nv m o ，m e m b e r sr e c o n s t r u c tt h e i r r c s o l l r c e e st of u l f i l lt h ep r o d u c d o nt a s ka tm i n i m u mt o t a lc o s t , a n da l l o c a t et h ep r o f i t s u c h p r o c e d u r e i sc a l l e dt a s ka u o c a t i o n t h ed e s i g na n d d e v e l o p m e n t o ft a s ka l l o c a t i o ns y s t e mi s o n eo ft h em o s ti m p o r t a n ta s p e c t si nv m or e s e a r c h i nt h i sw o r k ，w ep r o p o s e dab i d d i n g - b a s e dt a s ka l l o c a t i o nm e d e l g e o g r a p h i c a l l y d i s t r i b u t e dm e m b e r sc a nm a k em u l t i - b o u n d a r ya n dm u l t i b o u t n e g o t i a t i o n s o nt a s k a h o c a d o nt h r o u g hb i d d i n gp r o t o c 0 1 t h i st h e s i sc o n s i s t so ft w op a r t s ：s y s t e md e s i g na n d i m p l e m e n t a t i o n , 鹊w e l l a s b i d d i n gp r o t o c o l a n d a l g o r i t h m e x t e n s i v e r e s e a r c h e sa n d d i s c u s s i o n sa r ei n v o l v e d ，s u c ha ss y s t e ma r c h i t e c t u r e ，a p p h e dt e c h n o l o g i e s , d a t a p r o c e s s i n g , m o d u l i z a t i o n ，p r o t o c o ll a n g u a g e , n e g o t i a t i o ns t r a t e g y ，c o s tm o d e l ，s c h e d u l i n ga l g o r i t h m ，a n d s o o n i ns y s t e md e s i g n c o r b a - b a s e dm u l t i - a g e n ts y s t e mi s a d o p t e da st h eb a c k b o n et o s u p p o r t t h e i n t e r o p e m t i o na m o n g t h ed i s t r i b u t e di s o m e r i c s y s t e m s x m l - b a s e d d o e u m e n t a t i o na n dd a t ae x c h a n g ep r o v i d e su s e r - f r i e n d l yf o r m a ta n df u n c t i o n ，a u t o m a t i c d a t a d o c u m e n tp a r s i n g ，a n ds e a m l e s si n t e g r a t i o nw i t hd a t a b a s es y s t e m a c c o r d i n gt ot h e f u n c t i o n a lr e q u i r e m e n t s t h es y s t e ma r cd i v i d e di n t o9m o d u l e s ：t e n d e r e eb i dp r e p a r a t i o n m o d u l e ，t e n d e r e en e g o t i a t i o nm o d u l e ，t e n d e r e ec o n t r a c tm o d u l e ，t i m e rm o d u l e ，t e n d e r e rb i d p r e p a r a t i o nm o d u l e , t e n d e r e rn e g o t i a t i o nm o d u l e ，t e n d e r e r c o n t r a c tm o d u l e ，c o s tc a l c u l a t i o n m o d u l ea n d p r o d u c t i o ns c h e d u l i n g m o d u l e i np r o t o c o la n da l g o r i t h md e s i g n , w em o d i f i e dt h ee x t e n d e dc o n t a c tn e t w o r k p r o t o c o l w i t he n r i c h m e n to fp r o t o c o ll a n g u a g e ，a n dm a d ei ts u i t a b l ef o rm u l t i b o u n d a r y , m u l t i - b o u t b i dn e g o t i a t i o nb yr e m o v i n ga l lp o s s i b l ea n dp o t e n t i a lc o n f l i c t si nn e g o t i a t i o np r o c e d u r e - a p r o f i t - i n t e n d e dn e g o t i a t i o ns t r a t e g yw a s a l s op r o p o s e dt oe n s r r ee v e r y p a r t y h a st h eo p t i o nt o m a x i m i z ei t s p r o f i td u r i n gn e g o t i a t i o n t h e c o s tc a l c u l a t i o nm o d e lb a s e do n d y n a m i c s c h e d u l i n gp r o v i d e st h er e a s o n a b l er e f e r e n t i a lq u o t e p r i n ef o rt e n d e r e ri n b i dp r o c e d u r e i n o r d e rt oi m p r o v et h et a n d e r e r sc o m p e t i t i v e n e s s ，w ea l s op r o p o s e d am o d i f i e de d f 口a r l i e s t d u e d a yf i r s 0s c h e d u l i n ga l g o r i t h m t om a x i m i z et h eu s a g eo ft h ep r o d u c t i o nl i n e - b a s e do nt h es y s t e ma n dp r o t o c o ld e s i g n ，w ed e v e l o p e dt h ec r 0 6 s p l a t f o r m ，d i s t r i b u t e d , d r o t o t y p e t a s ka l l o c a t i o ns y s t e mu s i n gj a v a 2e n t e r p r i s ee d i t i o n i n t e g r a t e dw i t hv m o i n f o r m a t i o ns y s t e m ，t h es y s t e mc a r r i e so u tt h et a s ka l l o c a t o n i nah i g h l y - e f f i c i e n ta n dr o b u s t w a yb yv e r ys i m p l eh u m a n - c o m p u t e r i n t e m c d o n 华中科技大学硕士学位论文 k e y w o r d s ：v i r t u a lm a n u f a c t u r i n go r g a n i z a t i o n ( v v l o ) t a s ka l l o c a t i o n b i d d i n g m e c h a n i s m 华中科技大学硕士学位论文 1 绪论 本章首先介绍课题的来潭、目的和意义，然后对虚拟企业联盟及分布式环境中的任务分配问 题的相关研究现状进行综述，最后给出全文的主要研究内容 1 1 课题来源 本课题受到以下科研基金的资助： ( 1 ) 国家自然科学基金项目“虚拟制造组织的构造与控制”，项目编号， 7 0 0 1 1 6 1 9 4 9 ： ( 2 ) 香港研究资助局科研资助基金项目，项目编号：nh k u s t 0 2 3 0 0 。 1 2 课题的目的和意义 九十年代以后，日趋激烈的全球化市场竞争使传统制造业面临的压力与日惧增 p j 。为了快速响应市场需求变化，适应各种内外部突发事件等不确定性因素影响，制 造生产组织开始从传统的熬遍莹墼盼结构征鞋婴墨；i 5 趄a r c h i c e c t u r e ) 捌向扈王! 蛐结构 ( j 幽獭8 h i 斛a r c h i 惦c t u r e ) 【3 】转变。企业生产活动的控制也从集中式转向分散化1 4 - s l 。 新的制造组织模式，比如敏捷制造1 em a n u f a c t u r i a g ) r 1 0 1 、分散自律制造系统 ( h o l o n i cm a n u f a c t u r i n gs y s t e m ) 1 1 1 甜、网络制造( n e t w o r k e dm a n u f a c t u r i n g ) 1 4 j 【1 5 】、虚拟 企业f 1 岳2 1 l 和扩展型企业吲等，相继出现。 现代通信与交通运输技术的发展，尤其是计算机用络的广泛应用，为制造业跨企 业跨地域的合作创造了条件，借助网络通信技术，地理上异地分布、组织上平等独立 的多个企业可通过谈判协商合作，构成动态的虚拟企业，以提高产品质量、降低生产 成本、缩短产品投放市场时间熬，j 同把握市场机遇【2 = 】。同时，制造活动日趋服务 化。不仅产品开发设计、加工制造与装配等环节可以对外承包完成，c a d 、c a e 、 e r p 等功能领域也可以借助网络寻求外部服务。各个企业可以更多地专注于自己的核 心业务，借助网络信息服务和行业联盟政策法规自主协作与竞争，实现企业间优势互 补和社会资源动态优化组台。 基于敏捷制造、分布式制造、供应链管理和电子商务等诸领域的理论与技术成 果，虚拟制造组织的构造与控制项目提出了虚拟制造组织( v m o ，v i r t u a l m a n u f a c t u r i n go r g a n i z a t i o n ) 的概念。虚拟制造组织( v m o ) 具有集协约 ( p r o t o c 0 1 ) 、过程( p r o c e s s ) 和系统于一体的统一框架。框架中的成员公司可以在 统一的信息平台上自由交换经营数据与市场信息，在最少的法律、经济和行政等约束 1 华中科技大学硕士学位论文 下快速组建围绕单一产品的动态企业联盟，有效地集成和利用来自不同成员公司的生 产资源，打破地域和边缘的约束。 在v m o 模式下，彼此独立的成员企业互补性地贡献其核心竞争能力，依据技能 或服务“最低成本配置”原则快速组建动态企业联盟，在保证了动态企业联盟的竞争 优势的前提下，v m o 框架为成员企业提供了更好的分散自治性，组织灵活性，公平 合作与竞争，和强烈的项目管理特色，使得动态企业联盟在操作管理和运行效率上都 有了质的提升。 为实现v m o 制造模式，需要围绕其构造、运行与控制的各个方面进行研究。本 课题作为虚拟制造组织( v m o ) 研究项目的一个子课题提出，主要工作是在v m o 信 息系统框架下设计开发任务分配子系统，完成围绕项目进行的任务及和益分配过程。 该课题要根据v m o 内部成员问的动态任务分配要求，设计开发应用于这一过程的任 务分配原型系统，同时对涉及到的协议、策略和算法做深入研究。 任务分配系统的开发为v m o 中的制造企业( 制造资源) 的集成和重组提供了信 息交互与操作平台。整个任务分配过程可以在人机交互状态下快速完成，实现v m o 内部成员闻靠4 造资源的快速重组。任务分配协议及相关决策模型的研究充分考唐了 v m o 内部的成员的利益自主和公平竞争，为系统的运行提供良好的可操作性。包括 本系统在内的整个v m o 信息平台的研究开发，为实现制造企业的网络化、信息化、 集成化、敏捷化以及柔性化提供了可借鉴的集成框架和实现方法，为大中型企业的分 散化经营和中小型企业的动态联盟提供理论与技术基础，同时也为进一步提高我国制 造企业积极参与全球化市场竞争的能力提供先进的运行模式和技术手段。 1 3 国内外研究现状 1 3 1 虚拟企业联盟的研究状况 在“2 1 世纪制造业战略发展报告”中提出了新的工业生产模式一一基于双赢原则的 动态企业联盟。其目的是使用在计算技术上发展起来的产品制造、信息集残和通信系 统来构造新的竞争系统，把产品生产所需的所有资源一人、资金和设备通过网络和 通信技术联系在一起，进行集中管理，实现优化利用。 动态联盟是企业为了快速响应出现或根据预测即将出现的市场机遇而联合其他企 业组织的公司或集团( 利益共同体) ，它是某一时间阶段、某一市场需求的产物。它强 调通过企业闯的利益共享和风险共担来实现企_ , l k n 合作，强调联合竞争、共同盈利的 合作机制 2 6 z 7 1 。这个联盟是动态的，它有一定的生命周期。它随着某个市场机遇或者 某项新技术、新发明的应用要求而产生，当这一前提失去之后，联盟自动瓦解。动态 2 华中科技大学硕士学位论文 联盟的发起者通常为较早意识到市场机遇存在的企业，或者是这一未来产品的关键技 术的持有者。 动态联盟和太的企业集团不同，它更强调灵活、机动，有着更好的敏捷性。动态 联盟要求每个企业只贡献其核心竞争力，通过核心竞争力的互补来构成一个比其他竞 争对手更强的联盟。 与传统的工作方式相比较，动态联盟强调“动态”和“联盟”。“动态”反映了 市场和竞争环境的特点，而“联盟”代表了一种通过紧密合作去响应市场环境变化的 组织模式。动态联盟的重要作用也已经被众多企业认可，从组织形态出发，许多企业 已经进行了实践并取得了成功( 如表1 - 1 ) 。 表1 - 1 一些主要的动态联盟 动态联盟持续时间主要成员 v l s i 联盟1 9 7 6 1 9 7 9富士通、日立、三菱、日本电气、东芝、e t l m m p c 联盟1 9 8 0 一1 9 8 4 i b m 、h 饵l 、m i c t o s o f t a c e 联盟 1 9 9 1 1 9 9 2 m 晒、c o m p a q 、d e c p o w e r p c 1 9 9 1 i b m 、m o t o r o l a 、a p p l e 另一方面，动态联盟的成功运作还需要在企业信息网络构架上来保证。柔性、敏 捷的市场响应能力要求开放、动态、扁平式的信息管理结构和生产经营体系，这离不 开对各种生产经营信息、数据及知识( 如市场、资本、决策、管理、控制、生产、产 品、技术、人才及设备等) 的高效而快捷的采掘、处理、存储、传输与应用。很大程 度上，它们赖于企业对信息技术一特别是网络技术一在其业务活动中的应用、融合和 衍生【2 s - 3 0 。 为此，国内外纷纷在展开基于网络的制造业的集成信息和管理系统的研究，典型 的研究项目和成果有： 1 目前，美国国防部高级研究计划局( d a r p a ) 的敏捷制造网络研究予项目正 致力于制造系统国家信息基础结构的开发。在该基础结构中，制造企业能共事资源、 功能性和应用服务，并通过自动多代理来执行实际制造和制造商务活动中的各种角 色通过基于知识的系统来评估产品的可制造性以满足生产调度和规划的要求m 1 。 2 1 9 9 6 年5 月美国通用电器公司发表了“计算机辅助制造网络”( c o m p u t e r - a i d e dm a n u f a c t u r i n gn e t w o r k ，c a m n e t ) 的结构和应用，其目标是基于万维网提供多 种制造服务，使得成员企业能够通过万维网快速联结和相互传递、共享分布的制造消 息 3 2 】。 3 华中科技大学硕士学位论文 3 德。马丁航天公司的“制造系统的敏捷基础设施网络”( a i m s n e t ) 主要利用 国际互联网支持和管理敏捷企业供应链i 3 3 1 。 4 。美国的n m p f n a t i o n a li n d u s t r i a li n f o r m a t i o ni n f r a s t r u c t u r ep r o t o c o l s1 计划，致力 于构建虚拟企业的信息体系结构，其参与者包括信息技术提供商，工业制造企业，学 术研究部门及标准化组织。 5 欧盟的i n c o - d cm y s s i v e 计划【3 5 】。 6 2 0 0 0 年6 月由s o m a t i cl a bl t d 和i c c s - b a s ( i n s t i t u t eo fc o m p u t e ra n d c o m m u n i c a t i o ns c i e n c e s b u l g a r i a na c a d e m yo fs c i e n c e ) 合作完成的虚拟企业项目，构 建了信息控制系统以用于地域上分布的企业的远程管理和运作【狮。 7 华中科技大学在多项国家自然科学基金、重大项目的资助下，对基于a g e n t 的分布式网络化智能制造系统、网络化敏捷制造单元的基础理论与实现技术以及基于 c o r b a 的制造信息和知识共享技术进行深入研究，取得了一些积极成果p 7 3 1 3 8 1 。 8 美国n s f 和d a r p a 资助了开发基于w e b 的“度身订做”e s i g n t o m a n u f a c t u r e ) 快速原型系统的项目c y b e r c u t 3 9 3 。其侧重点在于产品、过程设计及加工 制造中的协同工作和信息集成与知识共享。 9 加拿大n s e r c 资助了面向分布式网络制造的新一代企业资源系统n e t m a n 的 研究与开发 删。其重点在于终端产品厂家与其伙伴之间基于产品结构的供应链整合。 1 0 欧共体e s p r i t 计划资助了涉及多家企业、由来自挪威、丹麦、意大利和德 国的研究人员参与的b i d p r e 项目f 4 1 】唧，其耳的在于开发面向标书准备的跨部门并行 化工作平台。 1 3 2 分布式环境中任务分配方案研究状况 动态企业联盟中的生产活动通常采用分布式管理模式，其任务分配问题也就是分 布式环境中的生产调度问题。在具有很多不可预测因素的开放环境里实现动态的计划 与调度作业，有很多困难i , 珏- 4 s 。近年来，众多学者在这一领域进行了研究并取得一些 积极成果： 1 s h o w 4 6 1 于1 9 8 8 年将招标投标方法用于动态任务分配。 2 u n 和s o l b e r g 4 7 1 ；e e1 9 9 2 年提出一个用谈判方法去协调计算机控制制造系统中 的工作流的分层框架，该框架建立在一个具有多目标的市场模型基础之上，在系统中 的每个a g e n t 都通过谈判而获得其他a g e n t 的服务。 3 b u r k e 和p r o s s e 一髂】于1 9 9 4 年提出个分布式的异步调度器( d i s t r i b u t e d a s y n c h r o n o u ss c h e d u l e r ，d a s l ，d a s 按a g e n t 的三种类型被组织成三个等级的层 次：战略a g e n t 、战术a g e n t 和操作a g e n t ，调度问题则在相应层次上被分解和分发。 华中科技大学硕士学位论文 4 ，1 9 9 5 年，s a a d l 4 9 等提出一个生产预约方法，该方法通过采用基于改进合同网 协议的招标般标机制产生生产计划和调度。 5 p a r u n a k l 5 0 j 等人于1 9 9 7 年提出，将制造资源( 如人、机器和工件等) 封装成 自主a g e n t ，每个a g e n t 能与在工厂内和工厂外的其他a g e n t 进行互操作，而且采用 一种混合的启发式调度技术一一向前向后调度、仿真调度和智能调度。 6 韩国的k a ph a w n m 【5 1 j 等人在1 9 9 7 年将生产系统的组成部分( 如任务、机 器等) 看作是能独立活动以获取利益实体，建立基于价格机制的标书构造和价格修订 机制，通过在各a g e n t 问的谈判实现任务分配。 这些研究项目针对分布式制造环境中的任务分配问题都提出了各自的解决方案， 试图在各个层次上解决这个问题。但是大部分研究仍然处在模型和算法研究阶段，能 够应用于专有信息平台的任务分配原型系统的成果仍然少见。 1 4 本文的主要研究内容 本论文的主要研究内容如下： 1 任务分配系统的设计：在分析虚拟制造组织的概念、构造及运行环境的基础 上确定其子系统一任务分配系统的功能要求；根据功能要求选择应用技术，并进 行系统设计，模块划分，接口定义。 2 任务分配协议、策略和算法研究：根据功能要求及系统的运行环境，确定任 务分配机制，制定任务分配过程中各方需遵循的协议，研究涉及到的策略和算 法。 3 功能模块的详细设计：根据系统设计中划分的模块及定义的接口，以及制定 的协议、策略等，详细设计每个模块的内部处理流程，实现系统功能。 4 数据处理的研究：分析系统中的数据流，定义数据交换格式及数据存储方 式，按照设计实现数据交换与存储功能。 5 人机界面的设计：作为人机交互系统，需分析人在系统中的作用，设计友好 的人机界面，将人的因素很好的纳入到系统中来。 本论文共分八章，各章节层次关系如图1 - 1 所示： 5 华中科技大学硕士学位论文 第一章绪论 ( 第二章虚拟制造组织一： l ( 第三章面向的任务