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

甄 卓

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

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

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

1 排程問題分析

在對不同工序、不同產(chǎn)線、不同機組的排程情況進行綜合分析之后,發(fā)現(xiàn)以下幾個方面對算法的設(shè)計有重要影響:

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

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

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

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

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

2 算法組成

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

2.1 等價材料過濾

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

2.2 材料排序

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

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

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

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

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

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

2.4 等價材料恢復

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

2.5 選取最優(yōu)解

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

3 算法實現(xiàn)

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

3.1 等價材料過濾

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

3.2 材料排序

綜合合同優(yōu)先級、工藝要求、生產(chǎn)目標,確定材料排序的方式,以C++標準庫提供過的sort函數(shù)為基礎(chǔ),自己實現(xiàn)排序的方式。比如,如果材料需要按質(zhì)量遞增的順序排序,排序方式以如下方式實現(xiàn):

class WeightUp

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

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

return true;

else

return false;

調(diào)用標注庫排序算法實現(xiàn)材料索引按照材料質(zhì)量遞增的方式排序。其中indexes代表需要待排計劃的材料的索引。

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

3.3 搜索可行解

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

backtrack(indexes,begin,current,result)

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

將current中緩存的序列作為結(jié)果加入result

函數(shù)返回

if 緩存序列為空

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

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

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

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

函數(shù)返回

else

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

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

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

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

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

3.4 頭部剪枝

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

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

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

將current中緩存的序列作為結(jié)果加入result

遍歷作為結(jié)果加入result的材料序列

將材料加入哈希表headPrune緩存

函數(shù)返回

if 緩存序列為空

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

如果該材料已經(jīng)在哈希表headPrune中出現(xiàn)

函數(shù)返回

else

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

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

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

函數(shù)返回

else

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

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

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

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

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

3.5 尾部剪枝

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

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

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

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

將current中緩存的序列作為結(jié)果加入result

遍歷作為結(jié)果加入result的材料序列

將材料加入哈希表headPrune緩存

將材料加入哈希表tailPrune緩存

函數(shù)返回

if 緩存序列為空

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

如果該材料已經(jīng)在哈希表headPrune中出現(xiàn)

函數(shù)返回

else

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

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

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

函數(shù)返回

else

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

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

創(chuàng)建臨時哈希表tempTailPrune,復制tailPrune

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

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

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

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

將tempTailPrune中新出現(xiàn)的材料加入tailPrune

3.6 等價材料恢復

經(jīng)過3.5得到了若干優(yōu)質(zhì)的可行解,但是這些解是過濾掉了等價元素的,需要根據(jù)3.1緩存的分組關(guān)系,將材料恢復。假設(shè)得到的結(jié)果序列為A0、B0、D0,則經(jīng)過恢復的序列為A0、A1、B0、B1、B2、D0、D1、D2。

3.7 選取最優(yōu)解

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

4 應(yīng)用效果

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

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

相比于人工排程或者既有的排程模型,該算法體現(xiàn)出了如下優(yōu)勢:

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

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

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

5 結(jié)論

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

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

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

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