[發明專利]云打印業務中一種基于圖的帶截止約束的拍賣算法

在審

• 申請號: 201710984390.4
• 申請日: 2017-10-20
• 公開（公告）號: CN107943427A
• 公開（公告）日: 2018-04-20
• 發明（設計）人: 暴建民;李樹強
• 申請（專利權）人: 南京郵電大學
• 主分類號: G06F3/12
• 分類號: G06F3/12;G06Q10/06
• 代理公司: 南京知識律師事務所32207
• 代理人: 李吉寬

1.云打印業務中一種基于圖的帶截止約束的拍賣算法，其特征在于，包括以下步驟：

步驟1、查看當前打印業務狀態state，State＝1,表示繁忙狀態，state＝0，表示空閑狀態；

步驟2、如果state＝1，則當訂單池存儲任務數量達到N個時，執行多個訂單多機器分配執行流程；如果state＝0，則每提交一個訂單，執行依次單個訂單分配流程；

步驟3、查看當前是否有未分配的訂單，如果有，則重復執行步驟2-3；如果沒有，則停止分配。

2.根據權利要求1所述的云打印業務中一種基于圖的帶截止約束的拍賣算法，其特征在于，步驟1中state狀態為一個boolean值，根據經驗人為設定。

3.根據權利要求1所述的云打印業務中一種基于圖的帶截止約束的拍賣算法，其特征在于，步驟2中的N值取決于后臺每分鐘接受的訂單數和算法復雜度的考慮。

4.根據權利要求3所述的云打印業務中一種基于圖的帶截止約束的拍賣算法，其特征在于，所述N的取值為100。

5.根據權利要求1所述的云打印業務中一種基于圖的帶截止約束的拍賣算法，其特征在于，步驟2中單個訂單分配的具體流程如下：

步驟1：通過獲取訂單j的位置信息，找到與該地區相對應的圖G_k；

步驟2：遍歷所有圖G_k中的頂點集V_k的位置信息進行計算，找到離訂單j最近的打印店頂點v_clo；

步驟3：按上述賦值算法流程，根據頂點v_clo進行查找與它相鄰的頂點，并存放在集合pane₁中，依次存放至集合pane_n，n的值為認為設定，把距離過遠的打印店直接排除；

步驟4：對所有具有競拍資格，在集合中的打印店進行賦值計算，然后找到最高匹配值的，則進行賦值即可。

6.根據權利要求1所述的云打印業務中一種基于圖的帶截止約束的拍賣算法，其特征在于，步驟2中多個訂單多機器分配的具體流程如下：

步驟1：將訂單集O里所有訂單按地區分為m個集合，對于訂單集O_k，k＝1,...,m，通過訂單集的地區分別找到與之對應的圖G_k；

步驟2：對訂單集O_k中的所有頂點進行遍歷，并在圖G_k中分別與訂單j最近的打印店集合S_clo；

步驟3：遍歷訂單集O_k里所有的訂單，分別對它們執行賦值算法流程，并剔除每個訂單的時間上和地點上不合適的打印店，最后對于訂單集O_k里每個訂單，對應一個賦值集合分別計算和存儲該地區所有適合該訂單的打印店的匹配值；

步驟4：依次遍歷查找所有的賦值集合將匹配值最高的打印店和訂單進行第一輪匹配，在此步中，每個打印店只能被賦給一個訂單，如果兩個訂單的最優匹配在同一個打印店，則取值最高的一個，如果兩個匹配值相同，則按順序匹配第一個；

步驟5：將已經匹配好的訂單排除出訂單集O_k，并生成新的訂單集O_k(τ)，對于新的訂單集O_k(τ)，重復執行第2-4步驟，直至所有的訂單都已經分配完畢。