基于改進(jìn)遺傳算法的輻照膜訂單排產(chǎn)研究*

王嘉樂，鄭飂默

(1.中國科學(xué)院大學(xué)，北京 100039；2.中國科學(xué)院沈陽計(jì)算技術(shù)研究所 高檔數(shù)控國家工程研究中心， 沈陽 110168；3.沈陽高精數(shù)控技術(shù)有限公司，沈陽 110168)

0 引言

在全球能源轉(zhuǎn)型的浪潮下，新能源作為油氣燃料的替代品，它的發(fā)展一直是世界關(guān)注的焦點(diǎn)，各種新材料不斷被提出。其中新能源汽車作為新能源應(yīng)用的典型代表，產(chǎn)銷規(guī)模急劇擴(kuò)大，電池作為新能源汽車的核心部件，僅2018上半年，鋰電池隔膜的總生產(chǎn)量就達(dá)到了7.6億平方米[1-2]。巨大的市場需求使得電池隔膜的研究生產(chǎn)成為了國內(nèi)外研究的熱點(diǎn)。

目前，業(yè)界普遍使用智能優(yōu)化算法來解決企業(yè)計(jì)劃生產(chǎn)編制問題，這些算法在處理計(jì)劃排產(chǎn)中出現(xiàn)的組合爆炸等問題都有著不俗的表現(xiàn)，常見的有遺傳算法[3]，蟻群算法[4]，模擬退火算法[5]，粒子群算法[6]，禁忌搜索算法[7]等。其中遺傳算法較其他算法編碼解碼方式多樣，遺傳操作簡單，能夠在全部解空間并行計(jì)算，對目標(biāo)函數(shù)設(shè)置以及搜索解空間沒有特定限制，算法適應(yīng)面廣的特點(diǎn)而有著更為廣泛的使用。

輻照膜是一種新型微孔薄膜，輻照膜利用重離子加速器產(chǎn)生的離子束對薄膜進(jìn)行輻照，當(dāng)離子穿過薄膜后留下的軌跡自動(dòng)就形成了微孔。在鋰離子電池材料的結(jié)構(gòu)中起到避免正負(fù)電極直接接觸同時(shí)又導(dǎo)通離子的作用[8]。目前國際上按照隔膜微孔的成孔機(jī)理不同主要分為干法，濕法和輻照這三種方法。其中干法和濕法是兩種工業(yè)上使用的成熟穩(wěn)定的生產(chǎn)方法，輻照是一種新型的電池隔膜生產(chǎn)工藝[9]。

相較于干法和濕法利用物理外力對薄膜進(jìn)行拉伸形成微孔，輻照微孔質(zhì)量更佳。但是由于整個(gè)加速器系統(tǒng)構(gòu)造復(fù)雜[10]，對現(xiàn)場溫濕度要求苛刻，這就使得輻照生產(chǎn)不同型號的薄膜時(shí)不能僅僅通過修改拉伸力來實(shí)現(xiàn)生產(chǎn)型號的更改，操作難度高，并且頻繁的切換型號不僅會(huì)造成生產(chǎn)時(shí)間的浪費(fèi)也會(huì)嚴(yán)重影響重離子加速器的使用壽命[11]。相較傳統(tǒng)薄膜生產(chǎn)過程，輻照膜更加注重薄膜的連續(xù)生產(chǎn)，相同型號的訂單應(yīng)盡量集中生產(chǎn)，原本適用于傳統(tǒng)薄膜生產(chǎn)的交付日優(yōu)先的排產(chǎn)方式[12]將導(dǎo)致頻繁的設(shè)備切換，大量的參數(shù)重置會(huì)造成輻照膜生產(chǎn)時(shí)間的浪費(fèi)，已經(jīng)不能夠滿足輻照膜生產(chǎn)的要求。

因此為實(shí)現(xiàn)訂單合理連續(xù)排產(chǎn)，解決由不連續(xù)生產(chǎn)而造成的輻照時(shí)間浪費(fèi)問題，提高生產(chǎn)效率，避免訂單延期，在解決傳統(tǒng)計(jì)劃調(diào)度問題的遺傳算法基礎(chǔ)上加入訂單重組策略，提出新的排產(chǎn)算法用于解決輻照膜訂單排產(chǎn)問題。

