季香君，馬立紅，劉紫玉

(河北科技大學(xué)經(jīng)濟管理學(xué)院，河北石家莊 050018)

流水工序調(diào)度與生產(chǎn)效率的關(guān)系模型分析

季香君，馬立紅，劉紫玉

(河北科技大學(xué)經(jīng)濟管理學(xué)院，河北石家莊 050018)

提出一種基于粒子群算法的流水工序調(diào)度任務(wù)優(yōu)化模型。利用流水工序調(diào)度任務(wù)的特點得到流水工序時間約束條件，利用粒子群算法的原理建立流水工序調(diào)度任務(wù)優(yōu)化模型，利用粒子群算法對模型進行求解。仿真實驗表明，利用該算法能夠得到流水工序調(diào)度問題的最優(yōu)解，提高生產(chǎn)效率。

流水工序；調(diào)度；混合粒子群算法；生產(chǎn)效率

隨著工業(yè)化水平的不斷提高和科學(xué)技術(shù)的不斷發(fā)展，制造業(yè)之間的競爭越來越激烈[1-2]。流水工序合理的生產(chǎn)調(diào)度因其能夠幫助企業(yè)提高生產(chǎn)效率[3]、增強企業(yè)競爭力，因此越來越受到人們的重視。流水工序的調(diào)度問題屬于強NP完全問題，優(yōu)化調(diào)度的實質(zhì)就是多項工序共享一定的資源時，這些資源不能讓所有工序都以最佳狀態(tài)獨享資源的處理要求，因此需要對流水工序進行合理安排，以確保在對資源共享的同時保證生產(chǎn)效率[4-5]。流水工序具有動態(tài)性、無序性、多目標性、多約束性等特點[6]，使得流水工序的調(diào)度問題成為難解的NP完全問題。流水工序調(diào)度問題已經(jīng)成為當前工業(yè)生產(chǎn)領(lǐng)域研究的熱門問題[7-10]。

傳統(tǒng)的流水工序調(diào)度優(yōu)化算法是基于啟發(fā)式搜尋算法的流水工序調(diào)度優(yōu)化算法、基于神經(jīng)網(wǎng)絡(luò)算法的流水工序調(diào)度優(yōu)化算法和基于遺傳算法的流水工序調(diào)度優(yōu)化算法，其中應(yīng)用最廣泛的是基于遺傳算法的流水工序調(diào)度優(yōu)化算法。這些調(diào)度優(yōu)化算法存在一個共同缺陷，就是只能適用于規(guī)模較小的流水工序調(diào)度問題，一旦流水工序規(guī)模增大，將會出現(xiàn)計算量呈指數(shù)級增大的缺陷，導(dǎo)致調(diào)度任務(wù)效率降低，生產(chǎn)效率下降。

為了避免上述弊端，本文分析了一種基于粒子群算法的流水工序調(diào)度優(yōu)化算法。根據(jù)流水工序的調(diào)度任務(wù)特點建立流水工序調(diào)度任務(wù)模型，利用粒子群算法對調(diào)度任務(wù)尋求最優(yōu)解。仿真實驗表明，利用粒子群算法能夠提高流水工序調(diào)度任務(wù)的效率，提高了生產(chǎn)效率，效果令人滿意。

1 傳統(tǒng)遺傳算法的流水工序調(diào)度優(yōu)化原理

遺傳算法是根據(jù)自然界中優(yōu)勝劣汰的基本法則演化而來的一種解決非線性復(fù)雜問題的基本方法。其基本原理是利用遺傳算法，按照一定的規(guī)則，從父系群體中選取適合要求的個體進行選擇、交叉、變異等基本遺傳操作，產(chǎn)生帶有父系基因的后代，反復(fù)進行遺傳操作后就能夠得到最優(yōu)解。遺傳算法相對于普通的搜尋方法具有良好的魯棒性。

1.1遺傳算法在流水工序調(diào)度問題的實現(xiàn)過程

1.1.1 選擇合適的染色體編碼方式

