陳 穎，葛顯龍

（重慶交通大學(xué) 經(jīng)濟(jì)與管理學(xué)院，重慶 400074）

1 引言

隨著機(jī)械自動(dòng)化、計(jì)算機(jī)集成技術(shù)以及自動(dòng)化立體倉(cāng)庫(kù)的發(fā)展，RGV成為自動(dòng)化裝卸搬運(yùn)的重要手段，有靈活、可控、易維護(hù)、自動(dòng)化程度高、安全等優(yōu)勢(shì)[1]，因此在物流活動(dòng)中得到了廣泛的應(yīng)用。但是，目前對(duì)于智能RGV的動(dòng)態(tài)調(diào)度策略還需進(jìn)一步研究和完善。當(dāng)自動(dòng)化倉(cāng)庫(kù)中有多臺(tái)RGV時(shí)，若調(diào)度不當(dāng)，容易造成運(yùn)輸和調(diào)度的碰撞和鎖死[2]；當(dāng)產(chǎn)品需要多工序加工時(shí)，不同工序的加工設(shè)備安置不當(dāng)，就會(huì)造成資源、時(shí)間的浪費(fèi)[3]；當(dāng)加工產(chǎn)品時(shí)，如果RGV不能對(duì)同時(shí)發(fā)出的信號(hào)做出正確的判別和響應(yīng)[4]，選擇正確的路線以及需要完成的操作，就會(huì)降低生產(chǎn)效率；當(dāng)機(jī)器發(fā)生故障時(shí)，就會(huì)影響調(diào)度方案和降低產(chǎn)量[5]。因此，需要解決RGV的合理調(diào)度問(wèn)題，提高RGV系統(tǒng)的運(yùn)行效率，使產(chǎn)量最大化。

國(guó)內(nèi)外文獻(xiàn)關(guān)于RGV調(diào)度的研究主要是控制、設(shè)計(jì)、路線的優(yōu)化以及碰撞和鎖死等方面，但是關(guān)于RGV動(dòng)態(tài)調(diào)度的研究卻很少。陳華針對(duì)自動(dòng)化立體倉(cāng)庫(kù)的2-RGV調(diào)度問(wèn)題，建立了基于分區(qū)法的混合整數(shù)線性規(guī)劃，使所有物料的總加工時(shí)長(zhǎng)最短[6]。楊少華等研究了環(huán)形輸送系統(tǒng)中多個(gè)RGV調(diào)度模型[7]，根據(jù)出入庫(kù)指標(biāo)和各種運(yùn)行參數(shù)，利用排隊(duì)論構(gòu)建了在不同狀態(tài)下的RGV調(diào)度模型。M.Dotoli和M.P Fanti應(yīng)用著色賦時(shí)Petri網(wǎng)絡(luò)構(gòu)建了一個(gè)具有環(huán)形輸送系統(tǒng)的自動(dòng)化立體倉(cāng)庫(kù)模型[8]，從六種RGV和堆垛機(jī)的利用率調(diào)度策略下選擇出最高效的調(diào)度策略。宴鵬宇與楊乃定[9]提出禁忌搜索和遺傳算法的混合模型，通過(guò)搜索最滿意的機(jī)器人作業(yè)順序來(lái)求解自動(dòng)化工作單元最小完工時(shí)間調(diào)度問(wèn)題。Liu Y K等研究了2-RGV系統(tǒng)的路徑區(qū)分模式和路徑整合模式[10]，并通過(guò)仿真實(shí)驗(yàn)對(duì)兩種策略的優(yōu)劣進(jìn)行比較。吳焱明等對(duì)RGV的動(dòng)態(tài)調(diào)度建立了遺傳算法模型，使得調(diào)度方案更符合實(shí)際情況[11]。徐偉華等針對(duì)雙工位的穿梭機(jī)系統(tǒng)運(yùn)用了約束理論，由先到先搬運(yùn)策略改為數(shù)學(xué)模型優(yōu)化調(diào)度[12]。劉曉平等提出了適用于工件工序存在并行性的染色體解碼方法，能夠有效解決工件可并行性加工的作業(yè)車間調(diào)度問(wèn)題[13]。吳正佳等針對(duì)柔性作業(yè)車間的故障問(wèn)題，提出了一種基于組合策略的重調(diào)度方法，可以有效地處理多種狀況下的設(shè)備故障擾動(dòng)[14]。前述文獻(xiàn)局限于利用智能優(yōu)化算法、仿真實(shí)驗(yàn)對(duì)機(jī)器的調(diào)度和路徑選擇進(jìn)行模擬，這些方法的優(yōu)點(diǎn)是可以得到一個(gè)可行方案，缺點(diǎn)是算法過(guò)于復(fù)雜以及不能對(duì)問(wèn)題進(jìn)行精確求解。

