基于多Agent的协作运营调度方法研究

河北工业大学硕士学位论文基于多Agent的协作运营调度方法研究姓名：文艳申请学位级别：硕士专业：管理科学与工程指导教师：康凯20081201河北工业大学硕士学位论文基于多Agent的协作运营调度方法研究摘要随着市场竞争的全球化，制造业面临着更为激烈的全球化市场竞争，企业之间的协作变得越来越重要。出现了以全球化分布式协作制造为手段，强调知识经济和大批量定制生产的协作制造模式。协作运营网络是根据协作制造哲理组织的、以满足顾客需求为导向的价值增值网络。协作运营调度问题是协作运营网络的核心环节，然而由于现实中各协作实体具有相对独立的经济利益和复杂的协作与竞争关系，这个问题十分复杂。本文构建了基于多Agent的协作运营调度系统，根据调度过程，将协作运营调度分为预测调度和反应调度两个阶段。在预测调度优化阶段，构建了数学模型，并引入蚁群算法进行求解。并通过仿真验证了调度模型的正确性，以及验证了算法的可收敛性和可调整性。在反应调度阶段，协作实体通过一个两阶段的决策过程解决延迟事件，分别为模糊决策和补偿协商过程，并用一个例子说明决策过程。关键词：协作运营，调度，多Agent，蚁群算法河北工业大学硕士学位论文RESEARCHONMULTI-AGENTBASEDCOLLABORATIVEOPERATIONSCHEDULINGMETHODABSTRACTWiththedevelopmentoftheglobalizationofmarketcompetition,themanufacturingindustryfacedwithadrasticglobalmarketcompetition.Thecollaborationamongthecompaniesisbecomingincreasinglyimportant.Collaborativemanufacturingisanewmanufacturingmodel,andthedistanceofcollaborativeentityiscross-enterpriseorganization,trans-cityortransnational.Thecoollaborativeoperationnetworkisthevalueincrementnetworkwhichsetsupaccordingtothecollaborativemanufacturingphilosophy.Coollaborativeoperationschedulingisalwaysthekeypartincoollaborativeoperationnetwork.Becauseeachcoollaborativeentityhastherelativelyindependenteconomicinterestandthecomplexcooperationrelations,thisquestionisverycomplex.Thisthesishasconstructedthemulti-agentbasedcoollaborativeoperationschedulingsystem.Accordingtoschedulingprocess,thecoollaborativeoperationschedulingdividesintotwostages:predictiveschedulingandreactivescheduling.Inthephaseofpredictivescheduling,establishthemathematicalmodel,antcolonyalgorithmisapplied.Exactnessofoptimizationmodelandcharactersofconvergenceandrectificationofthealgorithmultimatelygetsvalidatedthroughasimulation.Inthephaseofreactivescheduling,thecollaborativeentitysolvestheproblemthroughatwo-stagedecision-makingprocess:thefuzzydecision-makingprocessandthecompensatorynegotiationprocess.Andtakeacasetoexplainthedecision-makingprocess.KEYWORDS:CollaborativeOperation，Scheduling，Multi-Agent，AntColonyAlgorithm河北工业大学硕士学位论文1第一章绪论§1-1问题的提出与主要研究的问题进入21世纪以来，制造业发展环境出现了前所未有的变化。市场的复杂性和不确定性，用户需求的多样性，产品生命周期的短暂性，已成为企业生存与发展面临的重要问题。出现了以全球化分布式协作制造为手段，强调知识经济和大批量定制生产的协作制造模式。协作制造是组织、运营、管理满足顾客需求价值增值网络的一种制造哲理。本文把根据协作制造哲理组织的、以满足顾客需求为导向的价值增值网络称为协作运营网络。由于现实中各协作实体具有相对独立的经济利益和复杂的协作与竞争关系，因而任务在各成员之间的合理分配至关重要，这是协作运营调度过程所应解决的关键问题之一。从这个角度讲，协作运营调度问题是协作运营网络管理的核心问题之一，然而该问题非常复杂。可以说，协作制造环境下的调度优化过程是一个典型的随机、动态过程。要提高调度效率必须合理处理该运作过程中的随机性与动态性问题。协作运营调度的复杂性在于由协作实体自身偏好所引起的生产能力动态变化，这一点同传统的单个企业或车间作业调度[1]过程差异很大。生产调度研究面临着许多新问题，不仅仅只局限于单纯的企业内的生产调度了，而是进入了协作制造环境下的生产调度的时代。这迫切需要有新的调度方法和调度机制来解决。本文正是在这样的背景下，结合国内外现有研究成果，主要针对协作运营调度问题进行深入研究，并概括为下列三个问题：问题1：协作运营调度框架明确协作制造、协作运营网络和协作运营调度的概念，从调度过程角度，将协作运营调度分为协作运营预测调度和协作运营反应调度。建立基于多Agent的协作运营智能系统结构和协作运营调度框架，提出基于移动Agent的协调调度策略。问题2：协作运营预测调度模型和算法针对协作运营预测调度过程提出数学模型，引入了蚁群觅食的寻优机理（蚁群算法的寻优机理），设计特定算法及改进，提出了协作运营调度优化的蚁群寻优算法，并通过实验仿真验证模型和算法的有效性。问题3：协作运营反应调度的两阶段决策框架在制造执行过程中，不确定因素会引发各种突发事件，可能会导致协作单元的任务延迟，影响随后进行的任务，甚至使整个协作运营网络的任务失败。因此协作单元需要进行反应调度，提出一个协作单元Agent的两阶段决策过程框架，分别为模糊决策过程和补偿协商过程。§1-2研究思路与技术路线协作运营网络是任务驱动的，因此本文研究的协作运营调度贯穿协作运营网络整个生命周期。对基于多Agent的协作运营调度方法研究调度过程的各阶段提出不同的调度方法。图1.1是对本文研究思路与技术路线的简要描述。2图1.1论文的研究思路与技术路线Fig.1.1Anssertation协作制造是一种新型的制造模式，协作实体的空间距离可能是跨企业、跨城市甚至是跨国家的，其资营调度系统建模、任务优化调度、任务再调度等问题展开深入研究，进一步丰富协作运的角度将协作运营调度分为协作运营预测调度与协作¾和协作运营反应调度进行研究，分别提出模型及框架，并分别设计生产调度问题及研究现状Agent及多Agent系统协作运营调度问题界定基于多Agent的协作运营调度系统协作运营预测调度模型研究协作运营反应调度框架研究研究内容文献研究多Agent技术蚁群算法模糊决策补偿协商解决方法模拟仿真验证其有效性alysisprocessandtechnologyrouteofdi§1-3研究目的与研究意义源的分布、资源的层次、约束问题以及协作实体动态生产能力等特征必将影响到整个任务生产过程的资源调度。本文的研究目的是通过对协作运营调度方法的研究，提高协作运营网络和协作单元的综合收益水平。通过对协作运营理论和方法。本文的研究有如下意义：¾明确协作运营调度的概念，从调度过程运营反应调度。提出一个基于多Agent的协作运营智能系统结构，协作单元都是通过此系统互相协作。协作单元在订单驱动下建立基于Agent的协作运营调度系统。为协作运营调度的研究提出了新的思路。分别对协作运营预测调度了解决方法，为协作运营调度问题的解决提供了解决方案。河北工业大学硕士学位论文§1-4论文结构与主要内容3本文针对协作运营调度问题进行系统的研究，论文主要内容如下：究思路与技术路线，确定了本文gent和多Agent系统进行了简要总结和综述，为协了协作制造、协作运营网络、协作运营调度等相关概念，然后对协作架，然后针实验仿真验Fig.1eme第一章绪论：介绍本文的主要研究问题，阐明协作运营调度问题的研的研究目的与意义，提出本文的结构与主要内容。第二章相关文献综述：对生产调度问题研究现状、A作运营调度提供了理论基础。第三章相关概念界定：首先界定运营调度过程进行分析，将协作运营调度分为协作运营预测调度和协作运营反应调度。第四章基于多Agent的协作运营调度模型研究：首先提出基于多Agent的协作运营调度框对协作运营预测调度提出调度优化数学模型，昀后提出协作运营反应调度的决策框架。第五章协作运营调度解决方法研究：针对协作运营预测调度模型设计蚁群寻优算法。通过证模型和算法的有效性。介绍反应调度的两阶段决策过程，分别为模糊决策过程和补偿协商过程。第六章总结与展望：总结全文的研究内容，提出本文的研究不足和进一步的研究方向。本文的结构如图1.2所示。问题提出绪论理论回顾相关文献综述问题界定相关概念界定模型构建基于多Agent的协作运营调度模型研究图1.2论文结构.2Sturctureofthisth结论协作运营调度解决方法研究问题解决总结展望河北工业大学硕士学位论文4第二章相关文献综述§2-1生产调度问题及研究现状协作制造为制造企业增强核心竞争力提供了有利手段，然而在协作制造环境下，传统的独立的物理工厂/车间变成由多个异地分布、靠网络连接、并行工作的制造实体组成的协作运营网络，系统的不确定性、非预见性进一步增强，使得协作运营网络的管理与控制问题更加复杂。作为生产管理的核心内容和关键技术，生产调度问题是其中的主要难点之一。生产调度一直是制造系统的研究热点，也是理论研究中昀为困难的问题之一，已被证明是典型的NP问题。在当今制造系统日趋复杂的情况下，调度问题同时又是一个制造技术、自动化技术、系统工程与人工智能等多学科相互交织作用的综合问题。2-1-1生产调度问题概述生产调度着眼于解决制造系统内各种资源的合理安排，目的是提高劳动生产率和设备利用率，缩短生产周期，降低生产成本，优化计划安排，为计划的执行和控制提供指导。现代制造对新一代调度系统提出了新的要求，除了需要它具有稳定性、可靠性、可维护性等传统调度系统应有的特征外，还要具有可重构性、敏捷性和适应性等特征[2]。制造企业的竞争主要取决于产品的供货周期、质量和售后服务水平，而先进的生产管理是实现这一目标的一个重要手段。生产调度作为生产管理的核心内容和关键技术之一，是保证制造企业良性运转的关键性因素，因而，一直是智能制造、自动控制等领域的研究热点问题。随着市场竞争的日益激烈，制造业全球化、产品客户化对制造过程敏捷性和动态适应性要求的不断提高。在全球化制造趋势下，传统制造环境下的单一工厂生产，已经逐渐被多工厂生产所代替，此时的分布调度问题比照单工厂时要复杂得多。通常，分布调度问题涉及两方面的任务:（l）将制造任务分配到合适的工厂；（2）在每个工厂中进行生产调度。随着分布节点工厂