李 濤

中信重工機(jī)械股份有限公司 河南洛陽(yáng) 471039

隨 著全球制造業(yè)市場(chǎng)的競(jìng)爭(zhēng)越來(lái)越激烈，如何提高生產(chǎn)計(jì)劃排程效率成為礦山裝備制造企業(yè)提高市場(chǎng)競(jìng)爭(zhēng)力的重要手段[1]。該類(lèi)型企業(yè)生產(chǎn)的產(chǎn)品屬于重型裝備，擁有復(fù)雜的產(chǎn)品結(jié)構(gòu)和生產(chǎn)流程，具有生產(chǎn)周期長(zhǎng)、重復(fù)率低、單件小批量等特點(diǎn)，對(duì)生產(chǎn)系統(tǒng)的柔性要求較高。同時(shí)，不同零部件需要多個(gè)工廠協(xié)作來(lái)完成生產(chǎn)，進(jìn)一步增加了生產(chǎn)管理的難度。因此，該類(lèi)型企業(yè)需要利用先進(jìn)的 APS 系統(tǒng)來(lái)輔助不同分廠進(jìn)行生產(chǎn)計(jì)劃排程，同時(shí)實(shí)現(xiàn)對(duì)幾十甚至上百個(gè)訂單的生產(chǎn)排程，以達(dá)到提前預(yù)警和按期交貨等目標(biāo)[2]。

生產(chǎn)計(jì)劃排程是礦山裝備制造企業(yè)生產(chǎn)管理的核心環(huán)節(jié)，影響生產(chǎn)效率和客戶滿意度。通過(guò)基于遺傳算法的排程優(yōu)化研究，可以有效解決承制工廠 (生產(chǎn)分廠) 零部件的工序、車(chē)間和資源調(diào)度等問(wèn)題，以此提高生產(chǎn)計(jì)劃排程的效率和精度，降低成本和時(shí)間浪費(fèi)[3]。此外，該研究可以為礦山裝備制造企業(yè)生產(chǎn)管理提供技術(shù)支持和決策依據(jù)，提升企業(yè)的市場(chǎng)競(jìng)爭(zhēng)力。

1 研究?jī)?nèi)容和目標(biāo)

礦山裝備制造企業(yè)目前多采用以訂單為驅(qū)動(dòng)的生產(chǎn)模式，對(duì)生產(chǎn)系統(tǒng)的柔性要求較高，故需要利用先進(jìn)的 APS 系統(tǒng)來(lái)輔助不同承制工廠 (生產(chǎn)分廠) 進(jìn)行生產(chǎn)計(jì)劃排程。分廠級(jí)的排程算法需要嵌入到 APS系統(tǒng)中[4]，根據(jù)企業(yè)生產(chǎn)管理部門(mén)分配的生產(chǎn)任務(wù)和給定的關(guān)鍵節(jié)點(diǎn)計(jì)劃，并考慮多個(gè)訂單的零部件生產(chǎn)工單結(jié)構(gòu)順序、物料可用性以及上游工序預(yù)期完成時(shí)間等信息，解決零部件工序的車(chē)間和資源調(diào)度等問(wèn)題。根據(jù)不同工單的工序、優(yōu)先級(jí)、來(lái)料準(zhǔn)備等特點(diǎn)，將各個(gè)工單的各個(gè)工序合理地排布在可行的車(chē)間、資源和時(shí)間節(jié)點(diǎn)，在滿足交貨期的同時(shí)，降低成本，提高運(yùn)營(yíng)和生產(chǎn)效率。該算法將公司級(jí)主生產(chǎn)計(jì)劃和年度滾動(dòng)計(jì)劃中確定下來(lái)的關(guān)鍵時(shí)間節(jié)點(diǎn)，在組批算法中得到的合成工單作為輸入，并與其緊密銜接，從而實(shí)現(xiàn)在規(guī)定的時(shí)間跨度和交貨期內(nèi)，對(duì)關(guān)鍵工單排程。

