考慮AGV數量配置的柔性作業車間集成調度

摘" 要：自動導引車 （AGV）作為柔性作業車間支撐車間生產物流的重要裝備，已被應用于不少企業的生產組織中，其數量配置直接影響著車間運輸任務的落實和生產任務的順利進行。針對柔性作業車間中，AGV數量配置不盡合理，導致運輸任務響應不及時或AGV資源利用不充分的問題，文章以最小化最大完工時間和最小化AGV數量為目標，建立了考慮AGV數量配置的柔性作業車間集成調度模型，并設計了基于工序、加工設備和AGV三層編碼的改進NSGA-Ⅱ算法進行對模型求解，通過數值實驗與分析，得出了最優的AGV數量配置方案和柔性作業車間集成調度方案，為企業高效合理地管理和調度生產設備的相關決策，提供了一定的理論支持與實踐指導。

關鍵詞：柔性作業車間；AGV數量配置；集成調度；多目標優化

中圖分類號：TP301.6" " 文獻標志碼：A" " DOI：10.13714/j.cnki.1002-3100.2025.01.002

Abstract： The automatic guided vehicle（AGV）， as a crucial equipment supporting production logistics in flexible job shop， has been widely adopted in the production organization of many enterprises. The quantity configuration of AGV directly impact the implementation of workshop transportation tasks and the smooth progress of production tasks. Addressing the issue of suboptimal AGV quantity configuration in flexible job shop， leading to delayed response to transportation tasks or underutilization of AGV resources， this article aims to minimize the maximum completion time and AGV quantity. It establishes an integrated scheduling model considering AGV quantity configuration and designs an improved NSGA-II algorithm based on three-level encoding of processes， processing equipment， and AGVs for solution generation. Through numerical experiments and analysis， the optimal AGV quantity configuration and integrated scheduling solution for flexible job shop are obtained. This provides theoretical support and practical guidance for enterprises to efficiently and rationally manage and schedule production equipment， aiding in relevant decision-making processes.

Key words： flexible job shop; AGV quantity configuration; integrated scheduling; collaborative optimization

0" 引" 言

隨著工業4.0和智能制造概念的提出，與智能制造相關的技術和設備得到迅速發展，現代生產系統正在向著更加柔性化、智能化的生產組織方式轉變[1]。其中，柔性作業車間（Flexible Job Shop）和自動導引車（Automated Guided Vehicle，AGV）已被不少企業應用于生產組織中[2]。柔性作業車間通過對生產設備的靈活調度，能夠應對多樣化產品的生產需求，更快速的響應市場變化。AGV指具有自動導引功能，可以按照一定的路徑行駛的一種運輸車，其具有安全、靈活、智能、解放人力、柔性程度高等優點，可以根據不同的生產需求進行運輸任務的調度，為生產過程提供物流的精準運輸，已成為支撐車間生產物流的重要裝備。

然而，傳統作業調度中較少考慮運輸作業的影響[3-4]，生產流程中的工件運輸調度主要憑經驗進行現場安排。這往往造成加工作業調度與工件運輸作業調度的脫節，難以保證生產過程與生產物流的連續性。AGV與柔性作業車間集成調度，就是要同時考慮柔性作業車間加工作業調度與各生產環節間AGV運輸調度的充分協同，以確保生產作業的準時性和連續性，并高效地使用AGV資源。僅考慮加工作業調度的優化，往往需要配置更多的AGV數量來保證生產計劃的執行，而不恰當的AGV數量配置則會造成資源的浪費[5]，增加企業的固定成本；而僅考慮AGV調度的優化，可能導致其調度結果難以充分保證生產過程中對工件運輸的及時需求，影響生產方案的可執行性。因此，單一層面單一目標的調度優化難以滿足企業生產實際和降低成本的要求。如何優化AGV數量配置，以在保證生產任務及時完成的同時，盡可能減少AGV的使用數量，并高效合理地進行AGV與柔性作業車間的集成調度，已經成為現代生產企業有效管理和調度生產設備資源，提高生產效率和降低生產成本中急待解決的問題。