流水工序具有動態(tài)性、多目標性等特點，利用傳統(tǒng)的二進制編碼方式無法滿足生產(chǎn)要求。因此遺傳算法應(yīng)用到流水工序方面一般選用加工順序的直接編碼方案。設(shè)長度是L的染色體，將其分為n段長度分別為l1,l2,…，ln的子染色體，依次對應(yīng)流水工序的各個加工序列，染色體上的基因gab表示加工工序，1≤a≤n,1≤b≤La。圖1表示流水工序染色體的編碼方案。

圖1 流水工序染色體編碼方案Fig.1 Water process chromosome coding scheme

1.1.2 對流水工序的種群初始化操作

為了能夠得到流水工序的最優(yōu)調(diào)度方案，必須生成由不同調(diào)度方法構(gòu)成的調(diào)度群體，進行初始化操作，并以此為起點進行下一步遺傳操作。在流水工序調(diào)度中，設(shè)在t時刻各道工序的前列工序均可利用的工序集合為可利用集，記為U(t)，流水工序的可利用集合的子集是可利用集合與流水工序序列的交集。

初始化操作的過程如下：在初始時刻，可利用集合U(0)={(1,1),(2,1),…,(n,1)}，表示n個作業(yè)的第1道工序構(gòu)成集合。當一個工序進行作業(yè)時，將離開可利用集；當一個工序結(jié)束后，若此工序之后還有未完工序，則將未完的工序加入到可利用集合中，利用可利用集合能夠生成可行調(diào)度方法的集合。

1.1.3 建立流水工序調(diào)度個體適應(yīng)度函數(shù)

遺傳算法在進行最優(yōu)調(diào)度方案求解的過程是封閉的，只能根據(jù)個體適應(yīng)度函數(shù)對最優(yōu)解的優(yōu)劣進行判斷，適應(yīng)度越高的個體生存機會就越高。利用目標函數(shù)能夠轉(zhuǎn)化得到適應(yīng)度函數(shù)。在流水工序調(diào)度最優(yōu)方案的問題中，適應(yīng)度函數(shù)只能是正數(shù)，式(1)能夠表示流水工序調(diào)度問題的個體適應(yīng)度函數(shù)：

(1)

式中：wij表示流水工序個體i在工序j中的權(quán)重；T用于描述流水工序調(diào)度過程中某個體的調(diào)度時間。

1.1.4 設(shè)計合適的選擇遺傳算子

利用選擇遺傳算子能夠根據(jù)適應(yīng)度函數(shù)的值選擇合適的流水工序調(diào)度方案個體進行遺傳操作。設(shè)選擇某個流水工序調(diào)度方案個體的概率是Y，則利用式(2)能夠表示選擇遺傳算子的函數(shù)：

(2)

式中：xi表示調(diào)度方案集合中第i個調(diào)度方案；f(xi)表示第i個調(diào)度方案的適應(yīng)度；∑f(xi)表示所有調(diào)度方案個體適應(yīng)度之和。

1.1.5 確定交叉算子

由于流水工序調(diào)度問題的編碼方案與一般的編碼方案不同，因此，其交叉算子也與一般的交叉算子不同。在2個調(diào)度方案個體進行交叉時，必須在對應(yīng)的子染色體上交叉，而不能跨段交叉，如圖2所示。

圖2 子染色體對應(yīng)交叉示意圖Fig.2 Schematic diagram of chromosome corresponding cross

1.1.6 確定修正算子

利用遺傳算法求解流水工序中最優(yōu)調(diào)度方案的問題中，會出現(xiàn)不符合現(xiàn)實工藝流程的染色體，導(dǎo)致算法得不到最優(yōu)解。利用修正算子能夠避免此種情況的發(fā)生。對于不正確的調(diào)度方案，對染色體(調(diào)度方案)上的基因(工序)進行判斷，看是否符合工藝流程標準。如果不符合，則重新對工序進行排序，直至達到工藝流程要求為止。

1.2遺傳算法的缺陷

在流水工序調(diào)度最優(yōu)解的實際應(yīng)用中，由于工序規(guī)模難以確定，所以一旦工序規(guī)模增加，算法的計算量將呈指數(shù)級增加，不容易得到局部最優(yōu)調(diào)度方案的解，且收斂速度變慢，導(dǎo)致調(diào)度任務(wù)效率降低，生產(chǎn)效率降低，無法滿足工業(yè)生產(chǎn)的要求。為了避免傳統(tǒng)遺傳算法的弊端，本文提出一種基于粒子群算法的流水工序調(diào)度方案優(yōu)化方法。