1 數(shù)學(xué)模型

1.1 問題描述

輻照膜的工業(yè)生產(chǎn)流程主要分為：薄膜放卷，重離子輻照，敏化，蝕刻，薄膜收卷5大部分。所生產(chǎn)的輻照膜因?yàn)楸∧さ暮穸?，微孔的大小，開孔密度形狀的不同又細(xì)分為不同的型號。每種型號在生產(chǎn)時(shí)都要預(yù)先設(shè)定好系統(tǒng)的工作參數(shù)，如重離子加速器的輻照角度，輻照強(qiáng)度，收放卷的傳送速度等必要工藝參數(shù)。不同于傳統(tǒng)的干法濕法的物理拉升成孔原理，僅通過修改對薄膜的張力大小不能生產(chǎn)出不同型號的輻照膜。因此每當(dāng)生產(chǎn)不同型號的薄膜時(shí)，整條生產(chǎn)線都必須停機(jī)重新設(shè)定參數(shù)，當(dāng)訂單型號多樣時(shí)頻繁的切換生產(chǎn)型號不僅僅造成大量的時(shí)間浪費(fèi)，同時(shí)也會(huì)嚴(yán)重的影響系統(tǒng)的使用壽命，致使生產(chǎn)效率不能有效的提高。因此對于輻照膜，為減少訂單延誤提高生產(chǎn)效率，關(guān)鍵是實(shí)現(xiàn)訂單的連續(xù)化生產(chǎn)。

為了使訂單型號相同的薄膜盡量集中生產(chǎn)，提出訂單重組策略。即將相同型號的訂單，在約束條件容許的情況下，通過對訂單產(chǎn)量的合理調(diào)整實(shí)現(xiàn)相同型號訂單的集中生產(chǎn)，如圖1所示。

圖1 訂單重組原理

圖1中有A,B,C三種型號訂單，按傳統(tǒng)交付日排序會(huì)有4次型號切換。如果僅僅進(jìn)行簡單的訂單合并會(huì)造成訂單的延誤，例如在1號之后插入5號會(huì)使2號延期。訂單重組就是將5號的部分生產(chǎn)任務(wù)分別重組到1號和3號中，重組后型號切換將由4次降為3次。因?yàn)橹亟M只是對訂單的產(chǎn)量進(jìn)行合理重分配，并沒有因?yàn)橹亟M造成訂單數(shù)量的增加，不會(huì)造成訂單求解空間的組合爆炸。同時(shí)又在不影響交付日的情況下盡最大努力實(shí)現(xiàn)訂單的連續(xù)生產(chǎn)。

以已知的需求訂單為研究對象，在訂單最后交付日期，生產(chǎn)線最大產(chǎn)能等條件約束下，保持總產(chǎn)量不變以最大化連續(xù)訂單生產(chǎn)為優(yōu)化目標(biāo)，結(jié)合輻照膜訂單可重組的特點(diǎn)，建立輻照膜訂單排產(chǎn)模型。

假設(shè)條件：①企業(yè)輻照膜產(chǎn)能固定，生產(chǎn)線的產(chǎn)能固定不變。②輻照膜訂單能夠提前完工，提前完工對輻照膜的生產(chǎn)沒有影響。③訂單排產(chǎn)針對生產(chǎn)線上訂單。④輻照膜作為薄膜能夠進(jìn)行切分，訂單的產(chǎn)量能夠進(jìn)行合理拆分重組。⑤拆分重組訂單同原始訂單只存在訂購數(shù)量上的差別。

1.2 優(yōu)化目標(biāo)

保證生產(chǎn)總量不變的前提下，以最大化連續(xù)訂單生產(chǎn)為優(yōu)化目標(biāo)見式(1)～式(3)，建立排產(chǎn)模型具體分析如下：

