一种基于英式限制组合拍卖机制的网格资源调度方法

• 摘要：

  本发明提供一种基于英式限制组合拍卖机制的网格资源调度方法,属于网络技术领域,包括准备期、筛选期、拍卖期,本发明的调度方法以拍卖方式作为网格资源能力的定价方式,并以此进行网格资源的配置,能够很好地反映市场信息并充分调动广大用户将闲置资源加入到网格中来,提高网格环境下的资源调度效率;改进了原始的英式限制组合拍卖机制,使其适合对带状能力划分的网格资源的调度,并结合遗传算法设计了网格资源拍卖胜标确认方法,更好的适合实际的特殊网格资源调度情况.

• 专利类型：

  发明专利

• 申请/专利号：

  CN201110215347.4

• 申请日期：

  2011.07.29

• 公开/公告号：

  CN102289765A

• 公开/公告日：

  2011-12-21

• 发明人：

  王兴伟 刘军 王宇 黄敏

• 申请人：

  东北大学

• 主分类号：

  G06Q30/00(2006.01)I,G,G06,G06Q,G06Q30

• 分类号：

  G06Q30/00(2006.01)I,G,G06,G06Q,G06Q30,G06Q30/00

• 主权项：

  一种基于英式限制组合拍卖机制的网格资源调度方法,其特征在于:包括如下步骤:步骤1准备期:完成传统拍卖的委托和公布阶段;拍卖平台接受卖方的委托,记录并统计卖方提交的能力供应量和保留价;在公布阶段公开这次拍卖中卖方的能力供应量、保留价格和筛选期的结束时间;步骤2筛选期:在筛选期内对竞买人进行身份认证、登记,在网上银行冻结保证金之后,进行一轮筛选过程;规定买方的单位能力报价必须不低于卖方的保留价,否则视为无效;假设拍卖平台保留各时段总需求量是p倍的总供应量且出价最高的那部分买方,拍卖平台在筛选期到期后进行的筛选过程如下:步骤2.1:按照买方单位能力报价Bup的降序将买方标的重新排列,设置集合变量Td代表当前买方集合在各时段的总需求量,n代表已检查过的买方标的个数,将Td的初始值设为各时段需求量为0,n的初始值设为1;步骤2.2:从买方队列中复制第n个买方标的的信息,假设该标的需求量是Rcn,时间范围是修改Td在内的值,使使用变量Srp记录该买方的单位报价;步骤2.3:如果Td在所有时段的需求量都不低于p倍的供应量或n大于买方队列中的标的个数时,转到步骤2.4;否则,n＝n+1,转到步骤2.2;步骤2.4:保留买方标的队列中前n个买方的投标权,通知其他买方退出拍卖;步骤3拍卖期.完成传统拍卖中的操作和结算阶段;使用回合制拍卖过程,每一回合的流程如下:步骤3.1:将Srp作为起拍价格,确定每一回合拍卖的初始持续时间Tori、狙击检查时间Tcheck和狙击延长时间Tmore,如果距离本回合拍卖结束前的Tcheck时间内拍卖平台收到标的,则认为发生了"狙击"现象,将本回合的结束时间延长Tmore;步骤3.2:设置计时器,经过时间Tori触发;步骤3.3:平台接收买方标的,将买方标的按照单位能力报价Bup的降序排列;步骤3.4:计时器到期后,检查最后一个标的的到达时间是否在距离当前Tcheck的时间范围内,如果到达时间在该范围内,则将计时器设置为经过Tmore后触发,流程转向步骤3.3;如果到达时间不在该范围内,检查该回合是否收到新的标的,如果收到新的标的,进行胜标确认,向各买方公布获胜标的集合,流程转向步骤3.2;如果在该回合未收到新的标的,拍卖期结束,通知各买方拍卖结果并进行结算;其中胜标确认方法如下:步骤3.4.1胜标确认的数学模型卖方在每回合中都要根据该回合买方提交的标的确定并公布本轮的获胜者集合;假设卖方pidj在第l轮收到m个来自买方的标的,这m个买方分别为bidl1、bidl2Λ、bidlm,设买方bidli是否获胜的标识为xli,则该拍卖机制的胜标确认问题对应的数学模型为:Maximize: Σ l ≤ i ≤ m ( Bup li × ( T re i - T re i ) × x li ) s.t.xli∈{0,1} ∀ T s ≤ k ≤ T e , Σ l ≤ i ≤ m ( Rc k i × x li ) ≤ Pc - - - ( 3.1 ) 代表买方bidli在时间段[k,k+1]内的需求量;步骤3.4.2对传统的遗传算法进行修改用来求解胜标确认问题;步骤3.4.2.1染色体结构使用二维矩阵结构,矩阵由2行m列组成;每一列代表一个买方标的,第一行的整数a1i代表买方标的在标的队列中的位置,第二行的整数a2i使用0?1编码,其中1代表标的队列中的第a1i个标的获胜;步骤3.4.2.2初始化种群设定种群规模后,依次产生每个染色体;随机确定第一行的各元素值,保证各个元素位于[1,m]范围内且各不相同,随机确定第二行的各元素值,保证在各时段的需求量不超过供应量;步骤3.4.2.3适宜值函数选用卖方的成交额作为适值;步骤3.4.2.4选择、交叉、变异步骤3.4.2.4.1选择操作使用传统遗传算法中的轮盘赌选择法;步骤3.4.2.4.2交叉操作是依次将染色体的第一行中进行交叉的元素使用部分映射交叉操作进行重新排序,对第二行元素依次进行调整,其具体步骤如下:步骤3.4.2.4.2.1:使用变量n代表当前标的所在的列,设置变量NS代表部分映射集合,将n＝1,NS设置为空;步骤3.4.2.4.2.2:产生随机数Pnow,比较Pnow与当前交叉概率Pcrossover的大小,如果Pnow＜Pcrossover,将两个染色体的a1n组成映射集合合并到NS中;步骤3.4.2.4.2.3:如果n大于买方队列中的标的个数,转到步骤3.4.2.4.2.4;否则,n＝n+1,转到步骤3.4.2.4.2.2;步骤3.4.2.4.2.4:将n＝0;步骤3.4.2.4.2.5:检查两个染色体中的a1n是否在NS中,如果在,将a1n替换成NS中的下一个值,如果不在则保留原值;步骤3.4.2.4.2.6:n等于买方队列中的标的个数时,交叉操作结束;否则,n＝n+1,转到步骤3.4.2.4.2.5;步骤3.4.2.4.3变异操作是将发生变异的列的a1i与同一染色体中另一被选中的列的a1j进行交换:步骤3.4.2.4.4经过交叉和变异操作得到的染色体中的可能不满足 ∀ T s ≤ k ≤ T e , Σ l ≤ i ≤ m ( Rc k i × x li ) ≤ Pc ; 使用如下方法对染色体进行修正:步骤3.4.2.4.4.1:将设置变量n＝1;步骤3.4.2.4.4.2:检查是否满足 ∀ T s ≤ k ≤ T e , Σ l ≤ i ≤ n ( Rc k a 1 i × x 2 i ) ≤ Pc , 代表标的队列中的第a1i个买方在时间段[k,k+1]内的需求量,如果满足则a2n＝1,否则a2n＝0;步骤3.4.2.4.4.3:n大于买方队列中的标的个数时,检查操作结束;否则,n＝n+1,转到步骤3.4.2.4.4.2.FDA0000079730190000011.tif,FDA0000079730190000012.tif,FDA0000079730190000013.tif,FDA0000079730190000024.tif,FDA0000079730190000035.tif