一種改進(jìn)的基于遺傳算法的中藥生產(chǎn)調(diào)度系統(tǒng)

安 鑫，郭劍毅，2，花 植，王海雄

(1.昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院，云南昆明650051;

2.云南省計(jì)算機(jī)技術(shù)應(yīng)用重點(diǎn)實(shí)驗(yàn)室智能信息處理研究所，云南昆明650051)

作業(yè)車間調(diào)度問(wèn)題(job－shop scheduling problem，JSSP)可以描述為:給定一個(gè)藥品集合和一個(gè)機(jī)器集合，每個(gè)工件多道工序，每道工序需要在一臺(tái)給定的機(jī)器上非間斷地加工一段時(shí)間;每一臺(tái)機(jī)器一次最多加工一道工序;調(diào)度就是把工序分配給機(jī)器上某個(gè)時(shí)間段。其目標(biāo)是找到最短時(shí)間長(zhǎng)度的調(diào)度［1］。典型的中藥生產(chǎn)企業(yè)生產(chǎn)體系由多條生產(chǎn)線構(gòu)成，每條生產(chǎn)線接收原材料或前一條生產(chǎn)線輸出的半成品，多條生產(chǎn)線協(xié)同完成一種藥品的生產(chǎn)。若將每種劑型的生產(chǎn)流程進(jìn)行分解，每個(gè)設(shè)備對(duì)應(yīng)一道生產(chǎn)工序，則中藥制藥的生產(chǎn)調(diào)度問(wèn)題可看成是一般的JSSP問(wèn)題。

目前國(guó)內(nèi)在中藥制藥生產(chǎn)調(diào)度系統(tǒng)上的研究很少。文獻(xiàn)［2］提出用標(biāo)準(zhǔn)遺傳算法來(lái)解決中藥生產(chǎn)調(diào)度問(wèn)題。然而由于標(biāo)準(zhǔn)遺傳算法本身的缺陷，在尋優(yōu)求解過(guò)程中容易陷入局部最優(yōu)，且計(jì)算速度慢，使系統(tǒng)得不到理想的結(jié)果。筆者通過(guò)對(duì)中藥制藥企業(yè)的生產(chǎn)工藝流程進(jìn)行分析，將基于并行遺傳算法［3］與小生境遺傳算法［4］相結(jié)合的改進(jìn)遺傳算法應(yīng)用到中藥制藥生產(chǎn)調(diào)度系統(tǒng)中，通過(guò)改進(jìn)遺傳算法尋找到最優(yōu)解或次優(yōu)解，避免了尋優(yōu)過(guò)程中出現(xiàn)早熟和陷入局部最優(yōu)現(xiàn)象，并得到合理的生產(chǎn)調(diào)度方案，為中藥制藥生產(chǎn)調(diào)度提供了新的思路。

1 工藝流程分析及算法的提出

1.1 工藝流程

由于生產(chǎn)調(diào)度系統(tǒng)的通用性差，因此分析中藥制藥生產(chǎn)工藝流程對(duì)解決中藥制藥生產(chǎn)調(diào)度問(wèn)題至關(guān)重要。某中藥制造車間主要有膠囊劑生產(chǎn)線、外包生產(chǎn)線、片劑生產(chǎn)線、提取生產(chǎn)線、眼用制劑生產(chǎn)線、顆粒劑生產(chǎn)線、錠劑生產(chǎn)線和散劑生產(chǎn)線等8條生產(chǎn)線，每條生產(chǎn)線都需要經(jīng)過(guò)預(yù)前處理、成型和外包等工序，每種劑型的加工順序不變，且同種劑型不同藥品的加工工序基本相同，各生產(chǎn)線又由多個(gè)設(shè)備組成，每種藥品都有其生產(chǎn)加工流程和相應(yīng)生產(chǎn)工序?qū)?yīng)的生產(chǎn)加工設(shè)備，從而組成一個(gè)復(fù)雜的生產(chǎn)體系。

1.2 算法的提出

