ABSTRACT

Due to the complexity of resource allocation in each region, an optimal scheduling algorithm based on supply-demand relationship was proposed. The resource scheduling considered in this paper involves the supply and demand sides of each region, and solves resource optimization problems among regions. A multi-objective optimization is developed to search an optimal scheduling model, and an algorithm for solving optimal resource scheduling is given. Finally, two examples are given for verification analysis.

Keywords:Supply-Demand Relationship, Resource Optimization Scheduling, Goal Planning, Scheduling Algorithm

基于供需关系的优化调度算法及其应用

夏杰，吴文青^*，许海洋

西南科技大学理学院，四川 绵阳

收稿日期：2018年6月8日；录用日期：2018年6月22日；发布日期：2018年6月29日

摘 要

针对各个地区资源生产和消费的不协调，以及具体调配的复杂性，提出了一种基于供需关系的优化调度算法。本文考虑资源调度涉及各个地区的供给方和需求方，从理论上解决地区之间的资源优化问题。利用多目标优化建立了优化调度模型，并给出了求解资源优化调度的算法和具体操作步骤。最后，给出了2个实例进行验证分析。

关键词 :供需关系，资源优化调度，目标规划，调度算法

Copyright © 2018 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

随着计算机科学技术的飞速发展，利用互联网大量资源的网格计算将成为解决规模庞大、复杂问题的关键。要高效的实现网格的计算，许多复杂的网络需要处理，其中资源调度问题是网格优化中需要解决的一个关键问题 [1] 。一个高效的资源调度模型和调度算法，可以有效的利用网络的处理能力，提高网络算法程序的性能，以更好的利用网络资源 [2] 。各个地区资源的配置已成为各个行业、各个部门必不可少的调配方式。资源配置在电力部门，能源供给部门，水资源部门等应用广泛 [3] [4] [5] 。各个地区资源的合理配备为经济发展、资源共享提供了有力支撑和保障。

综合资源规划是将各种形式的资源，进行合理规划 [6] [7] [8] 。资源供给方通过各个机构的转化，对资源进行生产；资源需求方则表示本地区自己生产的资源不能自给自足，需要其他地区的补给。当本地区的资源不能满足自身的需求时，即供小于求时，此时需要将其他地区剩余的资源调配给本地区；相反，当本地区的资源在满足自身需求的条件下，还有剩余，即供大于求时，这时需要将本地区的多余的资源调配给其它地区；当供方资源恰好满足需求时，供需关系达到最优。事实上，资源供需的最优化平衡是很难实现的，因为资源供需关系具有很强的波动性，造成波动性的原因诸多，比如当地的政策因素、环境因素、经济因素、气候因素等。

本文研究的资源供需关系是指各个地区的供应与需求的关系，不涉及在资源调配过程中有关经济、运输费等市场因素的影响，单纯从资源的供应和需求的角度考虑问题。本文研究的供需关系的优化调度算法与运输问题是有差别的。运输问题 [9] [10] 是指如何将物资运往指定地点，并且实现运输成本最小。资源供需关系的优化一方面需要满足本地的资源需求，将多余的资源进行调配到其它地区，另一方面，本地区所生产的资源不能满足自己的需要时，由其它需求过剩的地区进行调配。通过各个地区资源的供给与需求的优化结合，可以实现资源浪费最小的资源调配方式。

本文重点解决的问题的具体描述如下：假设有m个地区，其中第i个地区的生产量和消费量分别为 $P_i$ 和 $C_i$ ， $i=1,2,\cdots ,m$ ，并且 $P_i$ 不一定等于 $C_i$ 。事实上， $P_i=C_i$ 是一种平凡情形，不予考虑。如何有效地分配 $P_i,C_i,\left(i=1,2,\cdots ,m\right)$ 的值，才能使得生产地的资源既能满足自身的需求，又能合理的分配给其他需要的地区。本文对于供需关系的资源分配问题，建立了多目标规划模型，并给出了资源分配的一种求解算法，最后，给出了供需关系的资源调度的2个实例。

2. 优化调度算法

2.1. 优化调度模型建立

