[發明專利]一種原材料下料排樣的求解方法

有效

• 申請號: 202211346050.6
• 申請日: 2022-10-31
• 公開（公告）號: CN115455341B
• 公開（公告）日: 2023-02-07
• 發明（設計）人: 梁橋康;肖海華;秦海;鄒坤霖
• 申請（專利權）人: 湖南大學
• 主分類號: G06F17/11
• 分類號: G06F17/11;G06Q10/04
• 代理公司: 長沙市護航專利代理事務所(特殊普通合伙) 43220
• 代理人: 莫曉齊

一種原材料下料排樣的求解方法，包括如下步驟：S1、確定原材料的長度、每種下料工件的數量、每種下料工件的尺寸大小；S2、建立原始數學模型，對原始數學模型矩陣化得到簡化后的數學模型；S3、建立初始單位矩陣，引入常量參數，然后對簡化后的數學模型進行初等行變化，得到新數學模型；S4、借助優化器對新數學模型進行求解，得到初始可行解；S5、基于初始可行解，利用CG算法求解到最優松弛解若該松弛解不是非負整數，則對其進行取整以得到整數解，選擇S4和S5中最好的解為原材料下料排樣方案。本發明提出一種基于新數學模型改進的CG算法以求解低需求的下料問題，可很好地提升CG算法的求解質量。

技術領域

本發明涉及原材料下料技術領域，特別涉及一種原材料下料排樣的求解方法。

背景技術

減少原材料消耗是企業實現綠色制造的必要手段之一，關乎著企業提高經濟效益和改善生態環境問題，是一種節能減排的最直接有效的方法，更是一種助力國家實現碳中和目標的重要手段。而與原材料消耗直接相關的切割問題普遍存在于實際工程問題中，如在造紙、鋼鐵、塑料、鋁和木材等各種行業的生產計劃中，切割問題是必不可少的。切割問題也稱為下料問題，其求解效果直接關系著制造企業的原材料消耗和生產效率。具體來講，經典一維切割庫存問題（CSP）的數學模型是指通過優化給定的目標函數（原材料成本最小化），將一組可用的庫存原料切割成客戶訂單要求的各種不同尺寸規格的產品。從數學理論層面上講，切割問題是典型的NP組合優化問題。目前，研究者們將求解此類問題的算法分為兩種，一種是通過構造優良的（以材料浪費最少為目標）切割排樣模式的方法，并盡可能反復使用這種切割模式來使目標函數最小化（材料成本最小），滿足客戶訂單對不同規格產品的需求量，這種方法通常被稱為構造式啟發式優化算法；另外一種是先使用列生成精確方法獲得原問題的松弛解，再結合啟發式算法將四舍五入技術應用于松弛解，同時更新切割模式以得到切割優化問題的最佳整數解，這種方法通常被稱為剩余式啟發式算法。

對于一維切割下料一般問題的求解方法，目前的研究技術基本上趨于成熟，但針對低需求下料問題的求解，現有存在的近似解算法幾乎都很難獲得令人滿意的最優解。而列生成精確算法（CG算法）雖能獲得最優松弛解，但其取整之后的整數解與理想最優整數解之間的差距往往較大，且產生不同的切割模式（不同下料排樣方案）數量較多，這致使企業制造產生大量的原材料浪費，并導致企業生產效率低下。

發明內容

本發明提供了一種原材料下料排樣的求解方法，以解決現有技術中現有算法獲得的最優解容易造成原材料浪費的技術問題。

為達到上述目的，本發明的技術方案是這樣實現的：

本發明提供了一種原材料下料排樣的求解方法，包括如下步驟：

步驟S1、確定原材料的長度、每種下料工件的數量、每種下料工件的尺寸大小；

步驟S2、依據原材料的長度、每種下料工件的數量、每種下料工件的尺寸大小建立原始數學模型，對原始數學模型矩陣化得到簡化后的數學模型；

步驟S3、建立初始單位矩陣，引入常量參數，利用初始單位矩陣和常量參數對簡化后的數學模型進行初等行變化，得到新數學模型；

步驟S4、借助Gurobi優化器對新數學模型（稱為VTC模型）進行求解，得到新數學模型的初始可行解，初始可行解包括下料排樣方案和決策變量，決策變量指不同排樣方案對應的變量，即對應每一種排樣方案所使用原材料的數量；

步驟S5、利用CG算法在初始可行解的基礎上繼續進行求解，得到最優松弛解,最優松弛解是指最優決策變量，若最優松弛解全為非負整數，則將最優決策變量求和的值與步驟S4中決策變量求和的值進行比較，選擇求和最小的一方所產生的決策變量作為最終的決策變量，其所對應的下料排樣方案為最終的原材料下料排樣方案，若最優松弛解不全為非負整數，則進入步驟S6；