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

(1.昆明理工大學信息工程與自動化學院，云南昆明650051;

2.云南省計算機技術應用重點實驗室智能信息處理研究所，云南昆明650051)

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

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

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

1.1 工藝流程

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

1.2 算法的提出

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

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

2 基于改進遺傳算法的模型原理

2.1 基于工序的編碼方法

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

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

表1 3個藥品3臺加工設備的加工數(shù)據(jù)

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

2.2 解碼實現(xiàn)

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

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

For i=1 to n×m;

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

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

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

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

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

2.3 操作算子

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

2.3.1 選擇算子

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

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

圖1 POX交叉

2.3.3 變異算子

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

2.3.4 種群間的個體交換

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

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

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

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

2.3.5 適應度函數(shù)

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

3 中藥制藥生產(chǎn)調度結果處理

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

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

圖2 甘特圖顯示調度結果

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

4.1 原型系統(tǒng)

根據(jù)該系統(tǒng)的設計目標和原則，原型系統(tǒng)采用Client/Server技術的兩層應用體系結構模型來實現(xiàn)，數(shù)據(jù)的存取和管理相互獨立，有單獨的數(shù)據(jù)庫管理系統(tǒng)對數(shù)據(jù)集中管理，方便調度人員通過客戶端實現(xiàn)對服務器的訪問。系統(tǒng)主要包括數(shù)據(jù)管理子系統(tǒng)、調度算法子系統(tǒng)、計劃分解子系統(tǒng)和調度結果處理子系統(tǒng)，算法系統(tǒng)作為單獨的子系統(tǒng)獨立出來以便擴展。

4.2 系統(tǒng)測試

4.2.1 性能驗證

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

表2 標準遺傳算法與改進遺傳算法參數(shù)配置

通過標準遺傳算法和改進后的遺傳算法解決MT06、MT10和MT20標準測試用例，并分別運算10次，得到如表3所示的實驗數(shù)據(jù)對比結果。

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

表3 實驗數(shù)據(jù)對比

4.2.2 應用驗證

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

5 結論

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

［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］王萬良，吳啟迪.生產(chǎn)調度智能算法及其應用［M］.北京:科學出版社，2007:54－63.

［7］王凌.車間調度及其遺傳算法［M］.北京:清華大學出版社，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］張超勇，饒運清.基于POX交叉的遺傳算法求解job－shop調度問題［J］.中國機械工程，2004，15(23):2149－2153.