本文在前人研究的基礎(chǔ)上，探索得到車間調(diào)度具有周期性，并且初始周期對(duì)以后的加工作業(yè)周期調(diào)度起到了決定性的作用，因此提出了最短路算法、多目標(biāo)優(yōu)化模型，解決了單工序、多工序RGV的動(dòng)態(tài)調(diào)度問(wèn)題，利用最小支撐樹(shù)和0-1整數(shù)規(guī)劃模型簡(jiǎn)化了算法、縮短了求解時(shí)間。

2 RGV動(dòng)態(tài)調(diào)度問(wèn)題描述

智能加工系統(tǒng)由帶有機(jī)械手抓和清洗槽的RGV、Computer numerical control（數(shù)控機(jī)床，以下簡(jiǎn)稱CNC）、RGV直線軌道、上料傳送帶和下料傳送帶等附屬設(shè)備構(gòu)成。機(jī)械手可以先后各抓取一個(gè)物料，完成上下料作業(yè)，清洗槽每次只能清洗一個(gè)物料。

圖1 RGV—CNC車間布局圖

圖2 帶機(jī)械手臂和清洗槽的RGV實(shí)物圖

在工作正常情況下，如果某CNC處于空閑狀態(tài)，則向RGV發(fā)出上料需求信號(hào)；否則，CNC處于加工作業(yè)狀態(tài)，在加工作業(yè)完成即刻向RGV發(fā)出需求信號(hào)。RGV在收到某CNC的需求信號(hào)后，會(huì)自行確定該CNC的上下料作業(yè)次序，并依次按順序?yàn)槠渖舷铝献鳂I(yè)。根據(jù)需求指令，RGV運(yùn)行至需要作業(yè)的某CNC處，同時(shí)上料傳送帶將生料送到該CNC正前方，供RGV上料作業(yè)。在RGV為某CNC完成一次上下料作業(yè)后，就會(huì)轉(zhuǎn)動(dòng)機(jī)械臂，將一只機(jī)械手上的熟料移動(dòng)到清洗槽上方，進(jìn)行清洗作業(yè)（只清洗加工完成的熟料）。RGV在完成一項(xiàng)作業(yè)任務(wù)后，立即判別執(zhí)行下一個(gè)作業(yè)指令。此時(shí)，如果沒(méi)有接到其他的作業(yè)指令，則RGV就在原地等待直到下一個(gè)作業(yè)指令。當(dāng)某CNC完成一個(gè)物料的加工作業(yè)任務(wù)后，即刻向RGV發(fā)出需求信號(hào)。如果RGV沒(méi)能即刻到達(dá)為其上下料，該CNC就會(huì)出現(xiàn)等待。

本文主要研究的是智能RGV的動(dòng)態(tài)調(diào)度問(wèn)題。首先針對(duì)一道工序的加工作業(yè)，優(yōu)化計(jì)算出在固定工作時(shí)長(zhǎng)內(nèi)的物料加工量。其次是針對(duì)兩道工序的加工作業(yè)，求得設(shè)備柔性和工藝路線柔性并存時(shí)的最大產(chǎn)量。

針對(duì)單工序RGV動(dòng)態(tài)調(diào)度的問(wèn)題，基于多目標(biāo)優(yōu)化的思想，建立最短路模型。由于初始周期RGV的工藝路線對(duì)以后的調(diào)度具有決定性的影響，因此必須確定初始周期的工藝路線和CNC加工順序。首先將各CNC之間的作業(yè)耗時(shí)量化為各CNC之間的路程大小，建立關(guān)于CNC之間耗時(shí)的賦權(quán)圖G(V,E)，并且求解出最小支撐樹(shù)，其次對(duì)解得的兩個(gè)最小支撐樹(shù)進(jìn)行具體分析，確定RGV的最短路和周期時(shí)長(zhǎng)。

