论文部分内容阅读
资源是一种自然存在物或能够给人类带来财富的物质、能量和信息的总称。资源优化是指决策者按相应的分配方案,对系统所属资源进行具体分配,从而满足系统收益最大化或其他既定目标。提高资源利用效率,优化资源配置已经成为相关学术研究中重点关注的问题。作为战略规划的核心任务,资源优化广泛存在于生产系统调度,项目调度,人力资源管理和云计算资源调度等系统中。资源的众多存在形式使资源优化不存在统一的模式。本文主要研究了启发式算法在不同类型资源优化问题的应用和求解方法,包括连续生产资源(如水,电力等),离散资源(如人力,设备等)和QoS资源(如CPU占用,延迟时间等)。本文的主要贡献包括:(1)研究了单机批调度连续资源优化问题与装箱问题之间的转化关系并提出相应的启发式算法。寻找资源优化问题和其他优化问题之间的转化关系不仅能为问题分析提供依据,而且能使用对应的求解算法进行资源优化。因此资源优化问题与其他优化问题的转化关系亟待研究。我们关注如何将批生产调度中的连续资源优化问题转化为装箱问题,从而利用装箱问题的相关算法求解该资源优化问题。(2)研究了一般资源函数在批调度连续资源优化问题上的应用并提出了相应的近似求解算法。结合上一部分研究工作中批调度连续资源优化背景,我们进一步研究了考虑一般资源函数的单机批调度连续资源优化问题。一般资源函数能够准确反应批调度环境下不同工件的差异性特征。相关研究指出,传统资源函数(如线性和凸递减资源函数)的相关结论和算法不能用于求解考虑一般资源函数的资源优化问题。我们采用边际分析方法分析了考虑一般资源函数的批调度资源优化问题的最优化条件,并以此提出了相应的启发式算法。(3)研究了考虑工件截止时间的离散资源优化问题的复杂度并提出了一个分布估计算法。与上述研究工作不同,我们考虑了单机生产加工的离散资源优化问题。由于离散资源和连续资源物理性质不同,上述相关资源优化方法和结论不能应用于此类问题。根据相关文献研究,将离散资源分配引入传统调度问题可能会改变问题的复杂度。因此,我们首先通过将离散资源优化问题转化为二划分问题论证了该离散资源优化问题的复杂度。由于二划分问题是NP-难问题,并且该转化过程可以在多项式时间内完成,因此该离散资源优化问题也是NP-难问题。为了求解该问题,我们基于一个近似的玻尔兹曼分布提出一个分布估计算法。我们提出了该分布的概率模型,并通过实验论证提供了学习该概率模型的简化方法。实验论证显示该分布估计算法在离散资源优化性能方面优于对比算法。(4)研究了QoS资源互补性的web服务组合问题并提出一个启发式求解框架。QoS资源优化问题存在于web服务组合应用中。不同于连续资源和离散资源,QoS资源是一个集合的概念并且部分QoS属性不具有可加性性质,因此本章研究问题不能采用求解离散资源和连续资源优化算法进行求解。近年来,有研究者指出在web服务组合问题中候选服务的QoS资源具有互补性,并且该互补性会显著影响web服务组合的解的质量。我们的研究主要关注实现相同功能的不同候选服务之间的互补性,并定义其为内部互补性。我们从现实实际背景出发,分析了QoS内部互补性如何影响候选服务和整个web服务组合解。进而,我们根据相应的假设提出了该问题的数学模型并分析了该问题的复杂度:首先,我们通过将该QoS资源优化问题的一个特例转化为多维多选择背包问题论证了该问题是NP-难问题:其次,我们证明了在一般情况下将该问题转化为多维多选择背包问题可能需要指数级时间,从而说明不能通过与背包问题的转化求解考虑QoS内部互补性的web服务组合问题。我们提出一个迭代式的求解框架。在每一次迭代中,该服务组合解的性能是通过求解一个分离背包问题实现的。根据该框架,我们提出两个启发式算法,并且在实验论证中说明它们在时间性能和求解精度要优于相应对比算法。上述实验进一步也说明了本文提出的迭代式求解框架的有效性。