初級(jí) APS 系統(tǒng)的排程算法是將工單工序的排程工作拆分為了車(chē)間級(jí)別和資源級(jí)別，并進(jìn)行優(yōu)化。此類(lèi)算法雖然可以做到減少跳線，并能在滿足父子工單關(guān)系的條件下，對(duì)工序進(jìn)行合理安排，但也存在一定的不足：將所有工單一起考慮，問(wèn)題規(guī)模太大，難以對(duì)影響生產(chǎn)交期較大的關(guān)鍵路徑上的工單進(jìn)行優(yōu)先滿足；2 個(gè)層級(jí)算法的基本邏輯都是基于簡(jiǎn)單的規(guī)則形式進(jìn)行實(shí)現(xiàn)，因此排程方案具有很大的局限性。

基于遺傳算法的優(yōu)化排程算法針對(duì)關(guān)鍵路徑工單進(jìn)行生產(chǎn)排程，再基于此對(duì)非關(guān)鍵路徑工單進(jìn)行排程，同時(shí)考慮了工單之間的父子關(guān)系、工單內(nèi)部的順序、車(chē)間之間的較少跳線、關(guān)鍵節(jié)點(diǎn)等，對(duì)“工單—父子關(guān)系—工序—車(chē)間—設(shè)備—時(shí)間節(jié)點(diǎn)”進(jìn)行了排程和優(yōu)化。與此同時(shí)，該算法基于企業(yè)整體的信息集成，融合企業(yè)內(nèi)部多部門(mén)和內(nèi)外部協(xié)同生產(chǎn)節(jié)點(diǎn)信息的更新以及物料達(dá)成等信息，以實(shí)現(xiàn)對(duì)企業(yè)內(nèi)外多部門(mén)的生產(chǎn)協(xié)同進(jìn)行整體統(tǒng)籌。

2 遺傳算法

2.1 基本原理

遺傳算法是由 John Holland 于 20 世紀(jì) 70 年代提出的一種基于種群的元啟發(fā)式算法[5-6]。該算法依據(jù)自然選擇和自然遺傳學(xué)機(jī)制進(jìn)行隨機(jī)全局搜索，在搜索過(guò)程中自動(dòng)獲取和積累有關(guān)搜索空間的知識(shí)，采用概率化的尋優(yōu)方法，不需要確定的規(guī)則就能自動(dòng)獲取和指導(dǎo)優(yōu)化的搜索空間，自適應(yīng)地控制搜索過(guò)程。

遺傳算法主要利用遺傳操作 (交叉、變異等) 對(duì)群體中的個(gè)體進(jìn)行全部或部分替換，不斷適應(yīng)環(huán)境，進(jìn)化到更優(yōu)的狀態(tài)。與其他優(yōu)化算法相比，遺傳算法適用范圍廣，具有全局尋優(yōu)能力、高可靠性、高并行性等優(yōu)點(diǎn)，被廣泛應(yīng)用于組合優(yōu)化、機(jī)器學(xué)習(xí)、人工智能、神經(jīng)網(wǎng)絡(luò)等領(lǐng)域[7-8]。

2.2 遺傳算法框架

遺傳算法的基本思想是模擬生物進(jìn)化過(guò)程搜索最優(yōu)解，因此，其過(guò)程包括個(gè)體的選擇、交叉、變異等要素，形成了遺傳算法的框架。其中，個(gè)體表示可行解決方案；種群是個(gè)體的集合。遺傳算法主要通過(guò)不斷對(duì)種群中的個(gè)體進(jìn)行操作，來(lái)逐漸搜索最優(yōu)解。

遺傳算法的框架為[9]：

(1) 初始化，隨機(jī)生成一組初始個(gè)體，即種群；

(2) 適應(yīng)度評(píng)價(jià)，對(duì)種群中的每個(gè)個(gè)體的成本、效益和適應(yīng)度等進(jìn)行評(píng)價(jià)；

(3) 選擇操作，根據(jù)適應(yīng)度大小，選擇一定數(shù)量的個(gè)體作為父代；

(4) 交叉操作，隨機(jī)選擇一對(duì)父代，利用交叉算子實(shí)現(xiàn)基因交換，產(chǎn)生新的個(gè)體；

(5) 變異操作，對(duì)新的個(gè)體進(jìn)行一定的概率變異操作，產(chǎn)生新的解決方案；

(6) 替換操作，根據(jù)適應(yīng)度，選擇新個(gè)體和舊個(gè)體進(jìn)行替換，形成新的種群；