2 基于粒子群算法的流水工序調(diào)度任務(wù)優(yōu)化模型

2.1流水工序調(diào)度問題的約束條件

在生產(chǎn)過程中，調(diào)度的任務(wù)是針對某項具體的生產(chǎn)加工任務(wù)，通過安排合理的加工工序和設(shè)備，達到提高生產(chǎn)效率的目的。流水工序的調(diào)度問題需要滿足以下約束條件：1)每個工件需要若干道加工工序；2)每個工件的加工工序不能改變；3)每臺設(shè)備只能進行一個工序，本道工序結(jié)束后工件才能進行下一個工序；4)在同一時刻，同一工件不能同時被2臺及以上的機器加工；6)每一道工序的加工時間都要在要求范圍之內(nèi)。

根據(jù)以上闡述，流水工序的調(diào)度任務(wù)就是通過合理安排加工工序和設(shè)備，縮短每一道工序的加工時間，提高生產(chǎn)效率。利用式(3)能夠描述流水工序調(diào)度任務(wù)，即各個工序的最小化完工時間：

(3)

式中：ck表示第k臺機器結(jié)束工序的時間。

2.2基于粒子群算法的流水工序調(diào)度任務(wù)優(yōu)化模型

粒子群算法源于人們對鳥群捕食的研究，是一種群智能的優(yōu)化算法。該算法最大的特點是以獨立的粒子為個體，并賦予每個粒子簡單的行為規(guī)則，使粒子群具有全局尋優(yōu)的智能化特性。利用粒子群算法解決復(fù)雜問題具有計算量小、收斂速度快、魯棒性強的特點。

2.2.1 基于粒子群算法的流水工序調(diào)度優(yōu)化算法實現(xiàn)步驟

1)對粒子種群(流水工序調(diào)度的集合)進行初始化，設(shè)粒子種群中有n個粒子(流水工序調(diào)度方案)，隨機產(chǎn)生n個解。

2)根據(jù)目標函數(shù)，計算每個粒子的適應(yīng)度值。

3)將各個粒子的適應(yīng)度值與之前經(jīng)歷的調(diào)度方案的適應(yīng)度值進行對比，如果這個值比之前的好，則保留當前的調(diào)度方案。

4)將各個粒子的適應(yīng)度值與全局經(jīng)歷的調(diào)度方案的適應(yīng)度值進行對比，如果這個值比之前全局經(jīng)歷的好，則保留當前的調(diào)度方案。

5)利用式(4)迭代方程對流程工序的組合進行更新：

vi(t+1)=ωvi(t)+c1r1(pi(t)-xi(t))+

c2r2(pg(t)-xi(t))xi(t+1)=

xi(t)+vi(t+1)。

(4)

式中：vi表示第i個調(diào)度方案的完工時間；ω是慣性系數(shù)，表示上一次迭代速度對本次迭代速度的影響；c1和c2表示學(xué)習(xí)因子，正常情況下，c1=c2；r1,r2表示互相獨立的2個函數(shù)；xi表示第i套調(diào)度方案在所有解的位置；pi表示單個調(diào)度方案從初始時刻到當前時刻搜尋到的最優(yōu)解；pg表示全局從初始時刻到當前時刻搜尋到的最優(yōu)解。

6)設(shè)置一個合適的適應(yīng)度值作為終止迭代的調(diào)度，得到最優(yōu)調(diào)度方案后終止粒子種群的迭代。

2.2.2 相關(guān)參數(shù)設(shè)置

流水工序的調(diào)度問題具有動態(tài)性、無序性、多目標性、多約束性等特點，在進行編碼時，一個粒子代表一種調(diào)度方案，所有同一工件的序號作為工序編號，根據(jù)工序編號在染色體出現(xiàn)的順序決定工件的工序。

迭代次數(shù)：設(shè)置粒子種群迭代次數(shù)為40次。

慣性系數(shù)：慣性系數(shù)的值越大越有利于搜尋全局最優(yōu)解，其值越小越有利于算法的收斂性。因此，利用自適應(yīng)函數(shù)能夠根據(jù)需要調(diào)節(jié)慣性系數(shù)值的大小。利用式(5)能夠描述自適應(yīng)度與慣性系數(shù)的關(guān)系：