(1)延誤日期率，在訂單生產(chǎn)總量不變的前提下，訂單的必要生產(chǎn)時(shí)間一定，訂單的延誤率越小表示訂單排產(chǎn)的效果最好，企業(yè)獲得的利潤越高。其中：k表示特定排產(chǎn)序列，i和j表示訂單，i,j∈ [1,2,…,n];aki表示訂單i依排序后的生產(chǎn)順序k，從排產(chǎn)日算起到生產(chǎn)完成為止所需時(shí)間;bi表示i訂單從排產(chǎn)日算起到交付日為止的有效生產(chǎn)時(shí)間;di表示i訂單延期(aki>bi)則為1，反之為0;si表示訂單i的訂購數(shù)量;c為常數(shù)，表示生產(chǎn)線的每日產(chǎn)能;式(1)LDi表示訂單i的延誤日期率；其中Di表示生產(chǎn)i訂單的必要時(shí)間，LDk∈[0,1]。

(1)

(2)訂單型號改變率(“互異”率)。定義“互異”特指排產(chǎn)序列中相鄰兩個(gè)訂單型號不同的情況，k表示特定的排產(chǎn)序列，用Ek表示排產(chǎn)序列k中“互異”情況發(fā)生的總次數(shù)。G表示所有訂單型號的總個(gè)數(shù)。式(2)STk表示k序列中的“互異”率，STk∈[0,1]。

(2)

(3)排產(chǎn)效率

將標(biāo)準(zhǔn)化后的延誤日期率和“互異”率相加用來量化表征訂單排產(chǎn)的效率SCk，SCk∈[0,2]。

SCk=LDk+STk

(3)

以SCk值得高低來代表輻照膜排產(chǎn)順序的好壞，SCk值越低說明序列里訂單延誤和“互異”情況發(fā)生的次數(shù)越少，生產(chǎn)成本越低，效率越高。

1.3 約束條件

(1)生產(chǎn)線產(chǎn)能約束：式(4)表示全部訂單量的總和小于等于年最大產(chǎn)能，c為常數(shù)表示日均產(chǎn)能。

(4)

(2)同型號合并生產(chǎn)約束：為了實(shí)現(xiàn)訂單的重組，式(5)保證重組后訂單的生產(chǎn)完成時(shí)間在交付日之前，式(6)保證下一訂單的最遲交付日之間有余量。表示將j訂單加入i訂單中的生產(chǎn)量。其中D訂單有富余的生產(chǎn)完成時(shí)間。

(5)

(6)

2 優(yōu)化算法設(shè)計(jì)

遺傳算法仿照自然種群優(yōu)勝劣汰的機(jī)制，由染色體編碼，交叉，變異，優(yōu)勢個(gè)體選擇4個(gè)主要步驟組成，是一種智能優(yōu)化算法。為了對上述目標(biāo)模型進(jìn)行優(yōu)化計(jì)算，結(jié)合輻照膜生產(chǎn)的實(shí)際特點(diǎn)，在自適應(yīng)遺傳算法的基礎(chǔ)之上引入訂單重組機(jī)制，從而使得訂單排產(chǎn)效果更好，同時(shí)加快了遺傳算法的收斂速度。

2.1 染色體編碼機(jī)制

改進(jìn)后的自適應(yīng)遺傳算法，染色體以實(shí)數(shù)方式構(gòu)成，染色體的排列順序就代表了實(shí)際的排產(chǎn)順序，同時(shí)為了適應(yīng)訂單重組機(jī)制，每次訂單重組后形成一個(gè)新的訂單群，每個(gè)遺傳個(gè)體由兩部分組成,分別為個(gè)體所屬的訂單群編號和個(gè)體染色體基因序列。

(0, [[R1], [R2], [R3], [R4], [R5], ……[Rn]])

(2, [[R1], [R2], [R3], [R4], [R5], ……[Rn]])

這里0,2就表示個(gè)體所屬的訂單群號，之后計(jì)算個(gè)體適應(yīng)度值時(shí)就采用相應(yīng)的訂單群計(jì)算。[R1～Rn]即為個(gè)體染色體基因序列，代表了實(shí)際訂單編號的排產(chǎn)順序。

2.2 適應(yīng)度函數(shù)及選擇機(jī)制