(7) 結(jié)束判斷，達(dá)到指定迭代次數(shù)或滿足精度要求時(shí)終止，返回最優(yōu)解。

2.3 基本操作

2.3.1 編碼和解碼

在遺傳算法中，個(gè)體需要進(jìn)行編碼和解碼。編碼是將決策變量轉(zhuǎn)換成目標(biāo)函數(shù)值，計(jì)算機(jī)可處理的二進(jìn)制表達(dá)式的過(guò)程。不同的編碼方式適用于不同類(lèi)型的函數(shù)問(wèn)題，例如，二進(jìn)制編碼適用于多目標(biāo)函數(shù)優(yōu)化；浮點(diǎn)編碼適用于連續(xù)性變量的優(yōu)化；排列編碼適用于旅行商問(wèn)題等。解碼是指將二進(jìn)制編碼重構(gòu)為原始問(wèn)題的過(guò)程。

2.3.2 選擇操作

選擇操作是根據(jù)適應(yīng)度大小，選擇一部分個(gè)體作為父代，這里的適應(yīng)度通常定義為目標(biāo)函數(shù)值或評(píng)價(jià)函數(shù)值。優(yōu)秀的個(gè)體被選中，不良的個(gè)體被淘汰。常見(jiàn)的適應(yīng)度選擇方法有輪盤(pán)選擇、錦標(biāo)賽選擇、最小競(jìng)標(biāo)賽等。

2.3.3 交叉操作

交叉操作是指將選出的父代進(jìn)行重組操作，產(chǎn)生新的個(gè)體。重組的方式常見(jiàn)有單點(diǎn)交叉、多點(diǎn)交叉、均勻交叉、基因重組等，交叉方式也根據(jù)問(wèn)題的性質(zhì)進(jìn)行調(diào)整。對(duì)于連續(xù)性變量問(wèn)題，可以采用基于結(jié)果隨機(jī)化的交叉方式，比如 BLX-α 交叉；對(duì)于多目標(biāo)問(wèn)題，則可以采用向量交叉，實(shí)現(xiàn)多目標(biāo)優(yōu)化。

2.3.4 變異操作

變異操作是指在交叉操作后對(duì)個(gè)體進(jìn)行一定概率的操作，產(chǎn)生新的解決方案。變異操作通常是單點(diǎn)變異，即隨機(jī)選擇一個(gè)基因位置，并改變其值。在實(shí)際應(yīng)用中，變異率設(shè)置過(guò)大會(huì)導(dǎo)致算法陷入局部最優(yōu)解，因此應(yīng)該根據(jù)具體問(wèn)題進(jìn)行設(shè)置。

2.3.5 替換操作

替換操作是在交叉和變異操作后，根據(jù)適應(yīng)度，選擇新個(gè)體和舊個(gè)體進(jìn)行替換，形成新的種群。常見(jiàn)的替換方式有全替換、部分替換等。

2.4 遺傳算法的優(yōu)缺點(diǎn)

遺傳算法作為一種常用的優(yōu)化算法，其優(yōu)缺點(diǎn)如下[10]。

2.4.1 遺傳算法的優(yōu)點(diǎn)

(1) 可以尋找全局最優(yōu)解，具有較強(qiáng)的全局尋優(yōu)能力；

(2) 算法具有較高的可靠性，能夠避免局部最優(yōu)解；

(3) 算法具有高度的并行性，可以利用并行處理技術(shù)進(jìn)行優(yōu)化；

(4) 算法適用范圍廣，可以用于多種類(lèi)型的問(wèn)題。

2.4.2 遺傳算法的缺點(diǎn)

(1) 遺傳算法的收斂速度相對(duì)較慢，需要較多的迭代次數(shù)；

(2) 在編碼、交叉、變異等操作中需要設(shè)置一系列參數(shù)，參數(shù)對(duì)算法效果影響較大；

(3) 操作不當(dāng)時(shí)，遺傳算法也有可能造成早熟現(xiàn)象，即過(guò)早收斂到局部最優(yōu)解。

3 排程優(yōu)化

3.1 輸入信息

遺傳算法的輸入信息包括：

(1) 產(chǎn)品對(duì)應(yīng)的物料信息；

(2) 資源及日歷信息；