生產(chǎn)調(diào)度問(wèn)題已被證明是非確定型多項(xiàng)式(non－deterministic polynomial，NP)，即 NP 難問(wèn)題［5］。中藥生產(chǎn)調(diào)度系統(tǒng)是一個(gè)多目標(biāo)系統(tǒng)，且在調(diào)度過(guò)程中受到諸多條件的約束，目前解決作業(yè)車間調(diào)度問(wèn)題的典型方法是基于神經(jīng)網(wǎng)絡(luò)和遺傳算法的JSSP［6］。標(biāo)準(zhǔn)遺傳算法的初始種群以及隨后進(jìn)化的種群都只有一個(gè)，在遺傳算子進(jìn)行選擇和交叉操作時(shí)，保持了解空間的多樣性，但是隨著優(yōu)化計(jì)算的進(jìn)行，到了計(jì)算后期，尋優(yōu)進(jìn)入平衡態(tài)，解空間內(nèi)的可能解集中于某個(gè)極值點(diǎn)，其后代產(chǎn)生近親繁殖，陷入局部最優(yōu)而無(wú)法得到全局最優(yōu)解或次優(yōu)解。在尋優(yōu)過(guò)程中一旦陷入局部最優(yōu)，就很難自行跳出局部極值［7］。而利用遺傳算法的隱含并行性對(duì)種群中各個(gè)可能解進(jìn)行交叉、變異操作并對(duì)多個(gè)可能解進(jìn)行判別和尋優(yōu)計(jì)算，即可有效避免陷入局部最優(yōu)。小生境遺傳算法的基本思想就是為了保持種群內(nèi)的多樣性，在種群內(nèi)部隨機(jī)選取若干個(gè)體構(gòu)成排擠成員，通過(guò)遺傳操作產(chǎn)生新個(gè)體，判斷新個(gè)體和排擠成員的相似性，剔除與排擠成員相似的新個(gè)體。在優(yōu)化計(jì)算的過(guò)程中，包含多個(gè)生存環(huán)境，同時(shí)種群內(nèi)部的多樣性得到延續(xù)。

為了彌補(bǔ)標(biāo)準(zhǔn)遺傳算法的不足，筆者采用了基于并行遺傳算法與小生境遺傳算法相結(jié)合的改進(jìn)遺傳算法，利用并行遺傳算法尋優(yōu)計(jì)算的并行性和小生境遺傳算法尋優(yōu)計(jì)算的多樣性等優(yōu)點(diǎn)，相對(duì)標(biāo)準(zhǔn)遺傳算法，這種改進(jìn)遺傳算法在克服早熟和局部極值等問(wèn)題上有較大的改善。

2 基于改進(jìn)遺傳算法的模型原理

2.1 基于工序的編碼方法

有效的編解碼方式能夠使隨后進(jìn)行的遺傳算法尋優(yōu)求解過(guò)程更加高效、可靠。針對(duì)生產(chǎn)調(diào)度問(wèn)題的編碼方式有很多，CHENG［8］總結(jié)了遺傳算法在解決生產(chǎn)調(diào)度問(wèn)題的8種染色體編碼方法，考慮產(chǎn)生可能解的合法性和可行性，以及中藥生產(chǎn)的作業(yè)車間調(diào)度模型，筆者將采用基于工序的編碼方法。

基于工序編碼方法是將調(diào)度編碼作為工序的序列，每個(gè)基因代表一道工序，比如對(duì)于3個(gè)藥品3臺(tái)機(jī)器問(wèn)題，一個(gè)染色體包括3×3個(gè)基因，每個(gè)藥品出現(xiàn)在染色體中3次。數(shù)據(jù)如表1所示。

表1 3個(gè)藥品3臺(tái)加工設(shè)備的加工數(shù)據(jù)

給出一個(gè)染色體［3 2 2 1 1 2 3 1 3］，其中1、2、3分別表示藥品加工工序1、2、3，假設(shè)每個(gè)藥品有3個(gè)加工工序，則每個(gè)藥品在染色體中出現(xiàn)3次。以藥品2為例，第一個(gè)2表示藥品2的第1個(gè)工序在設(shè)備1上加工，第二個(gè)2表示藥品2的第2個(gè)工序在設(shè)備3上加工，第三個(gè)2表示藥品2的第3個(gè)工序在設(shè)備2上加工。很顯然，染色體的任何一種排列都能產(chǎn)生可行解。