針對(duì)兩工序RGV動(dòng)態(tài)調(diào)度的問(wèn)題，基于單工序RGV的動(dòng)態(tài)調(diào)度模型，雖然兩工序加工存在著設(shè)備的柔性和工藝路線的柔性兩個(gè)問(wèn)題，但是實(shí)質(zhì)還是最短路問(wèn)題，與單工序加工不同的是，當(dāng)參數(shù)還沒(méi)有確定時(shí)，兩工序加工沒(méi)有唯一確定的最短路，因?yàn)閮傻拦ば虻募庸r(shí)長(zhǎng)和時(shí)長(zhǎng)比例決定了工藝路線的走向，但是有最根本的、確定的操作流程。在流程設(shè)計(jì)中，需要解決RGV的響應(yīng)原則問(wèn)題，即當(dāng)有信號(hào)沖突時(shí)，RGV先響應(yīng)完成加工第一道工序的CNC發(fā)出的信號(hào)。另一個(gè)需要確定的問(wèn)題是不同工序CNC的數(shù)量和位置情況。

3 調(diào)度優(yōu)化模型的建立

3.1 參數(shù)和變量

模型所需參數(shù)和變量見(jiàn)表1。

表1 符號(hào)說(shuō)明

3.2 模型假設(shè)

假設(shè)1：RGV上物料與下物料的時(shí)間相等。由于在實(shí)際操作過(guò)程中，有時(shí)上下物料一次性進(jìn)行，有時(shí)只進(jìn)行上、下物料其中一個(gè)操作，為了方便計(jì)算，使上下物料時(shí)間相等。

假設(shè)2：當(dāng)信號(hào)沖突時(shí)，RGV首先響應(yīng)加工前一道工序CNC發(fā)出的信號(hào)。這樣可以提高工序間銜接和時(shí)間的利用率。

假設(shè)3：當(dāng)RGV機(jī)械手上已有半成品時(shí)，在原地等待加工后一道工序的CNC發(fā)出信號(hào)，不響應(yīng)加工前一道工序的CNC發(fā)出的信號(hào)，否則就會(huì)使RGV系統(tǒng)發(fā)生混亂，導(dǎo)致自動(dòng)化加工的暫停，就需要人工解除障礙。

3.3 單工序RGV動(dòng)態(tài)調(diào)度的模型建立與分析

由于單工序調(diào)度具有周期性，并且初始周期也就是最開(kāi)始的行駛線路和機(jī)床加工順序不僅影響到了用時(shí)的多少，也對(duì)以后物料的裝卸及清洗作業(yè)順序起到了決定性的作用。因此，單工序RGV動(dòng)態(tài)調(diào)度的關(guān)鍵就在于優(yōu)化初始周期機(jī)床的加工順序和RGV的行駛線路。

將各個(gè)CNC機(jī)床看成一個(gè)點(diǎn)，用Vi表示，制作一個(gè)賦權(quán)圖G=(V,E)，G中每一條邊[vi,vj]上的ωij表示RGV加工作業(yè)所需要消耗的時(shí)間，例如ω13，則表示實(shí)際從CNC1#移動(dòng)到CNC3#所消耗的時(shí)間以及其過(guò)程中所需要的上下物料的時(shí)間。令上下物料時(shí)間、清洗時(shí)間、移動(dòng)時(shí)間、等待時(shí)間分別為x1i、x2i、x3i、x4i。

如果T=是G的一個(gè)支撐樹(shù)[15]，稱E′中所有邊的權(quán)之和為支撐樹(shù)T的權(quán)，記為ω(T)，即：

如果支撐樹(shù)T*的權(quán)ω(T*)是G的所有支撐樹(shù)的權(quán)中最小者，則稱T*是G的最小支撐樹(shù)，即：

得到的最小支撐樹(shù)即為耗時(shí)最少的最優(yōu)初始周期RGV行駛路線以及機(jī)床加工順序。

3.4 多工序RGV動(dòng)態(tài)調(diào)度的模型建立與分析

多工序加工與單工序加工不同之處在于設(shè)備的柔性和工藝路線的柔性，同時(shí)還有不同工序之間加工順序的先后性，由單工序RGV動(dòng)態(tài)調(diào)度模型可得，將各CNC機(jī)床之間所需要的移動(dòng)、上下料、清洗、加工時(shí)間等消耗的時(shí)間量化為各CNC機(jī)床之間的路徑，若要使得產(chǎn)量最大化，即求RGV行駛的最短路，RGV動(dòng)態(tài)調(diào)度過(guò)程操作流程[9]如圖3所示。

圖3 多工序RGV動(dòng)態(tài)調(diào)度流程圖

