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

季香君，馬立紅，劉紫玉

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

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

季香君，馬立紅，劉紫玉

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

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

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

隨著工業(yè)化水平的不斷提高和科學(xué)技術(shù)的不斷發(fā)展，制造業(yè)之間的競(jìng)爭(zhēng)越來(lái)越激烈[1-2]。流水工序合理的生產(chǎn)調(diào)度因其能夠幫助企業(yè)提高生產(chǎn)效率[3]、增強(qiáng)企業(yè)競(jìng)爭(zhēng)力，因此越來(lái)越受到人們的重視。流水工序的調(diào)度問(wèn)題屬于強(qiáng)NP完全問(wèn)題，優(yōu)化調(diào)度的實(shí)質(zhì)就是多項(xiàng)工序共享一定的資源時(shí)，這些資源不能讓所有工序都以最佳狀態(tài)獨(dú)享資源的處理要求，因此需要對(duì)流水工序進(jìn)行合理安排，以確保在對(duì)資源共享的同時(shí)保證生產(chǎn)效率[4-5]。流水工序具有動(dòng)態(tài)性、無(wú)序性、多目標(biāo)性、多約束性等特點(diǎn)[6]，使得流水工序的調(diào)度問(wèn)題成為難解的NP完全問(wèn)題。流水工序調(diào)度問(wèn)題已經(jīng)成為當(dāng)前工業(yè)生產(chǎn)領(lǐng)域研究的熱門問(wèn)題[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)化算法存在一個(gè)共同缺陷，就是只能適用于規(guī)模較小的流水工序調(diào)度問(wèn)題，一旦流水工序規(guī)模增大，將會(huì)出現(xiàn)計(jì)算量呈指數(shù)級(jí)增大的缺陷，導(dǎo)致調(diào)度任務(wù)效率降低，生產(chǎn)效率下降。

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

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

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

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

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

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

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

1.1.2 對(duì)流水工序的種群初始化操作

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

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

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

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

(1)

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

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

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

(2)

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

1.1.5 確定交叉算子

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

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

1.1.6 確定修正算子

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

1.2遺傳算法的缺陷

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

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

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

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

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

(3)

式中：ck表示第k臺(tái)機(jī)器結(jié)束工序的時(shí)間。

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

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

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

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

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

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

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

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

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

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

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

流水工序的調(diào)度問(wèn)題具有動(dòng)態(tài)性、無(wú)序性、多目標(biāo)性、多約束性等特點(diǎn)，在進(jìn)行編碼時(shí)，一個(gè)粒子代表一種調(diào)度方案，所有同一工件的序號(hào)作為工序編號(hào)，根據(jù)工序編號(hào)在染色體出現(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)驗(yàn)值決定，在流水工序調(diào)度問(wèn)題中設(shè)為3。

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

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

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

(6)

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

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

f=100×Zbest/T(jm)。

(7)

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

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

2.2.4 利用粒子群算法對(duì)模型求解

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

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

注：時(shí)間單位為min。

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

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

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

3 仿真實(shí)驗(yàn)結(jié)果及分析

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

圖5 實(shí)驗(yàn)結(jié)果Fig.5 Experimental results

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

實(shí)驗(yàn)中不同算法的機(jī)器平均利用率對(duì)比結(jié)果如圖6所示。

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

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

4 結(jié) 語(yǔ)

流水工序的調(diào)度問(wèn)題具有很強(qiáng)的動(dòng)態(tài)性、有序性、多目標(biāo)性、多約束性等特點(diǎn)，利用傳統(tǒng)的遺傳算法會(huì)因收斂速度慢導(dǎo)致生產(chǎn)效率降低，不能滿足生產(chǎn)過(guò)程的需要。本文提出一種基于粒子群算法的流水工序的調(diào)度優(yōu)化算法。仿真實(shí)驗(yàn)表明，本算法能夠提高機(jī)器的利用率，縮短生產(chǎn)加工工序的完成時(shí)間，提高生產(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)新效率評(píng)價(jià)研究[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é)校科學(xué)技術(shù)項(xiàng)目(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.