2.2 解碼實(shí)現(xiàn)

設(shè)計(jì)編碼算法產(chǎn)生的碼 s［i］，i=1，…，n×m，及其任意轉(zhuǎn)換方式解碼成可行的活動(dòng)調(diào)度策略的算法。解碼算法如下:

令 k［i］=1，i=1，…，n;

For i=1 to n×m;

得到加工藥品 s［i］的機(jī)器號(hào) Jm(s［i］，k［s［i］］);

令 k［s［i］］=k［s［i］］+1;

將藥品 s［i］在機(jī)器 Jm(s［i］，k［s［i］］－1)上的操作以最早允許加工時(shí)間加工，即從零時(shí)刻到當(dāng)前時(shí)刻對(duì)該機(jī)器上的各加工空閑依次判斷能否將該藥品插入加工。若能，則在空閑中插入加工，并修改該機(jī)器上的加工隊(duì)列;否則，以當(dāng)前時(shí)刻加工該藥品，將該藥品排在當(dāng)前隊(duì)列的末尾。算法中，藥品i能在空閑時(shí)間段［a，b］插入加工的條件為:

max［t(i)，a］+t_proc≤b

其中:a和b分別為空閑起始和終止時(shí)刻;t(i)為藥品i目前的最早允許加工時(shí)間;t_proc為藥品在機(jī)器上的加工時(shí)間。

2.3 操作算子

在改進(jìn)遺傳算法尋優(yōu)過(guò)程中，尋優(yōu)計(jì)算主要包括兩部分:種群內(nèi)尋優(yōu)和種群間優(yōu)良模式的交換。兩個(gè)種群同時(shí)相互獨(dú)立地以不同的遺傳進(jìn)化參數(shù)進(jìn)行尋優(yōu)計(jì)算，產(chǎn)生不同的優(yōu)良模式，在達(dá)到設(shè)定的進(jìn)化代數(shù)后，兩個(gè)種群停止各自尋優(yōu)計(jì)算，分別從各自種群中選出N個(gè)個(gè)體以及種群內(nèi)適應(yīng)度最高的個(gè)體，N是隨機(jī)產(chǎn)生的整數(shù)且小于種群規(guī)模數(shù)大于零，之后將兩個(gè)種群內(nèi)的N個(gè)個(gè)體以及種群內(nèi)適應(yīng)度最高的個(gè)體進(jìn)行交換，從而將不同優(yōu)良模式引入不同種群，實(shí)現(xiàn)不同優(yōu)良模式雜交。同時(shí)在兩個(gè)不同進(jìn)化參數(shù)種群分別獨(dú)立進(jìn)化的過(guò)程中，實(shí)現(xiàn)不同優(yōu)良模式尋優(yōu)的并行性。

2.3.1 選擇算子

兩個(gè)相互獨(dú)立的種群獨(dú)立進(jìn)行尋優(yōu)計(jì)算時(shí)，首先需要分別從各自的種群中進(jìn)行選擇操作。兩個(gè)種群獨(dú)自選擇時(shí)采用的是最優(yōu)個(gè)體保存策略方法，在兩個(gè)種群進(jìn)行個(gè)體交換時(shí)采用適應(yīng)度比例法，這樣保證適應(yīng)度高的個(gè)體得到保留，又不至于使算法陷入局部最優(yōu)。2.3.2 交叉算子

在中藥制藥調(diào)度系統(tǒng)中設(shè)計(jì)交叉算子最重要的標(biāo)準(zhǔn)是子代對(duì)父代優(yōu)良特性的繼承性和子代的可行性，筆者采用文獻(xiàn)［9］提出的新的交叉算子POX(precedence operation crossover)，如圖 1所示，它能夠更好地繼承父代優(yōu)良特征并且子代總是可行的。

圖1 POX交叉

2.3.3 變異算子

遺傳算法中的變異主要是為了保證其局部的隨機(jī)搜索能力和維持種群的多樣性。筆者采用的是基本位變異，即對(duì)可能解編碼字符串依照變異概率隨機(jī)將字符串中的一位或幾位進(jìn)行變異運(yùn)算。

2.3.4 種群間的個(gè)體交換