根據(jù)圖3多工序RGV動(dòng)態(tài)調(diào)度流程圖，假設(shè)總共需要完成M道工序，且各工序必要按照一定的先后順序進(jìn)行加工，xki表示第i個(gè)物料正在進(jìn)行第k道工序，建立的數(shù)學(xué)模型如下：

由于物料是否清洗取決于物料是否完成了全部的工序，而成品數(shù)量取決于物料是否清洗完成，因此利用0-1判斷矩陣來(lái)刻畫是否清洗物料和成品的數(shù)量。

另外要使物料加工多工序時(shí)間利用率以及物料加工產(chǎn)量最大化需要解決兩個(gè)問(wèn)題，一是CNC機(jī)床的刀具分配問(wèn)題，包括了數(shù)量和位置的分配；二是RGV對(duì)機(jī)床發(fā)出信號(hào)的處理問(wèn)題。

首先是CNC機(jī)床的刀具分配問(wèn)題：由于物料需要進(jìn)行M道工序，且必須先完成前一道工序才能完成后一道工序，因此n臺(tái)機(jī)床中必須要有分別完成M道工序的刀具，且一開(kāi)始會(huì)出現(xiàn)加工后一道工序的機(jī)床等待加工前一道工序的機(jī)床完成前一道工序加工的情況。由于物料的初始機(jī)床加工順序以及RGV的行駛路線決定了以后的物料加工作業(yè)，因此必須確定物料的初始加工情況。

對(duì)于CNC刀具數(shù)量的分配問(wèn)題，如果完成前一道工序的機(jī)床數(shù)量大于完成后一道工序的機(jī)床數(shù)量，意味著多出機(jī)床能夠進(jìn)行后一道加工的半成品必須在原來(lái)的機(jī)床上等待，因此，這不僅影響了該物料加工成為成品的時(shí)間，也浪費(fèi)了機(jī)床正常工作的時(shí)間。例如當(dāng)?shù)毒叻峙錇椋?個(gè)加工第一道工序的機(jī)床和3個(gè)加工第二道工序的機(jī)床時(shí)，當(dāng)5個(gè)機(jī)床接連完成第一道工序時(shí)，只能前3個(gè)物料進(jìn)行第二道工序的加工，剩下兩個(gè)半成品只能在原地等待，并且裝有半成品的機(jī)床不能進(jìn)行別的工作，隨著時(shí)間的推移，等待的時(shí)間會(huì)越來(lái)越長(zhǎng)，使得半成品排隊(duì)需要第二道加工的個(gè)數(shù)和時(shí)間都會(huì)增大，最后可能導(dǎo)致系統(tǒng)擁堵。

同理，當(dāng)加工前一道工序的CNC數(shù)量小于加工后一道工序的數(shù)量時(shí)，就會(huì)造成加工后一道工序的CNC有大量的空閑、等待時(shí)間，導(dǎo)致時(shí)間利用效率低，從而生產(chǎn)效率降低。因此，當(dāng)?shù)毒邤?shù)量分配差異越大時(shí)，排隊(duì)越加嚴(yán)重，為了將時(shí)間利用率最大化、生產(chǎn)產(chǎn)量最大化，CNC的刀具數(shù)量分配應(yīng)該相同，即臺(tái)CNC裝配加工第k道工序的刀具，

對(duì)于CNC刀具位置的分配問(wèn)題，當(dāng)M=2時(shí)，可以簡(jiǎn)化為加工第一道工序的CNC的位置分布問(wèn)題，當(dāng)這臺(tái)CNC確定后，另外加工第二道工序的CNC也隨之確定了。由單工序加工RGV動(dòng)態(tài)調(diào)度模型求得的最小支撐樹(shù)可知，RGV移動(dòng)與上下料耗時(shí)最少的情況是奇數(shù)與偶數(shù)編號(hào)分為一個(gè)組合的情況，如圖4所示。

即CNC1#和CNC2#為一組，CNC3#和CNC4#為一組，CNC5#和CNC6#為一組，CNC7#和CNC8#為一組。

圖4 兩工序動(dòng)態(tài)調(diào)度的工序組合

