李 凡，李順江，何玉東

（成都四威高科技產(chǎn)業(yè)園有限公司，四川 成都 610000）

1 引言

光伏業(yè)是未來最清潔、安全和可靠的能源，行業(yè)發(fā)展前景良好，智能物流可有效降低電池片在運(yùn)送過程中的損耗并大幅減少現(xiàn)場用工需求，有效降低企業(yè)生產(chǎn)環(huán)節(jié)的成本，因此很多光伏企業(yè)在構(gòu)建符合自身特點(diǎn)的智能工廠時，都將物流作為主要改造方向。智能物流系統(tǒng)的任務(wù)調(diào)度方法對車間生產(chǎn)效率和AGV 有效利用率有重要影響。目前國內(nèi)外對AGV 調(diào)度策略方面主要研究方向主在路徑規(guī)劃優(yōu)化、作業(yè)系統(tǒng)的效率優(yōu)化方向，大多文獻(xiàn)均是關(guān)于實(shí)現(xiàn)以上優(yōu)化目標(biāo)的算法及其效率。如：文獻(xiàn)[1]提出最小化岸橋操作的延遲時間和自動導(dǎo)引車的總行駛時間,來提高碼頭的裝卸效率[1]；文獻(xiàn)[2]提出了一種改進(jìn)的遺傳算法進(jìn)行AGV 任務(wù)的分配和路徑的優(yōu)化,通過改進(jìn)遺傳算法的變異算子,提高種群的收斂速度和收斂性[2]；文獻(xiàn)[3]針對汽車流水線的布局特征，以AGV 小車?yán)眯首罡?、?shù)量配置最少為目標(biāo)建立數(shù)學(xué)模型，提出了一種改進(jìn)的兩階段啟發(fā)式算法[3]；文獻(xiàn)[4]提出采用改進(jìn)遺傳算法來求解AGV 路徑，改進(jìn)遺傳算法具有更快的收斂速度，并且得到最優(yōu)解的概率更高[4]；文獻(xiàn)[5]提出以AGV運(yùn)行時間最短為目標(biāo),將多種群遺傳算法引入到兩階段路徑規(guī)劃策略[5]；文獻(xiàn)[6]提出以平均隊(duì)長和逗留時間作為性能指標(biāo)，由泊松過程和排隊(duì)論的基本理論建立M/M/1 排隊(duì)模型[6]；文獻(xiàn)[7]以岸橋前小車作業(yè)延遲時間和岸橋后小車與AGV 間的等待時間之和最小為目標(biāo)函數(shù)，建立了帶有時間窗約束的AGV調(diào)度混合整數(shù)規(guī)劃模型[7]；文獻(xiàn)[8]主要研究AGV 最優(yōu)調(diào)度方案和最佳AGV 數(shù)量匹配關(guān)系[8]，文獻(xiàn)[9]提出了以卸船完工時間最小化為目標(biāo)，提出考慮任務(wù)順序約束的岸橋與集卡聯(lián)合調(diào)度的混合整數(shù)規(guī)劃（MixedInteger Programming，MIP）模型和約束規(guī)劃模型約束的岸橋與集卡聯(lián)合調(diào)度的混合整數(shù)規(guī)劃（MixedInteger Programming，MIP）模型和約束規(guī)劃模型[9]。

文獻(xiàn)[5]、文獻(xiàn)[9]有提到任務(wù)排序但未給出明確的排序模型，其他文獻(xiàn)均未提到任務(wù)排序，然而在太陽能電池片生產(chǎn)現(xiàn)場，由于工序之間嚴(yán)格的先后關(guān)系、生產(chǎn)線產(chǎn)量要求、工序產(chǎn)出物料嚴(yán)格的存放時間要求等因素均對AGV 調(diào)度策略有決定性的影響，不能簡單的以整體物流搬運(yùn)效率最高為優(yōu)化目標(biāo)，因此針對太陽能電池生產(chǎn)線物流任務(wù)調(diào)度方法研究有重要意義。

