黎書文，張成龍，周知進

(1.貴州理工學院 機械工程學院，貴陽 550003；2.茅臺學院 釀酒工程自動化系，貴州 遵義 564500)

0 引言

隨著計算機技術的發(fā)展，柔性機器人制造單元(Flexible Robot Manufacturing Cell, FRMC)[1]將工業(yè)機器人應用于傳統(tǒng)的制造單元替代人工作業(yè)方式，通過中央控制計算機智能、高效完成制造過程中的搬運、安裝、卸載等環(huán)節(jié)，如何進行柔性制造單元調度優(yōu)化，提高生產效率成為研究的關鍵。

當前生產調度優(yōu)化廣泛應用于電子產品、鋼鐵冶金、航空航天等工業(yè)領域，是先進制造技術和現代管理技術的核心，能夠實時響應車間環(huán)境變化，提高生產效率、降低生產成本，有利于實現柔性制造系統(tǒng)的高效生產，最終提高企業(yè)的經濟效益。近年來，群體智能優(yōu)化算法不斷應用于優(yōu)化車間調度問題，并取得了顯著的效果。其中文獻[2]提出一種基于混沌粒子群算法的多約束車間作業(yè)調度優(yōu)化方法。文獻[3]將蝙蝠算法與量子粒子群算法相結合，克服了粒子群算法收斂過早易陷入局部最優(yōu)的缺點。文獻[4-7]以柔性車間調度優(yōu)化為目標，對粒子群算法進行改進，優(yōu)化了機器、工藝路徑，提高了車間作業(yè)調度的效率。但是上述研究求解模型較為理想，調度約束條件有限，與實際車間調度環(huán)境有一定的差異。

因此本文主要針對離散制造車間柔性調度優(yōu)化，以提高生產線工作效率為目標，建立柔性調度多目標優(yōu)化模型，并結合現有國內外研究基礎，基于粒子群算法優(yōu)化。針對基本粒子群算法求解過程中收斂性緩慢、穩(wěn)定性低、易陷入局部最優(yōu)等缺點，設計了一種改進算法，通過實驗結果驗證了算法的有效性，同時提高了提升了柔性車間調度的效率。

1 問題描述

1.1 離散制造現狀分析

電子元器件等離散制造行業(yè)具有生產產品結構復雜，工藝流程多變，物流需求多樣等特點，決定了行業(yè)生產計劃、生產任務具有多變性以及不確定性，因此需要通過柔性機器人制造單元(Flexible Robot Manufacturing Cell, FRMC)等軟件設施改進設備、物料供應、生產計劃等加工要素的配置合理性，提高行業(yè)管理控制水平，促進行業(yè)智能化方向發(fā)展。

1.2 問題模型

柔性作業(yè)車間調度(Flexible Job-shop Scheduling Problem, FJSP)相比傳統(tǒng)作業(yè)調度(Job-shop Scheduling Problem, JSP)更為接近生產實際，有利于合理安排生產計劃和管理控制，直接關系到企業(yè)生產效益。

柔性作業(yè)車間調度問題模型可作如下描述[6]：假定：①待加工的工件集為{J1,J2, … ,Jn}，車間加工機床集為{Ml,M2, … ,Mm}，其中工件數為n，機床數為m；②每個工件加工工序不同、順序固定，工序數為Pi，其中i=1, 2, … ,n；③Sijk、Eijk、mijk分別表示工件i的第j道工序在k號機床的開始加工時間、加工完成時間、加工消耗時間，其中k=1, 2, … ,m；④ck表示機床k運行時間，Cmax表示最后完工時間。柔性作業(yè)調度目標為均衡機床生產負荷下，合理分配工件加工工序設備，使得生產加工總時間最短，其目標函數為：

minCmax=min{maxck}

(1)

整個加工過程中每道工序可選擇任一機床實施加工，整個加工制造過程中同一時刻僅能加工某一道工序，對于任意工序而言，須遵守循序漸進原則，前道工序加工完成才可開始此道工序的加工。因此需滿足式(2)～式(4)約束條件：

Eijk-Ei(j-1)k≥mijk,1

(2)

Eabk-EijM≥mabk

(3)

EijM≥mijk

(4)

式(2)表示任一工件相鄰加工工序滿足順序約束；式(3)表示任一機床同一時刻僅能加工某一道工序；式(4)表示任一工序加工完成時間應高于其加工消耗時間。

2 基本粒子群算法

粒子群算法(Particle Swarm Optimization, PSO)[8-9]主要用來對各類工業(yè)、經濟和社會領域的多目標問題、約束問題、動態(tài)問題進行求解優(yōu)化，最早是Russell Eberhart和James Kennedy兩位博士在1995年提出。因其自身參數較少、原理簡單、易于實現等優(yōu)點，受到各領域研究人員的青睞，得到廣泛的應用與發(fā)展。粒子群算法通過迭代進化，更新速度和位置進行空間搜索尋優(yōu)，其中經典速度和位置更新公式為[10]：

vi(t+1)=ωvi(t)+c1r1(t)[Pi(t)-xi(t)]+
c2r2(t)[Pg(t)-xi(t)]

(5)

xi(t+1)=xi(t)+vi(t+1)

(6)

