信息物理融合系统(Cyber-Physical System,简称CPS)是在云计算、物联网等基础上发展起来的下一代智能系统,是信息过程与物理过程深度融合的系统,蕴藏着巨大的潜在应用价值。资源分配是CPS资源管理技术的核心。CPS中包含大量通过高速网络相互联接的异构资源,不同资源的功能不同,能力也相异,给CPS的资源管理与分配带来了巨大挑战。区间任务通常指任务的开始时间和结束时间固定的任务,其对应的任务调度问题称为区间调度。在CPS的任务调度场景中,存在很多以时间区间形式为背景的调度问题,如高峰时间段内的交通流量监测与控制、防空预警中的目标跟踪等。这些以时间区间形式存在的任务无疑增加了系统资源分配的难度。此外,在CPS中,传感器等设备在获取数据的同时需要将数据传送至计算设备和存储设备,在这些数据经过分析处理后实时做出决策。这一特性使得CPS中的任务往往需要多种资源协同工作来完成,且不是顺序式可分解的。因此凭借灵活有效的资源分配技术实现CPS的高效稳定运行,成为CPS研究的关键技术之一。本文以CPS资源分配的性能需求为牵引,主要针对CPS中面向区间任务的资源分配问题展开研究,为促进CPS资源管理技术的发展提供理论基础。本文的主要贡献如下:(一)研究CPS资源分配体系架构与模型。基于CPS系统构成及任务处理过程提出了CPS资源分配的体系架构,统一资源的调用接口,为资源的高效分配提供支持,并探讨了CPS中资源及任务的描述方法。据此基于最优化理论提出了CPS资源分配问题的建模方法,给出了一般问题的表示形式。资源分配机制的优劣影响着以负载性能为指标的系统稳定性,因此面向CPS中的稳定性问题,提出了基于丢弃率的排队模型,给出了平均队长、平均等待时间等参数的数学表达,为系统的稳定性分析奠定了理论基础。(二)研究CPS中面向资源分配的稳定性分析方法。资源分配策略决定着系统的任务处理效率,影响着系统的负载性能,而负载性能则与系统稳定性密切相关。通过将任务输入作为随机过程(如泊松过程等),考虑在不同资源分配机制下任务输入对系统负载性能及稳定性的影响,建立分配机制与系统稳定性之间的关系。据此以资源利用率(近似)最优算法为例,将系统不同时刻的状态转移作为马尔科夫链,基于李雅普诺夫漂移理论分析系统的稳定状态,得出关于系统稳定空间的结论,并给出了理论证明。而后通过仿真实验评估了算法在不同任务输入条件下的资源利用率,验证了理论分析的正确性。(三)研究面向区间任务的CPS单类资源分配问题。探讨了在资源充足条件下,以最小化所需资源为优化目标描述了该问题的模型,并通过最大覆盖子集算法将时间约束条件表示为代数形式,进而得到模型的整数规划表示。在此基础上提出了求解该模型的近似求解方法GreedyBS、GreedyMR,并基于次模函数的相关性质探讨了算法在最优性上的表现及相关证明。在仿真实验中,通过与整数规划模型下的分支定界法的对比,评估了不同算法在最优性及运行时间上的性能表现,分析了相关参数对算法性能的影响,并探讨了系统在不同算法下的稳定性。(四)针对面向区间任务的CPS多类资源分配,研究了资源充足和资源有限两种条件下的分配问题。在资源充足条件下,通过对问题的深入分析,将其转化为单类资源下的分配问题,在降低复杂度的同时避免了重复性研究。在资源有限条件下,由于优化目标的变化,考虑了如下两种情况:A)任务价值与资源能力无关;B)任务价值与资源能力相关。通过分析和对比A和B情况下资源分配问题的异同,建立了问题的规划模型。由于此问题下的约束条件较为苛刻,为此提出了可行集判断算法用于验证任务子集的可行性。在此基础上提出了求解模型的GA算法和BnB算法。而后分别在A和B情况下通过与Greedy算法的实验对比验证了算法的有效性和性能表现,同时对不同场景下所采用的资源分配方法提出了建议,并简要分析了不同算法的稳定性。(五)探讨了CPS资源分配方法在区域防空预警系统中的应用。区域防空预警系统是典型的军事信息物理融合系统,本文以该系统中的资源分配问题为案例,在深入分析该系统中资源和任务特点的基础上,探讨了资源有限及资源充足条件下的分配模型,并在给定模拟数据的基础上使用本文所提出的算法对模型进行了求解和分析。综上,本文研究了运筹学中的一类分配问题,也称指派问题。资源分配问题存在于各行各业的实际应用中,且随着应用环境的变化,分配问题的优化目标、约束条件也会发生改变,随之带来的是解决方法的变化。CPS中的资源分配问题所面临的难点在于多类资源的协同分配,据此,本文从CPS的概念及特性出发,对CPS资源分配框架及模型、资源分配机制与系统稳定性的关系、单类资源分配和多类资源分配方法循序渐进地展开研究。值得一提的是,本文所探讨的部分理论及方法在相同或相似的环境下也可应用于其他领域,如云计算、物联网等。