云采购平台虚拟供应商资源动态分配

摘 要：

重点探讨将云计算技术运用到采购环节中，构建云采购平台，探讨如何分配载有虚拟供应商资源的虚拟机，改善顾客满足情况。首先提出了云采购平台的概念，假设虚拟机载有供应商资源；其次提出了载有虚拟供应商资源的虚拟机分配流程，并且建立模型；然后分别采用最佳递减匹配（BFD）方法和仪跟踪多群粒子群优化（FTMPSO）算法对其求解；最后分析求解结果。采用最佳递减匹配算法时，优先满足的属性不同，得到的顾客满足情况不同；仪跟踪多群粒子群优化算法对虚拟供应商资源进行分配得到的顾客满足率高于用最佳递减匹配算法对虚拟供应商资源进行分配的顾客满足率。

关键词：虚拟供应商资源；虚拟机；物理服务器；客户需求；满足率

中图分类号： TP393.027.2

文献标志码：A

Dynamic allocation of virtual supplier resources based on cloud procurement platform

Abstract：

This paper focused on the application of cloud computing technology to purchase link to form a cloud procurement platform， and to explore how to allocate the virtual machine with the virtual suppliers resources， so as to improve the satisfaction of customers. Firstly， this paper proposed the concept of cloud purchase platform， assuming that the virtual machine containing the suppliers of resources； secondly proposed the allocation processes of virtual machines which contained the virtual suppliers resources and modeling； then the Best Fit Decreasing （BFD） and Finder-tracker multi-swarm Particle Swarm Optimization （FTMPSO） were adopted to get the solution； finally the results of computing were analyzed. In the BFD algorithm， the priority of each of the three attributes met different preferences of the customers requirements. Using FTMPSO algorithm to allocate virtual suppliers resources got higher satisfaction of customer than using BFD to allocated virtual suppliers resources.

Key words：

virtual supplier resource； virtual machine； physics server； customer requirement； satisfaction rate

0 引言

近几年云计算在各领域中的应用引起专家、学者的广泛关注。林云等[1]提出物流云服务及其业务架构图，并进行面向汽车业的物流云服务模式设计，但作者在文中并未对该设计实用性等进行验证。Grilo等[2]在其文中探讨了基于分布式电子采购在AEC（Architecture， Engineering and Construction）领域的应用（云市场），对相关的概念及框架进行了很好的诠释，但是仅局限于AEC领域，而云计算技术可以应用于许许多多的领域。

目前，云计算的应用研究主要集中于中小型企业信息化、高校网络教育平台、政府资源管理，应用在物流供应链中的研究较少。Xu[3]讨论了云计算的基本特征，引出云计算的制造和云制造概念并进行探讨，但是也仅是较大程度地停留在理论框架的构建层面。葛显龙[4]以及Ratien[5]分别在其文中提出类似的物流云服务的概念，前者侧重研究面向云计算的车辆调度问题，后者侧重研究企业等接受云计算的行为，但是基于云配送的车辆调度问题存在一定的局限性，企业等接受云计算技术需要做的准备未提及。

在前人研究的基础上，本文首先提出物流云采购平台的概念模型，然后在云采购平台基础上对云采购平台的虚拟资源的分配进行分析。主要探讨云平台在面对大量客户需求时，如何将其载有虚拟供应商资源的虚拟机进行分配，使其最大限度地满足客户需求。

1 问题描述

1.1 云采购平台概念模型

云采购是指基于云计算的采购模式，它是一种在网络环境下按照客户需求自觉进行信息挖掘和采集的系统，用于启用无处不在、方便且随需而变的网络资源[6]，共享一个资源池的资源，该资源池包括采购软件工具、采购所需单证、采购能力等，在该资源池里集中资源迅速地配置和发散，以达到以最少的管理成本和工作成本获取最优的服务，云采购平台如图1所示。

1.2 虚拟供应商资源分配背景

Nazario等[7]经过统计总结出针对大宗商品的采购，用于评价与选择供应商的变量主要有产品的品质、供应商产品的配送、产品的价格、供应商的制造能力、服务等，每一个变量在被引用的频率以及其所占所有文章的具体比例如表1所示。

