基于蟻群算法的柔性作業(yè)車(chē)間問(wèn)題求解

何奔洋

（福州大學(xué) 經(jīng)濟(jì)與管理學(xué)院，福建 福州 350111）

0 引言

隨著科技的不斷發(fā)展，社會(huì)環(huán)境也逐漸變得復(fù)雜多變，隨之而來(lái)的是產(chǎn)品的差異化與顧客需求的個(gè)性化逐漸地增強(qiáng)。對(duì)生產(chǎn)企業(yè)來(lái)說(shuō)，制造的產(chǎn)品也從單一品種大批量向多品種小批量逐漸演變。對(duì)于這種變化，傳統(tǒng)的生產(chǎn)調(diào)度方式已難以適應(yīng)，故柔性作業(yè)車(chē)間調(diào)度已逐漸成為生產(chǎn)企業(yè)提升經(jīng)濟(jì)效益的重要手段之一。柔性作業(yè)的調(diào)度方式通過(guò)對(duì)資源的合理分配及利用，從而達(dá)到目標(biāo)最優(yōu)值，能夠減少資源浪費(fèi)，更好地適應(yīng)如今的社會(huì)需求環(huán)境，故此，對(duì)于柔性作業(yè)車(chē)間調(diào)度問(wèn)題的研究也顯得十分必要。趙詩(shī)奎等對(duì)作業(yè)車(chē)間調(diào)度問(wèn)題的模型及求解算法進(jìn)行了總結(jié)，并對(duì)作業(yè)車(chē)間調(diào)度問(wèn)題的發(fā)展前景進(jìn)行了展望[1]，王凌等則對(duì)分布式車(chē)間調(diào)度問(wèn)題的優(yōu)化算法進(jìn)行了分析與總結(jié)[2]，張亞明對(duì)柔性制造生產(chǎn)方式進(jìn)行了深入的討論[3]，李愛(ài)平等則針對(duì)零件族為對(duì)象對(duì)柔性生產(chǎn)線進(jìn)行了設(shè)計(jì)與優(yōu)化[4]，余璇等提出了混合遺傳禁忌搜索算法對(duì)多目標(biāo)柔性作業(yè)車(chē)間調(diào)度問(wèn)題進(jìn)行了求解[5]，何東東搭建了柔性作業(yè)車(chē)間調(diào)度問(wèn)題模型并以改進(jìn)遺傳退火算法求解[6]，李濤等以卷煙制絲的生產(chǎn)為例對(duì)柔性制造技術(shù)進(jìn)行實(shí)際應(yīng)用[7]。

蟻群算法是通過(guò)模擬螞蟻覓食的一種優(yōu)化算法，最早應(yīng)用于TSP問(wèn)題的解決，后被應(yīng)用于各項(xiàng)優(yōu)化問(wèn)題的求解中。因此，基于以上研究，本文引入了蟻群算法對(duì)柔性作業(yè)車(chē)間的調(diào)度問(wèn)題進(jìn)行求解，以柔性作業(yè)車(chē)間調(diào)度問(wèn)題中最大完工時(shí)間的最小化為目標(biāo)，搭建了優(yōu)化模型，并引入了實(shí)例，驗(yàn)證了模型的適用性及蟻群算法在求解柔性作業(yè)車(chē)間調(diào)度問(wèn)題的可行性。

1 模型建立

1.1 問(wèn)題描述

柔性作業(yè)車(chē)間調(diào)度問(wèn)題可以描述為：有m個(gè)進(jìn)行加工的器械，共n個(gè)零件待加工。第i個(gè)零件的工序數(shù)為qi且qi＞1，對(duì)于相同零件的工序加工順序有要求；每道工序至少可由一個(gè)機(jī)器進(jìn)行生產(chǎn)，并且同一道工序經(jīng)不同的機(jī)器加工時(shí)間也不同；不同的零件之間的工序可以不同。通過(guò)靈活地調(diào)度資源，以進(jìn)行對(duì)各道工序的加工順序、加工機(jī)器的合理分配，從而實(shí)現(xiàn)工序最大加工時(shí)間最小的目標(biāo)，以提升效率減少成本。

