1. 引言
随着计算机科学技术的飞速发展,利用互联网大量资源的网格计算将成为解决规模庞大、复杂问题的关键。要高效的实现网格的计算,许多复杂的网络需要处理,其中资源调度问题是网格优化中需要解决的一个关键问题 [1] 。一个高效的资源调度模型和调度算法,可以有效的利用网络的处理能力,提高网络算法程序的性能,以更好的利用网络资源 [2] 。各个地区资源的配置已成为各个行业、各个部门必不可少的调配方式。资源配置在电力部门,能源供给部门,水资源部门等应用广泛 [3] [4] [5] 。各个地区资源的合理配备为经济发展、资源共享提供了有力支撑和保障。
综合资源规划是将各种形式的资源,进行合理规划 [6] [7] [8] 。资源供给方通过各个机构的转化,对资源进行生产;资源需求方则表示本地区自己生产的资源不能自给自足,需要其他地区的补给。当本地区的资源不能满足自身的需求时,即供小于求时,此时需要将其他地区剩余的资源调配给本地区;相反,当本地区的资源在满足自身需求的条件下,还有剩余,即供大于求时,这时需要将本地区的多余的资源调配给其它地区;当供方资源恰好满足需求时,供需关系达到最优。事实上,资源供需的最优化平衡是很难实现的,因为资源供需关系具有很强的波动性,造成波动性的原因诸多,比如当地的政策因素、环境因素、经济因素、气候因素等。
本文研究的资源供需关系是指各个地区的供应与需求的关系,不涉及在资源调配过程中有关经济、运输费等市场因素的影响,单纯从资源的供应和需求的角度考虑问题。本文研究的供需关系的优化调度算法与运输问题是有差别的。运输问题 [9] [10] 是指如何将物资运往指定地点,并且实现运输成本最小。资源供需关系的优化一方面需要满足本地的资源需求,将多余的资源进行调配到其它地区,另一方面,本地区所生产的资源不能满足自己的需要时,由其它需求过剩的地区进行调配。通过各个地区资源的供给与需求的优化结合,可以实现资源浪费最小的资源调配方式。
本文重点解决的问题的具体描述如下:假设有m个地区,其中第i个地区的生产量和消费量分别为
和
,
,并且
不一定等于
。事实上,
是一种平凡情形,不予考虑。如何有效地分配
的值,才能使得生产地的资源既能满足自身的需求,又能合理的分配给其他需要的地区。本文对于供需关系的资源分配问题,建立了多目标规划模型,并给出了资源分配的一种求解算法,最后,给出了供需关系的资源调度的2个实例。
2. 优化调度算法
2.1. 优化调度模型建立
设物资生产地和消费地分别为
,
为第i个部门物资的生产量,
为第j个部门物资的消费量,
表示第i个能源生产地向第j个能源需求地所分配的物资。根据所分配的物资的损耗最低为标准,本文初步建立如下的资源优化数学模型:
目标函数为:
(1)
约束条件为:
表达式(1)括号中的含义是:其他地方调配到第j地方的总量
与其需求量之差,目标函数表示的
意思是这种差的平方要达到最小,即分配物资的损耗最低。针对目标问题(1),我们下面给出了具体的算法步骤。
2.2. 优化调度模型的算法步骤
设m个生产部门物资的产量分别为
,m个物资消费部门的需求量分别为
。为了使物资在各个部门得到的合理分配,本文设立了优化调度模型的算法,其算法具体步骤如下:
步骤1:判断
是否等于
,
,如果
,则不需要考虑调配(该地区能够自给自足),若
,则表示该地区要么生产小于需求,要么生产大于需求。于是进入步骤2。
步骤2:分别用符号bigger记录
的个数,用smaller记录
的个数。事实上,只有在
的时候才需要对相应地区的资源进行调配,因为
时,bigger = 0,且smaller = 0,不需调配。
步骤3:确定bigger和smaller值的大小关系,取两者的较小者作为下一步需要调配的具体个数。
若
,则需要接收调配的地方小于供给的地方数,因此以接收地为出发点考虑调配。
若
,则能够供给的地方数小于需求的地方数,因此以供给地方数为出发点考虑调配。
步骤4:对资源进行具体分配,其中分配的原则是以供给地和对应的需求地两者的最小值为标准。比如
若
,则表示将供给地的3给需求地。
若
,则表示将供给地的1给需求地。
进一步,对生产地和消费地的数量进行更新。
对供应地方而言,基数是等于原产量减去所分配的数量。
对需求地方而言,其需求等于原需求数量减去得到的分配数量。
并将上述的变化情况记录在分配矩阵里面。
步骤5:重复步骤1到步骤4的过程,直到分配矩阵不再变化为止。
其算法流程图如图1所示。
3. 算法应用
3.1. 算例1
现设有
,6个地区,用MATLAB随机产生一组资源产量
和一组资源需求量为
,现需对6个地区的物资进行分配,得出最终的分配矩阵。
Figure 1. Flow chart of optimization model algorithm
图1. 优化模型算法流程图
计算分配矩阵的步骤如下:
现已知这6个地区的资源产量为
,资源需求量为
。
步骤1:判断资源产量
是否等于资源消费量
,
。由已知可知,这6个地区的资源产量与需求量显然不均衡,故需进行调配。
步骤2:计算资源产量
与资源消费量
的差值,可得
。进一步,分别用bigger记录资源产量大于消费的地区数为3,smaller记录资源消费量大于产量的地区数为3。
步骤3:根据bigger和smaller的大小,确定需要调配的个数为3个。
步骤4:以供给地和需求地两者的最小者对资源进行分配,
首先,对
和
进行调整,将供给地的资源数3给需求地。其次,对
和
进行调整,将供给地的资源数7给需求地,供给地所剩资源为1。最后
和
进行调整,将供给地的资源数2给需求地。
步骤5:更新可得
,重复步骤3的过程,最后可得分配矩阵为:
3.2. 算例2
能源生产和使用是任何经济结构的主要部分。在美国,能源政策的许多方面分散到国家层面。此外,不同国家的不同地区和行业也影响能源使用和生产。1970年,美国西部的12个州组成了西部州际能源协定(WIEC),其任务重点是促进这些州在发展和管理核能技术方面的合作。州际契约是两个或两个以上的州之间的合同安排,在这两个州之间,如何进行资源的调配就显得尤为重要。
沿着美国与墨西哥的边界,有四个州——加利福尼亚(CA)、亚利桑那州(AZ)、新墨西哥州(NM)和德克萨斯州(TX)——希望形成一个现实的新能源契约,重点是增加清洁能源和可再生能源的使用。本算例基于本文提出的优化分配算法对以上4个州的化石燃料、可再生能源、总能源进行和理调配。
下面以2009年,加利福尼亚(CA)、亚利桑那州(AZ)、新墨西哥州(NM)和德克萨斯州(TX)的能源生产与使用情况 [11] 如表1所示。
最后,根据优化调度算法,求得4个州的能源调度结果如表2所示。
Table 1. Table of energy production and consumption
表1. 能源生产与消费情况表
Table 2. Energy distribution allocation table
表2. 能源调度分配表
4. 结论
本文针对资源配置问题,提出了一种基于供需关系的资源优化算法。本文建立了多目标规划模型,并给出了资源分配的求解算法步骤,并给出了实例分析。结果表明,本文给出的优化调度算法能较好的对各个地区的资源进行合理分配,从而可作为政府部门进行资源调配做出决策的依据。
基金项目
西南科技大学大学生创新基金项目:“灰色神经网络组合模型在汽车保有量中的预测研究”(项目编号:cx18-061),主持人:夏杰。
NOTES
*通讯作者。