算法以式(7)為適應(yīng)度函數(shù)，選擇算子采用“輪盤賭”的方式。因?yàn)镾Ck表示排產(chǎn)效率，取值在[0,2]之間所以適應(yīng)度函數(shù)可以表示為：

maxF=3-SCk

(7)

式(7)將目標(biāo)函數(shù)求最小轉(zhuǎn)化為適應(yīng)度函數(shù)求最大，能夠更好的適應(yīng)輪盤賭選擇機(jī)制。

2.3 遺傳算子

(1)交叉算子

為使得算法能夠盡可能的搜索到全部的解空間，交叉算子采用由順序交叉方式[13]即隨機(jī)選擇親代中的一段基因固定復(fù)制到子代中，將另一親代中的固定基因之外的依次填充到子代基因的空位上，生成子代。

(8)

其中，fmax表示種群中最高適應(yīng)度值，favg表示種群的平均適應(yīng)度值，fkmax表示參與交叉的k1,k2中適應(yīng)度的最高值。

(2)變異算子

采用SHIFT變異算子[15]，隨機(jī)在染色體中選出一段基因，將之倒置之后重新放回到原選出位置，實(shí)現(xiàn)變異。在調(diào)度排產(chǎn)領(lǐng)域這種變異方式已被證實(shí)是最為有效的變異機(jī)制之一[16]。

同理變異概率Pb也采用自適應(yīng)方式，計(jì)算公式如下：

(9)

2.4 訂單重組策略

在傳統(tǒng)遺傳算法的基礎(chǔ)上加入訂單重組策略，將原始的訂單群通過基于適應(yīng)度值、延誤率、“互異”率的重組選擇策略后，重組形成新的訂單群能夠有效的提高算法的優(yōu)化性能，具體重組策略如下。

(1)統(tǒng)計(jì)生產(chǎn)時(shí)間情況

在遺傳算法的精英種群中找到多個(gè)優(yōu)秀個(gè)體k，遍歷這個(gè)k個(gè)體中的基因序列[[R1][R2]......[Rn]]，計(jì)算得到個(gè)體k的生產(chǎn)時(shí)間情況集A。

A={Jki|Jki=bi-aki,i∈[1..n]}

Jki=bi-aki

(10)

(11)

式(11)表示依據(jù)k個(gè)體的基因排序，從訂單排產(chǎn)日算起到訂單實(shí)際生產(chǎn)完成為止所需要的實(shí)際生產(chǎn)時(shí)間。其中si為訂單i的訂購數(shù)量，c為常數(shù)表示生產(chǎn)線的日產(chǎn)能。

式(10)表示依據(jù)k個(gè)體的基因排序，i訂單的實(shí)際需要生產(chǎn)天數(shù)同合同容許的計(jì)劃生產(chǎn)天數(shù)之差，Jki>0表示i訂單能夠順利生產(chǎn)完成且富余Jki天，Jki<0表示i訂單將延期完成且比計(jì)劃交付日延后Jki天。式中的bi表示從排產(chǎn)日到訂單交付日i訂單的計(jì)劃容許生產(chǎn)天數(shù)。

(2)選擇重組訂單

遍歷生產(chǎn)時(shí)間情況集A，找出Jki值最小的訂單i作為被拆訂單，和Jki值最大的訂單j，作為待插入訂單。其中對于j訂單需要保證Jk(i+1)的值大于零，即保證訂單產(chǎn)量調(diào)整后不會(huì)對后續(xù)訂單的生產(chǎn)有影響避免連鎖反應(yīng)，同時(shí)j訂單的交付日期要早于被拆訂單i，保證在交付日期之前完成額定產(chǎn)出。當(dāng)j訂單不滿足條件時(shí)選擇次大的訂單作為待插入訂單。如果沒有滿足上述條件的i,j則沒有可重組訂單。

(3)確定重組量

i表示訂單重組中減少生產(chǎn)量的延期訂單，j表示增加生產(chǎn)量的生產(chǎn)時(shí)間富余的訂單，z表示增加(減少)的生產(chǎn)量值。

z=

(12)