从表1可看出，对于大宗商品的采购，供应商的选择、评价指标主要集中在供应商的产品、配送以及成本等方面上。对于微小企业通过云采购平台采购，依托云平台的监管以及服务协议的存在，大宗商品的采购所考虑到的供应商的其他指标考虑较少。因此，该文章主要以供应商的供应量、配送水平、单价三个指标为标准，来衡量顾客的虚拟供应商资源的满足率。

顾客的虚拟供应商资源请求到达之前，物理服务器载有一定的虚拟机，请求到达时，云采购平台监管层首先判断已有的虚拟资源是否能够很好地满足顾客的需求[8]。如果已有的剩余虚拟供应商资源不足以满足用户需求时，云采购平台会采取相应的措施对其进行处理[7]。

1.3 虚拟供应商资源分配的流程

云采购平台集中大量采购资源，接受客户需求后，首先对其现有资源进行判断，然后考虑是否需要对相应的物理服务器增派载有虚拟供应商资源的虚拟机。虚拟供应商资源分配的流程如图2所示，其中，DPM（Demand in Physics Machine）即载有顾客虚拟供应商资源请求的物流服务器，SVM（Supply in Virtual Machine）即载有供应商资源的虚拟机，VSR（Virtual Supply Resources）即虚拟供应商资源。

2 虚拟供应商资源分配问题建模

2.1 载有虚拟供应商资源的虚拟机分配的问题描述

在一定区域、一定时段，面对供给一定需求无限大的情况，如何充分利用资源、满足顾客是一个值得考虑的问题。文献[9]从虚拟资源的价格以及虚拟资源的服务质量（Quality of Service，QoS）两方面考虑，采用了演化博弈的方式对云计算市场进行建模，最后通过动态演化整个市场可以达到演化稳定。文献[6]使用CloudSim仿真技术，对云市场的虚拟资源的分配进行了仿真分析等。

将载有虚拟供应商资源的虚拟机分配问题[10]描述为装箱问题。该装箱问题中的“箱子”是指载有顾客需求信息的物理服务器，箱子的容量是指载有的需求的相关属性，例如产品数量、能接受的最大供应价格、配送准时率等。装箱的物品为载有虚拟供应商资源的虚拟机。而虚拟机的分配问题与装箱问题有着不同的地方，即顾客的需求不是同时到达的。

2.2 载供应商资源的虚拟机动态分配模型建立

2.2.1 模型的建立

（1）模型集合与参数。

1）I={1，2，…，n}表示载有客户需求的物理服务器集合；

2）K={1，2，…，m}表示载有虚拟供应商资源的虚拟机集合；

3）T={1，2，…g}表示每天顾客需求到达物理服务器的时间段集合；

4）D={1，2，…，o}表示所有物理服务器所载有的客户需求集合；

5）Dit表示t时间段，到达物理服务器i的需求属性集合，该需求的到达服从Poission分布；

6）Sjt表示t时间段，可供分配的载有虚拟供应商资源的虚拟机集合；

7）SQUAkt表示t时间段，载有供应商资源的虚拟机k的供应商的供应量；

8）SPRIkt表示t时间段，载有供应商资源的虚拟机k的供应商的总的供应价格；

9）SDELkt表示t时间段，载有供应商资源的虚拟机k的供应商的配送时间截点；

10）λ表示顾客需求到达服从Poission分布的参数；

11）yijkt∈{0，1}表示t时间段，载有虚拟资源的虚拟机k是否从物理机i迁移到物理机j上，i≠j；

12）f1表示顾客商品数量的满足率；

13）f2表示消费者剩余与期望价格的比率；

14）f3表示配送时间剩余与期望配送时间的比率。

（2）决策变量。

1）aikt∈{0，1}表示t时间段，载有虚拟资源的虚拟机k是否分配到物理机i上；

2）WQUAikt表示t时间段，载有客户需求的物理服务器i已分配的虚拟机k的总供应量；

3）WPRIikt表示t时间段，载有客户需求的物理服务器i已分配的虚拟机k的总的供应价格；

