基于序贯时空博弈的动态邻接资源调度研究

邻接资源调度是一类特殊的资源约束调度，特点是系统资源必须以邻接模式分配，即离散资源必须相邻排列，连续资源必须构成不可重叠的单连通区域，常见于以多处理器阵列或封闭空间为服务资源的调度领域。在这一模式下，资源分配过程类似于刚性物体布局，构成了一种复杂的非线性组合资源约束，并与任务时序安排紧密关联，形成时空耦合效应。由于目前缺乏完善的时空耦合效应系统演化理论，以及有效的时序安排和资源分配同步实时优化算法，动态邻接资源调度成为理论研究与实际应用中的难点问题。本项目依据约束优化的拉格朗日松弛方法与零和博弈的相关性理论，提出动态邻接资源调度的博弈论分析框架- - 序贯时空博弈模型，力求通过以时序优化、布局优化和邻接约束惩罚为主体的3方双层博弈结构，深入阐释时空耦合效应下的动态邻接资源调度优化决策机制和系统演化规律，并结合具有时空随机特性的排队系统模型，设计基于协同博弈策略学习的优化决策算法和系统仿真平台。

以一维空间资源的动态邻接资源调度为主要背景，构建了动态邻接资源调度系统的基本仿真模型，细分了动态调度策略的组成方式，将其分解为“资源分配策略”、“队列排序策略”、“任务指派策略”、“服务器运行策略”4种子策略的组合。以计算机仿真为主要手段，通过邻接资源分配约束下排队系统临界稳定状态下的服务强度测算研究了系统稳态下的平均服务资源分配效率，并通过模拟极端饱和任务流情况下足够长时间内服务器资源占用效率研究了资源利用效率的平均指标，发现在给定任务尺寸分布区间后，基于先到先服务（FCFS）策略的开放式邻接资源调度过程的临界服务强度特征近似于一个缩减了服务资源尺寸后的常规多服务台排队系统，并且其缩减比例等于饱和任务流情况下的服务器资源稳态利用效率。基于上述定性结论，进一步在仿真实验的基础上，通过数据统计分析探讨了邻接资源调度中的时空耦合规律，主要研究了邻接资源分配约束下，服务器可用容量分布状态对动态调度目标优化的价值，利用matlab符号运算工具箱得到了任意尺寸分布区间下和服务资源容量与服务效率相关性函数生成算法，揭示出服务效率随服务资源容量增加而振荡性增加的非线性特征。根据这一性质提出了基于任务等待时间与服务器填充效率之间竞争性博弈的动态调度策略优化框架，并采用区间图（Interval Graph）模型提出了任务个体在时空资源上的竞争性博弈统一框架。理论应用方面，在前期研究基础上设计了“基于多Agent的三峡工程通航调度仿真平台”，并针对三峡船闸通航调度的具体问题研究了滚动时域框架下的三峡—葛洲坝联合通航调度模型和算法。结合课题在资源优化分配方面的研究成果，以输电网络中的动态监测和空间资源优化布局问题为背景，在动态资源优化、信息融合、智能算法等方面进行了一系列拓展研究，构建了基于进化算法和模糊Petri网络的绝缘子运行状态诊断模型，以及基于图论模型研究了PMU（向量监测单元）在电网络上的最优分配问题，提出利用电网拓扑结构和最小生成树算法改进遗传算法的优化方法。