式(12)表示當(dāng)j為k個(gè)體基因序的最后一位時(shí)，因?yàn)閖之后沒有未完成訂單，因此只要i訂單的產(chǎn)量小于j可接納量時(shí)就能夠?qū)訂單全部合并到j(luò)訂單中去，否則調(diào)整量z為j所能接納的最大量Jkj·c。

當(dāng)j不是最尾訂單，接納量要同時(shí)小于j和j+1訂單的容納量，以保證訂單重組之后對后續(xù)訂單的生產(chǎn)沒有影響，不會(huì)發(fā)生連鎖反應(yīng)。

最后i訂單的生產(chǎn)量為si-z，j訂單的生產(chǎn)量為sj+z，修改對應(yīng)值后完成訂單的重組，產(chǎn)生新的訂單集合，依此生成新的子代加入到父代種群中。訂單重組后計(jì)算個(gè)體的適應(yīng)度值只需按照對應(yīng)的訂單集合計(jì)算，而不需要對個(gè)體基因長度進(jìn)行改變，能夠有效的減少遺傳算法編碼的復(fù)雜度同時(shí)優(yōu)化排產(chǎn)效果。

2.5 算法流程

利用改進(jìn)后的遺傳算法優(yōu)化輻照膜訂單排產(chǎn)，首先隨機(jī)生成初代種群W1，個(gè)體基因長度同訂單總量相同，種群個(gè)體數(shù)為訂單數(shù)的2倍。每經(jīng)過11次遺傳操作加入1次訂單重組操作，選擇前10個(gè)精英個(gè)體進(jìn)行訂單重組，對重組后的訂單集隨機(jī)生成新的種群加入到原種群中，繼續(xù)進(jìn)行遺傳操作直到最大迭代次數(shù)或算法收斂，得到最終的排序結(jié)果。具體算法過程如圖2所示。

圖2 改進(jìn)后算法流程圖

3 實(shí)例驗(yàn)證

應(yīng)用上述改進(jìn)算法對輻照膜排產(chǎn)問題進(jìn)行求解。隨機(jī)選取輻照膜生產(chǎn)企業(yè)的銷售訂單，數(shù)據(jù)包括輻照膜訂單編號，薄膜定夠量，薄膜型號，訂單的交付日期等信息。對于其中的不同薄膜厚度，不同微孔形狀的訂單統(tǒng)一采用英文字母來區(qū)別訂單的型號。實(shí)驗(yàn)中遺傳算法的最大迭代次數(shù)為300次，基因編碼長度同訂單個(gè)數(shù)相同，交叉變異采用自適應(yīng)概率式(8)、式(9)，以式(7)為適應(yīng)度函數(shù)，式(3)為目標(biāo)函數(shù)。

3.1 實(shí)驗(yàn)一

實(shí)驗(yàn)一，用下述三種方法對50個(gè)隨機(jī)訂單進(jìn)行排產(chǎn)，試驗(yàn)結(jié)果如表1所示。

方法A：按照輻照膜訂單中要求的訂單結(jié)轉(zhuǎn)交付日期順序排產(chǎn)。

方法B：使用解決傳統(tǒng)薄膜排產(chǎn)問題的遺傳算法，不進(jìn)行訂單重組，進(jìn)行輻照膜排產(chǎn)。

方法C：采用加入訂單重組策略的新遺傳算法進(jìn)行輻照膜排產(chǎn)。

表1 三種方法對50個(gè)訂單排產(chǎn)結(jié)果對比

實(shí)驗(yàn)表明改進(jìn)后的遺傳算法通過將訂單進(jìn)行重組，使得訂單延誤次數(shù)降為0次，同時(shí)較A,B兩種排序方法，改進(jìn)后的遺傳算法使得因?yàn)樯a(chǎn)型號互異而導(dǎo)致的停機(jī)次數(shù)分別減少了73%和57%，算法能夠有效實(shí)現(xiàn)訂單的連續(xù)排產(chǎn)，同時(shí)優(yōu)化后的訂單沒有延誤情況的發(fā)生，算法的正確性得到了驗(yàn)證。

3.2 實(shí)驗(yàn)二

