李昆鵬，劉騰博+，阮炎秋

(1.華中科技大學(xué) 管理學(xué)院，湖北 武漢 430074；2.新加坡科技與設(shè)計大學(xué) 工程系統(tǒng)與設(shè)計，新加坡 487372)

1 問題的描述

近年來，在人工智能、物聯(lián)網(wǎng)、5G等創(chuàng)新技術(shù)的推動下，半導(dǎo)體行業(yè)的應(yīng)用場景不斷擴(kuò)展，同時半導(dǎo)體芯片作為信息技術(shù)產(chǎn)業(yè)的基石，對信息安全、國民經(jīng)濟(jì)起著至關(guān)重要的作用，已成為各國競相角逐的“國之重器”。2015年在國務(wù)院印發(fā)的《中國制造2025》中將集成電路放在發(fā)展新一代信息技術(shù)產(chǎn)業(yè)的首位，以推動半導(dǎo)體國產(chǎn)化進(jìn)程。從2015年至今，中國一直穩(wěn)居全球最大半導(dǎo)體消費市場，市場需求規(guī)模占全球41%，而自給率卻只能達(dá)到12%，這嚴(yán)重制約了我國信息產(chǎn)業(yè)的發(fā)展。半導(dǎo)體芯片制造是迄今為止最復(fù)雜的工藝過程，以14 nm晶圓工藝為例，全部流程需要1 100個步驟，生產(chǎn)線技術(shù)工藝復(fù)雜，涉及加工設(shè)備數(shù)量及類型繁多。隨著電子通信、計算機、網(wǎng)絡(luò)技術(shù)三大領(lǐng)域的需求不斷增加，傳統(tǒng)生產(chǎn)車間的人工作業(yè)模式顯然已難以滿足半導(dǎo)體的市場需求，松下、西門子等國際知名半導(dǎo)體企業(yè)紛紛嘗試將智能機器人自動導(dǎo)引小車(Automated Guided Vehicle, AGV)應(yīng)用于半導(dǎo)體生產(chǎn)車間，以實現(xiàn)柔性自動化生產(chǎn)線。目前，我國半導(dǎo)體制造業(yè)尚處于起步階段，進(jìn)口依賴問題依然嚴(yán)峻，在制造精度和自動化程度上與國際水平仍存在較大差距，而AGV憑借高靈活性、高穩(wěn)定性，已成為半導(dǎo)體行業(yè)實現(xiàn)自動化生產(chǎn)的關(guān)鍵設(shè)備之一。然而，如何設(shè)計更適用于半導(dǎo)體生產(chǎn)車間的AGV調(diào)度算法，以實現(xiàn)更快更精準(zhǔn)的生產(chǎn)任務(wù)運輸作業(yè)，是當(dāng)前國內(nèi)半導(dǎo)體制造業(yè)向智能制造轉(zhuǎn)型面臨的巨大挑戰(zhàn)。

目前，已有少數(shù)企業(yè)嘗試?yán)肁GV特性升級現(xiàn)有制造執(zhí)行系統(tǒng)(Manufacturing Execution System, MES)，在應(yīng)用MES的生產(chǎn)車間內(nèi)，電子貨架與加工機臺分別位于兩側(cè)，貨架用來存放半導(dǎo)體工件的半成品和成品，AGV來往于貨架與機臺之間，完成半導(dǎo)體運送任務(wù)，主要工作流程如圖1所示。首先根據(jù)客戶需求制定半導(dǎo)體工件生產(chǎn)計劃，然后將機臺與貨架間的工件運送任務(wù)分配至AGV，最后規(guī)劃AGV在機臺與貨架間的行走路徑，以實現(xiàn)半導(dǎo)體生產(chǎn)過程的自動化運輸作業(yè)。在半導(dǎo)體生產(chǎn)車間中，有若干加工機臺和電子貨架，根據(jù)半導(dǎo)體的加工工序要求，工件需在不同時間多次訪問同一機臺，具有明顯的可重入性。AGV的主要任務(wù)是將暫存在貨架上的工件運送至機臺加工，并將已完成加工的工件從機臺運送至貨架暫存。若機臺生產(chǎn)計劃時間開始，而工件未能被AGV及時運送到達(dá)機臺，或機臺加工完成，而工件未能被及時運走，則會導(dǎo)致機臺等待閑置及生產(chǎn)計劃的延后。在半導(dǎo)體車間中，設(shè)備購置費用高，生產(chǎn)調(diào)度的一個重要目標(biāo)是機臺閑置率最小。因此，為了保證各道工序順暢銜接以及機臺工作效率，AGV調(diào)度的總體目標(biāo)為：基于生產(chǎn)計劃決策AGV運送任務(wù)的順序及運送路線，以最小化AGV完成運送任務(wù)的總時間。該問題在設(shè)計AGV調(diào)度方案時不僅要考慮每道工序的計劃加工和完工時間，還要從全局對多臺AGV進(jìn)行路徑規(guī)劃以避免碰撞發(fā)生，是一個十分復(fù)雜的作業(yè)車間調(diào)度問題與AGV路徑規(guī)劃問題。

