李勝成

摘? 要：一種智能加工系統(tǒng)由8臺計算機數(shù)控機床（CNC）、1輛軌道式自動引導(dǎo)車（RGV）、1條RGV直線軌道、1條上料傳送帶、1條下料傳送帶等附屬設(shè)備組成。文章通過研究RGV的選擇判斷規(guī)律，以一道工序無故障情況為例，在RGV需要選擇去向時采用貪心算法，這體現(xiàn)為RGV每次選擇去向時選擇運動時間與上下料時間之和最小的目標(biāo)，將該過程定為所有判斷的原則。故可得出動態(tài)調(diào)度后每個CNC的總等待時間最少，將機床工作效率最大化。從而給出最優(yōu)動態(tài)調(diào)度策略。

關(guān)鍵詞：動態(tài)調(diào)度;貪心算法;靈敏性分析

中圖分類號：O221 文獻標(biāo)志碼：A? ? ? ? ?文章編號：2095-2945（2020）06-0016-02

Abstract： An intelligent machining system consists of 8 computer numerical control （CNC） machine tools， 1 rail guide vehicle（RGV）， 1 RGV linear track， 1 feeding conveyor belt， 1 cutting conveyor belt and other ancillary equipment. In this paper， the selection and judgment rule of RGV is studied. Taking a working procedure with no fault as an example， greedy algorithm is adopted when RGV needs to select the direction， which is reflected in the minimum sum of movement time and loading and unloading time when RGV selects the direction， and this process is set as the principle of all judgments. Therefore， it can be concluded that the total waiting time of each CNC after dynamic scheduling is the least， and the working efficiency of the machine is maximized. The optimal dynamic scheduling strategy is given.

Keywords： dynamic scheduling; greedy algorithm; sensitivity analysis

1 概述

對智能加工系統(tǒng)建立RGV動態(tài)調(diào)度模型[1]，需使用

matlab軟件編程，通過判斷語句和循環(huán)語句實現(xiàn)RGV的狀態(tài)轉(zhuǎn)換和系統(tǒng)時間的推進，程序模擬的信息世界變量轉(zhuǎn)換要遵循現(xiàn)實世界不同情況下物體運行規(guī)律，通過matlab程序仿真實現(xiàn)過程和結(jié)果的輸出，并通過優(yōu)化RGV工作狀態(tài)轉(zhuǎn)換原則來改善動態(tài)調(diào)度模型。

2 一道工序無故障情況

2.1 模型的建立

RGV具有的四個工作階段為：移動階段M、上下料階段F、清洗階段W、停止階段S[2]。

通過附件一所給系統(tǒng)作業(yè)流程，可總結(jié)出在一道工序無故障情況下各階段完成后可供選擇的階段線路圖（如圖1所示），系統(tǒng)總運行過程應(yīng)由若干該子圖拼接而成。

RGV的移動階段M后必定為上下料階段F，上下料階段F后必定為清洗階段W，這兩個階段不需要進行判斷。RGV在清洗階段W后有兩種可能的情況：

（1）完成清洗階段的時間點沒有需求信號，RGV進入停止階段。

（2）若此時有需求信號，根據(jù)此時RGV的位置和信號位置判斷，又分為以下兩種情況：

若此時RGV與需求信號在同一列上，即可直接進行上下料工作。

若此時RGV與需求信號不在同一列，通過判斷決定接下來移動的方向與距離。

智能加工系統(tǒng)通電后，RGV位于CNC1和CNC2正中間的初始位置，所有CNC都處于空閑狀態(tài)。故RGV的第一步應(yīng)為對所有CNC進行上料操作。我們發(fā)現(xiàn)上料側(cè)CNC一次上下料所需時間明顯小于下料側(cè)CNC，故優(yōu)先對上料側(cè)CNC進行上料操作，則對CNC初始上料操作的先后順序如圖2所示。

在此基礎(chǔ)上，我們利用貪心算法[1]，建立一道工序無故障情況下RGV動態(tài)調(diào)度模型。

貪心算法是指在對問題求解時，總是做出在當(dāng)前看來是最好的選擇，也就是說，不從整體最優(yōu)上加以考慮，他所做出的是在某種意義上的局部最優(yōu)解。故我們通過確定各個子階段的局部最優(yōu)解來進行RGV的動態(tài)調(diào)度，即在RGV的清洗階段W和停止階段S完成后接收到物料已完成信號時進行動態(tài)調(diào)度。[3]

該動態(tài)調(diào)度的決策僅考慮當(dāng)前情況且該決策無后效性。設(shè)某時刻RGV的位置為X0，RGV在該時刻同時接收到m個已完成信號，此時RGV進行去向判斷，判斷方法應(yīng)為RGV到達該點的移動時間與上下料時間之和最小。設(shè)第p個已完成信號的橫向位置為xp，則該信號與RGV的距離i=X0-xp，即本次移動時間為tMi=t，RGV為該CNC一次上下料的時間為tFp=tF奇，上料側(cè)CNC

tF偶，下料側(cè)CNC。則RGV下一步的去向應(yīng)為當(dāng)tM+tF=mint+tFp時信號的發(fā)出地，子流程的決策完成。

基于該去向判斷方法可知，當(dāng)優(yōu)先于某物料下料的物料數(shù)為s，則一個CNC完成一個物料所需的等待時間twait=mint+tFp。當(dāng)一個CNC八小時一共完成了n個成料和n'個半成品物料時，該CNC所需的總等待時間T為：

該情況下動態(tài)調(diào)度原則為每個CNC的總等待時間最少：

T=min

設(shè)tr為第r次上下料開始時間點，則tr+1表示第RGV執(zhí)行上下料操作開始的時間點，他們之間相隔時間至少為：一次上下料時間+加工時間+清洗時間+移動時間，可用該遞推式表示tr+1?tr+tF1+tP+tW+tM。

各CNC八小時總工作過程的約束條件為：

其中n'為平均每個CNC完成的半成料數(shù)量。

2.2 模型的求解

定義一個需求矩陣[x]2×4，元素為0表示物料無下料需求，1表示有下料需求。在初始上料完成后[x]2×4為全0矩陣。n為完成的成料數(shù)，初值為0。迭代求解程序流程圖如圖3所示：

最終可求得當(dāng)程序內(nèi)的總時間到達八小時后，成料數(shù)n及各物料的上、下料時間。

3 結(jié)束語

本文針對一道工序的情況，建立了基于貪心算法的數(shù)學(xué)模型，并且利用matlab[4]求解了該模型。經(jīng)過該方法調(diào)度后每個CNC的總等待時間最少，從而效率將最大化。對生產(chǎn)實際具有一定的借鑒作用。

參考文獻：

[1]周正昱.智能RGV的動態(tài)調(diào)度策略模型[J].南方農(nóng)機，2018（23）：55-56.

[2]董軍軍.動態(tài)規(guī)劃算法與貪心算法的比較與分析[J].軟件導(dǎo)刊，2008（02）：129-130.

[3]王建玲，齊紫茜，何璐.基于蟻群算法的車輛調(diào)度問題[J].交通科技與經(jīng)濟，2014，16（6）：37-39，94.

[4]卓金武，等.MATLAB在數(shù)學(xué)建模中的應(yīng)用[M].北京：北京航空航天大學(xué)出版社，2011.