4）WDELikt表示t时间段，载有客户需求的物理服务器i已分配的虚拟机k的总的配送时效；

5）DQUAit表示t时间段，载有客户需求的物理服务器i的客户需求产品的数量；

6）DDELit表示t时间段，载有客户需求的物理服务器i的客户需求中，顾客能接受的最晚配送时间截点；

7）DPRIit表示t时间段，载有客户需求的物理服务器i的客户需求中，客户能够接受的最大供应价格，质量相当的情况下，顾客总是希望得到更多的消费者剩余。

（3）目标函数与约束。

假定每一个载有虚拟供应商资源的虚拟机一次只能分配给给一个载有需求信息的物理服务器，每一个载有需求信息的物理服务器可以接受多个载有虚拟供应商资源的虚拟机。在此通过一个矩阵来形象地表达该分配模式。

3 粒子群及最佳递减匹配算法

粒子群优化（Particle Swarm Optimization， PSO）算法是模拟鸟群飞行觅食的行为，通过鸟之间的集体协作使整个鸟群达到最优。粒子群算法最早由Kennedy和Eberhart在1995年提出[11]。

动态环境下，基本的粒子群算法在收敛性以及找最优解时有一定的局限性。因此本文使用粒子群算法的改进算法即是仪跟踪多群粒子群优化（Finder-Tracker Multi-swarm Particle Swarm Optimization， FTMPSO）算法[12]。与PSO不同的是，FTMPSO是有着更好效应、更好的收敛性、更快找到全局最优解等优势的一种算法；在FTMPSO算法初始还选择了专为测试全局动态环境变化的测试点，文献[12]对于FTMPSO的效率等相关属性进行了实验仿真。

最佳递减匹配（Best Fit Decreasing， BFD）方法[13]是在最佳适应启发式（Best-Fit heuristic，BF）方法的基础上发展而来的，BF算法是从优先适应启发式方法（First-Fit heuristic， FF）改进而来的。最佳递减匹配方法在传统的装箱问题中通过首先对物品按重量降序排列，再结合BF算法实现。

4 算例分析

微小企业对原材料的采购不足以形成较大的规模，因而会选择固定的供应商，所以对于一般性的原材料采购，它们多选择通过云平台来实现。云平台聚集大量的供应商信息，形成一个资源池，接到顾客需求时，就会对该虚拟供应商资源进行分配。

在此，提出3个假设：1）假设载有需求的物理机的分布是分区域的，每一个区域有着固定数量的可供立即服务的载有虚拟供应商资源的虚拟机；2）物理机接受的需求可以无限大，在此假设每个区域的最大虚拟机个数也不能全部满足需求；3）假设每个固定区域可供使用的虚拟供应商集群规模为50。

假设在江浙沪地区存在着这样一批微小企业，它们要对橡胶原材料进行采购。在阿里巴巴网站上收集50家供应商的相关信息，供应商的供应信息如表2所示。

在一个虚拟机集群服务的区域，假设有10台物理服务器，每台物理服务器可以同时接受多个客户需求。在此假设顾客需求到达时按照一定的次序进入物理服务器，直到所有的服务器都载有客户需求时，已载有顾客需求的物理服务器开始载多个需求。假设客户需求发生的概率服从泊松分布，结合实际的网上调研工作，将某需求到达高峰期分为6个时段，每个时段客户需求的产生由Poission分布在Matlab中随机产生，每个时段到达的需求数如图3所示。

根据到达的顾客需求采用BFD算法对虚拟供应商资源进行分配，使其最大限度地满足顾客需求。在虚拟机充分迁移的情况下，分别计算优先考虑质量（QUANTITY，QUA）（即将QUA进行降序排列分配）、优先考虑价格（PRICE，PRI）以及优先考虑配送（DELIVERY，DEL）三种情况下的需求产品数量的满足率、 消费者剩余与期望价格的比率、 配送时间剩余与期望配送时间的比率。计算结果如图4所示。

从图4可看出，不同的优先满足情况（即消费者爱好）将会得到不同的顾客满足情况。因此，综合三种情况可得到顾客需求满足的平均情况，如表4所示。