基于MES工作流程，本文所研究的半導(dǎo)體生產(chǎn)車間智能AGV路徑規(guī)劃與調(diào)度問題可提煉為半導(dǎo)體車間生產(chǎn)調(diào)度問題和AGV路徑規(guī)劃問題。關(guān)于半導(dǎo)體車間生產(chǎn)調(diào)度問題的研究，KUMAR[1]最早提出了半導(dǎo)體生產(chǎn)線屬于可重入生產(chǎn)系統(tǒng)，是不同于Job-shop和Flow-Shop系統(tǒng)調(diào)度的第三類調(diào)度問題；UZSOY[2]首先證明半導(dǎo)體單批處理機調(diào)度問題為強NP-hard。大多數(shù)文獻(xiàn)將最小化最大完工時間作為優(yōu)化目標(biāo)[3-5]，部分文獻(xiàn)考慮了加權(quán)總完工時間[6]、平均延誤時間[7]、總延誤時間[8]、平均等待時間[9]等目標(biāo)。在求解方法上，KUMAR等[10]設(shè)計了啟發(fā)式規(guī)則應(yīng)用于半導(dǎo)體生產(chǎn)過程實時調(diào)度；BAEZ等[11]設(shè)計了一種基于人工神經(jīng)網(wǎng)絡(luò)技術(shù)的多目標(biāo)遺傳算法；馬慧民等[12]和郭乘濤等[13]分別提出了雙層粒子群算法和混合蟻群算法。極少學(xué)者采用精確算法求解，JIANG等[6]和CHOI等[14]分別提出了基于代理次梯度的拉格朗日松弛算法和分支定界算法。以上研究均僅對生產(chǎn)環(huán)節(jié)進(jìn)行優(yōu)化，尚未將AGV行駛路徑考慮在內(nèi)，無法應(yīng)用于多AGV協(xié)同工作的半導(dǎo)體生產(chǎn)車間。

綜上所述：①國內(nèi)外學(xué)者主要研究了采用傳統(tǒng)流水線生產(chǎn)的調(diào)度優(yōu)化問題，由于半導(dǎo)體制造工藝流程具有可重入性高、不確定性大、批處理加工及大規(guī)模生產(chǎn)等顯著區(qū)別于其他制造業(yè)的特點，而已有文獻(xiàn)中的調(diào)度算法在可重入式生產(chǎn)流水線的適用性不強；②AGV路徑規(guī)劃方面，多數(shù)文獻(xiàn)在已知障礙物的靜態(tài)環(huán)境下設(shè)計AGV避撞策略，無法適用于采用多臺AGV協(xié)同工作的智能化半導(dǎo)體生產(chǎn)車間；③由于采用AGV實現(xiàn)自動化生產(chǎn)已成為發(fā)展趨勢，而在半導(dǎo)體車間對AGV進(jìn)行路徑規(guī)劃的文獻(xiàn)較少，且很少有文獻(xiàn)涉及多種AGV避撞方式。因此，如何在動態(tài)環(huán)境下將工件生產(chǎn)任務(wù)分配、AGV路徑規(guī)劃及碰撞避免結(jié)合起來，設(shè)計多種避撞措施以靈活變換路徑，形成一套完整的AGV自動化物料運輸系統(tǒng)解決方案，將是本文研究的重點。

