半導(dǎo)體生產(chǎn)車間智能AGV路徑規(guī)劃與調(diào)度

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

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

1 問題的描述

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

目前，已有少數(shù)企業(yè)嘗試?yán)肁GV特性升級(jí)現(xiàn)有制造執(zhí)行系統(tǒng)(Manufacturing Execution System, MES)，在應(yīng)用MES的生產(chǎn)車間內(nèi)，電子貨架與加工機(jī)臺(tái)分別位于兩側(cè)，貨架用來存放半導(dǎo)體工件的半成品和成品，AGV來往于貨架與機(jī)臺(tái)之間，完成半導(dǎo)體運(yùn)送任務(wù)，主要工作流程如圖1所示。首先根據(jù)客戶需求制定半導(dǎo)體工件生產(chǎn)計(jì)劃，然后將機(jī)臺(tái)與貨架間的工件運(yùn)送任務(wù)分配至AGV，最后規(guī)劃AGV在機(jī)臺(tái)與貨架間的行走路徑，以實(shí)現(xiàn)半導(dǎo)體生產(chǎn)過程的自動(dòng)化運(yùn)輸作業(yè)。在半導(dǎo)體生產(chǎn)車間中，有若干加工機(jī)臺(tái)和電子貨架，根據(jù)半導(dǎo)體的加工工序要求，工件需在不同時(shí)間多次訪問同一機(jī)臺(tái)，具有明顯的可重入性。AGV的主要任務(wù)是將暫存在貨架上的工件運(yùn)送至機(jī)臺(tái)加工，并將已完成加工的工件從機(jī)臺(tái)運(yùn)送至貨架暫存。若機(jī)臺(tái)生產(chǎn)計(jì)劃時(shí)間開始，而工件未能被AGV及時(shí)運(yùn)送到達(dá)機(jī)臺(tái)，或機(jī)臺(tái)加工完成，而工件未能被及時(shí)運(yùn)走，則會(huì)導(dǎo)致機(jī)臺(tái)等待閑置及生產(chǎn)計(jì)劃的延后。在半導(dǎo)體車間中，設(shè)備購(gòu)置費(fèi)用高，生產(chǎn)調(diào)度的一個(gè)重要目標(biāo)是機(jī)臺(tái)閑置率最小。因此，為了保證各道工序順暢銜接以及機(jī)臺(tái)工作效率，AGV調(diào)度的總體目標(biāo)為：基于生產(chǎn)計(jì)劃決策AGV運(yùn)送任務(wù)的順序及運(yùn)送路線，以最小化AGV完成運(yùn)送任務(wù)的總時(shí)間。該問題在設(shè)計(jì)AGV調(diào)度方案時(shí)不僅要考慮每道工序的計(jì)劃加工和完工時(shí)間，還要從全局對(duì)多臺(tái)AGV進(jìn)行路徑規(guī)劃以避免碰撞發(fā)生，是一個(gè)十分復(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)體單批處理機(jī)調(diào)度問題為強(qiáng)NP-hard。大多數(shù)文獻(xiàn)將最小化最大完工時(shí)間作為優(yōu)化目標(biāo)[3-5]，部分文獻(xiàn)考慮了加權(quán)總完工時(shí)間[6]、平均延誤時(shí)間[7]、總延誤時(shí)間[8]、平均等待時(shí)間[9]等目標(biāo)。在求解方法上，KUMAR等[10]設(shè)計(jì)了啟發(fā)式規(guī)則應(yīng)用于半導(dǎo)體生產(chǎn)過程實(shí)時(shí)調(diào)度；BAEZ等[11]設(shè)計(jì)了一種基于人工神經(jīng)網(wǎng)絡(luò)技術(shù)的多目標(biāo)遺傳算法；馬慧民等[12]和郭乘濤等[13]分別提出了雙層粒子群算法和混合蟻群算法。極少學(xué)者采用精確算法求解，JIANG等[6]和CHOI等[14]分別提出了基于代理次梯度的拉格朗日松弛算法和分支定界算法。以上研究均僅對(duì)生產(chǎn)環(huán)節(jié)進(jìn)行優(yōu)化，尚未將AGV行駛路徑考慮在內(nèi)，無法應(yīng)用于多AGV協(xié)同工作的半導(dǎo)體生產(chǎn)車間。

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

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

2 初始路徑生成

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

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

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

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

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

2.1.2 模型建立

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

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

基于上述問題描述、假設(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)

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

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

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

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

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

3 AGV碰撞檢測(cè)及避免算法

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

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

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

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

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

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

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

3.2 避撞策略

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

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

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

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

4 仿真實(shí)驗(yàn)及數(shù)據(jù)測(cè)試

4.1 小規(guī)模仿真實(shí)驗(yàn)

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

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

表2 小規(guī)模實(shí)驗(yàn)結(jié)果

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

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

4.2 大規(guī)模仿真實(shí)驗(yàn)

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

表3 大規(guī)模實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

5 結(jié)束語

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