基于GA-IPSO算法的柔性生產(chǎn)線高級計劃排程方法研究*

吳永明，張晗，徐艷霞，趙旭東

(貴州大學 現(xiàn)代制造技術(shù)教育部重點實驗室，貴陽 550025)

0 引言

高級計劃排程(APS)是一種包含了眾多數(shù)學模型可以有效提高排程效率的生產(chǎn)線排程方法，可以有效解決企業(yè)遇到的多任務(wù)、多工序的生產(chǎn)排程問題。

目前，大部分學者針對高級計劃與排程問題的研究主要集中在構(gòu)造模型及求解算法等方面。寧維巍等分析了APS技術(shù)在這兩種生產(chǎn)管理下的應用情況[1]。黃健等提出了一種面向多品種小批量混裝線的高級計劃排程模型[2]。Krenczyk等提出了一種集成物料規(guī)劃系統(tǒng)與高級計劃排程系統(tǒng)的排程模型，通過可視化方法來進行生產(chǎn)計劃排程[3]。Bhawarkar等提出一種減少機器閑置時間和拖期懲罰高級計劃排程方法[4]。Ornek針對制造資源計劃系統(tǒng)無法考慮車間容量變換的問題，提出了基于約束規(guī)劃建立的高級計劃排程模型[5]。Marcosiris等提出了一種基于瓶頸分配方式的高級計劃排程模型以減少其在瓶頸問題中的影響[6]。Kenn等針對供應鏈設(shè)計了高級計劃排程系統(tǒng)，體現(xiàn)了排程系統(tǒng)的智能性[7]。James等針對設(shè)備負荷設(shè)計出一種根據(jù)零件工藝自動分配生產(chǎn)線的高級計劃排程系統(tǒng)[8]。劉晨等構(gòu)造了高級計劃排程模型并采用不等長矩陣的編碼方式的遺傳算法求解，但易在陷入局部最優(yōu)[9]。范營營等設(shè)計了一種啟發(fā)式算法縮短產(chǎn)品在車間的流動時間，提高了資源利用率，使派工層面科學化、正規(guī)化[10]。張騰飛等提出一種改進遺傳算法求解作業(yè)調(diào)度問題[11]。

然而，大部分學者對于APS模型的建立忽略了實際生產(chǎn)過程中，生產(chǎn)力較為不足或要求更快的交付定單等情況。針對上述問題，本文基于混合整數(shù)規(guī)劃，以最小化完工時間、降低生產(chǎn)成本為生產(chǎn)線排程優(yōu)化目標，建立高級計劃排程模型。在模型中將部分工序外包以解決由于生產(chǎn)能力不足導致訂單無法按時交付的問題。設(shè)計了一種GA-IPSO優(yōu)化算法求解高級計劃排程模型，在粒子的尋優(yōu)搜索過程當中實時動態(tài)地改變慣性權(quán)重值，并對粒子進行交叉、變異等操縱以增添粒子的多樣性，提升優(yōu)化算法的計算精度和尋優(yōu)搜索能力，防止優(yōu)化結(jié)果陷入局部最優(yōu)。通過實例驗證了高級計劃排程模型及優(yōu)化算法在提高企業(yè)排程效率問題上的有效性。

1 基于混合整數(shù)規(guī)劃的高級計劃排程模型

1.1 模型描述

及時可靠地交付訂單產(chǎn)品是制造型企業(yè)提高市場競爭力的基本條件，是生產(chǎn)線調(diào)度排程的重要目標之一。當企業(yè)因控制成本或生產(chǎn)能力限制無法按時完成訂單時，將生產(chǎn)過程中的部分工序外包成為一種合理的選擇。因而，結(jié)合混合整數(shù)規(guī)劃，創(chuàng)建一種基于高級計劃和排程方法的優(yōu)化模型。圖1為高級計劃排程優(yōu)化模型的示意圖。

圖1 排程模型示意圖

1.2 模型的假設(shè)條件

(1)機器間相互獨立，不存在先后關(guān)系；

(2)機器在某一時刻只能加工一個工序任務(wù)；