本文結(jié)合半導(dǎo)體生產(chǎn)線的工藝流程，在自動化物料運輸系統(tǒng)下研究AGV路徑規(guī)劃與調(diào)度問題，提出了兩階段優(yōu)化算法，如圖2所示。第1階段生成單AGV初始可行路徑，分別采用基于數(shù)學(xué)模型和基于時間優(yōu)先級的任務(wù)分配方法，將貨架與機臺之間的半導(dǎo)體工件運送任務(wù)分配至AGV，并根據(jù)一定的行駛規(guī)則生成每臺AGV的初始路徑;第2階段考慮碰撞避免獲得多AGV全局無碰路徑，設(shè)計碰撞檢測及避免算法檢測初始路徑中AGV可能發(fā)生沖突的節(jié)點，并采取相應(yīng)避撞策略對AGV路徑進(jìn)行動態(tài)調(diào)整，最終實現(xiàn)所有AGV能夠高效、無碰撞地完成半導(dǎo)體生產(chǎn)車間的物料運輸任務(wù)。最后通過算例實驗證明本文提出的兩階段算法能夠調(diào)度AGV在具有4個貨架和4個機臺的半導(dǎo)體車間中完成480個工件的運送任務(wù)，在求解效果和時間上均有較好的表現(xiàn)。相較于已有研究，本文不僅考慮了AGV任務(wù)分配方法，還提出了AGV在動態(tài)環(huán)境中的避撞策略，并通過靈敏度分析對AGV配置數(shù)量給出建議。研究成果豐富了AGV在不同場景中的應(yīng)用，能夠為半導(dǎo)體生產(chǎn)車間采用AGV實現(xiàn)自動化物料運輸系統(tǒng)提供參考。

2 初始路徑生成

AGV初始路徑生成主要包括兩個步驟：首先，將貨架與機臺之間的半導(dǎo)體工件運送任務(wù)分配至AGV，得到每臺AGV的運送任務(wù)序列，然后根據(jù)一定的行駛規(guī)則生成每臺AGV的初始路徑。本文分別在兩種任務(wù)分配方法下得到每臺AGV的運送任務(wù)序列：①以工件加工總完成時間最短為目標(biāo)建立數(shù)學(xué)模型進(jìn)行精確求解；②考慮生產(chǎn)計劃中工件計劃時間的緊急程度設(shè)計啟發(fā)式算法進(jìn)行高效求解。

2.1 基于數(shù)學(xué)模型的AGV任務(wù)分配方法

2.1.1 問題描述及假設(shè)

AGV路徑規(guī)劃與調(diào)度問題可描述如下：在采用AGV的半導(dǎo)體生產(chǎn)車間中，每個貨架有多個儲位且每個儲位僅暫存一種半導(dǎo)體工件。當(dāng)AGV運送加工工件時，先到暫存該工件的貨架取貨，再將其運送至機臺加工，若AGV實際到達(dá)機臺的時間小于計劃加工時間，則在機臺處等待；當(dāng)AGV運送完工工件時，先到加工該工件的機臺取貨，若AGV實際到達(dá)時間小于計劃完工時間，則在機臺處等待至計劃完工時間，再將其運送至貨架暫存。在MES的生產(chǎn)計劃中，對于工件的每道工序均有計劃加工時間和計劃完工時間，根據(jù)計劃時間下達(dá)指令至AGV完成工件加工上機和完工上架的運送任務(wù)。本文以AGV完成所有工件運送任務(wù)的時間最短為目標(biāo)建立數(shù)學(xué)模型，在滿足生產(chǎn)計劃的時間約束下，將工件運送任務(wù)分配至AGV，并對AGV執(zhí)行運送任務(wù)的順序進(jìn)行決策。

為了方便建模，考慮以下假設(shè)：①AGV電量充足；②加工機臺無開工準(zhǔn)備時間；③每臺AGV每次最多運送一種工件；④AGV在貨架或機臺前的位置進(jìn)行操作；⑤所有AGV同質(zhì)且每秒勻速行駛1個單元格；⑥將AGV行駛區(qū)域抽象為矩形網(wǎng)格，AGV沿網(wǎng)格行駛，故其行走距離為折線距離。

2.1.2 模型建立

根據(jù)問題描述，參數(shù)及變量定義如表1所示。

表1 參數(shù)符號及定義