设物资生产地和消费地分别为 $A_1,A_2,A_3,\cdots ,A_m$ ， $P_i\left(i=1,2,3,\cdots ,m\right)$ 为第i个部门物资的生产量， $C_j\left(j=1,2,3,\cdots ,m\right)$ 为第j个部门物资的消费量， $x_{ij}$ 表示第i个能源生产地向第j个能源需求地所分配的物资。根据所分配的物资的损耗最低为标准，本文初步建立如下的资源优化数学模型：

目标函数为：

$\min C={\displaystyle \sum _{j=1}^m{\left({\displaystyle \sum _{i=1}^m{x}_{ij}-C_j}\right)}^2}$ (1)

约束条件为：

$\{\begin{array}{l}{\displaystyle \sum _{j=1}^m{x}_{ij}}=P_i\\ x_{ij}\ge 0\end{array},i=1,2,3,\cdots ,m;j=1,2,3,\cdots ,m$

表达式(1)括号中的含义是：其他地方调配到第j地方的总量 ${\displaystyle \sum _{i=1}^m{x}_{ij}}$ 与其需求量之差，目标函数表示的

意思是这种差的平方要达到最小，即分配物资的损耗最低。针对目标问题(1)，我们下面给出了具体的算法步骤。

2.2. 优化调度模型的算法步骤

设m个生产部门物资的产量分别为 ${\left(P_1,P_2,P_3,\cdots ,P_m\right)}^{\text{T}}$ ，m个物资消费部门的需求量分别为 ${\left(C_1,C_2,C_3,\cdots ,C_m\right)}^{\text{T}}$ 。为了使物资在各个部门得到的合理分配，本文设立了优化调度模型的算法，其算法具体步骤如下：

步骤1：判断 $P_i$ 是否等于 $C_i$ ， $i=1,2,\cdots ,m$ ，如果 $P_i=C_i$ ，则不需要考虑调配(该地区能够自给自足)，若 $P_i\ne C_i$ ，则表示该地区要么生产小于需求，要么生产大于需求。于是进入步骤2。

步骤2：分别用符号bigger记录 $P_i>C_i$ 的个数，用smaller记录 $P_i<C_i$ 的个数。事实上，只有在 $P_i\ne C_i$ 的时候才需要对相应地区的资源进行调配，因为 $P_i=C_i$ 时，bigger = 0，且smaller = 0，不需调配。

步骤3：确定bigger和smaller值的大小关系，取两者的较小者作为下一步需要调配的具体个数。

Ÿ 若 $\text{bigger}>\text{smaller}$ ，则需要接收调配的地方小于供给的地方数，因此以接收地为出发点考虑调配。

Ÿ 若 $\text{smaller}>\text{bigger}$ ，则能够供给的地方数小于需求的地方数，因此以供给地方数为出发点考虑调配。

步骤4：对资源进行具体分配，其中分配的原则是以供给地和对应的需求地两者的最小值为标准。比如

若 $\text{bigger}\left(1\right)=6,\text{samller}\left(1\right)=-3$ ，则表示将供给地的3给需求地。

若 $\text{bigger}\left(1\right)=1,\text{samller}\left(1\right)=-2$ ，则表示将供给地的1给需求地。

进一步，对生产地和消费地的数量进行更新。

Ÿ 对供应地方而言，基数是等于原产量减去所分配的数量。

Ÿ 对需求地方而言，其需求等于原需求数量减去得到的分配数量。

并将上述的变化情况记录在分配矩阵里面。

步骤5：重复步骤1到步骤4的过程，直到分配矩阵不再变化为止。

其算法流程图如图1所示。

3. 算法应用

3.1. 算例1

现设有 $A_1,A_2,A_3,A_4,A_5,A_6$ ，6个地区，用MATLAB随机产生一组资源产量 $P=\left[10,8,23,21,9,20\right]$ 和一组资源需求量为 $C=\left[15,6,30,15,13,18\right]$ ，现需对6个地区的物资进行分配，得出最终的分配矩阵。

图1. 优化模型算法流程图

计算分配矩阵的步骤如下：

现已知这6个地区的资源产量为 $P=\left[10,8,23,21,9,20\right]$ ，资源需求量为 $C=\left[15,6,30,15,13,18\right]$ 。

步骤1：判断资源产量 $P_i$ 是否等于资源消费量 $C_i$ ， $i=1,2,\cdots ,6$ 。由已知可知，这6个地区的资源产量与需求量显然不均衡，故需进行调配。

步骤2：计算资源产量 $P_i$ 与资源消费量 $C_i$ 的差值，可得 $\text{value}=\left[-5,2,-7,8,-4,2\right]$ 。进一步，分别用bigger记录资源产量大于消费的地区数为3，smaller记录资源消费量大于产量的地区数为3。

步骤3：根据bigger和smaller的大小，确定需要调配的个数为3个。

步骤4：以供给地和需求地两者的最小者对资源进行分配，

$\begin{array}{l}\text{smaller}\left(1\right)=-5,\text{bigger}\left(1\right)=2,\\ \text{smaller}\left(2\right)=-7,\text{bigger}\left(2\right)=8,\\ \text{smaller}\left(3\right)=-4,\text{bigger}\left(3\right)=2\end{array}$

首先，对 $\text{smaller}\left(1\right)$ 和 $\text{bigger}\left(1\right)$ 进行调整，将供给地的资源数3给需求地。其次，对 $\text{smaller}\left(2\right)$ 和 $\text{bigger}\left(2\right)$ 进行调整，将供给地的资源数7给需求地，供给地所剩资源为1。最后 $\text{smaller}\left(3\right)$ 和 $\text{smaller}\left(3\right)$ 进行调整，将供给地的资源数2给需求地。

步骤5：更新可得 $\text{value}=\left[-3,0,0,1,-2,0\right]$ ，重复步骤3的过程，最后可得分配矩阵为：

$\text{value}=\left(\begin{array}{cccccc}10& 0& 0& 0& 0& 0\\ 2& 6& 0& 0& 0& 0\\ 0& 0& 23& 0& 0& 0\\ 0& 0& 6& 15& 0& 0\\ 0& 0& 0& 0& 9& 0\\ 0& 0& 0& 0& 2& 18\end{array}\right)$

3.2. 算例2

能源生产和使用是任何经济结构的主要部分。在美国，能源政策的许多方面分散到国家层面。此外，不同国家的不同地区和行业也影响能源使用和生产。1970年，美国西部的12个州组成了西部州际能源协定(WIEC)，其任务重点是促进这些州在发展和管理核能技术方面的合作。州际契约是两个或两个以上的州之间的合同安排，在这两个州之间，如何进行资源的调配就显得尤为重要。

沿着美国与墨西哥的边界，有四个州——加利福尼亚(CA)、亚利桑那州(AZ)、新墨西哥州(NM)和德克萨斯州(TX)——希望形成一个现实的新能源契约，重点是增加清洁能源和可再生能源的使用。本算例基于本文提出的优化分配算法对以上4个州的化石燃料、可再生能源、总能源进行和理调配。

下面以2009年，加利福尼亚(CA)、亚利桑那州(AZ)、新墨西哥州(NM)和德克萨斯州(TX)的能源生产与使用情况 [11] 如表1所示。

最后，根据优化调度算法，求得4个州的能源调度结果如表2所示。

表1. 能源生产与消费情况表

表2. 能源调度分配表

4. 结论

本文针对资源配置问题，提出了一种基于供需关系的资源优化算法。本文建立了多目标规划模型，并给出了资源分配的求解算法步骤，并给出了实例分析。结果表明，本文给出的优化调度算法能较好的对各个地区的资源进行合理分配，从而可作为政府部门进行资源调配做出决策的依据。

基金项目

西南科技大学大学生创新基金项目：“灰色神经网络组合模型在汽车保有量中的预测研究”(项目编号：cx18-061)，主持人：夏杰。

文章引用

夏 杰,吴文青,许海洋. 基于供需关系的优化调度算法及其应用
Optimal Scheduling Algorithm Based on Supply-Demand Relationship and Its Applications[J]. 运筹与模糊学, 2018, 08(03): 77-82. https://doi.org/10.12677/ORF.2018.83010

参考文献