(3)每臺機器具有固定且已知的準備時間；

(4)機器在開始加工零件之后無法停止；

(5)機器單次只可加工某一道工序；

(6)零件在機器上的加工時間已確定。

1.3 參數(shù)和變量說明

Oi：訂單(i=1,2,...,o)，其中：o為訂單數(shù)量；

Si：訂單Oi中未外包工序的總加工時間；

Di：訂單Oi中外包工序的總加工時間；

DTi：訂單Oi中外包工序的運輸時間；

Mr：零件編號(r=1,2,...,R)，其中：R為零件數(shù)量；

Nj：工序編號(j=1,2,...,J)，其中：J為工序數(shù)量；

rk：機器準備時間。

1.4 模型構(gòu)建

(1)

Si,Di,DTi≥0,?i.

(2)

rk>0

(3)

其中，公式(1)為以最小化訂單總完成時間為目標的函數(shù)；公式(2)限定訂單完工時間，運輸時間均為正數(shù)；公式(3)限定機器準備時間為正數(shù)。

2 基于GA-IPSO算法的APS模型求解

采用粒子群算法求解APS優(yōu)化模型。該算法具有操作簡便、精度高、收斂快等優(yōu)點，但是存在容易陷入局部最優(yōu)等問題。對此，加入遺傳算法中的交叉和變異等功能以提高算法的全局和局部意義下的搜索能力和效率。

2.1 粒子群算法

粒子群算法中的每一個粒子均具備兩個屬性：速度V和位置X。速度表示粒子搜索的快慢，位置表示粒子搜索的方向。粒子在解空間中獨立地搜索最優(yōu)解，并將其記為當前個體極值Pbest。將當前個體極值與粒子群中其他粒子相比較，得到最優(yōu)個體極值設(shè)為粒子群的全局最優(yōu)解Gbest。粒子群中的全部粒子依據(jù)尋優(yōu)得到的個體最優(yōu)解Pbest和全局最優(yōu)解Gbest來調(diào)整粒子自身的速度和位置。速度與位置的更新公式為：

(4)

(5)

式中，ω為慣性權(quán)重，以保持原本速度；C1為粒子追蹤歷史個體最優(yōu)解的權(quán)重系數(shù)；C2為粒子追蹤粒子全體最優(yōu)解的權(quán)重系數(shù)；ξ，η為[0，1]區(qū)間均勻分布的隨機數(shù)。圖2為基本粒子群算法的流程圖。

圖2 基本粒子群算法流程圖

2.2 GA-IPSO算法

圖3 遺傳-粒子群算法流程圖

2.3 算法步驟

2.3.1 初始化粒子種群

由于基本粒子群算法屬于連續(xù)尋優(yōu)過程，而生產(chǎn)線的工序排程為離散過程，因此必要對粒子進行某一方式編碼，用以擬定不同零件及不同工序之間的加工順序優(yōu)先級。對于m個零件，n道工序，其對應的粒子長度為m×n，每一道工序?qū)粋€10～30范圍內(nèi)的隨機數(shù)。與工序?qū)S機數(shù)執(zhí)行倒序排序，排序優(yōu)先級表示該工序加工優(yōu)先級。

2.3.2 目標函數(shù)

2.3.3 更新粒子的速度和位置

慣性權(quán)重是基本粒子群算法中更新粒子自身尋優(yōu)速度的最重要的參數(shù)。較大的設(shè)定值利于提升算法的全局尋優(yōu)能力，較小則增強算法的局部尋優(yōu)能力。基本粒子群算法的慣性權(quán)重通常采用固定值，但其缺點在于尋找最優(yōu)解的過程中，粒子群的多樣性容易隨著迭代過程而逐步降低，從而導致結(jié)果陷入局部最優(yōu)?，F(xiàn)加入一種動態(tài)改變慣性權(quán)重的方法，用來保持粒子群在迭代過程中的多樣性，避免結(jié)果陷入局部最優(yōu)。各代的慣性權(quán)重表達式為：