由于上料傳送帶靠近奇數(shù)號(hào)的CNC，因此奇數(shù)號(hào)CNC比偶數(shù)號(hào)的CNC上下物料時(shí)間更短，所以在循環(huán)周期組合順序確定的情況下，使得循環(huán)周期耗時(shí)最小，只需將初始耗時(shí)最小化即可，即將臺(tái)加工第一道工序的CNC排放在距離上料傳送帶的位置即可。因此臺(tái)加工第一道工序的CNC為圖4靠近上料傳送帶的CNC，即CNC1#、CNC3#、CNC5#、CNC7#。當(dāng)M＞2時(shí)，也和加工兩道工序類似，奇數(shù)號(hào)和偶數(shù)號(hào)的CNC編為一組加工單元，才能優(yōu)化線路和最大化利用時(shí)間。

其次是RGV對(duì)機(jī)床發(fā)出信號(hào)的響應(yīng)問(wèn)題：由于不確定前一道工序和后一道工序的加工時(shí)間，因此存在著半成品、成品加工完成時(shí)間的先后順序問(wèn)題[13]，如果半成品和成品同時(shí)完成，同時(shí)發(fā)出信號(hào)時(shí)，RGV應(yīng)該如何選擇？由于后一道工序必須依賴于前一道工序的完成，因此當(dāng)一個(gè)CNC發(fā)出半成品完成信號(hào)時(shí)，RGV就應(yīng)該立即響應(yīng)它，不管其它的CNC發(fā)出成品完成的信號(hào)，因?yàn)橹挥邪寻氤善沸断潞蟛拍苎b在其它后一道工序加工的CNC，不致浪費(fèi)此CNC的時(shí)間，如果先響應(yīng)成品完成信號(hào)，CNC卸下成品后，沒(méi)有現(xiàn)成的半成品裝上去，必須得再去取半成品回來(lái)，這樣一來(lái)一回?zé)o形之中就浪費(fèi)了時(shí)間，還妨礙了完成了半成品加工的CNC繼續(xù)加工生料的時(shí)間，因此當(dāng)信號(hào)沖突時(shí)，必須先響應(yīng)半成品完成的信號(hào)，也就是加工前一道工序機(jī)床發(fā)出的信號(hào)。當(dāng)無(wú)信號(hào)沖突時(shí)，就依據(jù)先發(fā)出信號(hào)先響應(yīng)的原則，使得等待時(shí)間最少。當(dāng)然，不存在相同的信號(hào)同時(shí)發(fā)出的情況，比如兩臺(tái)不同加工前一道工序的CNC同時(shí)發(fā)出半成品完成的信號(hào)，因?yàn)镽GV不可能同時(shí)為兩臺(tái)CNC上料。

4 算法求解

4.1 單工序RGV動(dòng)態(tài)調(diào)度模型求解

最短路算法用Dijkstra法求解步驟如下：

Step2：根據(jù)RGV收到的信號(hào)判斷進(jìn)行了上下物料、清洗和移動(dòng)中的哪一項(xiàng)操作，否則就為等待時(shí)間。如果Si=V，算法終止，這時(shí)，對(duì)每個(gè)v∈Si，d(vs,v)=P(v)；否則轉(zhuǎn)入第三步。

4.2 多工序RGV動(dòng)態(tài)調(diào)度模型求解

Step1：計(jì)算xki的最早開(kāi)始時(shí)間，判斷xki是否為物料的第一道工序，如果是第一道工序，則轉(zhuǎn)入第二步，否則，轉(zhuǎn)入第三步。

Step2：遍歷所有空閑的加工第一道工序的CNC與RGV的距離，找到距離最短的CNC開(kāi)始加工物料，使得

Step3：判斷RGV是否收到了加工工序更少的半成品完成的信號(hào)，如果是，則先進(jìn)行響應(yīng)處理，否則遍歷所有加工后一道工序空閑的CNC與RGV的距離，找到距離最短的CNC開(kāi)始加工物料，使得ω(vs,vj)=min{ω(vs,vi)+ωij}。

Step4：判斷xki是否為最后一道工序，即xki=xMi，如果是，則進(jìn)行成品的清洗，P(x)=P(x0)+x2i，否則轉(zhuǎn)入第三步。

5 算例分析

5.1 參數(shù)設(shè)置

算例參數(shù)設(shè)置見(jiàn)表2。

表2 參數(shù)設(shè)置

共有8臺(tái)CNC，固定工作時(shí)長(zhǎng)為8h，一條上料、下料傳送帶，一條RGV軌道。具體情況如圖5所示。

圖5 車間作業(yè)圖

5.2 結(jié)果分析