AGV與柔性作業車間集成調度問題是對柔性作業車間調度問題的拓展，吳斌等[6]最早將AGV運輸任務在生產作業車間的調度作為研究對象，在此基礎上，周曉曄等[7]通過在模型中加入了物料的齊套性約束，考慮了在途物料延遲到達的調度問題。Li et al.[8]為了降低運輸成本，對AGV運輸與工件加工的時間沖突增加處罰，提出了一種AGV延遲出發時間的策略，有效減輕了AGV與加工設備間的時間沖突。另外，在考慮運輸時間的研究中，多數研究[9-12]假設AGV的運輸能力總是足夠的，有足夠數量的AGV保證運輸任務的完成，但實際上有限的AGV數量僅能提供有限的運輸能力。對此，徐云琴等[13]建立了使用AGV運輸的柔性作業車間調度模型，對車間內最佳的AGV數量和AGV最優調度方案進行了研究。謝旦嵐[14]利用Flexsim仿真，分析不同AGV數量配置方案下AGV平均利用率以及AGV小時利用率，得出了符合實際生產需求的AGV數量配置。以上研究在生產方面和運輸方面的考慮上均有不同的側重，但都將AGV調度作為生產作業調度的后置問題，優先處理車間生產作業的調度問題，再為每道工序選擇合適的AGV進行運輸，這種方式無法充分利用AGV資源，就有可能導致需要配置更多AGV數量來保證工件的準時到達。

綜上，針對上述研究的不足，在柔性作業車間集成調度中，需要對加工作業調度和AGV調度進行同時處理，同步生成加工作業調度方案和AGV調度方案，并進行集成調度方案的迭代優化，使生產作業與運輸作業更充分的協同，從而在保證生產任務要求的前提下，確定最佳的AGV數量配置，以提高AGV的使用效率和車間調度方案的整體性能，實現生產與運輸的集成調度方案的整體最優。為此，本文以最小化最大完工時間和最小化AGV數量為優化目標，構建了考慮AGV數量配置的柔性作業車間集成調度模型，并設計了基于工序、加工設備、AGV三層編碼的改進NSGA-Ⅱ算法對模型進行求解，通過算例的實驗與分析，驗證了本文所提模型和改進算法的有效性。

1" 問題描述與模型建立

1.1" 問題描述

考慮AGV數量配置的柔性作業車間中AGV與加工作業集成調度問題的描述如下：有n個需要加工的工件，有m臺用于加工工件的加工設備，有r臺可以用于運輸工件的AGV。每個工件的加工工序是已知，每個工件的工藝路線不盡相同，每道工序可以從一組可用加工設備中選擇一臺進行加工，且同一工序在不同加工設備上的加工時間可能不同。AGV負責工件在加工設備間的運輸，每道工序可以選擇合適的AGV進行工件的運輸，AGV在不同的加工設備間的運輸時間可能不同。柔性作業車間中AGV與加工作業集成調度問題，需要為每道工序選擇合適的加工設備，確定工序的加工順序，并為每道工序選擇合適的AGV進行工件的運輸任務。

為方便模型描述，做出如下假設：（1）所有待加工工件的加工和運輸的優先級相同；（2）加工設備旁邊的緩沖區容量足夠；（3）0時刻，所有AGV和加工設備都處于可用狀態；（4）每臺加工設備只能同時加工一道工序；（5）AGV的裝載/卸載時間計入運輸時間內；（6）AGV的運行速度勻速不變，不受載重的影響。

1.2" 符號說明

為了方便模型建立，引入如下符號：

m表示第k臺加工設備，k=1，2，…，m；p表示第i個零件，i=1，2，…，n；r表示第v臺AGV，v=1，2，…，r；op表示工件p的第j道工序；p表示工序op在加工設備m上加工的時長；p表示工序op在加工設備m上開始加工的時間；p表示工序op在加工設備m上結束加工的時間；t表示AGV運送工序op的負載開始時間；p表示AGV運送工序op的負載結束時間；t表示AGV運送工序op的空載開始時間；t表示AGV運送工序op的空載結束時間；c表示工序op的完工時間；T表示工序op的配送時間；L表示一個無窮大的正數。x表示如果工序op在加工設備m上加工則為1，否則為0；z表示如果工序op先于工序op在加工設備m上加工則為1，否則為0；b表示如果工序op由AGV運輸則為1，否則為0；β表示如果工序op先于工序op由AGV運輸則為1，否則為0。

1.3" 目標函數與約束條件

優化目標1：最小化最大完工時間。

最大完工時間C是指完成所有工件的最后一道工序的最大完工時間。最大完工時間是衡量車間調度方案的重要指標，優化最大完工時間意味著降低在制品占用，縮短生產周期，達到快速響應市場需求，提高生產效率。

優化目標2：最小化AGV數量。

AGV數量r是指在一定生產任務下，用來保證運輸任務及時完成所需要的AGV數量。減少AGV數量是提升AGV使用效率的關鍵，優化AGV數量意味著提高AGV利用率，降低企業的相關成本。