本文主要創(chuàng)新點(diǎn)是針對太陽能電池生產(chǎn)線的特點(diǎn)，建立了物流任務(wù)排序模型，提出了將任務(wù)優(yōu)化的目標(biāo)集合從當(dāng)前所有任務(wù)，縮小為不大于該區(qū)域AGV 數(shù)量的任務(wù)，并針對該縮小后的任務(wù)集合進(jìn)行優(yōu)化，提出了優(yōu)化目標(biāo)函數(shù)及任務(wù)執(zhí)行時間計(jì)算方法，并采用匈牙利算法進(jìn)行求解，提高了求解效率且降低了優(yōu)化問題的復(fù)雜度。該調(diào)度策略相比本項(xiàng)目初期的調(diào)度方法提高了生產(chǎn)線產(chǎn)量、保障了工序產(chǎn)出物料不超時、提高了AGV有效利用率。

2 太陽能電池片生產(chǎn)線特點(diǎn)

如圖1產(chǎn)線流程圖所示，太陽能電池片車間中每條自動化生產(chǎn)線中有15臺設(shè)備，分別負(fù)責(zé)10道不同工序,工序與工序之間設(shè)有物料緩存區(qū)；設(shè)備與設(shè)備，設(shè)備與緩存之間通過AGV 搬運(yùn)花籃傳遞物料，花籃中裝滿了硅片，部分工序花籃中硅片消耗完后需通過AGV將空花籃返回上工序。每個設(shè)備有至少一個送料口和出料口與AGV 進(jìn)行對接傳遞花籃；當(dāng)送料口空或出料口滿的情況下，每個設(shè)備均有少量緩存，如果沒有AGV及時將物料運(yùn)送到該設(shè)備或?qū)⑽锪蠌脑撛O(shè)備取出，則該設(shè)備不能繼續(xù)生產(chǎn)，同時每個工序的產(chǎn)出物其可存放時間有明確要求，產(chǎn)線產(chǎn)量以最后一道工序的產(chǎn)出為準(zhǔn)。

物流路線有3類：設(shè)備到設(shè)備、設(shè)備到緩存、緩存到設(shè)備，所有的物流運(yùn)送均采用AGV，每臺AGV一次只能執(zhí)行1個物流任務(wù)。

圖1 產(chǎn)線流程圖

3 問題建模

3.1 任務(wù)排隊(duì)模型

由于產(chǎn)線跨度達(dá)250m，為提高運(yùn)輸效率，首先對產(chǎn)線進(jìn)行分區(qū)，不同分區(qū)的AGV單獨(dú)調(diào)度。

I表示第i個區(qū)域，Ri表示第i區(qū)域任務(wù)排序后的集合;Qin表示是i區(qū)域第n個任務(wù)的優(yōu)先級，Qin越大任務(wù)排序越靠前；N表示產(chǎn)線工序數(shù)量; Tin表示第n個任務(wù)的等待時間，γin為第n 個任務(wù)超時報(bào)警閾值，是一個常量;k 表示任務(wù)所在工序段編號;h 表示任務(wù)類型。以不因等待產(chǎn)生報(bào)廢品、生產(chǎn)線產(chǎn)量最高為目標(biāo)，任務(wù)排隊(duì)?wèi)?yīng)滿足以下約束條件：

（a）后工序段物流需求大于前工序段物流需求。

（b）同優(yōu)先級的任務(wù)，按其任務(wù)產(chǎn)生時間排序。

（c）超過設(shè)置的等待時間最大值的任務(wù)優(yōu)先級高于其他區(qū)域內(nèi)未超時的任務(wù)。

（d）連接任務(wù)不參與排序：指本任務(wù)的終點(diǎn)是某物流任務(wù)的起點(diǎn),在AGV執(zhí)行完當(dāng)前分配的任務(wù)后，必須立即執(zhí)行連接任務(wù)。

以上規(guī)則可用以下公式表示：

其中

其中

K 表示物流任務(wù)屬于那兩個工序間。如1 表示工序1與工序2之間。

任務(wù)類型h值含義：h=1表示上工序機(jī)臺到緩存；h=2 表示緩存到上工序機(jī)臺；h=3 表示下工序機(jī)臺到上工序機(jī)臺；h=4表示到下工序機(jī)臺到緩存；h=5表示緩存到下工序機(jī)臺；h=6表示上工序機(jī)臺下工序機(jī)臺。

3.2 分組優(yōu)化策略及目標(biāo)函數(shù)

由于產(chǎn)線生產(chǎn)過程中異常較多，物流需求有一定隨機(jī)性，物流任務(wù)的排序順序會隨新物流需求的產(chǎn)生在不斷變化，因此針對區(qū)域內(nèi)當(dāng)前所有任務(wù)進(jìn)行最優(yōu)解求解，不僅需要的時間長，而且也不能保證整體上是最優(yōu)解，因此在本太陽能電池片生產(chǎn)車間中采用以下策略進(jìn)行任務(wù)調(diào)度。