1.2 模型分析

在對(duì)工序的時(shí)間和資源進(jìn)行分配及安排時(shí)，常常會(huì)遇到許多現(xiàn)實(shí)問(wèn)題，因此，為了令模型更加地貼近實(shí)際，模型需滿足以下約束條件：

（1）任一工序可用的加工機(jī)器數(shù)大于一；

（2）同一時(shí)刻每個(gè)加工器械僅可加工一道工序；

（3）每個(gè)零件的任一工序僅可加工一次，且同一時(shí)刻僅可由一個(gè)機(jī)器加工；

（4）每道工序開(kāi)始加工后必須加工完成，不可中斷；

（5）每個(gè)零件的不同工序間存在順序要求，不同零件的工序間不存在順序要求。

模型主要參數(shù)包括：

Fij：工序Oij加工完成的時(shí)間

Fijk：工序Oij在機(jī)器Mk上結(jié)束加工的時(shí)間

Bijk：工序Oij在機(jī)器Mk上開(kāi)始加工的時(shí)間

pijk：工序Oij在機(jī)器Mk上的加工時(shí)間

1.3 模型建立

根據(jù)上述分析，建立工序最大完工時(shí)間的最小值優(yōu)化函數(shù)為：

由上即為優(yōu)化模型，其中：公式（1）為目標(biāo)函數(shù)，表示求所有的零件中最大的工序加工時(shí)間的最小值；公（2）表示的是工藝約束，即每個(gè)零件的各個(gè)工序必須按照順序進(jìn)行加工；式（3）表示每道工序由一臺(tái)機(jī)器加工且僅可加工一次，且開(kāi)始加工后必須加工直至完成不可中斷；式（4）為同一加工機(jī)器在同一時(shí)間僅可加工一道工序。

2 算法設(shè)計(jì)

本文使用蟻群算法對(duì)問(wèn)題進(jìn)行求解。蟻群算法是通過(guò)模擬螞蟻覓食的生物行為，根據(jù)螞蟻?zhàn)哌^(guò)的每條支路的長(zhǎng)短等因素來(lái)計(jì)算支路上信息素的濃度，并根據(jù)信息素濃度的大小來(lái)計(jì)算選擇該支路的概率，并以輪盤(pán)賭的方式?jīng)Q定是否接受此解，從而在全局范圍內(nèi)搜索滿意解。本文算法流程如圖1所示。

圖1 算法流程圖

蟻群算法首先進(jìn)行各參數(shù)的初始化，隨后螞蟻隨機(jī)選擇覓食路徑，并在路徑上留下分泌的信息素，信息素濃度與路徑的長(zhǎng)短成反比，同時(shí)信息素會(huì)揮發(fā)。后續(xù)螞蟻進(jìn)行搜索時(shí)會(huì)根據(jù)信息素的濃度選擇路徑，信息素濃度更高的路徑會(huì)有更大的概率被選中。隨著搜尋螞蟻數(shù)量的不斷增多，信息素的濃度會(huì)逐漸增高，最終搜索出最優(yōu)的方案。

3 實(shí)驗(yàn)計(jì)算

3.1 算例數(shù)據(jù)

為驗(yàn)證優(yōu)化模型及算法的實(shí)用性，引入了算例對(duì)模型及算法進(jìn)行仿真比較。表1中給出了6個(gè)零件以及10個(gè)加工機(jī)器的實(shí)例。其中包括了每個(gè)零件的各道工序的可加工的機(jī)器及不同機(jī)器上的加工時(shí)間。每列工序下左列為該道工序可進(jìn)行加工的機(jī)器設(shè)備，右列為不同機(jī)器上的加工時(shí)間，每道工序均有至少一個(gè)機(jī)器進(jìn)行加工，每個(gè)零件具有6道不同的工藝。