本文以最小化最大完工時間C和最小化AGV數量r為目標，建立的柔性作業車間集成調度問題的數學模型如下：

目標函數：

C=minmaxC" " " " " " " " " " " " " " " " " " " " " " （1）

r=minr" " " " " " " " " " " " " " " " " " " " " " " （2）

約束條件：

x=1" " " " " " " " " " " " " " " " " " " " " " " "（3）

p≤p， ？坌k" " " " " " " " " " " " " " " " " " " " " " （4）

p+p≤p+L1-z" " " " " " " " " " " " " " " " " " " " （5）

p+x·p=p" " " " " " " " " " " " " " " " " " " " " " （6）

b=1" " " " " " " " " " " " " " " " " " " " " " " "（7）

t≤t+L1-β" " " " " " " " " " " " " " " " " " " " " "（8）

p·x+T≤p" " " " " " " " " " " " nbsp; " " " " " " " " "（9）

maxt，p≤t" " " " " " " " " " " " " " " " " " " " "（10）

maxt，p≤p+L1-z" " " " " " " " " " " " " " " " " " " （11）

t+x·x·t=t" " " " " " " " " " " " " " " " " " " "（12）

式（3）表示每道工序必須且只能被分配給一個加工設備；式（4）表示每個工件的工序具有順序，每道工序必須在其上一道工序加工完成后才能開始加工；式（5）表示同一時刻同一臺機器最多只能加工一道工序，上一道工序加工完成后才能加工下一道工序；式（6）表示工序op在機器m加工；式（7）表示每道工序分配給一臺AGV運送；式（8）表示AGV將上一道工序的工件運送到其加工機器后，才能開始下一個運送任務；式（9）表示AGV從原材料庫LU處取走工件并送到第一道工序的加工設備m處，工序op才能開始加工；式（10）表示AGV到達加工設備m處，且工序op加工完成，才能開始運送；式（11）表示AGV將工件配送到m，且機器空閑，工序才能開始加工；式（12）表示AGV從機器m處將工件配送到op對應的機器m處進行加工。

2" 算法設計

NAGA-Ⅱ是一種受到生物進化中的自然選擇和遺傳機制啟發的多目標進化算法，在解決傳統調度問題上應用廣泛，在AGV與柔性作業車間集成調度中，AGV的引入使得問題的解空間復雜性顯著增加，導致算法難以有效地搜索全局最優解。為了避免算法陷入局部最優，本文設計了基于工序層（OV）、機器層（MV）和AGV層（AV）三層編碼的編碼方式，并對工件層、機器層和AGV層編碼分別采用不同的變異方式。此外，為了提高算法的求解速度，本文在改進NSGA-Ⅱ算法中，采用規則選擇和隨機選擇相結合的方法進行種群的初始化，并引入精英選擇策略，對每次迭代過后的非支配解進行儲存、篩選和更新，在保留解的多樣性基礎上提高了算法的收斂速度。

2.1" 編碼與解碼

2.1.1" 編" 碼

根據柔性作業車間中AGV與加工作業集成調度問題的特性，采用三層編碼的方式進行編碼，即工序層（OV）、機器層（MV）和AGV層（AV）三層編碼。具體編碼方式如圖1所示。其中，每層染色體長度為各工件工序數量的總和。工序層（OV）中，編碼數字表示工件編號，該編碼數字第幾次出現則表示該工件的第幾道工序。機器層（MV）中，編碼數字表示工件工序按照順序在其可選設備集中選擇的設備序號。AGV層（AV）中，編碼數字表示負責運送工序層編碼中對應位置上工序的AGV序號。

2.1.2" 解" 碼

通過染色體中工件工序的次序及其每道工序所選擇的加工設備及選擇的AGV進行解碼。如圖1所示，工件層（OV）中的工件3的第1道工序，選擇的加工設備是機器層（MV）中對應工件工序的機器序號為1的加工設備；選擇的AGV是序號為3的AGV。即工序O31所選擇的機器為M2，選擇的AGV是AGV3，以此類推。

2.2" 種群初始化、選擇、交叉與變異操作

2.2.1" 種群初始化

種群初始化是進化算法的起點，初始化策略直接影響著算法的求解質量和求解速度。完全隨機初始化可能導致初始解的優劣差距巨大，降低算法的收斂速度，難以保證可以得到較優解。本文采用規則選擇和隨機選擇相結合的方法進行種群的初始化，對于工件的第一道工序，根據不同設備距離原材料庫的距離，優先選擇運輸距離較短的加工設備；對于可由多臺加工設備加工的工序，根據不同設備加工時間的長短，優先選擇加工時間較短的加工設備。

