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

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

1 問題的描述

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

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

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

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

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

2 初始路徑生成

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

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

2.1.1 問題描述及假設

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

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

2.1.2 模型建立

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

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

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

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

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

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

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

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

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

3 AGV碰撞檢測及避免算法

3.1 算法設計

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

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

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

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

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

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

3.2 避撞策略

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

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

(2)任務起終點均不在同一橫縱方向 根據(jù)初始路徑中AGV按照“先橫后縱”的折線路線從起始點行駛至終點，若AGV在沿橫向行駛的過程中發(fā)生碰撞，采取e/f/g/h變換，即AGV在碰撞點前一柵格進行轉向；若AGV在沿縱向行駛的過程中發(fā)生碰撞，采取E/F/G/H變換，即AGV在轉向點前一柵格提前進行轉向。以上4種變換AGV均多轉向1次，但不會增加AGV行走時間。當轉向變換后AGV行駛至終點的過程中再次發(fā)生碰撞，此時先采取E/F/G/H轉向次數(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é)構建了一個大小為3×3的半導體生產(chǎn)車間，布局如圖4所示。車間中設置2個電子貨架用于暫存工件，3個機臺用于加工工件，2臺AGV初始狀態(tài)均位于車間左下角且速度為每秒勻速行駛1個單元格。實驗中運送任務算例根據(jù)半導體可重入性的特征隨機生成。所有測試在Intel Core i7 2.8 GHz CPU, 8 GB RAM的計算機上運行，采用CPLEX作為模型求解器，啟發(fā)式算法采用Python編碼，在Python 3.7平臺上實現(xiàn)。

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

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

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

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

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

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

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

由表3結果可知：

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

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

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

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

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

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

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

5 結束語

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