基于上述問題描述、假設(shè)條件及參數(shù)變量，構(gòu)建如下數(shù)學(xué)模型：

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

模型的決策為工件運送任務(wù)在AGV上的分配及每臺AGV完成運送任務(wù)的先后順序。目標(biāo)函數(shù)(1)表示最小化用時最長的AGV運送任務(wù)時間；式(2)和式(3)表示AGV從停靠點出發(fā)完成任務(wù)后返回?？奎c；式(4)和式(5)保證每個運送任務(wù)均被執(zhí)行；式(6)為線路流平衡約束；式(7)為AGV與運送任務(wù)之間的服務(wù)關(guān)系；式(8)和式(9)為AGV完成加工上機運送任務(wù)i的結(jié)束時間不得早于其開始時間與運送時間之和，且不得早于計劃加工時間；式(10)和式(11)為AGV執(zhí)行完工上架運送任務(wù)i的開始時間不得早于該工件加工上機運送任務(wù)的結(jié)束時間與加工時間之和，且不得早于計劃完工時間；式(12)表示若AGV先后執(zhí)行運送任務(wù)i和j，則任務(wù)j的開始時間不早于AGV完成任務(wù)i后走折線路線到達(dá)任務(wù)j起點的時間；式(13)和式(14)為消除子循環(huán)約束；式(15)表示0-1變量；式(16)和式(17)表示整數(shù)變量。該問題可簡化為任務(wù)分配問題(assignment problem)，為NP難題。

2.2 基于時間優(yōu)先級的AGV任務(wù)分配算法

全球半導(dǎo)體行業(yè)已經(jīng)進(jìn)入成熟發(fā)展的存量競爭階段，這對半導(dǎo)體的加工精度和生產(chǎn)能力提出了更高的要求，為了更好地利用AGV精準(zhǔn)、快速的特點，從而進(jìn)一步提高生產(chǎn)效率，本文以盡快完成半導(dǎo)體工件生產(chǎn)計劃為目標(biāo)，提出一種基于時間優(yōu)先級的AGV任務(wù)分配算法，主要流程如圖3所示。由MES制訂的工件生產(chǎn)計劃包括工件的暫存貨架、加工順序、每道工序的加工機臺及計劃加工時間和計劃完工時間。首先根據(jù)工件的計劃加工和完工時間對所有運送任務(wù)進(jìn)行排序，即優(yōu)先完成時間最緊急的任務(wù)，由此得到運送工件加工上機和完工上架的任務(wù)序列。然后按照AGV先完成先分配的原則依次安排AGV完成工件運送任務(wù)，并更新每臺AGV的運送任務(wù)序列，直至所有運送工件加工上機和完工上架的任務(wù)均分配至AGV執(zhí)行，最終得到每臺AGV的運送任務(wù)序列。

2.3 AGV行駛規(guī)則及路徑生成方法

本文對半導(dǎo)體生產(chǎn)車間進(jìn)行柵格化處理并用編號表示位置節(jié)點，如圖4所示，包括AGV?？奎c、加工機臺、電子貨架以及一個3×3的AGV行駛區(qū)域，機臺和貨架前的柵格為AGV操作位。在半導(dǎo)體生產(chǎn)車間中，AGV沒有任務(wù)時?？吭诮锹洌?dāng)接收到工件加工上機任務(wù)時，AGV將其從所在貨架取出并運送至機臺；當(dāng)接收到工件完工上架任務(wù)時，AGV將其從加工機臺取出并運送至貨架。AGV在?？奎c、貨架及機臺之間行走，完成工件的運送任務(wù)，為了保證半導(dǎo)體生產(chǎn)車間各工序順暢銜接，AGV按照“先橫后縱”的行駛規(guī)則有序運行，以降低碰撞概率，從而高效完成運送任務(wù)。根據(jù)AGV執(zhí)行每個運送任務(wù)的起點和終點，基于“先橫后縱”的行駛規(guī)則，可知AGV執(zhí)行每個運送任務(wù)時的初始路徑，如圖5所示。當(dāng)任務(wù)起終點同在橫向或縱向時，行駛路線為a/b/c/d；當(dāng)任務(wù)起終點均不在同一橫縱方向時，行駛路線為e/f/g/h。例如，如圖4所示，若AGV當(dāng)前運送任務(wù)為貨架1上的工件需在機臺3進(jìn)行加工，則其行駛路徑為4→5→6→9。AGV根據(jù)已確定的工件運送任務(wù)序列，在此規(guī)則下可得到每臺AGV完成其所有運送任務(wù)的初始路徑。

