Page 178 - 《软件学报》2020年第12期

3844 Journal of Software 软件学报 Vol.31, No.12, December 2020

作点集 P 以及离线预测的结果.算法的输出是任务的匹配结果集 M,其中的每一个元素都是稳点元组.在初始状
态,匹配结果 M 为空(第 1 行),将所有工作点设置为闲置状态(第 2 行).对于时刻 t,当一个新的对象 o 出现时,从离
线匹配结果 M off 中查找和 o 有关的元组(第 3 行~第 5 行).如果这个元组在实际情况下是稳定的,将(w,u,p)移出
M off ,作为一个分配结果加入到 M 中,将 u 从 U 中移除,将 w 从 W 中移除,并将 p 被更新为占用状态(第 6 行~第
10 行).如果在 M off 中不存在有关 o 的匹配结果,则原地等待(第 10 行~第 12 行).对于当前到达最长等待时间的
用户,则调用延迟匹配算法在同样等待的工人中查找是否具有稳定匹配(第 14 行~第 17 行).由于预测产生的误
差,会不可避免地出现一些意料之外的工人和用户,如果忽略这种情况,只按照预测的结果进行分配,会降低任
务匹配的数量,所以在预测指导之下,还需要再根据实际情况对分配结果进行调整.最后,算法会更新 M off 并移除
那些已经过期的预测结果.
算法 2. 预测指导的匹配算法.
输入:用户集 U,事件集 W,工作点集 P,离线匹配结果 M off ;
输出:全局任务匹配结果 M.
1. M=∅
2. 所有工作点处于闲置状态
3. For (当前时刻 t)
1. If (出现一个新的对象 o) //o 的类型可以是工人也可以是用户
5. 在 M off 中查找与 o 有关元组(w,u,p)
6. If ((w,u,p)存在)
7. 将(w,u,p)从 M off 中移除
8. 将(w,u,p)加入 M
9. 将 u 从 U 中移除,w 从 W 中移除,更新 p 为占用状态
10. Else
11. o 原地等待
12. Endif
13. Endif
14. If (到达最长等待时间的用户集 U t ≠∅)

15. 取出当前未分配任务且不属于 M off 的工人集 W t 、当前闲置且不属于 M off 的工作点集 P t
16. 调用延迟匹配算法
17. Endif
18. 删除 M off 中的过期结果
19. Endfor
例 6:按照例 5 中的划分方法,可以得到 90 个区域和 2 个时间槽,表 2 描述了预测方法所预测出的结果和离
1
线匹配结果,共匹配了 5 个任务.首先,在 t 0 时刻,w 1 和 u 1 出现,此时 w 1 对应 w 1 70,1 ,u 1 对应 u 87,1 ,(w 1 ,u 1 ,p 6 )可构成一个
稳定元组,如图 5(a)所示.在 t 2 时刻,u 2 出现,但 M off 中不存在与 u 2 对应的元组,所以 u 2 需要等待.同理,w 2 出现之后
依旧需要等待.在 t 4 时刻,w 3 和 u 3 出现,此时 w 3 对应 w 1 25,1 ,u 3 对应 u 1 27,1 ,(w 3 ,u 2 ,p 3 )可构成一个稳定元组.与此同时,u 2
到达最长等待时间,由于 w 3 在 M off 存在有关元组,此时可服务的工人为 w 2 ,可供选择的工作点是 p 5 ,(w 2 ,u 2 ,p 5 )可
1
构成一个稳定元组,如图 5(b)所示.在 t 5 时刻,w 4 出现并开始等待.在 t 6 时刻,u 4 和 u 5 出现,此时 w 4 对应 w ,u 4 对
3,2
1
1
应 u ,(w 4 ,u 4 ,p 1 )可构成一个稳定元组.u 5 开始等待,如图 5(c)所示.在 t 7 时刻,w 5 出现,w 5 对应 w ,u 5 对应 u 1 ,(w 5 ,
1,2 7,2 9,2
u 5 ,p 2 )可构成一个稳定元组,如图 5(d)所示.在 t 9 时刻, w 6 和 u 6 出现,此时 w 6 对应 w 1 ,u 6 对应 u 1 ,(w 6 ,u 6 ,p 6 )可构
84,2 64,2
成一个稳定元组.