[發明專利]一種任務求解方法及其裝置

在審

• 申請號: 202111166727.3
• 申請日: 2021-09-30
• 公開（公告）號: CN114237835A
• 公開（公告）日: 2022-03-25
• 發明（設計）人: 朱方舟;羅萬千;甄慧玲;李希君;袁明軒;曾嘉
• 申請（專利權）人: 華為技術有限公司
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/50;G06F17/12
• 代理公司: 深圳市深佳知識產權代理事務所(普通合伙) 44285
• 代理人: 閔晶晶

本申請公開了一種任務求解方法，方法包括：獲取第一線性規劃任務中多個第一規劃約束中每個第一規劃約束的重要性，重要性表示第一規劃約束對于降低第一線性規劃任務的求解時間的貢獻程度；根據所述重要性，對所述多個第一規劃約束進行采樣，以得到所述獲取所述多個第一規劃約束的子集，其中，所述重要性用于確定第一規劃約束的采樣概率；根據所述多個第一規劃約束的子集構建第二線性規劃任務；將第一求解結果作為第一線性規劃任務的初始值，并對初始化后的第一線性規劃任務進行求解。由于重要性表示第一規劃約束對于降低第一線性規劃任務的求解時間的貢獻程度，本申請可以使采樣得到的子模型的解接近于最優解，從而加速第一線性規劃任務的求解過程。

技術領域

本申請涉及調度領域，尤其涉及一種任務求解方法及其裝置。

背景技術

調度問題是大型制造、物流、生產等環節中最常見的問題之一，在不同的場景下，調度總是有不同的意義。例如：物流調度主要是指在物流過程中，物流公司根據待發貨物的重量、去向、規格、加急程度等對所屬的車輛和人員進行合理的安排和調度；而生產環境中的調度是根據不同產線中不同機器的產能以及生產需求，在若干任務(job)中完成對任務的排序以及任務和機器(可調度資源)之間的匹配；大型制造工廠/機場的工人/空乘排班(timetabling)也是調度問題的一種，這是由于這類問題的目標也是依照工人/空乘的工作特點以及場景需要在不同的時間段內完成最優匹配。因此，核心是排序以及最優分配，而不局限任務是人還是貨物。一般來講，調度問題的目標是在給定任務數的前提下得到最小總工時(makespan)所對應的排序。

很多的調度問題(如排產、線體調度、加工網絡布局等)都可以建模成一個數學問題來求解，線性規劃(linear programming，LP)是其中使用最廣的一類建模方法。線性規劃模型可以包括目標函數和約束條件，其中，目標函數是指根據待優化的目標和影響該目標的變量所設計的函數。例如，在排產問題中，整個排產的目標通常是在滿足所有資源約束的情況下，找出一個最好的加工計劃，使得需求的滿足率最高，同時整體的成本最小(例如成本可以包括但不限于加工成本、庫存成本、轉運成本)，此時，該目標函數可以是用于表示滿足率最大化以及成本最小化的函數。另外，約束條件是指在求解目標函數的過程中所要滿足的其他限制條件。

然而，隨著場景復雜性的提升，線性規劃任務中規劃約束的數量通常較多，求解線性規劃任務所需的求解時間很長。

發明內容

第一方面，本申請提供了一種任務求解方法，所述方法包括：

獲取第一線性規劃任務，所述第一線性規劃任務包括多個第一規劃約束；

在一種可能的實現中，終端設備可以將第一線性規劃任務作為待求解模型傳遞至服務器，進而服務器可以獲取第一線性規劃任務。又例如，終端設備可以將第一線性規劃任務作為求解待求解模型時所使用的的先驗信息，也就是將包括第一線性規劃任務在內的至少一個歷史模型傳遞至服務器，進而服務器可以獲取包括第一線性規劃任務在內的至少一個歷史模型；

通常情況下，線性規劃任務中約束的數量較多時，求解線性規劃任務所需的求解時間很長，因此可以首先選擇線性規劃任務中的部分約束，并基于選擇的部分約束進行求解，并將求解結果(選擇的部分約束中求解變量的狀態)賦予線性規劃任務，相當于將求解結果作為線性規劃任務的初始值，并對線性規劃任務進行求解，如果選擇的部分約束的求解結果與求解線性規劃任務后的求解結果基本一致(或者描述為較為接近，這里的求解結果基本一致可以理解為相同的約束中的求解變量的參數值基本一致)，則求解線性規劃任務時所需的迭代次數較少，也就是可以提高線性規劃任務的求解速度。

因此，在求解第一線性規劃任務之前，需要選擇一部分約束進行求解，且得到的求解結果與第一線性規劃任務的求解結果較為接近。