（1）單工序RGV動(dòng)態(tài)調(diào)度模型的求解。用破圈法和避圈法可以得到賦權(quán)圖中的最小支撐樹(shù)，從V1即從CNC1#開(kāi)始，箭頭方向表示行駛路線以及機(jī)床加工順序，本文采用避圈法，求得最終最小支撐樹(shù)如圖6、圖7所示。

將所得到的最小支撐樹(shù)放到實(shí)際加工系統(tǒng)調(diào)度操作中，可以得到兩種初始周期的機(jī)床加工順序以及RGV行駛路線的方式，對(duì)其具體的工藝路線和機(jī)床的加工順序進(jìn)行系統(tǒng)、動(dòng)態(tài)的分析，從中選出用時(shí)最少、產(chǎn)量最大的一種方式，具體分析如下：

最小支撐樹(shù)1：按相鄰操作間移動(dòng)距離最短原則，初始加工順序如圖8所示。

圖6 最小支撐樹(shù)1

圖7 最小支撐樹(shù)2

圖8 最小支撐樹(shù)1的機(jī)床初始加工順序

最小支撐樹(shù)1表示RGV首先選擇距離初始位置最近且貨源最近的CNC1#機(jī)床進(jìn)行第一個(gè)物料的裝卸加工，然后轉(zhuǎn)向?qū)α硗庖贿叺木嚯x初始位置最近的CNC2#機(jī)床進(jìn)行第二個(gè)物料的裝卸加工，接著向前移動(dòng)一個(gè)單位，重復(fù)剛才的步驟，直至將第八個(gè)物料裝在CNC8#機(jī)床上進(jìn)行加工。最后由于物料加工時(shí)間較長(zhǎng)，RGV停在CNC7#-CNC8#機(jī)床之間等待。當(dāng)最先裝上CNC的物料加工完成后，CNC1#機(jī)床發(fā)出成品加工完成的信號(hào)，RGV車獲得信號(hào)后向左移動(dòng)三個(gè)單位到達(dá)CNC1#機(jī)床，然后進(jìn)行上下物料以及清洗物料的工作，隨后對(duì)CNC2#機(jī)床進(jìn)行同樣的處理，最后以此方式循環(huán)往復(fù)。

最小支撐樹(shù)2：按距離貨源最近原則，初始加工順序如圖9所示。

圖9 最小支撐樹(shù)2的機(jī)床初始加工順序

最小支撐樹(shù)2表示RGV首先選擇距離初始位置最近且貨源最近的CNC1#機(jī)床進(jìn)行物料的裝卸加工，然后移動(dòng)一個(gè)單位到CNC3#機(jī)床進(jìn)行與CNC1#機(jī)床同樣的操作，接著按原路線返回，依次經(jīng)過(guò)CNC8#-CNC2#機(jī)床，最后停留在CNC2#機(jī)床旁等待。當(dāng)CNC1#機(jī)床上的物料加工完成之后，RGV直接進(jìn)行物料的裝卸和清洗工作，然后向右移動(dòng)一個(gè)單位，對(duì)CNC3#的物料進(jìn)行同樣的操作，最后以此方式循環(huán)往復(fù)。

最小支撐樹(shù)1與最小支撐樹(shù)2的區(qū)別和聯(lián)系：

①當(dāng)RGV移動(dòng)x個(gè)單位是移動(dòng)1個(gè)單位的整數(shù)倍時(shí)，最小支撐樹(shù)1和2的總耗時(shí)相同。

②由于在實(shí)際情況下，當(dāng)行駛總路程相同時(shí)，機(jī)械啟動(dòng)次數(shù)越多花的時(shí)間越多，最小支撐樹(shù)1完成一次周期循環(huán)需要啟動(dòng)RGV四次，最小支撐樹(shù)2需要啟動(dòng)六次，因此最小支撐樹(shù)1比最小支撐樹(shù)2用時(shí)更少。

結(jié)論：選擇最小支撐樹(shù)1的方式，即相鄰操作間移動(dòng)距離最短原則。

將參數(shù)帶入模型以此來(lái)檢驗(yàn)?zāi)Ｐ偷膶?shí)用性和有效性，由結(jié)果可得，單工序RGV動(dòng)態(tài)調(diào)度的周期為634s，8個(gè)連續(xù)作業(yè)時(shí)長(zhǎng)下，第一組能夠加工358個(gè)物料，第二組能加工338個(gè)物料，第三組能加工368個(gè)物料。

（2）兩工序RGV動(dòng)態(tài)調(diào)度模型的求解