(5)

式中：Hmax表示最大迭代次數(shù)。利用自適應(yīng)度與慣性系數(shù)的函數(shù)關(guān)系能夠減少0.4～0.9的線性。

學(xué)習(xí)因子：一般由經(jīng)驗值決定，在流水工序調(diào)度問題中設(shè)為3。

2.2.3 流水工序調(diào)度任務(wù)模型的建立

流水工序調(diào)度要解決的核心問題就是降低各個工序完成的時間，提高生產(chǎn)效率。因此，目標函數(shù)就是最大完成時間的最小值。根據(jù)上述要求建立的流水工序調(diào)度任務(wù)的目標函數(shù)模型如式(6)所示：

min(T(jm))=
min(max[T(1),T(2),…,T(i),…,T(m)]。

(6)

式中：T(i)表示第i道工序的完成時間；T(jm)表示整個加工任務(wù)結(jié)束時使用的時間。

利用式(7)能夠?qū)αＷ拥倪m應(yīng)度進行評估：

f=100×Zbest/T(jm)。

(7)

式中：Zbest表示根據(jù)生產(chǎn)運營需要設(shè)定的生產(chǎn)流程結(jié)束時最優(yōu)完成時間。利用粒子算法進行具體的流水工序調(diào)度最優(yōu)解的具體過程如圖 3所示。

圖3 利用粒子群算法搜尋過程Fig.3 Searching process by using particle swarm optimization algorithm

2.2.4 利用粒子群算法對模型求解

利用上述建立的流水工序調(diào)度任務(wù)模型，對生產(chǎn)過程中的工件、機器和加工工序進行調(diào)度安排，工件加工過程符合本文流水工序優(yōu)化模型中的約束條件。在加工過程中的每道工序的加工時間各不相同。設(shè)在某一流水工序中需要對6個工件和6臺機器進行調(diào)度安排，每個工件分別在一臺機器上加工一次。每個工件的加工工序與每道工序需要的時間如表1所示。

表1 加工工序?qū)?yīng)時間表

注：時間單位為min。

利用粒子算法對流水工序調(diào)度安排的結(jié)果如圖4所示。

圖4 粒子算法搜尋結(jié)果Fig.4 Particle algorithm search result

從圖4可知，利用粒子算法對流水工序調(diào)度方案搜尋的最小任務(wù)完工時間為182 min，充分體現(xiàn)出本文算法的有效性。

3 仿真實驗結(jié)果及分析

為了驗證本文算法的有效性和優(yōu)越性，需要進行一次仿真實驗。實驗對象為某水產(chǎn)品加工企業(yè)生產(chǎn)車間，加工某批次水產(chǎn)品的流水加工工序，設(shè)一次流水工序中有10個工件和10臺機器，設(shè)置迭代次數(shù)為100次，實驗重復(fù)進行100次。實驗結(jié)果如圖5所示。

圖5 實驗結(jié)果Fig.5 Experimental results

根據(jù)實驗結(jié)果可知，在流水工序規(guī)模較大時，利用本文算法能夠在迭代次數(shù)較少的情況下得到最優(yōu)解。傳統(tǒng)遺傳算法由于計算量過大導(dǎo)致收斂速度降低，容易得到局部最優(yōu)解，難以得到全局最優(yōu)解。

實驗中不同算法的機器平均利用率對比結(jié)果如圖6所示。

圖6 不同算法的機器平均利用率Fig.6 Average utilization rates of machine under different algorithms

從實驗結(jié)果可知，利用本文算法能夠有效提高實驗水產(chǎn)品企業(yè)生產(chǎn)車間機器的平均利用率，提高了該水產(chǎn)品企業(yè)的生產(chǎn)效率，相對傳統(tǒng)的遺傳算法具有很大的優(yōu)越性。

4 結(jié) 語