(3) 需要生產(chǎn)的工單、工序和工藝信息，包括父子工單關(guān)系、工序順序以及工單的最早開(kāi)始時(shí)間和最晚結(jié)束時(shí)間 (節(jié)點(diǎn)交期)；

(4) 生產(chǎn)時(shí)間期量工序生產(chǎn)時(shí)間和提前期，換線時(shí)間，制造效率 (用于修正實(shí)際的制造時(shí)長(zhǎng))；

(5) 物料供應(yīng)鏈信息物料庫(kù)存、采購(gòu)、到貨等信息；

(6) 生產(chǎn)計(jì)劃，包括公司級(jí)主生產(chǎn)計(jì)劃、年度滾動(dòng)計(jì)劃中確定的關(guān)鍵時(shí)間節(jié)點(diǎn)；

(7) 工單、工序的預(yù)排車(chē)間信息，如有此信息，則基于此進(jìn)行車(chē)間線體排程；

(8) 外協(xié)線體及其能力約束，可以為無(wú)限，對(duì)應(yīng)外協(xié)無(wú)限產(chǎn)能概念。

3.2 排程算法框架

產(chǎn)品的生產(chǎn)時(shí)長(zhǎng)主要取決于該訂單關(guān)鍵路徑上的工單生產(chǎn)時(shí)長(zhǎng)。該部分工單的生產(chǎn)時(shí)間較長(zhǎng)或其所占用關(guān)鍵的設(shè)備資源有限，如何對(duì)關(guān)鍵路徑上的工單進(jìn)行生產(chǎn)排程是個(gè)重要問(wèn)題。另外，除了關(guān)鍵路徑上的生產(chǎn)工單外，由于產(chǎn)品結(jié)構(gòu)復(fù)雜且零部件繁多，故而也需要對(duì)所有的非關(guān)鍵路徑的工單進(jìn)行排程。首先利用遺傳算法對(duì)關(guān)鍵路徑工單進(jìn)行排程優(yōu)化，然后考慮父子工單關(guān)系等約束，利用一定的規(guī)則對(duì)非關(guān)鍵路徑工單進(jìn)行排程，分廠級(jí) APS 排程算法框架圖如圖1所示。

圖1 分廠級(jí) APS 排程算法框架Fig.1 Branch level APS scheduling algorithm framework

3.3 關(guān)鍵路徑工單排程

首先對(duì)不同訂單的關(guān)鍵路徑使用遺傳算法進(jìn)行排程。

(1) 針對(duì)離散型裝備制造企業(yè)的排程，考慮父子工單關(guān)系以及工單內(nèi)部的工序，設(shè)計(jì)合理的編碼規(guī)則；

(2) 考慮車(chē)間減少跳線以及資源設(shè)備在成本、時(shí)間、優(yōu)先級(jí)等方面的權(quán)重考量，設(shè)計(jì)合理的解碼規(guī)則；

(3) 初始化種群；

(4) 設(shè)計(jì)合理的適應(yīng)度函數(shù)，并對(duì)其進(jìn)行計(jì)算，篩選出更優(yōu)解；

(5) 對(duì)種群進(jìn)行選擇、交叉、變異操作，產(chǎn)生下一代遺傳編碼；

(6) 重復(fù)以上過(guò)程，對(duì)排程結(jié)果不斷迭代優(yōu)化，直到滿足條件，得到最終的排程優(yōu)化結(jié)果。

3.4 非關(guān)鍵路徑工單排程

在關(guān)鍵路徑工單排程計(jì)劃的基礎(chǔ)上，基于優(yōu)先級(jí)規(guī)則對(duì)非關(guān)鍵路徑工單進(jìn)行啟發(fā)式的排程。同樣，也需要考慮工單的父子關(guān)系、工單內(nèi)部的工序順序、工單工序的車(chē)間線體選擇、工單工序的資源設(shè)備選擇以及開(kāi)始生產(chǎn)時(shí)間節(jié)點(diǎn)等內(nèi)容。

