方衛(wèi)杰，賴威鵬，耿昆侖，趙凱芳

（1.天津大學(xué)仁愛(ài)學(xué)院信息工程系，天津 301636；2.天津大學(xué)仁愛(ài)學(xué)院數(shù)學(xué)教學(xué)部，天津 301636）

0 引言

隨著信息技術(shù)的快速崛起，自動(dòng)化控制、機(jī)電一體化和機(jī)械智能化的發(fā)展，工業(yè)上出現(xiàn)了越來(lái)越多的自動(dòng)化加工的車(chē)間與工廠。RGV（Rail Guide Vehicle）軌道式自動(dòng)引導(dǎo)車(chē)被廣泛應(yīng)用于物流運(yùn)輸和物料加工。由于實(shí)際生產(chǎn)的時(shí)候是一輛RGV對(duì)多個(gè)CNC（Computer Number Controller），合理的安排RGV的調(diào)度策略是提高生產(chǎn)效率的重要因素。

1 基于貪心算法建模思想

考慮到 RGV的調(diào)度與物料的加工是動(dòng)態(tài)過(guò)程，本文采用貪心算法。 貪心算法（又稱貪婪算法）是指，在對(duì)問(wèn)題求解時(shí)，總是作出在當(dāng)前是最好的選擇?；舅枷胧牵好看螐南到y(tǒng)每一步結(jié)束處出發(fā)一步一步地進(jìn)行，根據(jù)某個(gè)優(yōu)化測(cè)度，每一步都要確保能獲得局部最優(yōu)解。每一步只考慮一個(gè)數(shù)據(jù)，選取其應(yīng)該滿足局部?jī)?yōu)化的條件。

針對(duì)本問(wèn)題，RGV每走一步之前會(huì)先向下搜索三層，找出這三步總用時(shí)最短的一條路線，然后RGV會(huì)選擇該路線的第一步作為局部最優(yōu)路線。貪心選擇圖示如下：

C - CNC的編號(hào)

T - RGV移動(dòng)所需的時(shí)間

F - 層數(shù)

圖1 貪婪算法選擇示意圖

2 雙工序無(wú)故障調(diào)度模型

將加工第一道工序的CNC稱為A類CNC，而加工第二道工序的CNC稱為B類CNC。

2.1 兩道工序CNC的數(shù)量和分布位置模型

針對(duì)有兩道加工工序的情況，確定CNC的排布位置，使得系統(tǒng)加工物料的效率更高.通過(guò)兩道工序加工所需的時(shí)間Tf，Ts來(lái)確定分別加工兩道工序的CNC的臺(tái)數(shù)N1，N2。

兩道工序CNC的位置分布關(guān)系到RGV總體的調(diào)度效率，即RGV從A類CNC處到B類CNC處所需的時(shí)間盡可能的少。

則可建立如下模型：

2.2 雙工序無(wú)故障調(diào)度模型

物料第一道工序加工完成后，無(wú)需清洗，直接進(jìn)行第二道工序；在初始狀態(tài)時(shí)，無(wú)論加工兩道工序CNC的比例是多少，RGV總是先為所有的A類CNC上料；在為B類CNC上下料前，必須先為A類CNC下料，并攜帶已完成第一道工序的物料，而后對(duì)B類CNC進(jìn)行上下料，所以無(wú)需專門(mén)為A類CNC上下料，只需研究第二道工序時(shí)RGV的調(diào)度。

取料階段RGV所需時(shí)間：

上料階段RGV所需時(shí)間

則對(duì)B類CNC進(jìn)行一次上下料處理所需總時(shí)間為：

綜上所述可得動(dòng)態(tài)規(guī)劃模型為：

2.3 模型求解

（1）由兩道工序CNC的數(shù)量和分布位置模型，得到 A、B類CNC分布.下圖為一二道工序所用時(shí)間不同比例下的CNC的分配案示意圖：

圖2 A、B類CNC分布

（2）調(diào)度模型求解：

算法步驟：

Step2：因?yàn)锽類CNC需要A類CNC提供已完成第一道工序的物料，所以RGV會(huì)先給所有的A類CNC上好料再給B類CNC上料，下圖為CNC在各種比例下，工作開(kāi)始時(shí)A類CNC上的順序：

圖3 初始RGV移動(dòng)方式

Step3：遍歷RGV下一步所有可能的走法，并找出其中耗時(shí)最少的哪條路線。

Step4：循環(huán)往復(fù)步驟三，直到加工總時(shí)間超過(guò)一個(gè)工時(shí)退出循環(huán)。

Step5：最后輸出算法結(jié)果。

（3）將結(jié)果繪制成甘特圖，由此可得RGV的調(diào)度策略，這里只給出RGV前3000秒在三組不同情況下加工時(shí)間及工序的甘特圖。橫軸為時(shí)間刻度，縱軸為CNC的編號(hào)（由上到下依次為1-8）。圖4為RGV前3000秒在三組不同情況下給CNC做上下料處理的時(shí)間與工序的甘特圖。

圖4

3 實(shí)物模型

圖5 智能加工系統(tǒng)模型

圖6 樹(shù)派編程環(huán)境