流水工序的調(diào)度問題具有很強的動態(tài)性、有序性、多目標性、多約束性等特點，利用傳統(tǒng)的遺傳算法會因收斂速度慢導(dǎo)致生產(chǎn)效率降低，不能滿足生產(chǎn)過程的需要。本文提出一種基于粒子群算法的流水工序的調(diào)度優(yōu)化算法。仿真實驗表明，本算法能夠提高機器的利用率，縮短生產(chǎn)加工工序的完成時間，提高生產(chǎn)效率，體現(xiàn)出本算法的有效性和優(yōu)越性。

/

[1] IBARRA O,KIM C.Heuristic algorithms for scheduling independent tasks on non-identical processors[J].Journal of the ACM,1977,77(2):280-289.

[2] 李艷玲，潘杰義，陳玥希.基于DEA的企業(yè)技術(shù)創(chuàng)新效率評價研究[J].河北工業(yè)科技，2005，22(2)：74-76. LI Yanling,PAN Jieyi,CHEN Yuexi.Research on evaluating the efficiency of enterprise technology innovation based on DEA method[J].Hebei Journal of Industrial Science and Technology,2005,22(2):74-76.

[3] SHEN Hua, WEI Feifei. Grid resources pricing model[J]. Journal of Hubei University of Technology, 2006,21(4): 45-50.

[4] ZOU L D.Single machine group scheduling problem based on improved genetic algorithm[J].Computer Simulation, 2011,27(4):308-313.

[5] FOSTER I,KESSELMAN C,TUECKE S.The anatomy of the grid:Enabling scalable virtual organization[J].High-Performance Computing Applications,2001,15(3):200-222.

[6] GE Xiang,ZHANG Li. A new quantum genetic algorithm and its application[J].Journal of Electronics, 2004,32(3):17-30.

[7] ARMSTRONG R,HENSGEN D,KIDD T.The relative performance of various mapping algorithm is independent of sizable variance in run-time predictions[A].7th IEEE Heterogeneous Computing Workshop(HCW’98)[C].[S.l.]:[s.n.]，1998.79-87.

[8] LIAN Zhigang，GU Xingsheng，JIAO Bin．A similar particle swarm optimization algorithm for permutation flowshop scheduling to minimize makespan[J]．Applied Mathematics and Computation，2006，175(1)：773-785．

[9] PAN Q K， WANG L．Nidle permutation flow shop scheduling based on a hybrid discrete particle swarm optimization algorithm[J]．International Journal of Advanced Manufacturing Technology，2007(7):1252-1256.

[10] YANG Qingyun，SUN Jigui，ZHANG Juyang,et al．A hybrid discrete particle swarm algorithm for open-shop problems[A]．Proceedings of the 6th International Conference on Simulated Evolution and Learning[C]．Hefei:[s.n.]，2006.158-165．

Relational model analysis of assembly line scheduling and efficiency

JI Xiangjun， MA Lihong， LIU Ziyu

(School of Economics and Management, Hebei University of Science and Technology, Shijiazhuang Hebei 050018, China)

Based on particle swarm algorithm, a kind of flow process scheduling optimization algorithm is presented in this paper. Time constraint condition is obtained according to the characteristics of assembly line scheduling, and assembly line scheduling optimization model is established by using particle swarm algorithm principle, then the particle swarm algorithm is used for the solution of the model. Simulation results show that the algorithm can get the optimal solution of assembly line scheduling problem, so as to improve the production efficiency.

assembly line; scheduling; hybrid particle swarm optimization algorithm; production efficiency

1008-1534(2014)04-0291-05

2014-01-16;

2014-04-04;責(zé)任編輯：張士瑩

河北省自然科學(xué)基金(F2012208018)；河北省高等學(xué)?？茖W(xué)技術(shù)項目(ZD2014027)

季香君(1971-)，女，河北唐山人，副教授，碩士，主要從事管理科學(xué)與工程、企業(yè)管理方面的研究。

E-mail：jxjrsc@126.com

TP391

A

10.7535/hbgykj.2014yx04005

季香君，馬立紅，劉紫玉.流水工序調(diào)度與生產(chǎn)效率的關(guān)系模型分析[J].河北工業(yè)科技,2014,31(4):291-295. JI Xiangjun，MA Lihong，LIU Ziyu.Relational model analysis of assembly line scheduling and efficiency[J].Hebei Journal of Industrial Science and Technology,2014,31(4):291-295.