（a）開始執(zhí)行的任務(wù)不再參與任務(wù)的分配。

（b）對某區(qū)域內(nèi)物流任務(wù)排序，排序后按區(qū)域內(nèi)agv 數(shù)量將排名前n 個任務(wù)組成一組,要求組內(nèi)任務(wù)執(zhí)行時間最短.

（c）有新物流任務(wù)產(chǎn)生且影響到前n個任務(wù)排序時，重新進(jìn)行任務(wù)分配。

Taskk表示排序后某區(qū)域內(nèi)的第k個物流任務(wù)，i為該區(qū)域內(nèi)agv 小車數(shù)量,該區(qū)域內(nèi)任務(wù)分配的對象可用以下集合表示：

為保障物流任務(wù)執(zhí)行效率，以i個agv執(zhí)行k個物流任務(wù)時其所用時間最短為目標(biāo)，優(yōu)化目標(biāo)函數(shù)可用以下公式表示：

Tik表示:第i個AGV執(zhí)行第k個任務(wù)所時間。

3.3Tik計(jì)算

設(shè)某區(qū)域有i臺AGV，k個物流任務(wù)(如果k＞i則按先產(chǎn)生先服務(wù)和分組策略選前i個產(chǎn)生的物流任務(wù))，每個agv執(zhí)行第k個物流任務(wù)所需時間：

其中ai表示第i個agv執(zhí)行完當(dāng)前任務(wù)所需時間,如果agv當(dāng)前沒有任務(wù)則?i=0，否則：

其中Δi1表示agv由當(dāng)前所在位置到上貨點(diǎn)并取到貨所需時間;Δi2表示由上貨點(diǎn)到下貨點(diǎn)并送完貨所需時間；如果agv已取到貨，則Δi1=0，Δi2表示當(dāng)前所在位置到下貨點(diǎn)并送完貨需時間，Δi1、Δi2的計(jì)算是方法是根據(jù)“迪杰斯特拉”算法獲取從P1點(diǎn)到Pn所需經(jīng)過的所有點(diǎn)，那么可依據(jù)點(diǎn)的坐標(biāo)得到agv小車實(shí)際需要行駛的距離，用函數(shù)Dis(P1,P2,...,Pn)表示。因此第i輛agv到達(dá)目的地Pn所需時間如下，γ表示花籃傳輸時間，是一個常量：

βik表示第i個agv執(zhí)行第k個任務(wù)所需時間：

其中Δi3表示agv由執(zhí)行完上一次任務(wù)后所在位置到上貨點(diǎn)并取到貨所需時間；Δi4表示由上貨點(diǎn)到下貨點(diǎn)并送完貨所需時間，其計(jì)算方式與Δi1、Δi2的計(jì)算方式一致。

4 匈牙利算法介紹

1955年，庫恩提出了指派問題解法，該方法以匈牙利數(shù)學(xué)家康尼格提出的關(guān)于矩陣中0元素的定理為基礎(chǔ)，因此得名匈牙利法。該解法中指出，指派問題最優(yōu)方案就是要在n階系數(shù)矩陣中找出n個分布于不用行不同列的元素使得他們的和最小。

匈牙利算法的本質(zhì)是通過對n階系數(shù)矩陣進(jìn)行變換使得矩陣中的獨(dú)立0元素與矩陣的階數(shù)一致，然后將系數(shù)矩陣中的所有獨(dú)立0元素都變成元素1，而其他元素均變成0元素，得到的新矩陣便為原指派問題的解矩陣，根據(jù)解矩陣中0元素所在的行、列數(shù)，就可確定最優(yōu)的任務(wù)分配組合。

獨(dú)立0 元素指該0 元素所在的行和列中不能再有其他的獨(dú)立0元素。

5 算法驗(yàn)證

假設(shè)i=3,k=2，AGV1當(dāng)前坐標(biāo)點(diǎn)是P0，AGV2當(dāng)前坐標(biāo)點(diǎn)是P4，AGV3當(dāng)前坐標(biāo)點(diǎn)是P11，有2個待執(zhí)行任務(wù)，從P2至P3，P8至P9，所有agv當(dāng)前均沒有執(zhí)行任務(wù)，因此由于i＜k，因此不用對任務(wù)排序，直接進(jìn)入分組優(yōu)化。

