[发明专利]一种基于云容器服务的批处理拍卖机制

摘要

本发明公开了一种基于云容器服务的批处理拍卖机制；首先利用云容器映射投标者的子任务关系图以及所需各种资源的数量。引入在线批处理的思想，等待固定的时间对一批投标者进行一轮拍卖，将所有的约束条件写成一个整数线性规划，对线性规划中有关子任务关系以及完成时间的非常规约束进行处理，写出对偶线性规划，通过互补松弛性原理对原始解进行更新，为每一个投标者挑选合理且最优的调度计算需付费用，选择单位资源价格最大并且自身效用为正的投标者中标，最后根据Posted Price机制，利用剩余资源量对每个时隙的资源价格进行更新，避免了提前耗尽资源的情况，有利于接受未来的投标者。本发明具有激励相容，计算可行以及经济有效的优点。

主权项

一种基于云容器服务的批处理拍卖机制，其特征在于，定义一个资源池中的资源种类为R，每种资源的容量定义为Cr.在跨度为{1,…,T}的时段内I个投标者随机到达，每个投标者提交一个标：{M,ti,Gi,Nim,Him,di,Bi}，其中M是每个投标者的子任务数量，ti是投标者到达时间，Gi是子任务的关系图，Nim是完成每个子任务所需的时隙数，Him表示每个投标者子任务的资源配置集合，di,Bi分别表示完成任务的最后期限和投标价格，投标者投标后拍卖商根据需求已经资源量判断是否中标，以期得到社会福利最大，且每一个投标者都会给出一个真实的估价vi，这个估价不受其他投标者的影响，这时的拍卖机制是真实的，则包括以下步骤：步骤1：在拍卖机制真实的前提条件下，运用Compact Exponential Optimization对上社会福利最大化的云容器拍卖写成整数线性规划进行简化，用Γi来表示每个投标人符合约束条件的调度集合；maximizeΣiΣS:t∈SBixiS]]>subjectto:ΣiΣS:t∈SfirS(t)xiS≤Cr,∀r,∀t,]]>ΣS∈ΓixiS≤1,∀i.]]>xiS∈{0,1},∀i,∀S.]]>步骤2：利用原始对偶算法写出对偶线性规划，得到两个对偶变量ui与κr(t)，其中，对偶变量ui表示投标者的效用，κr(t)表示时隙t的资源价格：minimizeΣiui+ΣtΣrCrκr(t)]]>subjectto:ui≥Bi-ΣtΣrfirS(t)κr(t),∀r,∀t,]]>kr(t),ui≥0,∀i,∀r,∀t.]]>步骤3：一旦投标人i的schedule S使得对偶约束变紧，即，就更新原始变量xiS，而且每个投标者的效用不能为负值，ui>0，所以ui=max{0,maxΓi(Bi-ΣrΣtfirS(t)κr(t))};]]>步骤4：将原始变量xi，表示示是否将投标人i的容器m分配给时隙t的函数zim(t)，表示时隙t中已被分配的资源的函数wr(t)以及对偶变量ui初始化为0，将κr(t)初始值设为其中系数k为大于1的数，参数σ定义为在时间范围T内所有种类资源的最小占用率，Fr表示最小单位资源价格，即步骤5：每等待θ个时隙处理一次，将到来的所有投标者放入集合ρq，用ψ表示中标者的集合，当ρq为空集时，一轮批处理拍卖结束；步骤6：将属于集合{ρq/ψ}的投标者进行处理，得到每个人的效用ui，最优schedule Si，所需最小费用costi以及所分配的每个时隙占用的资源量集合步骤7：计算步骤7中所有用户的单位资源价格，并挑选出单位资源价格最大的投标人；即，μ=argmaxi∈ρq/ψ{BiΣrΣtfirS(t)κr(t)}.]]>步骤8：如果投标人的效用ui>0，将该投标者放入集合ψ，按照scheduleSi为该投标人分配资源，并收取费用costi；同时将时隙t∈Si的剩余资源数量wr(t)以及价格κr(t)进行更新，价格的更新公式为：κr(t)=σFrk(kDrσFr)wr(t)Cr.]]>其中，Dr与Fr分别代表最大和最小单位资源价格，这两个是预估参数，wr(t)代表在时隙t时的已使用资源量；步骤9：如果投标人的效用ui<0，该投标者被拒绝，将该投标者从集合ρq中删除，同时进入下一轮循环，直到集合ρq为空集时，结束循环。