根據(jù)離散型裝備制造企業(yè)生產(chǎn)組織方式，整個(gè)協(xié)同制造體系包括很多外部協(xié)同制造過(guò)程，包括工藝性和能力性外協(xié)，因此在以上排程算法和規(guī)則中，將外部協(xié)同制造作為一個(gè)車(chē)間線體 (該車(chē)間實(shí)際為一個(gè)虛擬車(chē)間，僅用于表示工單的外部協(xié)同制造)，根據(jù)企業(yè)“無(wú)限產(chǎn)能”的理念，可以將該車(chē)間的產(chǎn)能設(shè)置為無(wú)限大，也可以設(shè)置一定的約束。

3.5 多訂單關(guān)鍵路徑工單生產(chǎn)排程算法

3.5.1 編碼規(guī)則

算法的關(guān)鍵點(diǎn)之一便是編碼規(guī)則。遺傳算法通過(guò)染色體的基因信息對(duì)索要決策的內(nèi)容進(jìn)行編碼。針對(duì)離散型裝備制造企業(yè)的生產(chǎn)排程，筆者提出了一個(gè)同時(shí)考慮父子工單以及工序的編碼方式。

首先，染色體中每個(gè)數(shù)字代表對(duì)應(yīng)工單編號(hào)，如：工單 1、2、3 等，同一數(shù)字出現(xiàn)的次數(shù)代表該工單擁有的工序數(shù)量，而同一數(shù)字出現(xiàn)的先后順序則代表工單內(nèi)部的工序順序。如圖2 所示，Oi,k表示第i個(gè)工單的第k道工序。從左至右，O3,1代表工單 3 的第1 道工序；O1,1代表工單 1 的第 1 道工序；O2,1代表工單 2 的第 1 道工序；O2,2代表工單 2 的第 2 道工序，以此類(lèi)推。通過(guò)這種編碼方式即可實(shí)現(xiàn)工單內(nèi)不同工序順序的排序。

圖2 染色體示例Fig.2 Chromosome example

其次，在實(shí)際的生產(chǎn)過(guò)程中，必須滿足父子工單的順序關(guān)系。因此，本部分的染色體編碼規(guī)則可根據(jù)BOM 結(jié)構(gòu)/工單樹(shù)中的父子工單關(guān)系，對(duì)訂單中多工單的加工順序進(jìn)行調(diào)整。具體的，找到父子工單關(guān)系中最高層級(jí)的父工單，并以此作為染色體調(diào)整起點(diǎn)，依次向下一層級(jí)進(jìn)行修復(fù)。修復(fù)的過(guò)程如下：對(duì)每一個(gè)父工單對(duì)應(yīng)的工序節(jié)點(diǎn)進(jìn)行檢查，若該父工單工序的右側(cè)存在子工單工序，則兩者交換，直到父工單的全部工序檢查完畢，順延至下一層級(jí)重復(fù)修復(fù)過(guò)程。以“1→4”為例，假設(shè)工單 1 是工單 4 的子工單，那么染色體的修復(fù)過(guò)程如圖3 所示。

圖3 染色體修復(fù)過(guò)程Fig.3 Chromosome repair procedure

通過(guò)以上的編碼規(guī)則和調(diào)整修復(fù)過(guò)程，即可實(shí)現(xiàn)染色體工單內(nèi)部工序順序以及父子工單關(guān)系的要求。

3.5.2 解碼規(guī)則

在種群解碼過(guò)程中，采用基于空閑時(shí)間段的主動(dòng)調(diào)度工序解碼方法以獲得可行序列解，即新的待排序工序需要同時(shí)滿足車(chē)間分配、資源分配、以及考慮物料問(wèn)題，在對(duì)已排序工序開(kāi)工時(shí)間不產(chǎn)生影響的基礎(chǔ)上，根據(jù)當(dāng)前機(jī)器空閑時(shí)間，安排至最早可開(kāi)工的時(shí)間點(diǎn)。

3.5.3 車(chē)間分配

對(duì)工單中不同工序進(jìn)行車(chē)間分配，總體目標(biāo)是減少同一工單在不同車(chē)間之間的轉(zhuǎn)換，從而減少跳線時(shí)間和降低跳線成本。通過(guò)構(gòu)建整數(shù)規(guī)劃模型的方法，以工單工序之間的跳線最小化為目標(biāo)，對(duì)工單內(nèi)部各道工序進(jìn)行車(chē)間分配決策。模型參數(shù)包括各工單的工序以及對(duì)應(yīng)的車(chē)間信息。對(duì)每一個(gè)工單運(yùn)行一次分配決策，可完成對(duì)所有工單的車(chē)間預(yù)分配工作。