表1 零件加工實(shí)例

3.2 算法參數(shù)設(shè)置

對(duì)于本文所使用的蟻群算法，需要事先設(shè)置算法初始參數(shù)，參數(shù)設(shè)置如表2所示。

表2 算法參數(shù)設(shè)置

3.3 實(shí)驗(yàn)結(jié)果

本文采用MATLAB編程求解。通過(guò)求解得到最優(yōu)解為47min，可得到最小工時(shí)為47min的甘特圖，最優(yōu)解甘特圖如圖2所示。根據(jù)甘特圖進(jìn)行結(jié)果分析可得到，機(jī)器平均利用率為44.1%，其中機(jī)器1與機(jī)器10利用率最低，僅為6.4%，利用率遠(yuǎn)低于平均利用率，而利用率最高的機(jī)器4與機(jī)器5則高達(dá)80.9%，最高機(jī)器利用率和最低機(jī)器利用率之間相差較大。所以在日常生產(chǎn)加工過(guò)程中，企業(yè)可針對(duì)利用率低的機(jī)器1和機(jī)器10進(jìn)行改善，解決其利用率過(guò)低的問(wèn)題，提高資源利用率。同時(shí)對(duì)于利用率較高的機(jī)器4和機(jī)器5需要做好日常維護(hù)，防止其因?yàn)槭褂眠^(guò)度而出現(xiàn)損壞等現(xiàn)象。

圖2 最優(yōu)解甘特圖

由圖3，給出了蟻群算法求解結(jié)果的目標(biāo)函數(shù)優(yōu)化曲線。由圖可見(jiàn)，目標(biāo)函數(shù)迭代至第10代即可得到最優(yōu)值，從最初的54min下降至最優(yōu)解47min，顯示了良好的收斂效果。通過(guò)優(yōu)化模型優(yōu)化后，加工總耗時(shí)相較優(yōu)化前降低了13.0%，顯示了良好的優(yōu)化效果，由此可見(jiàn)本文模型可以大幅度減少生產(chǎn)作業(yè)中柔性調(diào)度的完工時(shí)間，對(duì)柔性作業(yè)車(chē)間調(diào)度問(wèn)題有良好的優(yōu)化效果。并從實(shí)例中可看出，蟻群算法在計(jì)算中表現(xiàn)良好，能夠有效地求解出最優(yōu)解，并可適用于柔性作業(yè)車(chē)間調(diào)度問(wèn)題的模型求解中，在解決柔性作業(yè)車(chē)間調(diào)度問(wèn)題中具有較強(qiáng)的實(shí)用性。

圖3 算法迭代圖

生產(chǎn)力不斷發(fā)展，社會(huì)也不斷地進(jìn)步，單品種大批量制造中常用的調(diào)度方式已出現(xiàn)靈活度差、難以適應(yīng)強(qiáng)個(gè)性化需求等種種問(wèn)題，柔性作業(yè)車(chē)間調(diào)度的方式逐漸成為主流。本文基于此根據(jù)實(shí)際情況設(shè)立了約束條件，以完工實(shí)際最小化為優(yōu)化目標(biāo)搭建了整數(shù)規(guī)劃模型。采用了蟻群算法對(duì)模型進(jìn)行求解，并為驗(yàn)證模型和算法的實(shí)用性和應(yīng)用價(jià)值引入實(shí)例進(jìn)行仿真對(duì)比。從結(jié)果中可以看出，本文所設(shè)計(jì)的算法及搭建的模型具有較好的優(yōu)化效果及收斂性，可作為生產(chǎn)柔性調(diào)度作業(yè)問(wèn)題中的優(yōu)化求解工具。在今后的生產(chǎn)作業(yè)優(yōu)化中也具有較大的實(shí)用性，可根據(jù)具體情況靈活求解不同問(wèn)題，具有較高的使用價(jià)值。