“妙在似與不似之間”，這是老觀念，傳承就是要像，不像就不叫傳承，首先是傳承，或者叫繼承，才能談得上創(chuàng)新。先要走入，方能走出。連老師的皮毛都沒有學到，形與神都學不像，談何創(chuàng)新？只有學不像老師的人，才天天說要創(chuàng)新，因為學不會老東西，只能講創(chuàng)新。真正的學生，通常都會說，一輩子連老師的皮毛都沒有學到，這不能理解為謙辭。

(6)

式中，gn為迭代次數(shù)；gnmax為最大迭代次數(shù)；ωs為初始慣性權(quán)重，取1.2；ωe為迭代至最大次數(shù)時的慣性權(quán)重，取0.4。

同時，為增加粒子的收斂性，現(xiàn)加入速度限制范圍。設(shè)置編碼后產(chǎn)生隨機速度范圍的0.25倍，即粒子的速度區(qū)間。分別按公式(4)、式(5)重置粒子的尋優(yōu)速度和位置。

2.3.4 粒子的交叉

現(xiàn)將遺傳算法中的交叉增添至粒子群算法的搜索過程中。采用隨尋優(yōu)搜索過程動態(tài)變化的交叉概率以增加交叉粒子的多樣性。計算公式為：

(7)

式中，pc為交叉概率；pcmax為最大交叉概率，取1；pcmin為最小交叉概率，取0.5。采取兩點交叉法以及隨機抽取交叉法進行交叉操作。生成一個[0，1]區(qū)間內(nèi)隨機數(shù)，若其小于0.5，則采取兩點交叉法；否則，采取隨機抽取交叉法。兩點交叉法操作如下：

(1)從全部粒子中隨機選取兩個粒子作為父代粒子進行交叉操作；

(2)隨機生成兩個交叉點并保證交叉長度界限大于粒子總長度的1/3且小于粒子總長度的2/3；

(3)將所選取的兩個粒子中，位于兩交叉點之間的部分進行交換，生成兩個新的子代粒子，交叉結(jié)束。

隨機抽取交叉法操作如下：

(1)從全部粒子中隨機選取兩個粒子作為父代粒子進行交叉操作；

(2)生成與粒子相同長度的list列表，列表中隨機排列元素1和2；

(3)將第一條粒子中與list列表中元素1所在位置對應的位置中的元素提取出，將第二條粒子中與list列表中元素2所在位置對應的位置中的元素提取出，組成一條新的粒子；

(4)將上述操作執(zhí)行兩遍，生成兩條新的子代粒子，交叉結(jié)束。

2.3.5 粒子的變異

粒子群算法的變異過程為：基于輪盤賭選擇法，隨機抽取種群中某一粒子；生成一個(0,1)間的隨機實數(shù)r，若r小于變異概率pm=0.1，則經(jīng)由編碼方法隨機產(chǎn)生新粒子替換之前粒子；否則，依次對下一粒子執(zhí)行上述操作。

2.4 GA-IPSO算法的特點

(1)粒子群算法采用速度和位置更新公式來重置各代粒子，遺傳算法即不斷經(jīng)由父代染色體間的交叉得到子代。兩種算法的聯(lián)合,可以有效地增強粒子的全局尋優(yōu)能力、速度以及精度。

(2)粒子群算法參數(shù)選擇要求較低，而遺傳算法則對參數(shù)要求較高，兩算法的結(jié)合可以在不影響優(yōu)化性能的前提下降低對于參數(shù)設(shè)置的要求。

3 算例驗真與分析

結(jié)合某一制造型企業(yè)接到的客戶訂單來驗證高級計劃排程模型及求解算法的有效性。訂單包括6個零件，每一個零件需要6道工序來完成，訂單要求總完成時間低于320min，現(xiàn)有共5臺機器來完成該訂單。各臺機器的準備時間分別為20，10，10，15，20min。表1為各零件的各道工序制造時間，表2為各零件的各道工序所屬加工機器的編號。

表1 各工序制造時間(單位：min)

表2 各工序所屬加工機器編號