3 AGV碰撞檢測及避免算法

3.1 算法設(shè)計

當(dāng)多臺AGV在?？奎c、貨架、機臺之間行走執(zhí)行工件的運送任務(wù)時，極有可能發(fā)生碰撞，為了解決AGV碰撞問題，以免造成死鎖情況，確保多AGV系統(tǒng)安全順暢地運行，本文設(shè)計碰撞檢測及避免算法對AGV初始路徑進(jìn)行實時重調(diào)度，以保證在行走區(qū)域內(nèi)不存在兩臺AGV同時占用相同位置。為了表示AGV位置和時間兩個維度，本文基于柵格化車間建立二維預(yù)約表，采用數(shù)字編號表示AGV每時刻的行駛位置，如[1,1]、[2,4]、[3,5]表示AGV在1 s～3 s的行走路徑為1→4→5。此外，采用重復(fù)編號表示AGV靜止等待，如[3,8]、[4,8]、[5,8]表示AGV在3 s～5 s時段停留在編號為8的位置。

碰撞檢測及避免算法流程如圖6所示，主要步驟為：

(1)基于AGV初始路徑建立初始二維預(yù)約表，考慮到工件加工所需時間大致相同，為了降低AGV集中到達(dá)機臺前等待造成擁堵的概率，因此需要對AGV的相鄰運送任務(wù)設(shè)置出發(fā)時間間隔，即在AGV路徑中加入停留節(jié)點表示機臺加工時間，以更新二維預(yù)約表。

(2)根據(jù)更新后的二維預(yù)約表計算AGV實際到達(dá)加工機臺的時間。若AGV實際到達(dá)時間早于計劃加工時間或計劃完工時間，則加入停留節(jié)點，使AGV在機臺處等待至計劃時間再投放或取出工件，以此更新二維預(yù)約表。

(3)檢查AGV預(yù)約表中是否存在與其他AGV同時刻同位置，若在相同時間同一位置被重復(fù)占用，則表示發(fā)生沖突，此時根據(jù)避撞策略采取相應(yīng)調(diào)整措施，更新二維預(yù)約表并再次進(jìn)行碰撞檢測，直到該運送任務(wù)的所有路徑不存在沖突。

(4)同理完成AGV所有運送任務(wù)的碰撞檢測和調(diào)整。

3.2 避撞策略

在半導(dǎo)體生產(chǎn)車間環(huán)境中，多AGV系統(tǒng)出現(xiàn)沖突的情況復(fù)雜多樣，但其本質(zhì)都是時空重疊問題，即同一時間，兩臺AGV在同一位置相遇而發(fā)生碰撞，此時采取相應(yīng)的調(diào)整措施。由生產(chǎn)計劃表可知AGV執(zhí)行當(dāng)前運送任務(wù)的計劃加工時間和計劃完工時間，按時間的緊急程度確定AGV的優(yōu)先級，即時間越靠前的運送任務(wù)AGV優(yōu)先級越高。由于優(yōu)先級低的AGV需要對優(yōu)先級高的AGV進(jìn)行避讓，以盡快滿足時間更緊急的加工任務(wù)，從優(yōu)先級最高的AGV依次對每臺AGV進(jìn)行路徑調(diào)整。由AGV的二維預(yù)約表可知每臺AGV每時刻所在的位置，若檢測到當(dāng)前AGV初始路徑中存在行駛柵格在某時刻已被其他優(yōu)先級更高的AGV占用，則表示兩臺AGV將在該位置發(fā)生碰撞，此時優(yōu)先級較低的AGV根據(jù)其任務(wù)起終點的位置關(guān)系進(jìn)行路徑變換，如圖7所示，具體調(diào)整措施如下：

(1)任務(wù)起終點同在橫向或縱向 在初始路徑中AGV沿直線從任務(wù)起點行駛至終點，當(dāng)檢測到某位置發(fā)生碰撞時，根據(jù)AGV起終點位置關(guān)系變換路徑。若AGV起終點同在橫向上，采取a/b變換。若同在縱向上，采取c/d變換。以上4種變換AGV均多轉(zhuǎn)向4次。