根據(jù)“迪杰斯特拉”算法計(jì)算，AGV1（編號78）、AGV2（編號76）、AGV3（編號75）執(zhí)行物流任務(wù)時的路徑如圖2、3、4 所示，路徑中點(diǎn)的坐標(biāo)見表2，agv 速度S=0.5m/s，每次對接時間γ=30s，由公式（6），（7），（8），（9）可計(jì)算出AGV1和AGV2按執(zhí)行任務(wù)時各自需要的時間見表1：

表1 AGV執(zhí)行任務(wù)時間

圖2 AGV1路徑

圖3 AGV2路徑

圖4 AGV3路徑

以每個agv 執(zhí)行每一個任務(wù)所需時間作為矩陣的1行，構(gòu)建如下所示待求解矩陣。

表2 各路徑點(diǎn)坐標(biāo)

由于匈牙利算法只支持對n階該矩陣（行數(shù)與列數(shù)相等）進(jìn)行變換，因此需采用補(bǔ)充i-k 個虛擬物流任務(wù)且每個agv 執(zhí)行時間均為0 的方式，從而得到該問題的待求解矩陣如下

采用匈牙利算法對其進(jìn)行求解，其過程及結(jié)果如下,如圖5所示：

圖5 矩陣變換過程

為獨(dú)立0元素，第三個矩陣的獨(dú)立0元素的個數(shù)等于矩陣階數(shù)，因此將獨(dú)立0元素改為1，獨(dú)立0元素以外的其他元素全部改為0，即可得到最優(yōu)解矩陣，并通過該矩陣可知最優(yōu)分配方案為：由AGV1執(zhí)行第1 個物流任務(wù)，AGV2 執(zhí)行第3 個虛擬物流任務(wù)，AGV3執(zhí)行第2個物流任務(wù)。最優(yōu)分配方案下執(zhí)行完所有任務(wù)所需最少時間為：

由于i,k 均較小，可直觀看出該算法的結(jié)論是正確的。

6 效果對比

本項(xiàng)目最初分配算法是：任務(wù)按任務(wù)產(chǎn)生時間排序，定時循環(huán)未分配任務(wù)列表，然后循環(huán)計(jì)算每個AGV執(zhí)行該任務(wù)的時間，將時間最小的agv分配給任務(wù)，當(dāng)不同AGV執(zhí)行統(tǒng)一任務(wù)時間相同時，采用隨機(jī)分配法，選擇AGV編號最小的。

如圖2所示，針對本文“算法驗(yàn)證”一節(jié)的案例，按原算法，取時間最少的AGV，若時間一致則按AGV編號排序，取編號最小的AGV，因此其分配的方案為：

75 號車執(zhí)行任務(wù)1,76 號車執(zhí)行任務(wù)2。該方案任務(wù)執(zhí)行的總時間為：

140+180=320＞310 采用匈牙利算法得到的任務(wù)總執(zhí)行時間)

因此原有任務(wù)分配算法效果不及匈牙利算法；其次任務(wù)按時間排序不能滿足產(chǎn)線產(chǎn)量最高、工件不超時的原則，因此本文提出的任務(wù)調(diào)度策略以及優(yōu)化方法比原始的策略和算法更優(yōu)。

7 程序?qū)崿F(xiàn)邏輯及應(yīng)用案例

圖6是系統(tǒng)實(shí)現(xiàn)該調(diào)度策略和算法的程序邏輯流程圖，圖7所示是應(yīng)用了該任務(wù)分配方法的調(diào)度系統(tǒng)軟件。該調(diào)度系統(tǒng)是成都四威高科技產(chǎn)業(yè)園有限公司針對光伏行業(yè)研發(fā)的智能物流調(diào)度系統(tǒng)。

8 結(jié)論

本文所述的AGV調(diào)度策略在保證生產(chǎn)車間產(chǎn)量的條件下，有效提高了該太陽能電池片生產(chǎn)車間的物流效率。本文排序模型考慮的約束條件只有工序順序，連接任務(wù)，是否超時，復(fù)雜應(yīng)用中約束將更多且不能與后端的執(zhí)行優(yōu)化分割開來看，下一步將著重研究多約束條件下為使得產(chǎn)線產(chǎn)能最高，如何進(jìn)行任務(wù)排序和選擇優(yōu)化策略。

圖6 程序邏輯流程圖

圖7 AGV調(diào)度系統(tǒng)界面