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

来源 :上海交通大学 | 被引量 : 0次 | 上传用户:beibei114
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
生产调度是对生产制造中机器资源进行合理的分配,由于其重要的实用价值及数学上的难处理性(NP-hard),长期受到制造领域和学术界的高度重视.本文在现有异构目标调度问题基础上,提出并研究生产调度中的一般异构目标调度(General Heterogeneous ObjeetivesScheduling,GHOS)问题,即:多个具有不同性能指标的客户竞争有限生产资源,同时,生产方对于其生产资源的利用也有独立全局要求的调度问题.对于这一问题,目前已有的相关研究十分有限,在建模、算法设计以及应用方面都留有很大的研究空间. GHOS问题本质上是一个多人多目标优化问题,传统调度以生产方为主体,很难兼顾客户不同的异构目标,本文采用非合作博弈理论(Noncooperative Game,NG)研究GHOS问题.首先结合问题的特点和博弈理论在其它领域的应用,在NG基础上,建立了分别描述客户与生产方要求的工件层模型和机器层模型,定义了Nash均衡(NashEquilibrium,NE)调度的概念.然后在借鉴博弈应用研究思路的基础上,展开了本文对GHOS问题的分析和求解研究.在工件层模型中,讨论了NE调度集合的相关理论问题,给出了一种求解NE调度集合的算法.并且将该算法推广后,成功应用于传统单机调度问题的求解.然后,进一步考虑机器层模型,给出了分别遵循知识论和进化论两种NE求解观点的算法.归纳起来,本论文主要做了以下七个方面的研究工作: ●剖析了博弈理论蕴涵的方法论思想和基本原理,提炼了冲突、优化和均衡作为博弈应用的三条基本原则.进而回顾并分析了博弈理论在控制、规划、调度问题中的应用现状,展现了三条基本原则在应用中的体现,并指出博弈应用研究的要点在于建模、分析与求解.由此,阐明了本论文研究的动机、可行性和未来的研究思路. ●在现有调度研究基础上,结合现代制造业面临的问题,提出对GHOS问题进行研究,并采用NG概念给出了GHOS问题的一般描述框架,建立了工件层模型和机器层模型,其中,工件层模型中反映了客户的优化目标,客户的竞争结果采用NE调度概念予以描述,机器层模型则考虑了生产方的目标.论文详细分析了两层模型与其它各类调度问题的关系,指出了本文建模方式所具有的一般性. ●以客户分别具有正规型和任意性能指标的动态同速并行机调度为例,分析了在四种不同全局性能指标衡量下的工件层NE调度集合的性能界.并将结果推广到静态和单机情况下,指出了个体和全局优化之间存在的冲突. ●设计了描述冲突工件集合的冲突窗口,并以此作为子问题,设计了一种在单机下求·在全局目标下,设计了基于冲突窗口的子问题最优调度,由此发展出一种用于求解最小化完工时间之和的单机调度问题的滚动时域算法.通过理论分析和算例验证,说明了该算法的优越性.·为探索如何解决个体优化与全局优化之间的关系,以动态同速并行机下,客户具有正规型性能指标的GHOS为研究对象,借鉴Lagrange算法,设计了一种两层迭代算法,称之为类市场法.在工件层,每个客户按自身目标最优地竞争相应的机器资源;机器层则根据客户的竞争情况,按照设计好的博弈框架,调整机器资源价格,引导工件层竞争结果趋向于全局优化.仿真表明,该算法能很好地平衡个体和全局优化的要求. ●对于Job-shop环境下,客户可能具有非正规型性能指标的GHOS问题,设计了一种并行遗传算法模拟客户之间的相互竞争和学习行为.算法中,每个子群代表一个独立客户的策略选择,通过各个子群的协同进化,得到一组均衡的结果.为了提高算法的搜索能力和解的质量,在解码中应用了局部搜索(local search)和最优化技术.仿真计算的例子说明了该方法的有效性.
其他文献
视觉跟踪定位技术是船舶跟踪与三维定位技术中的一个分支,该技术常采用摄像机作为图像采集模块,将实时的位置信息反馈到跟踪定位系统中进行计算处理。但由于轮船发动机以及舰
生物按照细胞类型分类有真核生物与原核生物,本文主要从真核生物与原核生物两个角度研究生物信息领域的意义所在。  随着高通量测序技术的发展,大量物种被测序并装配获得基因
采用自动配置的无线传感器网络(Wireless Sensor Networks, WSN),是近几年全球范围的新技术研究热点之一。它集成了无线通信技术、传感器技术、微机电系统技术和分布式信息处
随着材料科学与技术的发展日新月异,新材料、新技术、新工艺和新方法层出不穷,材料信息的数据量和复杂性也大大提高。航天先进功能材料数据管理系统将各种涉及材料方面的数据(
在模式分类问题中普遍存在着数据集不平衡的现象,即不同类的样本在数量和分布上存在较大差异。非平衡数据的分类具有着重要的现实意义,因为少数类样本通常伴随着高昂的错分代价
随着计算机技术和通信技术的飞速发展,传感器技术的发展也进入了网络化阶段,网络传感器技术的发展对提高传感器的数据处理和数据传输能力具有十分重要的意义。而我国煤矿现用
具有干扰的非线性系统的分析与综合一直是控制理论的研究热点。 本文基于Lyapunov稳定性,以DOBC理论和H控制理论为主要方法,以线性矩阵不等式 (LMI)为主要数学工具,讨论了含