①第一組數(shù)據(jù)的求解。第一組RGV的動(dòng)態(tài)調(diào)度過(guò)程為：先對(duì)奇數(shù)號(hào)的CNC從編號(hào)1-7進(jìn)行上料，然后在CNC7#與CNC8#之間等第一道工序加工完成的信號(hào)，接著將CNC1#上的半成品放入到CNC2#上進(jìn)行第二道工序加工，以此類推，直到將CNC7#上的半成品放入CNC8#機(jī)床上進(jìn)行加工，然后又在CNC7#與CNC8#之間等待，由于第一組數(shù)據(jù)中，第二道加工工序的時(shí)間與第一道加工工序的時(shí)間相差不大，但是CNC1#先上料，因此，CNC1#先加工完成，然后發(fā)出半成品加工完成信號(hào)，于是，RGV移動(dòng)到CNC1#并對(duì)此進(jìn)行上下料，在進(jìn)行此操作時(shí)，CNC3#也發(fā)出了半成品加工完成的信號(hào)，但是RGV機(jī)械手上已經(jīng)擁有一個(gè)半成品，且這個(gè)半成品還需要等待CNC2#機(jī)床發(fā)出成品加工完成的信號(hào)后安裝到CNC2#上，因此，本文給出了假設(shè)3：當(dāng)RGV機(jī)械手上已有半成品時(shí)，在原地等待加工第二道工序的CNC發(fā)出信號(hào)，不響應(yīng)加工第一道工序的CNC發(fā)出的信號(hào)，如果響應(yīng)了，會(huì)造成RGV系統(tǒng)混亂，因?yàn)闆](méi)有多余的機(jī)械槽口來(lái)存放多余的半成品，最多只能暫存一個(gè)半成品，才能實(shí)現(xiàn)半成品與成品之間的上下料。

最終的動(dòng)態(tài)調(diào)度結(jié)果為：總共能完成235個(gè)成品的加工（包括清洗在內(nèi)），多余5個(gè)加工完成的半成品，1個(gè)加工完成的成品來(lái)不及清洗。

②第二組數(shù)據(jù)的求解。第二組RGV的動(dòng)態(tài)調(diào)度過(guò)程與第一組相同。

最終的動(dòng)態(tài)調(diào)度結(jié)果為：總共能完成209個(gè)成品的加工（包括清洗在內(nèi)），多余4個(gè)加工完成的半成品。

③第三組數(shù)據(jù)的求解。第三組RGV的動(dòng)態(tài)調(diào)度過(guò)程為：由于第三組數(shù)據(jù)中第一道工序加工時(shí)長(zhǎng)接近第二道工序時(shí)長(zhǎng)的三倍，因此，與前兩組的RGV調(diào)度有很大的差異。首先對(duì)奇數(shù)號(hào)的CNC從編號(hào)1-7進(jìn)行上料，然后在CNC7#與CNC8#之間等第一道工序加工完成的信號(hào)，接著將CNC1#上的半成品放入到CNC2#上進(jìn)行第二道工序加工，以此類推，直到將CNC7#上的半成品放入CNC8#機(jī)床上進(jìn)行加工，然后又在CNC7#與CNC8#之間等待。因?yàn)榈诙拦ば驎r(shí)長(zhǎng)比第一道加工時(shí)長(zhǎng)小很多，因此，偶數(shù)號(hào)的CNC從CNC2#開(kāi)始先發(fā)出成品加工完成信號(hào)，RGV立即對(duì)其響應(yīng)，將CNC2#上的成品卸下并且清洗，此時(shí)，CNC2#暫時(shí)空閑，而在執(zhí)行清洗工作時(shí)，CNC4#也發(fā)出了成品加工完成信號(hào)，所以RGV立即響應(yīng)新的信號(hào)，以此類推，RGV將CNC8#上的成品卸下并且清洗，然后在CNC8#和CNC7#之間等待CNC1#發(fā)出信號(hào)，然后立即對(duì)其進(jìn)行響應(yīng)，重復(fù)以上的工序。

最終的動(dòng)態(tài)調(diào)度結(jié)果為：總共能完成184個(gè)成品的加工（包括清洗在內(nèi)），多余5個(gè)加工完成的半成品，1個(gè)加工完成的成品來(lái)不及清洗。

將三組數(shù)據(jù)的不同參數(shù)與求解結(jié)果放在一起進(jìn)行比較，見(jiàn)表4。

表4 兩工序RGV動(dòng)態(tài)調(diào)度結(jié)果

