馮大光，唐立新
東北大學(xué)物流優(yōu)化與控制研究所，遼寧省制造系統(tǒng)與物流優(yōu)化重點實驗室，遼寧沈陽

沈陽農(nóng)業(yè)大學(xué)理學(xué)院，遼寧沈陽

摘　　　要：ｎ個工件要在一臺有高度限制的批處理機上分批進(jìn)行加工，工件ｊ的加工時間和高度分別為ｐｊ和ｓｊ，批的加工時間為批中加工時間較大的工件的加工時間，每批加工時，機器的剩余量為批處理機的高度與批中工件的高度和之差，目標(biāo)函數(shù)較小化機器空余總量和工件總完成時間，該ＮＰ�搽y問題源于鋼鐵企業(yè)的罩式退火爐調(diào)度問題。基于部分工件分批性質(zhì)，提出貪婪算法；提出工件ＳＰＴ順序的較優(yōu)分批－動態(tài)規(guī)劃算法，并對兩種算法進(jìn)行了比較。為了進(jìn)一步檢驗算法，把動態(tài)規(guī)劃算法應(yīng)用于總完成時間較小化問題，與已有算法進(jìn)行了比較；根據(jù)相鄰批的工件加工時間的取值，提出分批修改規(guī)則，并與動態(tài)規(guī)劃結(jié)合實現(xiàn)局域搜索算法（ＤＰＬＳ），通過仿真實驗表明ＤＰＬＳ算法非常有效。

關(guān)　鍵　詞：罩式退火爐；批處理機；貪婪算法；動態(tài)規(guī)劃；局域搜索

１　引　言

鋼鐵企業(yè)生產(chǎn)的板卷具有一定的高度，為改變其物理結(jié)構(gòu)滿足市場的需求，需要利用罩式退火爐進(jìn)行退火。板卷根據(jù)的用途不同，退火時間也不同，一般需要４�玻堤鞎r間。罩式退火爐具有一定的高度，只要放入爐內(nèi)的板卷高度之和不超過爐子的高度，多個板卷就可以疊放，同時進(jìn)行退火，同時結(jié)束退火。多個板卷同時進(jìn)行退火時，以其中退火時間較長板卷的退火時間作為共同的退火時間，同時退火的板卷稱為批。需要退火處理的板卷往往很多，而罩式退火爐的數(shù)量又有限，所以如何對板卷進(jìn)行分批，使得進(jìn)行爐子充分利用是一個迫切需要解決的問題。在進(jìn)行組批時，應(yīng)盡量使?fàn)t子空余總量較小，并且不能把退火時間相差較多的板卷放在一起，避免加熱燃料的浪費和待退火板卷庫存的增加，對于國家提倡的創(chuàng)建“節(jié)約型社會” 具有十分重要的意義。

登錄網(wǎng)站后可下載文件