經(jīng)由基本粒子群算法和遺傳-粒子群算法分別對高級計劃排程模型進行求解，參數(shù)設(shè)定為：種群規(guī)模100；迭代次數(shù)100次；c1,c2為2.05；終止條件即迭代次數(shù)。兩種算法均由Matlab軟件編程實現(xiàn)。將數(shù)據(jù)代入可得到各工序最優(yōu)加工順序甘特圖及最短加工完成時間。圖4為3種情況下的尋優(yōu)過程對比圖。表3為實驗結(jié)果對比。

圖4 迭代對比圖

參數(shù)算法類型基本粒子群算法(未外包工序)GA-IPSO算法(未外包工序)GA-IPSO算法(外包工序)運行時間3.82s5.66s3.96s最優(yōu)解335min318min288min最優(yōu)解的迭代次數(shù)4次33次26次

由3種算法的迭代圖以及實驗結(jié)果對比表可知，基本粒子群算法的運行時間較短且在第4代便搜索出最優(yōu)解，明顯出現(xiàn)陷入局部最優(yōu)的情況，導致尋優(yōu)精度較差。而GA-IPSO的執(zhí)行時間雖較長，但其在迭代進化的過程中有效的避免了進入局部最優(yōu)，提高了算法的求解精度，使算法更好地趨近全局最優(yōu)解。在未外包工序時，遺傳—粒子群算法求解得到的訂單總完成時間為318min，僅比訂單要求時間提前兩分鐘。但在實際操作過程中，如機器操作問題等突發(fā)狀況會導致實際生產(chǎn)時間不如排程結(jié)果精確從而導致訂單無法按時交付。因而，排程優(yōu)化結(jié)果并不足以完成要求。

現(xiàn)將6號零件的第3～6道工序安排至其他企業(yè)的租賃機器進行生產(chǎn)。其中，租賃機器無生產(chǎn)準備時間，生產(chǎn)所需原材料的運輸時間及零件完成后運輸回企業(yè)的運輸時間均為76min。將數(shù)據(jù)代入排程優(yōu)化模型并求解得到最優(yōu)工序排程甘特圖及最小完工時間。圖5、圖6為排程結(jié)果調(diào)度甘特圖。表4為未外包工序與外包工序情況下的排程結(jié)果對比表。

圖5 GA-IPSO算法的調(diào)度甘特圖(未外包工序)

圖6 GA-IPSO算法的調(diào)度甘特圖(外包工序)

參數(shù)排程類型未外包工序外包工序生產(chǎn)完工時間318min288min機器等待時間249min224min

實驗結(jié)果表明：加入了遺傳算法部分功能后的GA-IPSO算法能夠極大地降低算法在求解過程中進入局部最優(yōu)的概率，有效提高了算法的求解精度。并且租賃其他企業(yè)的生產(chǎn)機器時，通過高級計劃排程模型進行生產(chǎn)線排程，可得到最小完工時間為288min，生產(chǎn)過程中各機器的空閑時間為224min，明顯少于未租賃機器時的排程結(jié)果。租賃其他廠的生產(chǎn)線能夠極大減少零件制造時間，降低生產(chǎn)過程中各臺機器的等待時間，壓縮了生產(chǎn)成本，有效地提升了企業(yè)的生產(chǎn)效率。

4 結(jié)論

本文構(gòu)建了一種基于高級計劃排程方法的生產(chǎn)線排程模型，通過實例驗證得出以下結(jié)論：

(1)結(jié)合租賃生產(chǎn)線后的高級計劃排程模型能夠較快得到最優(yōu)工序排程計劃，有效地降低了總完工時間，壓縮了生產(chǎn)成本。

(2)在GA-IPSO算法迭代過程中輔以交叉和變異等操作，同時隨尋優(yōu)動態(tài)地改變慣性權(quán)重。仿真結(jié)果驗證了該算法能夠提高粒子的適應度，加快粒子的尋優(yōu)過程并能有效地避免結(jié)果陷入局部最優(yōu)。

本文構(gòu)建的高級計劃排程模型及求解算法具有一定的通用性，為未來企業(yè)制定生產(chǎn)計劃提供了新的思路。