一種求解排程問題的剪枝搜索算法

甄 卓

(寶山鋼鐵股份有限公司中央研究院,上海 201999)

寶武集團提出將綠色作為企業發展的生命底色和戰略基色,大力推進智慧制造支撐綠色發展。同時市場環境也在發生變化,需求呈現多品種小批量定制化的趨勢。智慧制造能力日漸成為鋼鐵制造企業的核心競爭力,而排程作為智慧制造的關鍵部分,需要企業給予足夠的重視和投入。如果不能使用模型進行智能排程,那么智慧制造就是名不副實的。寶鋼研究院智能制造所的智能優化領域技術團隊,在智能排程領域深耕多年,取得了豐富的經驗和豐碩的成果。針對鋼級“以優充次”的煉鋼組爐問題,構建了以煉鋼成本最小化與煉鋼余材最小化為目標的多目標優化模型[1]。針對煉鋼生產中的鋼種集約問題,以圖論的工具,設計了基于最大獨立集的求解方法[2]。針對連鑄計劃中的組中間包問題,建立了多旅行商模型,提出了一種結合啟發式、鄰域搜索和EDA進化的混合優化算法[3]。在煉鋼連鑄計劃中,改進后的新工藝條件使得中間包壽命的評價方法由固定爐數變成了固定時間,針對這種變化,提出了相應的中間包優化模型[4]。結合雙目標旅行商問題提出了最大最小螞蟻算法[5]。將熱軋生產計劃優化問題歸結為多目標獎金收集車輛路徑問題,實現了一種Pareto最大最小螞蟻系統算法[6]。提出了一種實用有效的計劃排程優化算法,開發了基于該優化模型的軋制計劃排程優化應用系統[7]。設計了基于局部搜索與混合多樣性策略的多目標粒子群算法[8]。針對板坯重可變的自產板坯設計問題,設計了一種基于列生成與網絡最大流的兩階段優化算法[9]。自主開發了不銹鋼與碳鋼交叉軋制計劃混合排程優化模型[10]。

已有成果更多關注于單工序,針對工序特點進行設計,在算法通用性和復用性方面考慮不足。在對以往的工作成果進行總結的基礎上,結合寶鋼生產實際情況,對排程問題進行深入分析并抽象,提出了一種通用的算法,可以在不同工序、不同機組上復用,而且算法運行速度快。此外,算法執行一次,可以得到對應多種優化目標的多個最優解。該算法目前已在寶鋼某熱鍍鋅產線上線試用。

1 排程問題分析

在對不同工序、不同產線、不同機組的排程情況進行綜合分析之后,發現以下幾個方面對算法的設計有重要影響:

(1) 材料之間的順序。材料完全無序的情況在實際中幾乎不會出現,合同的優先級和工藝規程都會對材料的先后順序提出要求。例如生產計劃的編排以合同為單位,不同的合同具有不同的優先級;再比如冷軋工序要按從寬到窄的順序安排軋制。如果可以充分利用材料之間確定的順序關系,則可以顯著提升算法效率。

(2) 通板規程,即判斷兩個材料是否可以連續生產的規則。在實際生產中,通板規程數量最多,比如冷軋工序要關注材料的寬度跳躍、厚度跳躍、溫度跳躍等。由于任意相鄰兩塊材料都要滿足所有的通板規程,所以在計劃構建過程中,大量的時間將用于通板規程的檢測。同時,通板規程對產品的質量、設備的狀態都有直接影響。比如平整過程中,如果違反厚度跳躍的約束,一方面會影響產品表面,另一方面也會影響平整輥表面,嚴重時導致產品表面質量不合格,更換平整輥。所以通板規程是規程檢測的重中之重。

(3) 優化目標。在實際生產過程中,在不同情況下,生產的目標會發生變化。比如說季度初的目標是促生產,季度末的目標是保合同。排程模型應該能夠支持多種優化目標。如果模型可以一次給出若干種優化目標下的最優結果供比較選擇,對生產管理有積極意義。

在之前的成果中,通常把排程問題建模為組合優化問題,以材料之間的序為決策變量,以規程為約束條件,求某種目標下的最優解。這樣做有幾方面的不足:第一,在鋼鐵生產過程中,材料之間經常是有序的。建模為組合優化問題,建模過程中難以充分利用材料有序這一條件。第二,有很多規程難以用數學公式表達,限制了組合優化模型的表達能力。比如如果限制硅鋼產品不能和汽車外板連續軋制,這種規程難以用數學公式的方式表達。第三,在不同情況下,優化目標可能不同,如果建模成單目標組合優化問題,那么為了求解不同目標下的最優解,需要分多次從頭求解。

