基于非合作博弈的生产调度建模与算法研究

《基于非合作博弈的生产调度建模与算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于非合作博弈的生产调度建模与算法研究摘要生产调度是对生产制造中机器资源进行合理的分配，由于其重要的实用价值及数学上的难处理性(NP．hard)，长期受到制造领域和学术界的高度重视．本文在现有异构目标调度问题基础上，提出并研究生产调度中的一般异构目标调度(GeneralHeterogeneousObjectivesScheduling，GHOS)问题，即：多个具有不同性能指标的客户竞争有限生产资源，同时，生产方对于其生产资源的利用也有独立全局要求的调度问题。对于这一问题，目前已有的相关研究十分有限，在建模、算法设计以及应用方面都留有很大的研究空间．GHOS问题本质上是一个多人多目标优化问题，

2、传统调度以生产方为主体，很难兼顾客户不同的异构目标，本文采用非合作博弈理论(NoncooperativeGame，NG)研究GHOS问题。首先结合问题的特点和博弈理论在其它领域的应用，在NG基础上，建立了分别描述客户与生产方要求的工件层模型和机器层模型，定义了Nash均衡(NashEquilibrium，NE)调度的概念。然后在借鉴博弈应用研究思路的基础上，展开了本文对GHOS问题的分析和求解研究．在工件层模型中，讨论了NE调度集合的相关理论问题，给出了一种求解NE调度集合的算法。并且将该算法推广后，成功应用于传统单机调度问题的求解。然后，进一步考虑机器层模型，给出了分别遵循知识论和进化论两

3、种NE求解观点的算法。归纳起来，本论文主要做了以下七个方面的研究工作：·剖析了博弈理论蕴涵的方法论思想和基本原理，提炼了冲突、优化和均衡作为博弈应用的三条基本原则。进而回顾并分析了博弈理论在控制、规划、调度问题中的应用现状，展现了三条基本原则在应用中的体现，并指出博弈应用研究的要点在于建模、分析与求解。由此，阐明了本论文研究的动机、可行性和未来的研究思路。·在现有调度研究基础上，结合现代制造业面临的问题，提出对GHOS问题进行研究，并采用NG概念给出了GHOS问题的一般描述框架，建立了工件层模型和机器层模型，其中，工件层模型中反映了客户的优化目标，客户的竞争结果采用NE调度概念予以描述，机器

4、层模型则考虑了生产方的目标。论文详细分析了两层模型与其它各类调度问题的关系，指出了本文建模方式所具有的一般性。●以客户分别具有正规型和任意性能指标的动态同速并行机调度为例，分析了在四种不同全局性能指标衡量下的工件层NE调度集合的性能界。并将结果推广到静态和单机情况下，指出了个体和全局优化之间存在的冲突。·设计了描述冲突工件集合的冲突窗口，并以此作为子问题，设计了一种在单机下求解工件层NE调度集合的滚动算法，证明了算法的有效性。·在全局目标下，设计了基于冲突窗口的子问题最优调度，由此发展出一种用于求解最小化完工时间之和的单机调度问题的滚动时域算法。通过理论分析和算例验证，说明了该算法的优越性。

5、·为探索如何解决个体优化与全局优化之间的关系，以动态同速并行机下，客户具有正规．型性能指标的GHOS为研究对象，借鉴Lagrange算法，设计了一种两层迭代算法，称之为类市场法。在工件层，每个客户按自身目标最优地竞争相应的机器资源；机器层则根据客户的竞争情况，按照设计好的博弈框架，调整机器资源价格，引导工件层竞争结果趋向于全局优化。仿真表明，该算法能很好地平衡个体和全局优化的要求。·对于Job-shop环境下，客户可能具有非正规型性能指标的GHOS问题，设计了一种并行遗传算法模拟客户之间的相互竞争和学习行为。算法中，每个子群代表一个独立客户的策略选择，通过各个子群的协同进化，得到一组均衡的结

6、果。为了提高算法的搜索能力和解的质量，在解码中应用了局部搜索(10calsearch)和最优化技术。仿真计算的例子说明了该方法的有效性。关键词：生产调度，非合作博弈，Nash均衡，滚动时域方法，Lagrange松弛，遗传算法2StudyonmodelandalgorithmsofproductionschedulingbasedonnoncooperativegameAbstractProductionschedulingistoreasonablyallocatemachineresourcesinmanufacturing．Duetoitsimportantpracticalvaluea

7、ndNP-hardcharacteristic，itdrawshJIghattentionofmanufacturersandacademe．BasedonthecurrentHeterogeneousObjectivesSchedulingresearch，thisdissertationproposesandstudiestheGeneralHeterogeneousObjectivesSchedulin