不確定條件下車間調(diào)度混合算法的調(diào)度優(yōu)化策略

黨欣旸

摘要：隨著時(shí)代的發(fā)展，國際經(jīng)濟(jì)競爭日趨激烈。人們對產(chǎn)品的要求逐步增高，使得企業(yè)對工件的時(shí)間規(guī)劃和做工要求上更加精益求精。實(shí)際生產(chǎn)的不確定性也越來越受到各界的重視，諸如機(jī)器發(fā)生故障的不確定性、用戶具體要求的模糊性、工件實(shí)際加工時(shí)間的模糊性等不確定因素也在車間調(diào)度中被加以考慮。而這類問題也由于更接近于實(shí)際生產(chǎn)活動而倍受關(guān)注，諸類不可預(yù)測事件具有動態(tài)性，相較于確定性的問題難度有所加深，算法也更加復(fù)雜。通過眾多學(xué)者的不斷努力，目前已經(jīng)出現(xiàn)不少的研究成果。

關(guān)鍵詞：生產(chǎn)調(diào)度；不確定性；調(diào)度建模；調(diào)度算法

1.隨機(jī)模擬和期望值函數(shù)

車間調(diào)度問題作為一個(gè)NP復(fù)雜度問題，通常用一個(gè)非線性規(guī)劃模型來描述。隨機(jī)規(guī)劃模型的一般表示形式為（1.1）：

期望值反映的是變量的平均值，能夠一定程度上體現(xiàn)隨機(jī)變量的某些特征。期望值對一些隨機(jī)問題具有非常重要的意義。因此，如果利用隨機(jī)變量期望值的性質(zhì)，上述（1.1）可以轉(zhuǎn)化為下面的隨機(jī)規(guī)劃模型：

2.隨機(jī)模擬目標(biāo)函數(shù)的確定

用Ri表示車間中的m臺可用設(shè)備；n個(gè)工件則對應(yīng)了有Tn個(gè)訂單生產(chǎn)任務(wù)，每個(gè)工件包含Ki道工序來源于其對應(yīng)的加工工序集OPiKi并由它決定了Ti的取值，記作Ti={OPi1，OPi2，…，OPiKi}；設(shè)備用Rj（1

在實(shí)際生產(chǎn)的過程中可能會產(chǎn)生許多不確定的客觀因素而影響調(diào)度的執(zhí)行，從而影響實(shí)際作業(yè)需要完成的目標(biāo)。所以要對調(diào)度進(jìn)行優(yōu)化，本文的優(yōu)化目標(biāo)是完工時(shí)間較短和成本消耗較低。對于一個(gè)需要進(jìn)行生產(chǎn)調(diào)度的訂單來說，由于所包含的零部件的工藝復(fù)雜性程度存在差別，可以取“最慢工件任務(wù)的完工周期最短”作為時(shí)間目標(biāo)，設(shè)置信概率為η，pt表示平均加工時(shí)間，則可以用機(jī)會約束描述為：

3.生成目標(biāo)函數(shù)

車間調(diào)度的目標(biāo)之一是調(diào)度時(shí)間的最小化，不確定條件下的作業(yè)車間調(diào)度模型同樣要求得到的調(diào)度作業(yè)序列是一個(gè)作業(yè)時(shí)間最短的序列。而在企業(yè)的生產(chǎn)車間中，往往是n個(gè)加工順序不同的工件以不同的時(shí)間在m臺機(jī)器上完成加工，工序之間往往存在前后約束，所以調(diào)度時(shí)間的目標(biāo)應(yīng)該是最小化最大完工時(shí)間，所以，模型得到每一個(gè)調(diào)度作業(yè)序列所包含工件的最大完成時(shí)間，即Cmax，定義了調(diào)度模型的調(diào)度任務(wù)，即調(diào)度序列不包括已完成的工序或工件且不包括已著手的工序（該部分工序應(yīng)該繼續(xù)加工至該工序結(jié)束后再安排它工序）；運(yùn)用描述了模型對于時(shí)間評估因素的要求，即得到的N個(gè)調(diào)度方案中要求取調(diào)度時(shí)間最小化的調(diào)度作業(yè)序列。評估調(diào)度時(shí)間，可以按照調(diào)度時(shí)間最小化合理調(diào)度安排各作業(yè)，同理，各個(gè)作業(yè)間如果進(jìn)行了合理調(diào)度，則各機(jī)器空余時(shí)間自然會現(xiàn)對變少，滿足作業(yè)車間對加工時(shí)間最小化的目標(biāo)?；谶@些考量，目標(biāo)函數(shù)可以表示為：

小結(jié)

本章采取通過神經(jīng)網(wǎng)絡(luò)逼近隨機(jī)模擬的方式，成功的模擬了實(shí)際加工情況中的動態(tài)事件發(fā)生的不確定性，并用改進(jìn)的優(yōu)化算法尋優(yōu)并與單純的遺傳算法和退火模擬算法做對比顯示出了改進(jìn)算法的優(yōu)越性。（作者單位：大連交通大學(xué)）

參考文獻(xiàn)：

[1]王書鋒，鄒益仁.車間作業(yè)調(diào)度（JSSP）技術(shù)問題簡明綜述[J].系統(tǒng)工程理論與實(shí)踐.2003，1：49-55.

[2]陳永亮，徐燕申，張冠偉.基于知識的模塊化柔性生產(chǎn)線快速設(shè)計(jì)系統(tǒng).組合機(jī)床與自動化加工技術(shù)，2002（7）：4一20.

[3]范路橋，常會友，朱旭東.作業(yè)調(diào)度問題研究[J].現(xiàn)代計(jì)算機(jī)（專業(yè)版），2005，187：21-25.

[4]X U Zhenhao，GU Xingsheng.Scheduling algorithm for flow-shop under uncertainty with zero wait [J].Computer Integrated Manufacturing Systems，2004，10（10）：1247-1251.

[5]李郝林，施展.遺傳算法在生產(chǎn)調(diào)度應(yīng)用中的關(guān)鍵技術(shù)[J].組合機(jī)床與白動化加工技術(shù)，2003，7：27-31.