基于對排程問題的和已有工作的分析,提出了一種新的算法。算法以通板規程為約束,利用材料已知的先后順序,對合規的材料序列展開搜索,給出一個包含了若干優質可行解的集合。根據優化目標,在可行解集合中挑選出最優解;若存在多種優化目標,可以從可行解集合中挑選出多種優化目標下的多個最優解。為了提升算法執行效率,提升搜索結果質量,采取了頭部剪枝和尾部剪枝兩種優化技巧。

2 算法組成

算法由等價材料過濾、材料排序、搜索可行解(剪枝優化)、等價材料恢復和選取最優解幾個部分順序組成。

2.1 等價材料過濾

寶鋼生產計劃以合同為核心,掛在同一合同下的材料其目標規格和其他工藝指標相同。有的合同雖然不同,但從排程的角度來看,材料之間仍可視為等價。材料等價的現象十分常見,待排計劃的材料中,只有一部分是不同的。如果只保留不同的材料,將顯著減小問題的規模,在后續的排序和搜索中,顯著減少運算次數,提升運算速度。所以首先對材料進行過濾,等價的材料只保留一個,再進行排序和搜索,最后將過濾掉的材料恢復。例如有材料序列A0、A1、B0、B1、B2、C0、D0、D1、D2,其中A0、A1等價,B0、B1、B2等價,D0、D1、D2等價,經過過濾之后,以A0、B0、C0、D0作為后續步驟的輸入。

2.2 材料排序

由于合同交期的不同,生產計劃目標的不同,設備狀態的不同,工藝上的要求,材料之間存在先后順序。比如緊急合同優先于一般合同,精整過程中要求材料按照寬度遞減等。綜合各方面的要求,可以指定材料排序的方式。材料經過排序后,確定材料生產序列的問題,就從排列問題簡化為組合問題,極大降低了運算代價。

2.3 搜索可行解(剪枝優化)

在材料先后順序確定的條件下,進行可行生產序列的搜索。一邊搜索,一邊進行通板規程檢測。為了生產的穩定和產品的質量,排計劃時會盡可能地把所有的材料排入計劃,以免排出若干個“碎片”計劃,導致機組需要不斷地中斷生產,調整設備和人員。為了保證不遺漏任何可行的序列,使用深度優先搜索策略。為了便于開發和調試,采用了遞歸的實現方式。

假設算法已經從材料A出發,通過深度優先搜索嘗試了所有以A為開頭的序列,并得到了一個合法的材料序列A、B、C、D、E,那么B、C、D、E,C、D、E,D、E,E這幾種序列就不需要保留,只應保留最長的A、B、C、D、E。進一步,在后續搜索過程中,不需要再以B為開頭搜索可行的序列。這是由深度優先搜索的特性決定的,在以A為開頭的搜索過程中,所有以B為開頭的序列都已經嘗試過了。C、D、E同理。這種剪枝方式可以避免大量的從序列頭部開始的無效搜索,稱之為頭部剪枝。

除此之外,假設算法已經從材料A出發,通過深度優先搜索嘗試了所有以A為開頭的序列,并得到了一個合法的材料序列A、B、C、D、E,那么A、B、C、E,A、B、D類似的序列就不需要保留,把這些無效的序列丟棄,可以大量減少搜索結果中的無效序列。另外,在算法搜索到序列A、B、C、E時,不需要再繼續向后搜索,因為深度搜索策略的特性決定了A、B、C、E后續所有可能的材料序列,在搜索到A、B、C、D、E時都已經嘗試過。這種從尾部過濾無效搜索的方式,稱之為尾部剪枝。

通過頭部剪枝和尾部剪枝,根據已經搜索到的結果避免后續無意義的搜索,顯著提升了算法運行速度并提升了結果質量。極端情況下,在O(n)時間內,就可以求得全部可行序列。需要指出的是,算法保證在給出的可行序列集合中,沒有任何一個序列是另一個序列的子序列。

2.4 等價材料恢復

為了提升排序和搜索效率,等價的材料只保留一個參與運算,在算法執行完畢之后,需要將被過濾掉的等價材料重新插入到結果中。與2.1對應,如果搜索得到的結果是A0、B0、D0,則經過恢復,得到序列A0、A1、B0、B1、B2、D0、D1、D2。

2.5 選取最優解

在已經得到了全部可行解的前提下,從中選取到的最優解一定是全局最優解。此外,在生產中通常有若干種優化目標,從中可以挑選出對應每種優化目標的全局最優解。也就是說,一次搜索,就可以得到若干最優解,方便管理人員進行對比和挑選。

3 算法實現

算法以C++實現,以C++標準庫提供的組件為基礎。為了減小算法執行過程中大批數據移動造成的開銷,以vector存儲待排序的材料序列,以材料在vector中的下標作為材料的索引。后續所有的計算針對索引進行。