模型的目標(biāo)函數(shù)為

式中：wi,i+1,m,n為工序i到工序i+1 之間，從車(chē)間m跳線到車(chē)間n的成本 (權(quán)重)；yi,i+1,m,n為 0～1 決策變量，若為 1，則代表工序i到工序i+1 之間，從車(chē)間m跳線到車(chē)間n；xi,m為 0～1 決策變量，若為 1，則代表工序i分配到車(chē)間m內(nèi)；xi+1,n為 0～1 決策變量，若為 1，則代表工序i+1 分配到車(chē)間n內(nèi)。

第1 個(gè)約束用于保證每道工序只可能被分配到一個(gè)車(chē)間；第 2、3、4 個(gè)約束用于保證，只有當(dāng)跳線真實(shí)發(fā)生的情況下，0～1 決策變量的值才為 1；第 5、6、7 個(gè)約束規(guī)定變量類(lèi)型。

另外，也可在此模型中增加負(fù)荷平衡等因素和目標(biāo)，即在對(duì)工單工序分配車(chē)間的過(guò)程中，考慮不同車(chē)間資源的負(fù)荷平衡，最小化跳線。

3.5.4 資源分配

在車(chē)間分配的基礎(chǔ)上，對(duì)車(chē)間的資源進(jìn)行工序分配。采取啟發(fā)式基于資源權(quán)重規(guī)則的資源分配方法，將各項(xiàng)需要考慮的資源約束限制賦予不同的權(quán)重，并累加在一起，選取最合適該道工序的資源。各項(xiàng)資源約束限制有：加工成本最小、間隔時(shí)間最小、工作完工時(shí)間最小、該工作與前一道工序的工作的時(shí)間間隔最小、制造時(shí)間最少和占用負(fù)荷量最小的資源。

3.5.5 排程結(jié)果

基于染色體編碼，從左到右依次對(duì)工序進(jìn)行排程?？紤]前序工單完成時(shí)間＋物料提前期 (若物料充足，則提前期為 0)，逐一安排工序—車(chē)間—機(jī)器—時(shí)間點(diǎn)。甘特圖排程結(jié)果如圖4 所示。灰色部分代表物料沒(méi)有及時(shí)到達(dá)造成的提前期，通過(guò)以上解碼方法生成完整的排程結(jié)果。

圖4 甘特圖排程Fig.4 Gantt chart scheduling

利用企業(yè)集成的信息平臺(tái)，將不同訂單生產(chǎn)中與其他部門(mén)或外部協(xié)同工廠生產(chǎn)節(jié)點(diǎn)信息以及物料可用性等信息更新到模型中，從而得到與實(shí)際生產(chǎn)過(guò)程更為匹配的生產(chǎn)計(jì)劃排程方案。

3.5.6 適應(yīng)度函數(shù)

遺傳算法中判別解 (染色體) 的好壞，是通過(guò)適應(yīng)度函數(shù)的計(jì)算來(lái)實(shí)現(xiàn)。采用的函數(shù)計(jì)算規(guī)則如下：權(quán)重 (1)×生產(chǎn)成本＋權(quán)重 (2)×最大完工時(shí)間＋權(quán)重(3)×關(guān)鍵時(shí)間節(jié)點(diǎn)逾期懲罰項(xiàng)。

3.5.7 交叉、變異算子

交叉算子包括：①單點(diǎn)交叉，通過(guò)選取兩條染色體，在隨機(jī)選擇的位置點(diǎn)上進(jìn)行分割并交換右側(cè)的部分，從而得到兩個(gè)不同的子染色體；②兩點(diǎn)交叉，是指在個(gè)體染色體中隨機(jī)設(shè)置了兩個(gè)交叉點(diǎn)，然后再進(jìn)行部分基因交換；③多點(diǎn)交叉，是指在個(gè)體染色體中隨機(jī)設(shè)置多個(gè)交叉點(diǎn)，然后進(jìn)行基因交換；④ 部分匹配交叉，保證每個(gè)染色體中的基因僅出現(xiàn)一次，通過(guò)該交叉策略在一個(gè)染色體中不會(huì)出現(xiàn)重復(fù)的基因。在交叉操作結(jié)束后，對(duì)染色體的可行性進(jìn)行判斷，如果不可行，則進(jìn)行修復(fù)。