2.2.2" 選擇操作

選擇性過強會導致早熟收斂，陷入局部最優；選擇性過弱，則會導致尋優過程太慢。本文采用精英選擇策略對染色體進行選擇，使用的是NSGA-II算法的非支配排序選擇方法，并對初始種群進行了非支配排序選擇，生成初始種群全局最優解。然后對種群和子代進行非支配排序選擇和擁擠度的計算生成下一代的種群。最后又對精英存儲庫與種群的聯合進行非支配排序選擇，并進行刪除重復個體、更新精英庫的操作。

2.2.3" 交叉操作

本文采用保持順序的POX交叉方式。將隨機選擇父代1的染色體基因復制到子代1對應的空位中，并隨機選擇父代2的染色體基因復制到子代2中。然后將父代2中擁有子代1的基因（父代1復制到子代1的基因）按順序取出，并將剩余基因按順序填補到子代1相應的空位中，同時對父代1進行相同的操作生成子代2。

2.2.4" 變異操作

變異操作的選擇，本文對工件層（OV）編碼采用交換變異，對機器層（MV）編碼和AGV層（AV）編碼采用獨立于工件層（OV）編碼的隨機選擇變異，即隨機選擇變異位置，并將其變異成可以使用的機器或AGV編碼。

2.3" 算法流程

所提算法的總流程如下所示：

步驟1：隨機生成一個初始種群P，當前代數gen=0；

步驟2：對種群進行非支配排序，計算擁擠度；

步驟3：基于非支配等級和擁擠距離，使用二元錦標賽選擇來選擇父代；

步驟4：對所選擇的父代進行交叉操作產生子代；

步驟5：對子代進行變異操作；

步驟6：將父代P和子代Q合并，產生一個大小為2N的種群R；

步驟7：對R種群進行非支配排序和擁擠距離計算；

步驟8：對R種群進行選擇操作，選擇出N個個體作為下一代的種群P；

步驟9：判斷是否到達最大迭代數，如果當前代數gen達到最大迭代次數G，則終止算法，輸出所得非支配解的前沿，否則，gen=gen+1，返回步驟2。

3" 數值實驗與結果分析

3.1" 實驗數據

為驗證本文所建立的考慮AGV數量配置的柔性作業車間集成調度模型和改進NSGA-Ⅱ算法的可行性與有效性，本文柔性作業車間數據采用文獻[15]中處理過的某制造企業的數據，其中待加工工件有4件，每個工件需要4～6道加工工序，可用的加工設備有8臺，運輸數據采用文獻[16]中所提方法，在0，10之間隨機生成運輸時間，最大交貨期設置為100，AGV的數量范圍為1～6。具體加工時間信息如表1所示，AGV在加工設備間的運輸時間如表2所示。

3.2" 實驗環境與參數設置

實驗環境為Intel（R）Core（TM）i5-10210U CPU@1.60GHz 2.11 GHz處理器，16.0GB內存，編譯軟件為Pycharm 2022.2.5，本文算法的相關參數如表3所示。

3.3" 結果分析與討論

不同AGV數量配置下的最大完工時間如表4所示，隨著AGV數量的增加，最大完工時間隨之相應減少，在滿足交貨期的前提下，案例所需的最佳的AGV數量配置為3。如圖2所示為最佳AGV數量配置下，AGV與柔性作業車間集成調度方案甘特圖。

為了進一步檢驗本文所提AGV與加工作業協同調度的影響，分別對本文所提協同調度方案和先處理加工作業調度再處理AGV調度這兩種方案進行分別求解，為方便表述，本文所述方案命名為方案1，后者命名為方案2。程序獨立運行100次并取解的平均值，具體結果如圖3所示。

根據圖3可知，在滿足交貨期的前提下，方案1最少需要使用3臺AGV，而方案2需要最少使用4臺AGV才能保證完工時間小于交貨期；同時，在使用相同數量AGV的情況下，方案1的平均完工時間也均小于方案2，在所使用的AGV數量分別為3，4，5，6的情況下，方案1比方案2的平均完工時間分別縮短約11.01%、3.06%、3.16%和2.13%。這表明，本文所提AGV與加工作業協同調度方案，在滿足生產任務要求的前提下，無論是所需AGV數量還是平均完工時間，均比方案2更優。因此，本文所提方法能夠在一定生產任務下，確定最佳的AGV數量配置方案和AGV與柔性作業車間集成調度方案，實現AGV資源的使用效率和車間調度方案整體性能的提升。

