具有時(shí)間窗約束的柔性流水車間設(shè)備利用率排產(chǎn)優(yōu)化問題研究

董曉婷

（四川建筑職業(yè)技術(shù)學(xué)院設(shè)備工程系，四川 德陽 618000）

0 引言

柔性流水車間排產(chǎn)優(yōu)化問題 (flexible flow-shop scheduling problem, FFSP)既需要解決工件的上線序，還需處理每道工序并行工位的分配， 屬NP-Hard 問題。實(shí)際制造企業(yè)生產(chǎn)過程是滾動(dòng)連續(xù)的生產(chǎn)過程， 計(jì)劃部門按照固定時(shí)間節(jié)奏在生產(chǎn)線投放生產(chǎn)任務(wù)， 在多工序、 生產(chǎn)周期長的生產(chǎn)車間中各個(gè)工序的正在加工在制品是多次投產(chǎn)的生產(chǎn)任務(wù)， 如果每次投產(chǎn)生產(chǎn)任務(wù)在各個(gè)工序不限制在一定時(shí)間范圍內(nèi)生產(chǎn)， 會(huì)增加排產(chǎn)沖突的可能性， 所以可以通過設(shè)置每個(gè)工序的時(shí)間窗進(jìn)行控制， 使得排產(chǎn)在各工序時(shí)間窗內(nèi)進(jìn)行排產(chǎn)， 增加排產(chǎn)時(shí)間窗約束會(huì)增加排產(chǎn)的問題復(fù)雜性，但是也可以更好提升排產(chǎn)結(jié)果在實(shí)際應(yīng)用的效果。 緊致遺傳算法(compact genetic algorithm, CGA)屬于一種變量無關(guān)的分布估計(jì)算法[1]，于1998 年被美國UIUC 大學(xué)Harik 教授首次提出[2]。 該算法計(jì)算量小，優(yōu)化速度非?？?， 但同時(shí)具有隨著進(jìn)化代數(shù)進(jìn)化活力不足，容易落入局部極值的缺陷。 本文采用一種改進(jìn)CGA 算法，增強(qiáng)該算法進(jìn)化活力，克服落入局部極值，以達(dá)到更好解決FFSEUP-TWC 的目標(biāo)。

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

1.1 問題描述

具有時(shí)間窗約束[3]的柔性流水車間設(shè)備利用率排產(chǎn)優(yōu)化問題可以描述為： 個(gè)工件按上線順序經(jīng)過每道工序進(jìn)行加工， 工件在每個(gè)工序給定的時(shí)間窗內(nèi)進(jìn)行生產(chǎn)加工， 即限定每個(gè)工序的并行工位的有效工作時(shí)間范圍內(nèi)加工， 工件可選擇并行工位中任意一個(gè)工位加工， 工件在各工序的加工時(shí)間已知， 通過全局優(yōu)化算法來優(yōu)化上線序和并行工位分配情況， 進(jìn)而提高的生產(chǎn)線上設(shè)備利用率。

1.2 約束條件

（1）柔性流水車間排產(chǎn)的一般性約束：

式（1）表示工序Operj上的開工時(shí)間與完工時(shí)間的約束。 工件Ji的生產(chǎn)時(shí)間用Ti,j，表示，開工時(shí)間用Si,j表示，完工時(shí)間用Ci,j表示。

（2）柔性流水車間排產(chǎn)的時(shí)間窗約束

式（3）表示工序Operj的時(shí)間窗開始時(shí)間Twbj與工件Ji的開工時(shí)間Si,j的約束關(guān)系，要求在工序Operj，所有工件的開工時(shí)間Si,j都要大于等于時(shí)間窗開始時(shí)間Twbj。

式（4）表示工序Operj的時(shí)間窗結(jié)束時(shí)間Twej與工件Ji的完工時(shí)間Ci,j， 的約束關(guān)系， 要求在工序Operj所有工件的完工時(shí)間Ci,j，都要小于等于時(shí)間窗結(jié)束時(shí)間Twej。

1.3 建立設(shè)備利用率優(yōu)化目標(biāo)