3.1 等價材料過濾

為了方便等價材料的過濾和恢復,需要配套使用哈希函數和哈希表,記錄材料之間的等價關系。根據產線的具體要求,設計一個哈希函數,為材料生成一個鍵,保證等價的材料生成的鍵值相同。從前向后掃描材料序列,加入哈希表。如果一個材料的鍵值已經出現過,則代表該材料已經存在等價材料,需要加入相應的等價材料組。在所有的材料分組完畢之后,每個材料組選取一個代表,作為后續算法步驟的輸入。比如哈希表中形成了材料分組為A0、A1一組,B0、B1、B2一組,C0一組,D0、D1、D2一組,以A0、B0、C0、D0作為下一步驟的輸入。

3.2 材料排序

綜合合同優先級、工藝要求、生產目標,確定材料排序的方式,以C++標準庫提供過的sort函數為基礎,自己實現排序的方式。比如,如果材料需要按質量遞增的順序排序,排序方式以如下方式實現:

class WeightUp

bool operator()(int left,int right) {

if ((_items + left)->MAT_WT < (_items + right)->MAT_WT)

return true;

else

return false;

調用標注庫排序算法實現材料索引按照材料質量遞增的方式排序。其中indexes代表需要待排計劃的材料的索引。

::std::sort(indexes.begin(),indexes.end(),WeightUp(data,count));

3.3 搜索可行解

為了搜索到盡量長的滿足通板規程的材料序列,使用深度優先搜索的策略;為了搜索到所有的可行解,以遞歸的方式進行深度優先搜索。算法的整體邏輯是,在一開始,將材料加入空的緩存序列,再向后選取一個元素,如果加入之后滿足通板規程,則將該元素加入緩存序列,遞歸地進行深度優先搜索。搜索結束之后,將之前加入緩存的材料退出。再向后選取一個元素,重復執行上述步驟。indexes代表參與搜索的材料的索引,begin代表當前要加入序列的材料在indexs中的位置,current緩存了當前搜索得到的材料序列,result存儲了搜索得到的結果。偽代碼如下:

backtrack(indexes,begin,current,result)

if begin已經超出indexes的范圍,沒有材料可以加入緩存序列

將current中緩存的序列作為結果加入result

函數返回

if 緩存序列為空

遍歷begin指向的材料及之后的材料

將遍歷到的材料加入緩存序列current

backtrack(indexes,i + 1,current,result),遞歸執行

退出新加入緩存序列current的材料

函數返回

else

遍歷begin指向的材料及之后的材料

if 遍歷到的材料加入緩存序列,不違反通板規程

將遍歷到的材料加入緩存序列current

backtrack(indexes,i + 1,current,result),遞歸執行

退出新加入緩存序列current的材料

3.4 頭部剪枝

假設待排序的材料是A、B、C、D,那么深度優先搜索的策略會先搜索所有以A開頭的合法序列,再搜索以B開頭的合法序列,再搜索以C開頭的合法序列,最后搜索以D為開頭的合法序列。如果在以A開頭的搜索中,搜索到了A、B、D這樣一個合法序列,根據深度優先搜索的特性,可以知道,所有以B為開頭的合法序列都已經被搜索到,且以B為開頭的序列,一定包含在以A為開頭的序列之中。生產實際需要盡量將更多的材料排入計劃,所以A、B、D優于B、D?；谝陨蟽牲c分析,可以得出結論,如果已經得到了A、B、D這樣的序列,那么沒有必要再以B或者D開頭進行搜索。這樣就大大減少了算法的運算量。這種從頭部剪枝的方式,可以通過修改搜索算法實現。以哈希表headPrune存儲已經出現在結果中的材料,當這些材料出現在緩存序列的頭部時,直接退出,不進行后續搜索。偽代碼如下:

backtrack(indexes,begin,current,headPrune,result)

if begin已經超出indexes的范圍,沒有材料可以加入緩存序列

將current中緩存的序列作為結果加入result

遍歷作為結果加入result的材料序列

將材料加入哈希表headPrune緩存

函數返回

if 緩存序列為空

遍歷begin指向的材料及之后的材料

如果該材料已經在哈希表headPrune中出現

函數返回

else

將遍歷到的材料加入緩存序列current

backtrack(indexes,i + 1,current,headPrune,result),遞歸執行

退出新加入緩存序列current的材料

函數返回

else

遍歷begin指向的材料及之后的材料

if 遍歷到的材料加入緩存序列,不違反通板規程

將遍歷到的材料加入緩存序列current

backtrack(indexes,i + 1,current,headPrune,result),遞歸執行

退出新加入緩存序列current的材料

3.5 尾部剪枝

假設待排序的材料是A、B、C、D、E、F、G,以A為開頭的搜索中假設已經搜索到了合法序列A、C、D、E,那么A、C、E和A、D、E這樣的序列就不需要出現在最終的搜索結果中。而且深度優先搜索的特性決定了從A、C、E出發得到的所有后續序列,已經包含在以A、C、D、E出發得到的所有后續序列之中。所以在已經得到以A、C、D、E這樣的結果之后,不需要以其子序列出發再進行搜索。以這種在序列尾部考慮剪枝的方式,可以從另一方向顯著減少搜索的代價,提升結果的質量。

具體的實現方法是,使用一個哈希表來標記已經存在于結果中的材料,在算法回溯的過程中,如果要加入緩存的材料已經出現在結果中,那就不需要搜索下去。比如A、C、D、E已經出現在搜索結果中,當前緩存的序列是A、D,接下來要嘗試將E加入,獲得A、D、E,但是E已經出現在了結果中,所以可以跳過E,直接嘗試加入F,如果加入F滿足通板規程,則得到了一個新的合法序列——A、D、F。新增哈希表tailPrune,緩存前一次遞歸哪些材料已經作為結果輸出,算法偽代碼如下:

backtrack(indexes,begin,current,headPrune,tailPrune,result)

if begin已經超出indexes的范圍,沒有材料可以加入緩存序列

將current中緩存的序列作為結果加入result

遍歷作為結果加入result的材料序列

將材料加入哈希表headPrune緩存

將材料加入哈希表tailPrune緩存

函數返回

if 緩存序列為空

遍歷begin指向的材料及之后的材料

如果該材料已經在哈希表headPrune中出現

函數返回

else

將遍歷到的材料加入緩存序列current

backtrack(indexes,i + 1,current,headPrune,tailPrune,result)

退出新加入緩存序列current的材料

函數返回

else

遍歷begin指向的材料及之后的材料

if 遍歷到的材料沒有出現在哈希表tailPrune中,且加入緩存序列不違反通板規程

創建臨時哈希表tempTailPrune,復制tailPrune

將當前遍歷到材料以后的材料,從tempTailPrune中移除

將遍歷到的材料加入緩存序列current

backtrack(indexes,i + 1,current,headPrune,tempTailPrune,result)

退出新加入緩存序列current的材料

將tempTailPrune中新出現的材料加入tailPrune

3.6 等價材料恢復

經過3.5得到了若干優質的可行解,但是這些解是過濾掉了等價元素的,需要根據3.1緩存的分組關系,將材料恢復。假設得到的結果序列為A0、B0、D0,則經過恢復的序列為A0、A1、B0、B1、B2、D0、D1、D2。

3.7 選取最優解

根據不同的優化目標,可以給材料序列設定不同的打分函數,將打分函數應用于可行解序列,即可選出分數最高的材料序列。例如要選取包含材料數最多的材料序列,可以從前向后遍歷可行解集合,挑選出最長的材料序列。

4 應用效果

算法使用寶鋼某熱鍍鋅產線的實際生產數據進行了試驗,得到如圖1所示結果。從圖1可以看出,算法運行時間隨材料個數增加而上升,但上升趨勢平緩。材料數量在一定范圍內時,算法運行時間與材料數量接近線性相關。熱鍍鋅產線的生產前庫的庫存是有限的,實踐證明,在達到最大庫存的情況下,算法可以在2 s內執行完畢。

圖1 算法運行時間隨輸入材料數變化趨勢圖Fig.1 Tendency chart for time cost of the scheduling algorithm

相比于人工排程或者既有的排程模型,該算法體現出了如下優勢:

(1) 運行速度快。絕大部分情況下,算法可以在2 s內給出結果。

(2) 一次運行,多個最優解。在提前設定好多種優化目標之后,算法運行一次,就可以給出各種優化目標對應的最優解,供計劃員對比和選擇。

(3) 算法通用性高,方便移植。算法對排程問題的假設比較簡單,一是材料有序,二是盡可能將更多地材料排入計劃。只需要根據新產線的情況,定義好材料排序方式、通板規程以及優化目標,即可應用該算法求得最優的材料序列。目前在酸軋排程模型中,已經成功移植了該算法。

5 結論

(1) 寶武集團將綠色作為生命底色和戰略基色,大力推進智慧制造支撐綠色發展,智慧制造能力日漸成為鋼鐵制造企業的核心競爭力。排程作為智慧制造的核心部分,需要開展深入的研究和實踐。

(2) 本文提出了一個算法,可以快速求解排程問題。

(3) 該算法運行速度快;一次執行可以給出多種優化目標下的最優解;具有通用性,易于移植與推廣。

(4) 目前已經應用于寶鋼某熱鍍鋅產線的智能排程,實踐證明了該算法的可行性與優越性,并成功移植到了酸軋產線的排程模型中。