[發(fā)明專利]一種任務(wù)求解方法及其裝置

在審

• 申請(qǐng)?zhí)枺?/td>: 202111166727.3
• 申請(qǐng)日: 2021-09-30
• 公開(kāi)（公告）號(hào): CN114237835A
• 公開(kāi)（公告）日: 2022-03-25
• 發(fā)明（設(shè)計(jì)）人: 朱方舟;羅萬(wàn)千;甄慧玲;李希君;袁明軒;曾嘉
• 申請(qǐng)（專利權(quán)）人: 華為技術(shù)有限公司
• 主分類號(hào): G06F9/48
• 分類號(hào): G06F9/48;G06F9/50;G06F17/12
• 代理公司: 深圳市深佳知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 44285
• 代理人: 閔晶晶

1.一種任務(wù)求解方法，其特征在于，所述方法包括：

獲取第一線性規(guī)劃任務(wù)，所述第一線性規(guī)劃任務(wù)包括多個(gè)第一規(guī)劃約束；

獲取所述多個(gè)第一規(guī)劃約束中每個(gè)第一規(guī)劃約束的重要性，所述重要性表示第一規(guī)劃約束對(duì)于降低所述第一線性規(guī)劃任務(wù)的求解時(shí)間的貢獻(xiàn)程度；

根據(jù)所述重要性，對(duì)所述多個(gè)第一規(guī)劃約束進(jìn)行采樣，以得到所述獲取所述多個(gè)第一規(guī)劃約束的子集，其中，所述重要性用于確定第一規(guī)劃約束的采樣概率；

根據(jù)所述多個(gè)第一規(guī)劃約束的子集構(gòu)建第二線性規(guī)劃任務(wù)；

對(duì)所述第二線性規(guī)劃任務(wù)進(jìn)行求解，得到第一求解結(jié)果；

將所述第一求解結(jié)果作為所述第一線性規(guī)劃任務(wù)的初始值，并對(duì)初始化后的所述第一線性規(guī)劃任務(wù)進(jìn)行求解，得到第二求解結(jié)果。

2.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述第一線性規(guī)劃任務(wù)和所述第二線性規(guī)劃任務(wù)均包括規(guī)劃目標(biāo)。

3.根據(jù)權(quán)利要求1或2所述的方法，其特征在于，所述方法還包括：

獲取對(duì)所述第二線性規(guī)劃任務(wù)進(jìn)行求解的第一求解時(shí)間、以及對(duì)初始化后的所述第一線性規(guī)劃任務(wù)進(jìn)行求解的第二求解時(shí)間；

對(duì)所述第一線性規(guī)劃任務(wù)進(jìn)行求解，得到求解所述第一線性規(guī)劃任務(wù)的第三求解時(shí)間；

根據(jù)所述第一求解時(shí)間和所述第三求解時(shí)間的加和，相對(duì)于所述第一求解時(shí)間的減少程度，更新所述每個(gè)第一規(guī)劃約束的重要性，其中，更新后的所述重要性與所述減少程度正相關(guān)。

4.根據(jù)權(quán)利要求3所述的方法，其特征在于，所述方法還包括：獲取對(duì)所述多個(gè)第一規(guī)劃約束進(jìn)行采樣的采樣時(shí)間；

所述根據(jù)所述第一求解時(shí)間和所述第三求解時(shí)間的加和，相對(duì)于所述第一求解時(shí)間的減少程度，更新所述每個(gè)第一規(guī)劃約束的重要性，包括：

根據(jù)所述第一求解時(shí)間、所述第三求解時(shí)間以及所述采樣時(shí)間的加和，相對(duì)于所述第一求解時(shí)間的減少程度，更新所述每個(gè)第一規(guī)劃約束的重要性，以得到更新后的每個(gè)第一規(guī)劃約束的重要性。

5.根據(jù)權(quán)利要求3或4所述的方法，其特征在于，所述方法還包括：

獲取第三線性規(guī)劃任務(wù)，所述第三線性規(guī)劃任務(wù)包括所述多個(gè)第二規(guī)劃約束，所述多個(gè)第二規(guī)劃約束和所述多個(gè)第一規(guī)劃約束的約束類型相同；

獲取所述多個(gè)第二規(guī)劃約束中每個(gè)第二規(guī)劃約束的重要性，其中更新后的每個(gè)第一規(guī)劃約束的重要性用于作為約束類型相同的第二規(guī)劃約束的重要性；

根據(jù)所述每個(gè)第二規(guī)劃約束的重要性，對(duì)所述多個(gè)第二規(guī)劃約束進(jìn)行采樣，以獲取第四線性規(guī)劃任務(wù)，其中，所述每個(gè)第二規(guī)劃約束的重要性用于確定第二規(guī)劃約束的采樣概率，所述第四線性規(guī)劃任務(wù)包括所述多個(gè)第二規(guī)劃約束中的部分第二規(guī)劃約束；

對(duì)所述第四線性規(guī)劃任務(wù)進(jìn)行求解，得到第三求解結(jié)果；

將所述第三求解結(jié)果作為所述第三線性規(guī)劃任務(wù)的初始值，并對(duì)初始化后的所述第三線性規(guī)劃任務(wù)進(jìn)行求解，得到第四求解結(jié)果。

6.根據(jù)權(quán)利要求1至5任一所述的方法，其特征在于，所述第二線性規(guī)劃任務(wù)包括M個(gè)求解變量，所述第一求解結(jié)果包括各個(gè)求解變量的參數(shù)值；

所述將所述第一求解結(jié)果作為所述第一線性規(guī)劃任務(wù)的初始值，包括：

將所述第一求解結(jié)果中各個(gè)求解變量的參數(shù)值作為所述第一線性規(guī)劃任務(wù)中的M個(gè)求解變量的參數(shù)值。

7.根據(jù)權(quán)利要求1至6任一所述的方法，其特征在于，所述第一線性規(guī)劃任務(wù)用于為至少一個(gè)待調(diào)度任務(wù)分配調(diào)度資源，所述第一規(guī)劃約束為調(diào)度資源滿足的約束，所述調(diào)度資源為生產(chǎn)線、生產(chǎn)設(shè)備或生產(chǎn)廠家。

8.根據(jù)權(quán)利要求1至7任一所述的方法，其特征在于，所述得到第二求解結(jié)果之后，所述方法還包括：

獲取第二規(guī)劃約束，所述第二規(guī)劃約束包括松弛變量以及所述松弛變量的上界；

將所述第二規(guī)劃約束增加至所述第一線性規(guī)劃任務(wù)，以得到更新后的所述第一線性規(guī)劃任務(wù)，并求解所述更新后的第一線性規(guī)劃任務(wù)。