从图5可看出，在分配一定的载有虚拟供应商资源的虚拟机数量的情况下，FTMPSO能够使顾客的需求满足率更高，此时仅有序号为24、44的虚拟机未被分配。

5 结语

云计算将广泛应用到物流供应链中，其虚拟供应链资源的分配问题将得到广泛研究。本文在云计算的基础上，提出了云采购平台的概念模型、重点研究了载有虚拟供应商资源的虚拟机的分配问题。在算例分析中，使用同一种方法研究了虚拟机迁移与不迁移情况下，顾客需求的满足率。在虚拟供应商资源的分配过程中，虚拟机的迁移将有利于提高顾客需求满足率。对于微小企业，云采购平台为其原材料的采购带来了巨大的便利，云平台的资源大量集中以及资源透明化使得原材料成本降低。通过一定的虚拟供应商资源分配方法，使得微小企业的采购需求得到最大限度的满足。但是本文存在着很多不足，例如对于需求到达的模拟过于粗糙，对虚拟机迁移的成本没有过多的考虑，作者在以后的日子里将对其进行更进一步的完善。

参考文献：

[1] LIN Y， TIAN S. Logistics cloud service： innovation model of logistics service oriented to supply chain[J]. Application Research of Computers， 2012，29（1）：224-228.（林云，田帅辉.物流云服务——面向供应链的物流服务新模式[J].计算机应用研究 2012，29（1）：224-228.）

[2] GRILO A， JARDIM-GONCALVES R. Cloud-marketplaces： distributed e-procurement for the AEC sector[J]. Advanced Engineering Information，2013，27（2）：160-172.

[3] XU X. From cloud computing to cloud manufacturing[J]. Robotics and Computer-Integrated Manufacturing， 2012， 28（1）：75-85.

[4] GE X. Study on vehicle scheduling problem and algorithm based on cloud distribution model[D].Chongqing： Chongqing University， 2011.（葛显龙.面向云配送模式的车辆调度问题及算法研究[D].重庆：重庆大学，2011）

[5] RATTEN V. Entrepreneurial and ethical adoption behavior of cloud computing[J]. Journal of High Technology Management Research， 2012，23（2）：155-164.

[6] LIN J， LIANG J. Research on virtual machine dynamic resource allocation and placement algorithm[D]. Shanghai： Fudan University， 2012.（李进超，梁瑾.虚拟机动态资源分配及放置算法研究[D].上海：复旦大学，2012.）

[7] NAZARIO G， JAVIER P， ISABEL F， et al. Supplier selection model for commodities procurement. Optimised assessment using a fuzzy decision support system[J].Applied Soft Computing， 2013（13）：1939-1951.

[8] AMIT N， SANJAY C， GAURAV S. Policy based resource allocation in IaaS cloud[J]. Future Generation Computer Systems， 2012，28（1）：94-103.

[9] LE W， ZHANG X. Research on strategy of virtual machine resource allocation and placement in cloud computing environment[D]. Kunming： Yunnan University， 2012.（乐伟，张学杰.云计算环境下虚拟机资源分配以及部署策略研究[D].昆明：云南大学，2012.）

[10] PRASAD C， ROHIT P， ALEX B， et al. Utility-directed resource allocation in virtual desktop clouds[J]. Computer Networks，2011，55（18）：4112-4130。

[11] KENNEDY J， EBERHT R. A new optimizer using particle swarm theory[C]// Proceedings of the 6th International Symposium on Micro Machine and Human Science. Piscataway： IEEE，1995： 39-43.

[12] DANIAL Y， BABAK N，ALIREZA S M， et al. A novel multi-swarm algorithm for optimization in dynamic environments based on particle swarm optimization[J]. Applied Soft Computing，2013，13（4）：2144-2158.

[13] ZHANG L， WU Z. The simulation of BFD hybrid genetic algorithm about bin packing problem[D]. Nanjing： Hohai University， 2006.（张丽岩，吴中.装箱问题BFD混合遗传算法的仿真研究[D].南京：河海大学，2006.）