對(duì)兩個(gè)相互獨(dú)立的種群分別進(jìn)行尋優(yōu)計(jì)算后，再進(jìn)行種群間的個(gè)體交換。其具體方法如下:

(1)隨機(jī)產(chǎn)生整數(shù) N，N的取值范圍是［1，min(pop1，pop2)］，pop1為種群1的個(gè)體數(shù)量減去1，pop2為種群2的個(gè)體數(shù)量減去1。

(2)每個(gè)種群內(nèi)隨機(jī)選取N個(gè)個(gè)體和最優(yōu)個(gè)體，在pop1和pop2間交換選中的N+1個(gè)個(gè)體。

(3)完成種群間個(gè)體交換。

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

中藥生產(chǎn)調(diào)度系統(tǒng)以中藥生產(chǎn)時(shí)間F(x)最短為目標(biāo)函數(shù)，F(xiàn)IT［F(x)］為適應(yīng)度函數(shù)，根據(jù)目標(biāo)函數(shù)映射方法最小化問(wèn)題原則，適應(yīng)度函數(shù)取目標(biāo)函數(shù)的導(dǎo)數(shù)使得適應(yīng)度函數(shù)值和個(gè)體適應(yīng)度呈正比關(guān)系，即FIT［F(x)］=1/F(x)。

3 中藥制藥生產(chǎn)調(diào)度結(jié)果處理

在中藥制藥生產(chǎn)調(diào)度系統(tǒng)中，信息通過(guò)改進(jìn)算法子系統(tǒng)求得最優(yōu)解或次優(yōu)解，通過(guò)解碼生成調(diào)度方案，并根據(jù)調(diào)度結(jié)果繪制成相應(yīng)的甘特圖或生產(chǎn)報(bào)表，為生產(chǎn)計(jì)劃制定和生產(chǎn)決策人員提供支持，甘特圖顯示調(diào)度結(jié)果如圖2所示。

從圖2可清晰地看出以下信息:某藥品各道工序的開始和結(jié)束時(shí)間;各種藥品的完工時(shí)間及所有藥品的完工時(shí)間;各生產(chǎn)線上設(shè)備的生產(chǎn)利用時(shí)間。各藥品嚴(yán)格按照生產(chǎn)工藝安排生產(chǎn)次序，對(duì)照生產(chǎn)工藝庫(kù)各藥品對(duì)應(yīng)的工序先后和工序時(shí)間，從甘特圖可以看出調(diào)度方案是可行的。

圖2 甘特圖顯示調(diào)度結(jié)果

4 原型系統(tǒng)的實(shí)現(xiàn)與測(cè)試

4.1 原型系統(tǒng)

根據(jù)該系統(tǒng)的設(shè)計(jì)目標(biāo)和原則，原型系統(tǒng)采用Client/Server技術(shù)的兩層應(yīng)用體系結(jié)構(gòu)模型來(lái)實(shí)現(xiàn)，數(shù)據(jù)的存取和管理相互獨(dú)立，有單獨(dú)的數(shù)據(jù)庫(kù)管理系統(tǒng)對(duì)數(shù)據(jù)集中管理，方便調(diào)度人員通過(guò)客戶端實(shí)現(xiàn)對(duì)服務(wù)器的訪問(wèn)。系統(tǒng)主要包括數(shù)據(jù)管理子系統(tǒng)、調(diào)度算法子系統(tǒng)、計(jì)劃分解子系統(tǒng)和調(diào)度結(jié)果處理子系統(tǒng)，算法系統(tǒng)作為單獨(dú)的子系統(tǒng)獨(dú)立出來(lái)以便擴(kuò)展。

4.2 系統(tǒng)測(cè)試

4.2.1 性能驗(yàn)證

改進(jìn)后遺傳算法性能驗(yàn)證選用的是MT06、MT10和MT20標(biāo)準(zhǔn)測(cè)試用例，分別對(duì)改進(jìn)后的混合遺傳算法在中藥調(diào)度系統(tǒng)中的尋優(yōu)結(jié)果進(jìn)行分析和比較。算法的參數(shù)配置如表2所示。

表2 標(biāo)準(zhǔn)遺傳算法與改進(jìn)遺傳算法參數(shù)配置