實(shí)驗(yàn)二，以10個(gè)輻照膜訂單為例對訂單重組結(jié)果和改進(jìn)前后的遺傳算法的收斂性進(jìn)行實(shí)驗(yàn)比較，實(shí)驗(yàn)結(jié)果圖橫軸為遺傳代數(shù)，縱軸為染色體所代表的排產(chǎn)效率SCk，具體實(shí)驗(yàn)效果如圖3、圖4所示。

傳統(tǒng)遺傳算法：

圖3 傳統(tǒng)遺傳算法結(jié)果圖

圖4 改進(jìn)后的遺傳算法結(jié)果圖

排序結(jié)果：[5], [3], [1], [6], [4], [2], [8], [10], [7], [9]，“互異”次數(shù)：6次，總延誤日期：130天，共有[1,2,7]這3個(gè)訂單發(fā)生延誤不能夠按時(shí)完成。排產(chǎn)效率最小值為：1.2150847。原始訂單集的詳細(xì)信息見表2。

表2 原始輻照膜訂單

改進(jìn)后的遺傳算法：

排序結(jié)果：[[1], [2], [4], [3], [8], [10], [5], [6], [7], [9]]，“互異”次數(shù)：5次，總延誤日期：0天。排產(chǎn)效率最小值為：0.5。拆分后對應(yīng)的訂單集的詳細(xì)信息見表3。

表3 輻照膜訂單重組后的結(jié)果

表2、表3說明算法實(shí)現(xiàn)了對訂單生產(chǎn)量的重分配，改進(jìn)后的算法互異次數(shù)有效降低，延誤率降為零。同時(shí)通過圖3、圖4比較發(fā)現(xiàn)加入訂單重組的遺傳算法和傳統(tǒng)遺傳算法都在迭代進(jìn)行了100次后實(shí)現(xiàn)了算法的收斂，雖然訂單拆分染色體算法較傳統(tǒng)算法計(jì)算流程復(fù)雜但是重組并沒有增加待排序訂單的個(gè)數(shù)，算法仍具有良好的收斂性。

綜合上述兩個(gè)實(shí)驗(yàn)，訂單重組遺傳算法對于輻照膜能夠合理的進(jìn)行生產(chǎn)排序，由于算法實(shí)現(xiàn)了訂單的合并使得停機(jī)次數(shù)降低了57%，節(jié)約了生產(chǎn)時(shí)間使得排序后訂單的延期次數(shù)降為零，增大了企業(yè)利潤。同時(shí)通過實(shí)驗(yàn)二的比較，從遺傳迭代收斂圖的比較上能夠明顯看到改進(jìn)前后的算法都在100代時(shí)實(shí)現(xiàn)了收斂，算法步驟的增多沒有影響算法的實(shí)質(zhì)性能，仍然具有良好的收斂性。

4 結(jié)論

對于輻照膜訂單排產(chǎn)的研究，結(jié)合輻照膜生產(chǎn)特性，將訂單重組策略加入到傳統(tǒng)遺傳算法中，改進(jìn)后的遺傳算法能夠更好的適應(yīng)輻照膜訂單排產(chǎn)的需要，突破了由于訂單集固有缺陷對排產(chǎn)效率的桎梏，重組后的訂單集排產(chǎn)更加合理，有效減少了訂單延期和“互異”情況的發(fā)生。實(shí)驗(yàn)驗(yàn)證了所提模型和算法的正確性，最終得到了符合條件的排產(chǎn)序列。訂單排產(chǎn)不能僅關(guān)注車間生產(chǎn)能力，對于訂單本身的不合理也應(yīng)作出修正，對于產(chǎn)品可拆分的訂單在排產(chǎn)時(shí)都可以合理的進(jìn)行訂單數(shù)量的重分配，對于其他智能優(yōu)化算法，如蟻群，粒子群等算法在進(jìn)行可拆分訂單的排產(chǎn)時(shí)都可以嵌入訂單重組的機(jī)制，能夠有效解決訂單本身的不合理，從而得到更好的優(yōu)化結(jié)果。融合多種機(jī)制求解可拆分訂單排產(chǎn)算法是值得進(jìn)一步研究探討的問題。

DOI:10.1007/s40092-017-0205-y.