(2)任務(wù)起終點均不在同一橫縱方向 根據(jù)初始路徑中AGV按照“先橫后縱”的折線路線從起始點行駛至終點，若AGV在沿橫向行駛的過程中發(fā)生碰撞，采取e/f/g/h變換，即AGV在碰撞點前一柵格進(jìn)行轉(zhuǎn)向；若AGV在沿縱向行駛的過程中發(fā)生碰撞，采取E/F/G/H變換，即AGV在轉(zhuǎn)向點前一柵格提前進(jìn)行轉(zhuǎn)向。以上4種變換AGV均多轉(zhuǎn)向1次，但不會增加AGV行走時間。當(dāng)轉(zhuǎn)向變換后AGV行駛至終點的過程中再次發(fā)生碰撞，此時先采取E/F/G/H轉(zhuǎn)向次數(shù)較少的變換方式，若仍無法避開碰撞，再根據(jù)AGV行駛方向及終點位置采取a/b變換以有效規(guī)避碰撞點。

(3)若AGV路徑終點被其他優(yōu)先級更高的AGV占用，此時優(yōu)先級較低的AGV在其終點前一柵格靜止等待，即延遲避撞策略，如A、B、C、D所示。

4 仿真實驗及數(shù)據(jù)測試

4.1 小規(guī)模仿真實驗

本節(jié)構(gòu)建了一個大小為3×3的半導(dǎo)體生產(chǎn)車間，布局如圖4所示。車間中設(shè)置2個電子貨架用于暫存工件，3個機臺用于加工工件，2臺AGV初始狀態(tài)均位于車間左下角且速度為每秒勻速行駛1個單元格。實驗中運送任務(wù)算例根據(jù)半導(dǎo)體可重入性的特征隨機生成。所有測試在Intel Core i7 2.8 GHz CPU, 8 GB RAM的計算機上運行，采用CPLEX作為模型求解器，啟發(fā)式算法采用Python編碼，在Python 3.7平臺上實現(xiàn)。

為了比較基于數(shù)學(xué)模型的任務(wù)分配方法和基于時間優(yōu)先級的任務(wù)分配算法在兩個階段的求解效果差異，分別采用兩個方法求解并進(jìn)行比較，結(jié)果如表2所示。在表2和以下闡述中，為便于表述，將這兩種方法分別描述為：兩階段算法(數(shù)學(xué)模型)與兩階段算法(時間優(yōu)先級)。展示結(jié)果為AGV完成所有工件運送任務(wù)的時間。其中：ItemNum表示運送任務(wù)數(shù)量；Period 1表示碰撞調(diào)整前的初始路徑總時間，即第1階段結(jié)果；Period 2表示經(jīng)過碰撞調(diào)整后的最終路徑總時間，即第2階段結(jié)果；Gap1表示兩種方式在碰撞調(diào)整前的運送時間差異度；Gap2表示兩種方式經(jīng)過碰撞調(diào)整后的運送時間差異度；Time表示求解所用時間(單位:s)。

表2 小規(guī)模實驗結(jié)果

結(jié)果表明，對于第1階段，兩階段算法(時間優(yōu)先級)與兩階段算法(數(shù)學(xué)模型)的初始路徑在個別算例上存在一定差異，但最大僅相差3.51%；對于第2階段，兩個方法得到的結(jié)果一致。這說明對于小規(guī)模算例，由于在生產(chǎn)計劃中已考慮加工順序，AGV只需按照生產(chǎn)計劃的時間要求執(zhí)行任務(wù)即可，實際完成時間與AGV在執(zhí)行任務(wù)時發(fā)生的碰撞相關(guān)，與任務(wù)執(zhí)行順序關(guān)系不大。此外，在小規(guī)模算例中僅由兩臺AGV執(zhí)行較少運送任務(wù)數(shù)且任務(wù)起終點多不在相同橫縱方向上，因此當(dāng)檢測到碰撞時，優(yōu)先采取e/f/g/h或E/F/G/H變換路徑，可在避開碰撞的同時不增加總完成時間。