式中，i=1, 2, …,N，N表示粒子群種群規(guī)模大小；ω表示慣性權重因子；r1和r2為服從(0, 1)均勻分布的獨立隨機變量；c1和c2為非負常數，表示學習因子；xi=(xi1,xi2, … ,xiD)、vi=(vi1,vi2, … ,viD)分別表示粒子空間坐標位置向量和速度向量，vi∈[-vmax,vmax]；Pi=(Pi1,Pi2, … ,PiD)、Pg=(Pg1,Pg2, … ,PgD)分別表示粒子個體最優(yōu)位置和種群最佳位置。

3 改進粒子群算法

3.1 穩(wěn)定性分析

粒子群算法提出以來，眾多國內外研究人員不斷進行改進，試圖提高算法性能。其中文獻[11]從粒子群穩(wěn)定性角度開展研究，對式(5)速度、式(6)位置更新公式進行分析，推導得出粒子的速度和位置變化過程的二階差分方程式(7)、式(8)：

vi(t+2)+(c1+c2-ω-1)vi(t+1)+ωvi(t)=0

(7)

xi(t+2)-(1+ω-c1-c2)xi(t+1)+
ωxi(t)-c1Pi(t)-c2Pg(t)=0

(8)

因此從粒子種群穩(wěn)定性出發(fā)，通過分析式(7)、式(8)二階差分方程，得出粒子的速度、位置變化過程穩(wěn)定的條件為1-ω>0且2ω+2-c1-c2>0。

3.2 改進算法設計

因此，根據粒子穩(wěn)定性條件1-ω>0且2ω+2-c1-c2>0，為提高粒子全局尋優(yōu)能力，避免算法陷入局部最優(yōu)，結合慣性權重對粒子行為影響分析結果，提出一種慣性權重余弦自適應調整方法如式(9)所示：

ω(t)=0.1+0.9cos(t/maxgen)

(9)

慣性權重余弦自適應調整可以提高粒子行為的自適應性，算法運行初期具有較大的慣性權重，保證粒子的具有較高的行為發(fā)散性，加大搜索范圍，提高全局尋優(yōu)能力、避免算法陷入局部最優(yōu)；算法運行過程中，慣性權重呈逐漸遞減狀態(tài)，集中粒子行為，減小搜索范圍，有利于加速算法收斂，提高算法局部尋優(yōu)能力。

為避免粒子陷入局部最優(yōu)，提高粒子學習能力，根據上文所得粒子行為穩(wěn)定性條件，基于文獻[12]提出的學習因子伴隨慣性權重自適應調整策略，對學習因子進行修正調整，得出自適應調整學習因子c1、c2公式如下：

(10)

因此，本文設計改進粒子群算法速度和位置更新公式為：

vi(t+1)=ω(t)vi(t)+c1(t)r1(t)[Pi(t)-xi(t)]+
c2(t)r2(t)[Pg(t)-xi(t)]

(11)

xi(t+1)=xi(t)+vi(t+1)

(12)

3.3 改進算法流程

本文設計粒子群算法主要流程如圖1所示。

圖1 改進粒子群算法流程

4 實驗仿真

4.1 實驗環(huán)境

為驗證本文改進后的粒子群算法性能，在Win10/MATLAB(R2010b)實驗平臺，Intel(R) Core(TM) i5-6500 CPU@3.19GHz, 8.00GB RAM配置計算機64位操作系統(tǒng)下，設計了基于MATLAB的仿真程序，分別選取Kacem、MK等兩個經典調度案例集進行仿真驗證，并將改進算法的仿真結果與經典粒子群算法、模擬退火算法(Simulated Annealing, SA)的仿真結果進行了對比分析。

4.2 結果分析

本文改進粒子群算法(簡稱CPSO)、經典粒子群算法(簡稱PSO)、模擬退火算法(簡稱SA)三種算法參數設置如下，迭代次數maxgen統(tǒng)一設置為500。其中CPSO、PSO粒子種群規(guī)模N設置為50，CPSO慣性權重與學習因子設置分別選取式(9)、式(10)；PSO慣性權重設置為1，學習因子c1=2.05,c2=2.05。三種算法在Kacem、MK兩個案例集中仿真實驗對比結果分別如表1、表2所示。

表1 Kacem案例集仿真實驗對比結果

表2 MK案例集仿真實驗對比結果

因此通過表1、表2實驗對比結果可以得出，本文改進粒子群算法相比經典粒子群算法、模擬退火算法具有較強的調度優(yōu)化效果。其中MK01最佳調度結果甘特圖如圖2所示，最短完工時間為40。

圖2 MK01最佳調度甘特圖

同時通過圖3中三種算法在工件數n=20，機床數m=4時調度優(yōu)化的加工時間對比曲線可得出，PSO具有較快的收斂速度，但是收斂過早易陷入局部最優(yōu)；SA全局尋優(yōu)能力較強，但是運行初期尋優(yōu)效果較差、收斂緩慢；CPSO提高了算法的全局尋優(yōu)能力，避免了粒子早熟收斂、易陷入局部最優(yōu)等缺點，提高了算法優(yōu)化效果。

圖3 三種算法對比曲線

5 結論

本文針對離散制造車間柔性調度優(yōu)化策略進行研究，建立了一種面向離散制造模式的柔性調度模型，針對柔性調度模型優(yōu)化求解問題，提出了一種慣性權重、學習因子自適應調整的改進粒子群算法，并進行了仿真實驗對比驗證。實驗結果表明，本文改進算法在優(yōu)化車間調度問題方面具有較快的收斂速度以及全局搜索能力，能夠在一定程度上提升了柔性車間調度的效率，對于均衡企業(yè)生產計劃與作業(yè)計劃，提高企業(yè)服務質量有著較高的理論與實際價值。