具有時間窗約束的柔性流水車間設備利用率排產優化問題研究

董曉婷

（四川建筑職業技術學院設備工程系，四川 德陽 618000）

0 引言

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

1 數學模型

1.1 問題描述

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

1.2 約束條件

（1）柔性流水車間排產的一般性約束：

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

（2）柔性流水車間排產的時間窗約束

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

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

1.3 建立設備利用率優化目標

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

2 算法分析

2.1 建立并初始化概率模型

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

2.2 新個體的編碼和解碼

3 仿真分析

3.1 構建仿真數據

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

3.2 研究方案和參數設置

構造2 組調度方案： 方案1 是采用CGA 算法的柔性流水車間設備利用率排產優化方案； 方案2 是采用SACGA 算法的柔性流水車間設備利用率fUR排產優化方案； 以總設備利用率作為2 組方案的全局調度優化目標和適應度函數，也做優化結果的評價指標。

設置CGA 算法種群規模NP=4， 最大訓練代數Gmax=500，學習系數K=6，基于信息熵的自適應學習速率調整關聯的參數 （式9）， 學習速率的調整倍率β1=1.2，β2=0.8，學習速率的信息熵調整閥值α1=0.4，α2=0.6。

表1 每個工序時間窗時間范圍表（單位：min）

3.3 仿真結果分析

20 次仿真運算結果的平均值如表3。

表3 2 組方案仿真結果數值分析表

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

4 結論

在解決FFSEUP-TWC 問題時， 以fUR作為優化目標。 在全局優化優化過程中， 分別采用CGA 算法、SACGA 算法進行排產優化效果對比分析，SACGA 算法在FFS 的全局優化過程中能夠獲取更高設備利用率。證明采用SACGA 的全局優化方法可以得到更好的排產優化調度結果。