4" 結" 論

高效合理地管理和調度生產設備資源，對于企業追求生產效率和降低成本至關重要。AGV與柔性作業車間的集成調度，是實現車間生產與運輸整體最優的關鍵，而恰當的AGV數量配置是實現車間生產與運輸的及時性與連續性的重要保證。本文針對考慮AGV數量配置的柔性作業集成調度問題，分析了AGV與加工作業協同調度的影響關系，構建了以最小化最大完工時間與最小化AGV數量為目標的柔性作業車間集成調度模型，并設計了基于工序、加工設備和AGV三層編碼的改進NSGA-Ⅱ算法對模型進行求解。通過對算例的分析與討論發現，本文所設計的改進NSGA-Ⅱ算法所得解的質量較高。本文所示方法能在一定生產任務下，確定最佳的AGV數量配置方案和AGV與柔性作業車間集成調度方案。本文對企業優化AGV數量配置，提高柔性作業車間集成調度方案的整體性能，降低企業生產成本，提高生產車間的生產組織水平具有重要意義。

參考文獻：

[1]" AHANGAR N K， KHALILI M， TAYEBI H. The three-objective optimization model of flexible workshop scheduling problem for minimizing work completion time， work delay time， and energy consumption[J]. Tehnicki Glasnik， 2021，15（1）：76-83.

[2] 牛昊一，吳維敏，章庭棋. 自適應樽海鞘群算法求解考慮運輸時間的柔性作業車間調度[J]. 浙江大學學報（工學版），2023，

57（7）：1267-1277.

[3] 杜凌浩，向鳳紅. 改進多鄰域候鳥優化算法的柔性作業車間調度研究[J]. 兵器裝備工程學報，2022，43（12）：299-306.

[4]" BAYKASOGLU A， MADENOGLU F S， HAMZADAYI A. Greedy randomized adaptive search for dynamic flexible job-shop scheduling[J]. Journal of Manufacturing Systems， 2020，56：425-451.

[5] 劉智飛，馬可欣. 柔性車間雙資源集成調度的小生境遺傳算法優化[J]. 制造技術與機床，2023（8）：32-38.

[6] 吳斌，丁鈺超，ABLABASRI. 自動導引車與機器集成調度問題研究現狀[J]. 計算機工程與應用，2023，59（6）：1-12.

[7] 周曉曄，馬小云，朱梅琳. 機器人-人工揀選環境下混流裝配線齊套物料配送優化[J]. 計算機集成制造系統，2024（4）：1527

-1536.

[8]" LI Z-K， SANG H-Y， LI J-Q， et al. Invasive weed optimization for multi-AGVs dispatching problem in a matrix manufacturing workshop[J]. Swarm and Evolutionary Computation， 2023，77：101227.

[9] 曾亮，詹逸鵬，王粟. 基于文化混合算法的多AGV調度研究[J]. 現代電子技術，2021，44（9）：105-109.

[10]" ZHANG F， LI J. An improved particle swarm optimization algorithm for integrated scheduling model in AGV-served manufacturing systems[J]. Journal of Advanced Manufacturing Systems， 2018，17（3）：375-390.

[11]" ZHANG G， SUN J， LIU X， et al. Solving flexible job shop scheduling problems with transportation time based on improved genetic algorithm[J]. Mathematical Biosciences and Engineering， 2019，16（3）：1334-1347.

[12]" DAI M， TANG D， GIRET A， et al. Multi-objective optimization for energy-efficient flexible job shop scheduling problem with transportation constraints[J]. Robotics and Computer-Integrated Manufacturing， 2019，59：143-157.

[13] 徐云琴，葉春明，曹磊. 含有AGV的柔性車間調度優化研究[J]. 計算機應用研究，2018，35（11）：3271-3275.

[14] 謝旦嵐. 自動化生產線中AGV數量配置的仿真優化研究[J]. 物流工程與管理，2021，43（2）：41-45.

[15] 賀長征，宋豫川，雷琦. 柔性作業車間多自動導引小車和機器的集成調度[J]. 中國機械工程，2019，30（4）：438-447.

[16]" HUANG X， YANG L. A hybrid genetic algorithm for multi-objective flexible job shop scheduling problem considering transportation time[J]. International Journal of Intelligent Computing and Cybernetics， 2019，12（2）：154-174.