由表4可知，在其他因素相差不大的情況下，不同工序的耗時(shí)對(duì)成品產(chǎn)量有很大的影響。

第一組數(shù)據(jù)中，第一道工序和第二道工序耗時(shí)相差不大，但是由于第一道工序先進(jìn)行加工，因此不會(huì)有較長(zhǎng)時(shí)間的等待問(wèn)題，對(duì)時(shí)間的利用率較高。

第二組數(shù)據(jù)中，第一道工序耗時(shí)比第二道工序耗時(shí)幾乎少了一半，加工完成的半成品可以快速地投入到第二道工序的加工中，但是由于第二道工序的耗時(shí)過(guò)長(zhǎng)，則取完半成品后必須等待CNC第二道工序完成，因此對(duì)時(shí)間的利用率比第一組低，所以產(chǎn)品產(chǎn)量也比第一組低。由于第二組數(shù)據(jù)中，RGV的移動(dòng)、上下料、清洗等耗時(shí)均比第一組高，因此為了使第一組和第二組具有可比性，除了第一道和第二道工序保留不變外，其它都用第一組的參數(shù)計(jì)算，結(jié)果完成成品的數(shù)量為211，與原來(lái)的209相比，效果并不顯著。由此可見(jiàn)，對(duì)產(chǎn)量數(shù)量影響最大的是加工不同工序的時(shí)間和時(shí)間比例。

第三組數(shù)據(jù)中，加工第二道工序的耗時(shí)遠(yuǎn)小于加工第一道工序耗時(shí)，并且第二道工序的進(jìn)行必須依賴于第一道工序的完成，所以造成了加工第二道工序的CNC工作時(shí)間的大量浪費(fèi)。同理，為了使第三組和第一組具有可比性，除了第一道和第二道工序保留不變外，其它都用第一組的參數(shù)計(jì)算，結(jié)果完成成品的數(shù)量為210，與原來(lái)的209相比，影響很小，效果并不顯著。

兩道工序加工RGV動(dòng)態(tài)調(diào)度的結(jié)論：

加工不同工序的時(shí)間和時(shí)間比例是影響產(chǎn)量最重要的原因，其他清洗時(shí)間、上下料時(shí)間、移動(dòng)時(shí)間等因素對(duì)產(chǎn)量的聯(lián)合影響可以微乎不計(jì)。由于此兩道工序有順序上的依賴性，因此，第一道工序和第二道工序不宜相差太大，否則就會(huì)出現(xiàn)等待或者排隊(duì)的情況。當(dāng)加工第二道工序時(shí)間遠(yuǎn)大于加工第一道工序的時(shí)間時(shí)，就會(huì)造成加工第一道工序的CNC等待，反之，則會(huì)造成加工第二道工序的CNC等待。最好的情況是第一道工序加工時(shí)間比第二道工序加工時(shí)間少一點(diǎn)，以此來(lái)彌補(bǔ)進(jìn)行其他操作所消耗的時(shí)間。

6 結(jié)語(yǔ)

本文主要研究的是智能RGV的動(dòng)態(tài)調(diào)度問(wèn)題。首先針對(duì)單工序的加工作業(yè)調(diào)度問(wèn)題，由于初始周期時(shí)正常工作循環(huán)周期起著決定性的作用，因此對(duì)于初始周期建立了關(guān)于耗時(shí)的賦權(quán)圖，求解出最小支撐樹(shù)，得到最優(yōu)調(diào)度方案。其次是針對(duì)多工序的加工作業(yè)調(diào)度問(wèn)題，分析在設(shè)備柔性和工藝路線柔性并存時(shí)的最優(yōu)調(diào)度，由此建立了多目標(biāo)優(yōu)化模型，并采取了0-1整數(shù)規(guī)劃模型進(jìn)行求解。最后設(shè)置相關(guān)參數(shù)進(jìn)行案例求解和分析，最后得出，在一個(gè)班次內(nèi)，對(duì)于不同操作參數(shù)的RGV進(jìn)行了比較與分析，得到不同工序加工時(shí)長(zhǎng)對(duì)RGV的動(dòng)態(tài)調(diào)度起到了絕對(duì)性的影響，其他的上下物料、清洗、移動(dòng)時(shí)間對(duì)RGV的調(diào)度情況幾乎沒(méi)有影響，因此，該模型對(duì)于車間內(nèi)不同設(shè)備模擬效果好，實(shí)用性強(qiáng)。