零等待流水車間與并行機調(diào)度問題及其在煉鋼—連鑄過程中的應(yīng)用研究.pdf

1、在零等待流水車間調(diào)度問題中，生產(chǎn)過程的各級工序之間沒有任何緩沖空間，且工件加工完畢后不能停留在加工機器上，工件在上一級工序的加工結(jié)束時間必須與下一級工序的開始作業(yè)時間相同并且工件在車間的流向是單向的。進一步，如果至少有一級工序上存在多臺功能相同的加工機器時稱為零等待混合流水車間調(diào)度問題。這類制造環(huán)境在諸如冶金和化工等工業(yè)過程中普遍存在。例如在鋼鐵生產(chǎn)企業(yè)的煉鋼-連鑄生產(chǎn)過程中，零等待調(diào)度的實現(xiàn)，可以減少鋼水在空氣中的溫降，對實現(xiàn)熱送熱裝

2、的生產(chǎn)方式起著重要的作用。 在混合流水車間加工環(huán)境中往往存在瓶頸環(huán)節(jié)，而整個生產(chǎn)過程的效率又常常是由瓶頸環(huán)節(jié)決定的。盡管并行機調(diào)度問題可以看作是混合流水車間的一個特例，但是，基于解決瓶頸環(huán)節(jié)的重要性，有必要單獨對并行機問題進行深入的研究。煉鋼-連鑄過程中鋼水的澆鑄通常是在幾臺功能相同的并排連鑄機完成的。鋼水在連鑄機上的澆鑄具有很多約束條件，是整個生產(chǎn)過程中的瓶頸環(huán)節(jié)，對并行機上的成組調(diào)度問題的研究，為連鑄與軋制環(huán)節(jié)的工序匹配和能

3、源節(jié)約提供了保障。 本文以煉鋼-連鑄過程為背景，對零等待流水車間和并行機調(diào)度中的若干問題進行了深入的研究。由于這些問題都是NP-難問題，無法找到可以精確求得最優(yōu)解的多項式時間算法，因此發(fā)展快速求得近似解的有效算法是本文的研究重點。本文的主要貢獻如下： 1.研究優(yōu)化目標為總流程時間最小化的兩機和三機零等待流水車間調(diào)度問題。在兩機問題中將工件在每臺機器上的處理過程分為調(diào)整、加工和移除三個相互分離的部分；在三機問題中將工件在每

4、臺機器上的處理過程分為調(diào)整和加工兩個相互分離的部分。而經(jīng)典的流水車間調(diào)度算法為了簡化問題的求解難度，不考慮工件在機器上所需的調(diào)整時間和移除時間，或者簡單的把調(diào)整和移除時間并入加工時間。顯然本文的處理方法更符合生產(chǎn)過程的實際情況。討論了最優(yōu)解中工件排列應(yīng)滿足的條件，并結(jié)合貪婪式的搜索機制提出了能夠快速求得近優(yōu)解的啟發(fā)式算法。 2.對于機器數(shù)目大于三的零等待流水車間調(diào)度問題，簡單的啟發(fā)式算法所求得的調(diào)度結(jié)果往往并不理想。遺傳算法、禁

5、忌搜索等具有全局搜索能力的智能優(yōu)化算法已被證明可以很好的近似求解大規(guī)模的NP-難優(yōu)化問題，但往往由于收斂速度慢、對算法參數(shù)敏感以致于很難在實際生產(chǎn)過程中應(yīng)用。將遺傳算法和所求問題的結(jié)構(gòu)信息與已有的啟發(fā)式算法結(jié)合，提出了混合遺傳算法。在算法的求解質(zhì)量和求解速度兩個方面獲得了滿意的折衷，為智能優(yōu)化算法在實際工程中的應(yīng)用奠定了基礎(chǔ)。仿真計算表明，所提出的混合遺傳算法優(yōu)于目前已有的算法。 3.研究優(yōu)化目標為最大完工時間最小化的零等待混合

6、流水車間問題。首先研究了一類特殊的兩級問題并給出了基于Johnson規(guī)則的啟發(fā)式算法，在該類問題中第一級只有一臺可以利用的機器，第二級具有多臺相同的并行機器，并且考慮與工件作業(yè)時間分離的設(shè)備調(diào)整時間和移除時間。對于多級零等待混合流水車間調(diào)度問題提出了構(gòu)造完整調(diào)度方案的方法，改進了一種用于求解一類無中間緩沖區(qū)但非零等待的混合流水車間問題的近似求解算法，計算結(jié)果表明了算法的有效性。 4.研究優(yōu)化目標為總提前/拖后完工時間最小化的并行

7、機成組調(diào)度問題，提出了三階段的啟發(fā)式算法。首先把并行機問題看成單機問題，以最小化總拖后時間為目標排列工件的加工次序；然后將已排序的工件分配給并行的各機器，并適當調(diào)整工件的次序以減小調(diào)整時間從而減小各機器上后面工件的完成時間，達到減小工件總拖后時間的目的；最后采用GTW算法對各機器上的工件調(diào)度插入適當?shù)目臻e時間以求獲得最小的總提前/拖后完工時間。為進一步提高算法的求解質(zhì)量在所提出的啟發(fā)式算法的第一階段引入遺傳搜索過程，提出了能夠在合理的計

8、算時間內(nèi)求得高質(zhì)量近優(yōu)解的混合遺傳算法。 5.將零等待流水車間調(diào)度算法、并行機成組調(diào)度算法，應(yīng)用于煉鋼-連鑄生產(chǎn)調(diào)度仿真系統(tǒng)，并開發(fā)了相應(yīng)的軟件。該調(diào)度仿真系統(tǒng)接受日計劃下達的生產(chǎn)指令，以熱軋階段預(yù)排序得到的連鑄坯的要料期作為計劃的交貨期，合理的安排在各工序上的加工設(shè)備和加工順序計劃。與計劃層和熱裝工序的緊密配合實現(xiàn)了煉鋼-連鑄-熱軋生產(chǎn)過程的一體化管理。與傳統(tǒng)的連鑄坯裝爐加熱軋制工藝比較，具有節(jié)能，提高產(chǎn)品質(zhì)量和成材率，簡化工