式5 中fUR表示的FFS 中所有工位總設(shè)備利用率，為工位實(shí)際工作時(shí)間與工位提供工作時(shí)間的比值，工件在各工序中在所分配工位上的加工時(shí)間之和為實(shí)際工作時(shí)間， 工位提供工作時(shí)間是時(shí)間窗開始時(shí)間Twbj和最后一個(gè)工件的完工時(shí)間max{Ci,j}之差，這個(gè)時(shí)間設(shè)置成該工序的時(shí)間窗的時(shí)間范圍Ts1。

2 算法分析

2.1 建立并初始化概率模型

建立n×n 的矩陣P1作為CGA 算法的上線序概率模型來優(yōu)化排產(chǎn)的上線序, 概率模型中1 至n 行對(duì)應(yīng)工件J1至Ji，1 至n 列對(duì)應(yīng)個(gè)體的1 至n 位表示工件Ji在上線加工隊(duì)列中位置s 上出現(xiàn)的概率； 建立n×Ms的矩陣P2作為CGA 算法的工位分配概率模型來優(yōu)化多工序并行工位分配, 概率模型中1 至n 行對(duì)應(yīng)工件J1至Ji，1 至Ms列對(duì)應(yīng)個(gè)體的工序Oper1至工序Operm選擇工位的概率表 示 工 件Ji在工序Operj的并行工位WSj,k上出現(xiàn)的概率。 矩陣P1和矩陣P2合成為一個(gè)n×(n+Ms)的矩陣P 作為CGA 算法的概率模型。

2.2 新個(gè)體的編碼和解碼

3 仿真分析

3.1 構(gòu)建仿真數(shù)據(jù)

為了研究FFSEUP-TWC 問題， 構(gòu)造具備4 道工序的FFS 驗(yàn)證模型的數(shù)據(jù)， 每道工序的并行工位數(shù)分別為{3,2,3,2}。生產(chǎn)任務(wù)是加工8 個(gè)工件(n=8)，每個(gè)工件在各工序并行工位加工時(shí)間取[20,40]內(nèi)的隨機(jī)數(shù)。

3.2 研究方案和參數(shù)設(shè)置

構(gòu)造2 組調(diào)度方案： 方案1 是采用CGA 算法的柔性流水車間設(shè)備利用率排產(chǎn)優(yōu)化方案； 方案2 是采用SACGA 算法的柔性流水車間設(shè)備利用率fUR排產(chǎn)優(yōu)化方案； 以總設(shè)備利用率作為2 組方案的全局調(diào)度優(yōu)化目標(biāo)和適應(yīng)度函數(shù)，也做優(yōu)化結(jié)果的評(píng)價(jià)指標(biāo)。

設(shè)置CGA 算法種群規(guī)模NP=4， 最大訓(xùn)練代數(shù)Gmax=500，學(xué)習(xí)系數(shù)K=6，基于信息熵的自適應(yīng)學(xué)習(xí)速率調(diào)整關(guān)聯(lián)的參數(shù) （式9）， 學(xué)習(xí)速率的調(diào)整倍率β1=1.2，β2=0.8，學(xué)習(xí)速率的信息熵調(diào)整閥值α1=0.4，α2=0.6。

表1 每個(gè)工序時(shí)間窗時(shí)間范圍表（單位：min）

3.3 仿真結(jié)果分析

20 次仿真運(yùn)算結(jié)果的平均值如表3。

表3 2 組方案仿真結(jié)果數(shù)值分析表

表2 數(shù)值分析結(jié)果可知： 2 組方案都可以得到較好的調(diào)度結(jié)果，但方案2 的總設(shè)備利用率fUR和總設(shè)備利用率變化幅度f'UR的值最大，總設(shè)備利用率變化幅度的均值比方案1 的CGA 算法的的提高23.04%，但是由于加入了自適應(yīng)策略， 增加了計(jì)算的復(fù)雜性，增加了16.27%運(yùn)行時(shí)間成本。

4 結(jié)論

在解決FFSEUP-TWC 問題時(shí)， 以fUR作為優(yōu)化目標(biāo)。 在全局優(yōu)化優(yōu)化過程中， 分別采用CGA 算法、SACGA 算法進(jìn)行排產(chǎn)優(yōu)化效果對(duì)比分析，SACGA 算法在FFS 的全局優(yōu)化過程中能夠獲取更高設(shè)備利用率。證明采用SACGA 的全局優(yōu)化方法可以得到更好的排產(chǎn)優(yōu)化調(diào)度結(jié)果。