通過(guò)標(biāo)準(zhǔn)遺傳算法和改進(jìn)后的遺傳算法解決MT06、MT10和MT20標(biāo)準(zhǔn)測(cè)試用例，并分別運(yùn)算10次，得到如表3所示的實(shí)驗(yàn)數(shù)據(jù)對(duì)比結(jié)果。

從實(shí)驗(yàn)數(shù)據(jù)可知，改進(jìn)遺傳算法在計(jì)算小規(guī)模尋優(yōu)求解問(wèn)題MT06問(wèn)題時(shí)能夠迅速收斂并得到最優(yōu)解，在計(jì)算規(guī)模偏大的尋優(yōu)求解問(wèn)題MT10問(wèn)題和MT20問(wèn)題時(shí)還無(wú)法達(dá)到最優(yōu)解，只能得次優(yōu)解，由于該系統(tǒng)是針對(duì)某中型中藥制藥企業(yè)進(jìn)行研究的，規(guī)模相對(duì)較小，因此，可進(jìn)行實(shí)際應(yīng)用，并得到可行的調(diào)度方案。

表3 實(shí)驗(yàn)數(shù)據(jù)對(duì)比

4.2.2 應(yīng)用驗(yàn)證

對(duì)比該中藥制藥企業(yè)的生產(chǎn)計(jì)劃表，系統(tǒng)可以自動(dòng)生成調(diào)度方案，且藥品信息、設(shè)備信息和工序信息都是從相應(yīng)的數(shù)據(jù)庫(kù)中取得的，一旦有變動(dòng)，只需更改數(shù)據(jù)庫(kù)。同時(shí)改變了人工調(diào)度方式設(shè)備利用率低，調(diào)度效率不高，調(diào)度結(jié)果達(dá)不到最優(yōu)，費(fèi)時(shí)費(fèi)力，且制作報(bào)表時(shí)容易出錯(cuò)等問(wèn)題，大大提高了生產(chǎn)排程的效率。

5 結(jié)論

通過(guò)分析中藥制藥生產(chǎn)流程和特點(diǎn)，利用基于并行遺傳算法與小生境遺傳算法相結(jié)合的改進(jìn)遺傳算法來(lái)解決中藥制藥調(diào)度問(wèn)題，有效地抑制了早熟和局部極值現(xiàn)象，通過(guò)測(cè)試驗(yàn)證了調(diào)度方案的可行性，為解決中藥制藥生產(chǎn)調(diào)度問(wèn)題提供了理論依據(jù)和實(shí)用價(jià)值。

［1］CONWAY RW，MAXWELLW，MILLER LW.Theory of scheduling［M］.Addison － Wesley:Reading Mass，1967:21－36.

［2］GUO JY，HUA Z.A schedulingmodelof Chinesemedicine production based on genetic algorithm research and applications［C］//International Conference on Machine Learning and Cybernetics2009.Baoding:［s.n.］，2009:241－253.

［3］FALKENAUER E，BOUFFOUIX S.A genetic algorithm for job shop scheduling［C］//Proceedings of IEEE International Conference on Robotics and Automation Sacremento.［S.l.］:［s.n.］，1991:824 －829.

［4］GRUDININ N.Reactive power optimization using successive quadratic programmingmethod［J］.1998(4):1219－1225.

［5］STEPHEN A C.The complexity of theorem － proving procedures［C］//Proc of the 3rd Annual ACM Symp on Theory of Computing.New York:AC Press，1971:151－158.

［6］王萬(wàn)良，吳啟迪.生產(chǎn)調(diào)度智能算法及其應(yīng)用［M］.北京:科學(xué)出版社，2007:54－63.

［7］王凌.車間調(diào)度及其遺傳算法［M］.北京:清華大學(xué)出版社，2003:122－129.

［8］CHENG RW，GEN M，TSUJIMURA Y.A tutorial survey of job－shop scheduling problems using genetic algorithms－I representation［J］.Computers＆ Industrial Engineering，1996，30(4):983 －997.

［9］張超勇，饒運(yùn)清.基于POX交叉的遺傳算法求解job－shop調(diào)度問(wèn)題［J］.中國(guó)機(jī)械工程，2004，15(23):2149－2153.