綜上可知，由于多AGV在同一車間行駛必須考慮碰撞影響，系統(tǒng)實際完成時間取決于碰撞調(diào)整后的運送時間，即第2階段的最終結(jié)果。對于本文小規(guī)模算例，采取兩種方式求解的最終結(jié)果一致，因此本文提出的兩階段算法(時間優(yōu)先級)能有效解決小規(guī)模問題。在計算時間方面，隨著數(shù)據(jù)規(guī)模增大，CPLEX求解時間呈指數(shù)型增長，且當(dāng)加工任務(wù)數(shù)達(dá)到36時，CPLEX在90 min內(nèi)無法得到結(jié)果，由于受CPLEX求解限制，在小規(guī)模問題中算例數(shù)量較少。而實際半導(dǎo)體生產(chǎn)車間規(guī)模較大，進(jìn)行大規(guī)模最優(yōu)解求解不可行，因此本文提出的兩階段算法(時間優(yōu)先級)具有很好的實用性。

4.2 大規(guī)模仿真實驗

本節(jié)構(gòu)建了一個大小為4×9的半導(dǎo)體生產(chǎn)車間，與圖4所示布局相同，僅在數(shù)量上不同，電子貨架、加工機臺數(shù)均為4。首先采用基于時間優(yōu)先級的任務(wù)分配方法得到AGV運送任務(wù)序列，再根據(jù)行駛規(guī)則生成AGV初始路徑；然后采用AGV碰撞檢測和避免算法獲得全局AGV無碰路徑，得到AGV完成所有運送任務(wù)的時間；最后通過對比兩階段算法結(jié)果與生產(chǎn)計劃最優(yōu)時間的差異，以驗證本文算法的求解效果，通過對比僅采用延遲避撞策略與采用本文3.2節(jié)所有避撞策略的結(jié)果，以說明設(shè)計多種避撞策略的必要性。在僅采用延遲避撞策略中，AGV采取等待措施而非變換路徑，當(dāng)檢測到當(dāng)前AGV行駛柵格中存在某時刻被其他優(yōu)先級更高的AGV占用，則該AGV在碰撞點前一柵格等待，直到目標(biāo)柵格處于空閑狀態(tài)。結(jié)果如表3所示，其中，ItemNum表示運送任務(wù)數(shù)量，Expected time表示生產(chǎn)計劃的最優(yōu)完成時間，Priority表示第1階段初始路徑完成時間，Only delay表示僅采用延遲避撞策略的結(jié)果，All method表示采用所有避撞策略的結(jié)果。Gap1、Gap2、Gap3分別表示采用本文所有避撞策略的完成時間與最優(yōu)完成時間、第一階段初始路徑完成時間、僅采用延遲避撞策略完成時間的結(jié)果差異，負(fù)號表示相對減少。

表3 大規(guī)模實驗結(jié)果

由表3結(jié)果可知：

(1)Gap1表明采用本文所有避撞策略的完成時間與最優(yōu)時間的差值均小于11%，在可接受范圍內(nèi)，說明本文提出的兩階段算法(時間優(yōu)先級)在求解大規(guī)模問題時效果較好，能夠在獲得全局AGV無碰路徑的同時按生產(chǎn)計劃高效地完成運送任務(wù)。

(2)由Gap2可以看出，采用本文所有避撞策略與第一階段未進(jìn)行碰撞避免的完成時間相差不超過4%，說明采用避撞策略對完成時間的影響不大。在采用多臺AGV協(xié)同工作的生產(chǎn)車間，必須采取合理的避撞措施以實現(xiàn)生產(chǎn)車間穩(wěn)定運行，而本文兩階段算法(時間優(yōu)先級)可在保證運行效率的同時獲得AGV無碰路徑，具有一定的可行性。

(3)Gap3表明僅采用延遲避撞策略的完成時間比采用本文所有避撞策略的完成時間基本增加1%～5%，說明僅采取延遲等待措施可能會造成時間浪費，增加整體作業(yè)完成時間，十分有必要采取多種路徑變換方式對AGV進(jìn)行碰撞避免，而本文考慮多種情況對AGV路徑進(jìn)行調(diào)整，符合生產(chǎn)車間復(fù)雜的工作情況，具有一定的靈活性。

4.3 AGV數(shù)量靈敏度分析