變異算子包括：①將位翻轉(zhuǎn)突變應(yīng)用于二進(jìn)制染色體時(shí)，隨機(jī)選擇一個(gè)基因，其值被翻轉(zhuǎn) (求補(bǔ))；②將交換突變應(yīng)用于二進(jìn)制或整數(shù)的染色體時(shí)，將隨機(jī)選擇 2 個(gè)基因并交換其值；③倒換突變應(yīng)用后，將選擇一個(gè)隨機(jī)基因序列，并將該序列中的基因順序打亂 (或倒換)。在變異操作結(jié)束后，對(duì)染色體的可行性進(jìn)行判斷，如果不可行，則進(jìn)行修復(fù)。

3.6 基于規(guī)則的非關(guān)鍵路徑工單生產(chǎn)排程算法

在關(guān)鍵路徑工單已經(jīng)排程完畢的基礎(chǔ)上，采用基于優(yōu)先級(jí)規(guī)則的啟發(fā)式分配方法，再對(duì)非關(guān)鍵路徑工單進(jìn)行相應(yīng)的排程。

(1) 考慮父子工單將工單進(jìn)行層級(jí)分解，從最高層級(jí)父工單開(kāi)始進(jìn)行工單分層，排程規(guī)則均從最高層級(jí)父工單開(kāi)始，依次運(yùn)行算法排程。

(2) 考慮同層級(jí)工單、工序順序選中當(dāng)前層級(jí)的工單 (由于同層級(jí)，因此互不影響)，根據(jù)優(yōu)先級(jí)進(jìn)行排序，并由高到低依次輸入算法。優(yōu)先級(jí)的規(guī)定除人為指定外，可以將以下幾點(diǎn)進(jìn)行自由組合并排出優(yōu)先級(jí)：交貨期 (升序/降序)、工單最早開(kāi)始時(shí)刻 (升序/降序)、工單人為優(yōu)先級(jí) (升序/降序)、工單制造數(shù)量(升序/降序)、工單最晚結(jié)束時(shí)間 (升序/降序)、工單余裕度 (升序/降序)、先到先做 (升序/降序)。

(3) 開(kāi)始時(shí)間節(jié)點(diǎn)的排程方法對(duì)工序進(jìn)行排程需要同時(shí)滿足車(chē)間分配、資源分配以及考慮物料問(wèn)題，且對(duì)已排序工序開(kāi)工時(shí)間不產(chǎn)生影響的基礎(chǔ)上，根據(jù)當(dāng)前機(jī)器空閑時(shí)間，安排至最早可開(kāi)工的時(shí)間點(diǎn)，即不存在可以加工任意可加工工序的空閑時(shí)間段。

4 結(jié)語(yǔ)

通過(guò)對(duì)遺傳算法進(jìn)行介紹，重點(diǎn)闡述了遺傳算法在礦山裝備離散制造企業(yè)排程優(yōu)化模型設(shè)計(jì)應(yīng)用的研究過(guò)程。在研究過(guò)程中，進(jìn)一步驗(yàn)證了遺傳算法具有較高的求解效率和廣泛的適應(yīng)性。

遺傳算法能夠?qū)ふ胰肿顑?yōu)解，保證算法的全局尋優(yōu)能力，但是在編碼、交叉、變異等操作過(guò)程中，需要設(shè)置一系列參數(shù)。其對(duì)參數(shù)的選取十分敏感，選取不合理，可能會(huì)影響算法的效果。此外，遺傳算法的收斂速度相對(duì)較慢，需要較多的迭代次數(shù)，因此算法在處理大規(guī)模或者高維度優(yōu)化問(wèn)題時(shí)比較困難。

在未來(lái)的理論研究和算法模型應(yīng)用中，可以利用遺傳算法結(jié)合其他方法，如人工神經(jīng)網(wǎng)絡(luò)、模擬退火等來(lái)進(jìn)行研究，以進(jìn)一步提升算法的效率與精度。另外，如何解決算法早熟現(xiàn)象和局部最優(yōu)解等問(wèn)題，值得進(jìn)一步深入研究。