對于企業(yè)來說，生產(chǎn)車間的運營需考慮效率和成本兩個方面，若能在保證高效率的同時減少AGV數(shù)量，可進(jìn)一步降低運營成本。基于此，本節(jié)在4×9的生產(chǎn)車間中，采用兩階段算法(時間優(yōu)先級)探討最優(yōu)數(shù)量的AGV調(diào)度問題，在不同規(guī)模的運送任務(wù)下測試不同數(shù)量AGV對系統(tǒng)運作效率的影響。結(jié)果如表4所示，其中，N表示運送任務(wù)數(shù)，A表示AGV數(shù)，每個任務(wù)的第1行為任務(wù)總完成時間(單位：s)，第2行為系統(tǒng)碰撞次數(shù)。

表4 不同情況的系統(tǒng)效率

由表4可知，在不同的運送任務(wù)規(guī)模下，AGV數(shù)量由1增加至4時，任務(wù)完成時間減幅明顯，碰撞次數(shù)緩慢增加；當(dāng)由5逐步增加時，兩者均增幅明顯，如圖8和圖9所示。導(dǎo)致該情況的原因是：在一定范圍內(nèi)增加AGV數(shù)量可以減少每臺AGV的平均任務(wù)數(shù)，且不會造成太多碰撞；當(dāng)AGV數(shù)量較多時，雖然每臺AGV完成任務(wù)數(shù)減少，但碰撞的可能性急劇增加，此時AGV不斷變換路徑導(dǎo)致行走時間增加，因此不斷增加AGV數(shù)量對減少運送任務(wù)的完成時間、改善系統(tǒng)工作效率影響不大。綜上，在4×9的半導(dǎo)體生產(chǎn)車間中合適的AGV配置數(shù)量為3～4臺，此時完成時間和碰撞次數(shù)均相對較少。通過對車間中AGV的使用數(shù)量進(jìn)行靈敏度分析，可為不同車間規(guī)模的AGV數(shù)量配置提供參考，以實現(xiàn)采用較少AGV高效完成工件運送任務(wù)，達(dá)到合理利用車間資源、提高企業(yè)經(jīng)濟(jì)效益的目的。

5 結(jié)束語

本文研究了半導(dǎo)體生產(chǎn)車間中采用自動化物料運輸系統(tǒng)的AGV調(diào)度優(yōu)化問題，主要包括單AGV路徑規(guī)劃問題及多AGV碰撞避免問題，并基于此設(shè)計了兩階段優(yōu)化方法進(jìn)行求解。首先，分別采用數(shù)學(xué)模型求解和基于時間優(yōu)先級的任務(wù)分配算法將半導(dǎo)體工件運送任務(wù)分配至AGV，并根據(jù)每臺AGV的運送任務(wù)序列和AGV行駛規(guī)則生成初始路徑。其次，設(shè)計碰撞檢測及避免算法，針對不同碰撞情況采取相應(yīng)的調(diào)整策略，從而獲得高效可行的全局AGV調(diào)度方案。然后，通過算例實驗表明本文兩階段算法(時間優(yōu)先級)能夠調(diào)度AGV在具有4個貨架和4個機臺的半導(dǎo)體車間中完成480個工件運送任務(wù)，并且在算法效率和求解時間上均具有很好的實用性。最后，通過實驗證明了本文提出的多種避撞策略能夠在獲得AGV無碰路徑的同時，按生產(chǎn)計劃高效地完成運送任務(wù)，并對AGV數(shù)量進(jìn)行靈敏度分析，給出了半導(dǎo)體生產(chǎn)車間最優(yōu)的AGV數(shù)量配置建議。綜上所述，本文根據(jù)半導(dǎo)體制造工藝流程對AGV進(jìn)行任務(wù)調(diào)度，并對AGV進(jìn)行路徑規(guī)劃及碰撞避免，最終獲得自動化物料運輸系統(tǒng)實時調(diào)度方案，可為我國建設(shè)智能化半導(dǎo)體生產(chǎn)車間提供參考。此外，本文提出的算法可擴(kuò)展到其他采用AGV的自動化碼頭、智能倉庫等實際應(yīng)用場景，具有很強的實用價值。未來將考慮AGV非勻速的情況以及AGV的充電問題。