基于全局空閑工位優(yōu)先的機(jī)動(dòng)車檢測(cè)調(diào)度算法

劉曉鑫，趙祥模，張立成，周 洲

(長(zhǎng)安大學(xué) 信息工程學(xué)院，陜西 西安 710064)

0 引 言

近幾年，我國(guó)機(jī)動(dòng)車保有量爆發(fā)式增長(zhǎng)[1]，但機(jī)動(dòng)車檢測(cè)行業(yè)的檢測(cè)效率沒(méi)有明顯提升，導(dǎo)致檢測(cè)行業(yè)提供的服務(wù)不能滿足車主的檢測(cè)需求。優(yōu)化機(jī)動(dòng)車檢測(cè)調(diào)度流程是解決上述矛盾的有效途徑之一。根據(jù)P. Brucker等研究可知：機(jī)動(dòng)車檢測(cè)調(diào)度屬于柔性車間調(diào)度問(wèn)題(flexible job-shop scheduling problem，F(xiàn)JSP)，Garey M R等研究結(jié)果表明該問(wèn)題是NP-hard問(wèn)題。

目前求解FJSP問(wèn)題的方法主要可歸納為兩類：精確求解和近似求解。精確求解可通過(guò)排列組合、分支界定、動(dòng)態(tài)規(guī)劃[2]等方法解決，但是只適應(yīng)于規(guī)模較小的情況。在問(wèn)題規(guī)模較大時(shí)，多采用近似求解法。S. Zhang等[3]通過(guò)改進(jìn)蟻群算法，提出了增強(qiáng)型蟻群優(yōu)化元啟發(fā)式算法，用來(lái)解決作業(yè)車間環(huán)境下的調(diào)度問(wèn)題。Piroozfard H等[4]通過(guò)考慮碳足跡在環(huán)境中的排放，提出了一種改進(jìn)的多目標(biāo)遺傳算法，優(yōu)化了工作車間調(diào)度問(wèn)題。Nouiri M等[5]應(yīng)用粒子群優(yōu)化算法求解FJSP問(wèn)題。Lu C等[6]從實(shí)際制造企業(yè)出發(fā)，提出了既考慮產(chǎn)品最大壽命，又考慮能源消耗的混合多目標(biāo)回溯搜索算法，用于解決置換流車間調(diào)度問(wèn)題。Gao L等[7]為了更好解決焊接行業(yè)中的動(dòng)態(tài)調(diào)度問(wèn)題，提出一種混合多目標(biāo)灰狼優(yōu)化器。Liu Y等[8]為了釋放系統(tǒng)節(jié)能潛力，提升系統(tǒng)效率，提出了一種總電耗和總加權(quán)時(shí)滯最小化的雙目標(biāo)調(diào)度模型。上述學(xué)者針對(duì)不同實(shí)際環(huán)境對(duì)相應(yīng)的FJFP問(wèn)題進(jìn)行了解答，但是在機(jī)動(dòng)車檢測(cè)領(lǐng)域，針對(duì)檢測(cè)車間作業(yè)調(diào)度問(wèn)題的研究較少。

本文以最小調(diào)度完成時(shí)間和最大工位資源利用率為目標(biāo)，結(jié)合實(shí)際生產(chǎn)環(huán)境，采用全局工位優(yōu)先的原則，對(duì)機(jī)動(dòng)車檢測(cè)調(diào)度流程進(jìn)行了優(yōu)化和改進(jìn)。

1 機(jī)動(dòng)車檢測(cè)調(diào)度問(wèn)題分析

1.1 問(wèn)題描述

機(jī)動(dòng)車檢測(cè)調(diào)度問(wèn)題可概括的描述為：將機(jī)動(dòng)車檢測(cè)任務(wù)安排在不沖突的時(shí)間和檢測(cè)工位中，同時(shí)滿足各種約束。具體地講，有Vn輛機(jī)動(dòng)車要在m個(gè)檢測(cè)車間進(jìn)行檢測(cè)，每個(gè)檢測(cè)車間有k個(gè)檢測(cè)工位。已知每輛機(jī)動(dòng)車在每個(gè)檢測(cè)工位上的檢測(cè)任務(wù)及檢測(cè)耗時(shí)，對(duì)Vn輛機(jī)動(dòng)車在m個(gè)檢測(cè)車間上的檢測(cè)順序進(jìn)行安排，使得Vn輛機(jī)動(dòng)車在完成m個(gè)檢測(cè)車間的檢測(cè)任務(wù)后,一些性能指標(biāo)達(dá)到最優(yōu)化。本文中的最優(yōu)化指標(biāo)是：最小化完成時(shí)間和最大化資源利用率。

最小化完成時(shí)間指：完成最后一輛機(jī)動(dòng)車的最后一項(xiàng)檢測(cè)項(xiàng)目的時(shí)刻應(yīng)該盡可能早，即完成所有機(jī)動(dòng)車的檢測(cè)任務(wù)，檢測(cè)車間耗時(shí)最短。當(dāng)Vn輛機(jī)動(dòng)車完成檢測(cè)項(xiàng)目申請(qǐng)后，各檢測(cè)車間和檢測(cè)工位分別要檢測(cè)的機(jī)動(dòng)車就已經(jīng)確定。要使得檢測(cè)完成時(shí)間最小化，需要通過(guò)調(diào)度算法，降低檢測(cè)工位空轉(zhuǎn)時(shí)間，使得各檢測(cè)車間能夠盡快的完成機(jī)動(dòng)車的檢測(cè)任務(wù)。

最大化資源利用率指在完成Vn輛機(jī)動(dòng)車的檢測(cè)任務(wù)期間，通過(guò)調(diào)度算法，盡可能使得各車間各檢測(cè)工位能夠時(shí)刻保持運(yùn)轉(zhuǎn)。換而言之，盡可能降低檢測(cè)設(shè)備的空轉(zhuǎn)時(shí)間。

1.2 約束條件

為了確保本算法在實(shí)際工程中的可操作性，保證檢測(cè)車間能夠有序正常運(yùn)行，需要滿足以下約束：①同一車間內(nèi)機(jī)動(dòng)車按工位排列順序進(jìn)行檢測(cè)；②不同車間之間機(jī)動(dòng)車可隨意跳轉(zhuǎn)檢測(cè)；③各檢測(cè)車間各檢測(cè)工位檢測(cè)任務(wù)各不相同；④同輛機(jī)動(dòng)車同一時(shí)刻只能在一個(gè)工位接受檢測(cè)；⑤設(shè)定原子時(shí)間，將每個(gè)項(xiàng)目的檢測(cè)耗時(shí)設(shè)定為原子時(shí)間的整數(shù)倍；⑥檢測(cè)任務(wù)一旦開(kāi)始不得中斷；⑦如果多個(gè)檢測(cè)車間，同時(shí)競(jìng)爭(zhēng)同一輛機(jī)動(dòng)車時(shí)，當(dāng)前檢測(cè)車間正在檢測(cè)的車輛數(shù)量少的車間優(yōu)先；⑧如果多個(gè)檢測(cè)車間，同時(shí)競(jìng)爭(zhēng)同一輛機(jī)動(dòng)車，并且當(dāng)前各車間的檢測(cè)車輛數(shù)量相等時(shí)，機(jī)動(dòng)車能夠最先檢測(cè)的車間優(yōu)先，否則隨機(jī)選擇一個(gè)車間檢測(cè)。

1.3 解決方案

由1.1節(jié)可知，最小化檢測(cè)完成時(shí)間和最大化工位資源利用率，均與檢測(cè)車間中各檢測(cè)工位的運(yùn)行狀態(tài)有關(guān)。因此，從檢測(cè)工位角度分析和解決問(wèn)題。

步驟1 將Vn輛機(jī)動(dòng)車在各檢測(cè)工位上申請(qǐng)的檢測(cè)項(xiàng)目按照檢測(cè)工位進(jìn)行分組。每個(gè)檢測(cè)工位維護(hù)一個(gè)檢測(cè)車輛隊(duì)列，隊(duì)列中的機(jī)動(dòng)車按照在該工位申請(qǐng)檢測(cè)項(xiàng)目的先后順序依次排列；

步驟2 在滿足1.2節(jié)約束條件的前提下，當(dāng)檢測(cè)車間首個(gè)檢測(cè)工位空閑時(shí)，從該工位的檢測(cè)車輛隊(duì)列中，順序調(diào)度機(jī)動(dòng)車進(jìn)行檢測(cè)；

步驟3 當(dāng)所有機(jī)動(dòng)車完成所申請(qǐng)的檢測(cè)任務(wù)之前，循環(huán)執(zhí)行步驟2。

2 基于FIFO策略的機(jī)動(dòng)車檢測(cè)調(diào)度算法

基于FIFO策略的機(jī)動(dòng)車檢測(cè)調(diào)度算法(簡(jiǎn)稱為：FIFO)廣泛應(yīng)用在當(dāng)今工業(yè)環(huán)境中，例如：榆林、咸陽(yáng)、商洛等多地區(qū)的10余個(gè)機(jī)動(dòng)車檢驗(yàn)機(jī)構(gòu)的機(jī)動(dòng)車檢測(cè)調(diào)度算法均是基于FIFO策略的調(diào)度方式[9]。FIFO具有理解簡(jiǎn)單、易于實(shí)現(xiàn)的優(yōu)點(diǎn)，其算法調(diào)度流程可總結(jié)如下：

步驟1 將檢測(cè)機(jī)構(gòu)所有檢測(cè)工位按照某個(gè)順序進(jìn)行排列，得到檢測(cè)工位隊(duì)列stationArray。檢測(cè)工位在stationArray中的順序一旦確定，不可更改；

步驟2 將申請(qǐng)檢測(cè)的機(jī)動(dòng)車按照申請(qǐng)時(shí)間先后順序排列，得到機(jī)動(dòng)車隊(duì)列vehicleArray；

步驟3 從vehicleArray按順序調(diào)度機(jī)動(dòng)車，按照檢測(cè)工位在stationArray中的順序，依次完成機(jī)動(dòng)車的檢測(cè)任務(wù)。當(dāng)前工位的下一個(gè)檢測(cè)工位繁忙時(shí)，機(jī)動(dòng)車必須在當(dāng)前工位等待，直到下一個(gè)檢測(cè)工位空閑時(shí)才可以進(jìn)入檢測(cè)；

步驟4 當(dāng)stationArray中第一個(gè)檢測(cè)工位沒(méi)有機(jī)動(dòng)車檢測(cè)時(shí)，從vehicleArray中調(diào)度下一輛機(jī)動(dòng)車進(jìn)入檢測(cè)流程。步驟4在算法調(diào)度過(guò)程中獨(dú)立執(zhí)行，時(shí)刻監(jiān)控stationArray中第一個(gè)檢測(cè)工位的狀態(tài)；

步驟5 循環(huán)執(zhí)行步驟3，直到完成vehicleArray中所有機(jī)動(dòng)車的檢測(cè)任務(wù)。

由上述調(diào)度流程可知：當(dāng)采用FIFO調(diào)度機(jī)動(dòng)車時(shí)，機(jī)動(dòng)車必須順序完成stationArray中的檢測(cè)任務(wù)，不能出現(xiàn)跳過(guò)某個(gè)檢測(cè)工位，檢測(cè)下一個(gè)項(xiàng)目的情況。這樣可能導(dǎo)致一個(gè)顯著的問(wèn)題：由于下一個(gè)檢測(cè)工位處于繁忙狀態(tài)，機(jī)動(dòng)車完成當(dāng)前檢測(cè)項(xiàng)目后，繼續(xù)在當(dāng)前檢測(cè)工位等待，即使該機(jī)動(dòng)車在下一個(gè)檢測(cè)工位沒(méi)有檢測(cè)任務(wù)也必須等待。這樣必然導(dǎo)致：需要進(jìn)入當(dāng)前工位檢測(cè)的機(jī)動(dòng)車，也必須等待已經(jīng)完成檢測(cè)任務(wù)的機(jī)動(dòng)車進(jìn)入下一個(gè)檢測(cè)工位之后，才能進(jìn)入當(dāng)前工位進(jìn)行檢測(cè)。最終導(dǎo)致：機(jī)動(dòng)車等待時(shí)間加長(zhǎng)、檢測(cè)工位空轉(zhuǎn)時(shí)間延長(zhǎng)、機(jī)動(dòng)車檢測(cè)完成時(shí)刻延后、檢測(cè)工位資源利用率降低。

因此，有必要引進(jìn)新的機(jī)動(dòng)車檢測(cè)調(diào)度策略，克服和優(yōu)化FIFO帶來(lái)的缺陷和不足，縮短檢測(cè)完成時(shí)間、提升檢測(cè)工位資源利用率。

3 基于全局工位優(yōu)先的機(jī)動(dòng)車檢測(cè)調(diào)度算法

3.1 符號(hào)定義

定義1 空閑工位:當(dāng)前，如果檢測(cè)工位沒(méi)有對(duì)任何機(jī)動(dòng)車執(zhí)行檢測(cè)任務(wù)，則稱該檢測(cè)工位為空閑工位。此時(shí)該檢測(cè)工位處于空閑狀態(tài)。如果機(jī)動(dòng)車在空閑工位，說(shuō)明該機(jī)動(dòng)車在等待下一個(gè)檢測(cè)工位完成檢測(cè)任務(wù)。

定義2 繁忙工位:如果檢測(cè)工位不是空閑工位，則該工位是繁忙工位。此時(shí)該檢測(cè)工位處于繁忙狀態(tài)。

定義3 空轉(zhuǎn)時(shí)間:檢測(cè)工位處于空閑狀態(tài)的一段時(shí)間，稱為該檢測(cè)工位的空轉(zhuǎn)時(shí)間。

定義4 繁忙時(shí)間:檢測(cè)工位處于繁忙狀態(tài)的一段時(shí)間，稱為該檢測(cè)工位的繁忙時(shí)間。

定義5 運(yùn)行時(shí)間:檢測(cè)工位空轉(zhuǎn)時(shí)間與繁忙時(shí)間之和，稱為該檢測(cè)工位的運(yùn)行時(shí)間。

定義6 未完成檢測(cè)任務(wù)機(jī)動(dòng)車隊(duì)列:每個(gè)檢測(cè)工位都維護(hù)一個(gè)未完成檢測(cè)任務(wù)機(jī)動(dòng)車隊(duì)列(簡(jiǎn)記為：stationReVehicles隊(duì)列)。將在檢測(cè)工位申請(qǐng)檢測(cè)的機(jī)動(dòng)車，按照申請(qǐng)時(shí)間先后順序排列，得到該檢測(cè)工位的stationReVehicles隊(duì)列。

定義7 機(jī)動(dòng)車等待狀態(tài):如果機(jī)動(dòng)車正在等待某個(gè)檢測(cè)工位，則該機(jī)動(dòng)車處于等待狀態(tài)。

3.2 全局空閑工位優(yōu)先

結(jié)合1.1節(jié)和第2章節(jié)的描述分析可知：為空閑工位選擇機(jī)動(dòng)車調(diào)度策略，關(guān)乎該調(diào)度算法的性能優(yōu)良。結(jié)合空閑工位在實(shí)際車間的分布情況與當(dāng)前機(jī)動(dòng)車的檢測(cè)情況，提出全局空閑工位優(yōu)先策略：

當(dāng)檢測(cè)車間第一個(gè)檢測(cè)工位處于空閑狀態(tài)時(shí)，將該檢測(cè)工位的stationReVehicles隊(duì)列中，處于等待狀態(tài)的第一輛機(jī)動(dòng)車，調(diào)度到該工位進(jìn)行檢測(cè)。因?yàn)樵谌址秶鷥?nèi)為空閑工位調(diào)度機(jī)動(dòng)車，所以稱為全局空閑工位優(yōu)先。

3.3 算法流程與步驟

基于全局空閑工位優(yōu)先策略，實(shí)現(xiàn)機(jī)動(dòng)車檢測(cè)的調(diào)度算法稱為基于全局空閑工位優(yōu)先的機(jī)動(dòng)車檢測(cè)調(diào)度算法(vehicle scheduling algorithm for testing based on global idle station priority，VSABOSP)。由1.2小節(jié)(2)、(3)，將檢測(cè)車間的狀態(tài)與該車間首個(gè)檢測(cè)工位的狀態(tài)保持一致。結(jié)合上述設(shè)定，將VSABOSP各車間具體流程闡述如下：

步驟1 根據(jù)Vn輛機(jī)動(dòng)車的申請(qǐng)時(shí)間，為每一個(gè)檢測(cè)工位構(gòu)建stationReVehicles隊(duì)列；

步驟2 在滿足1.2節(jié)約束條件的前提下，基于全局空閑工位優(yōu)先策略，為各檢測(cè)車間調(diào)度機(jī)動(dòng)車。各檢測(cè)車間各檢測(cè)工位并行執(zhí)行檢測(cè)任務(wù)；

步驟3 當(dāng)檢測(cè)車間首個(gè)檢測(cè)工位完成檢測(cè)任務(wù)后，將該檢測(cè)工位設(shè)置為空閑狀態(tài)。然后，同時(shí)執(zhí)行步驟2和步驟4；

步驟4 基于FIFO算法完成機(jī)動(dòng)車在該檢測(cè)車間剩余工位的檢測(cè)任務(wù)；

步驟5 從檢測(cè)工位的stationReVehicles隊(duì)列中刪除已完成該工位檢測(cè)任務(wù)的機(jī)動(dòng)車；

步驟6 如果機(jī)動(dòng)車已經(jīng)完成所有檢測(cè)任務(wù)，則駛離檢測(cè)車間，等候打印報(bào)告單；否則，將該機(jī)動(dòng)車設(shè)置為等待狀態(tài)。

VSABOSP中每個(gè)檢測(cè)車間并行執(zhí)行，并且執(zhí)行流程類似，如圖1所示。

圖1 VSABOS檢測(cè)車間流程

3.4 算法復(fù)雜性分析

機(jī)動(dòng)車數(shù)量作為算法的輸入規(guī)模，采用基本操作計(jì)數(shù)法對(duì)算法的復(fù)雜度進(jìn)行分析。由3.3節(jié)可知，從空閑工位的stationReVehicles隊(duì)列中為其選取首輛處于等待狀態(tài)的機(jī)動(dòng)車，是本算法的基本操作。對(duì)于空間復(fù)雜度，以機(jī)動(dòng)車信息作為基本計(jì)數(shù)單元。

3.4.1 時(shí)間復(fù)雜度

通過(guò)分析VSABOSP調(diào)度過(guò)程，空閑工位選取機(jī)動(dòng)車的次數(shù)與在該檢測(cè)工位申請(qǐng)檢測(cè)的機(jī)動(dòng)車數(shù)量成正比關(guān)系。因此，當(dāng)算法輸入的規(guī)模為n時(shí)，算法的時(shí)間復(fù)雜度為

T(n)=O(f(n))=O(n)

(1)

3.4.2 空間復(fù)雜度

在VSABOSP調(diào)度過(guò)程中，每個(gè)檢測(cè)工位的stationReVehicles隊(duì)列中均維護(hù)在該工位有檢測(cè)任務(wù)的機(jī)動(dòng)車信息。因此，對(duì)于n輛機(jī)動(dòng)車在m個(gè)檢測(cè)工位進(jìn)行檢測(cè)的情況，算法的空間復(fù)雜度為

S(n)=O(f(n,m))=O(n*m)

(2)

3.5 算法高效性證明

采用數(shù)學(xué)歸納法對(duì)VSABOSP的高效性進(jìn)行證明。由1.2小節(jié)和3.3小節(jié)可知，檢測(cè)車間狀態(tài)與該車間首個(gè)檢測(cè)工位狀態(tài)一致；車間完成檢測(cè)的時(shí)刻與該車間最后一個(gè)檢測(cè)工位完成檢測(cè)的時(shí)刻一致。

在下面證明之前，結(jié)合工業(yè)實(shí)際，作如下假設(shè)：

假設(shè)1：算法在3個(gè)檢測(cè)車間內(nèi)調(diào)度，檢測(cè)車間分別為車間a、車間b、車間c。車間a、b、c僅表示車間代號(hào)，無(wú)實(shí)際意義。

假設(shè)2：申請(qǐng)檢測(cè)的機(jī)動(dòng)車數(shù)量為Vn。其中Vn為整數(shù)，取值范圍：Vn∈[1,+∞]。

假設(shè)3：FIFO按照車間a、車間b、車間c的順序調(diào)度。

(1)當(dāng)Vn=1時(shí):此時(shí)，只有一輛機(jī)動(dòng)車，由假設(shè)1可得:任何檢測(cè)順序都是等價(jià)的。因此，以車間a、b、c的順序進(jìn)行檢測(cè)。檢測(cè)調(diào)度Gantt圖，如圖2所示。

圖2 Vn等于1

此時(shí)，VSABOSP和FIFO的調(diào)度耗時(shí)，均為任務(wù)1、任務(wù)2、任務(wù)3三者檢測(cè)耗時(shí)之和。即VSABOSP調(diào)度時(shí)間不會(huì)大于FIFO。

(2)假設(shè)當(dāng)Vn=n-1時(shí)，VSABOSP比基于FIFO的檢測(cè)調(diào)度算法高效。

用集合 {0,1,2} 中的元素組合表示車間a、b、c在完成自身車間最后一輛機(jī)動(dòng)車檢測(cè)任務(wù)的時(shí)刻先后順序。每個(gè)車間可以取集合 {0,1,2} 中的任意值。例如：組合為 (2,0,1)， 則表明車間b首先完成檢測(cè)任務(wù)，然后車間c完成檢測(cè)任務(wù)，最后車間a完成檢測(cè)任務(wù)。

無(wú)論采用VSABOSP，還是FIFO，當(dāng)完成n-1輛機(jī)動(dòng)車的檢測(cè)調(diào)度任務(wù)后，各檢測(cè)車間的完成時(shí)刻組合，見(jiàn)表1。

表1 車間完成檢測(cè)時(shí)刻組合

(3)當(dāng)Vn=n時(shí):將當(dāng)完成n-1輛機(jī)動(dòng)車的檢測(cè)任務(wù)時(shí)，F(xiàn)IFO在車間a、b、c的完成時(shí)刻分別記為：TFa(n-1)、TFb(n-1)、TFc(n-1)； VSABOSP在車間a、b、c的完成時(shí)刻分別記為：TSa(n-1)、TSb(n-1)、TSc(n-1)。 第n輛機(jī)動(dòng)車在車間a、b、c的檢測(cè)耗時(shí)為T(mén)a、Tb、Tc。

由假設(shè)3可知，對(duì)于FIFO，車間a的首個(gè)檢測(cè)工位是整個(gè)算法的起始工位。根據(jù)3.3節(jié)步驟3可知，存在“車間a的首個(gè)檢測(cè)工位已經(jīng)完成某輛機(jī)動(dòng)車的檢測(cè)任務(wù)，但是該檢測(cè)工位空轉(zhuǎn)，等待下一個(gè)工位空閑”的情況。這樣必然導(dǎo)致車間a完成n-1輛機(jī)動(dòng)車的檢測(cè)時(shí)刻延后，即車間a的完成時(shí)間加長(zhǎng)。所以，當(dāng)完成n-1輛機(jī)動(dòng)車的檢測(cè)任務(wù)時(shí)，TFa(n-1)與TSa(n-1)之間滿足如下不等式

TFa(n-1)≥TSa(n-1)

(3)

同理

TFb(n-1)≥TSb(n-1)

(4)

TFc(n-1)≥TSc(n-1)

(5)

結(jié)合表1和式(3)～式(5)可得到：當(dāng)完成n-1輛機(jī)動(dòng)車的檢測(cè)任務(wù)時(shí)，如果VSABOSP各車間的完成時(shí)刻為表1中的 (x,y,z)， 則FIFO各車間的完成時(shí)刻為在表1中的可能取值為 (x,y,z) 及其同一行右側(cè)和同一列下方包圍區(qū)域的所有組合。例如：VSABOSP各車間的完成時(shí)刻組合為 (0,0,0)， 則FIFO可以取表1中的任意情況。

VSABOSP完成第n輛機(jī)動(dòng)車的結(jié)束時(shí)刻為

TS(n)=min{TSa(n-1),TSb(n-1),TSc(n-1)}+Ta+Tb+Tc

(6)

FIFO完成第n輛機(jī)動(dòng)車的結(jié)束時(shí)刻為

TF(n)=TFa(n-1)+Ta+Tb+Tc

(7)

分情況討論式(6)、式(7)的大小關(guān)系：

情況1：TSa(n-1)≥TSb(n-1)或者TSa(n-1)≥TSc(n-1)。

結(jié)合式(3)可得TS(n)與TF(n)的關(guān)系

TS(n)≤TSa(n-1)+Ta+Tb+Tc≤TFa(n-1)+Ta+Tb+Tc=TF(n)

(8)

情況2：TSa(n-1)

結(jié)合式(3)可得TS(n)與TF(n)的關(guān)系

TS(n)=TSa(n-1)+Ta+Tb+Tc≤TFa(n-1)+Ta+Tb+Tc=TF(n)

(9)

對(duì)比式(8)和式(9)可得：最壞情況下，VSABOSP與FIFO調(diào)度效率一樣，其它情況下VSABOSP會(huì)表現(xiàn)的更高效。

4 仿真實(shí)驗(yàn)

對(duì)Vn輛機(jī)動(dòng)車的檢測(cè)任務(wù)，分別采用FIFO和VSABOSP進(jìn)行模擬實(shí)驗(yàn)仿真，其中Vn的取值范圍為：Vn={5,10,20,30,40,50,60,70,80,90,100}。 實(shí)驗(yàn)環(huán)境為Windows 10 專業(yè)版64 位操作系統(tǒng)，Intel?CoreTMi7-6800K CPU @ 3.40 GHz 處理器，16 GB RAM。使用JDK1.8.0_171編碼實(shí)現(xiàn)。

4.1 VSABOSP偽代碼

VSABOSP調(diào)度偽代碼由VSABOSP主算法、testing子算法、findVehicleForWorkshop子算法3部分組成。其中，VSABOSP主算法用于協(xié)調(diào)各子算法之間的調(diào)度關(guān)系，控制程序起止；testing子算法模擬檢測(cè)車間檢測(cè)機(jī)動(dòng)車；findVehicleForWorkshop子算法用于在滿足1.2節(jié)約束條件的前提下，為各檢測(cè)車間調(diào)度機(jī)動(dòng)車。為了更好闡述算法流程，將調(diào)度過(guò)程中涉及到的對(duì)象進(jìn)行定義。

4.1.1 對(duì)象定義

檢測(cè)項(xiàng)目對(duì)象，定義如下：

Class Item {

String name; // 檢測(cè)項(xiàng)目名稱

int time; // 檢測(cè)耗時(shí) }

檢測(cè)工位對(duì)象，定義如下：

Class Station {

int currTime; // 最后一輛機(jī)動(dòng)車完成檢測(cè)的時(shí)刻

boolean idle; // true： 空閑狀態(tài) (默認(rèn))； false： 繁忙狀態(tài)

List items; // 可檢項(xiàng)目列表

Vehicle veh; // 在該工位正在檢測(cè)的機(jī)動(dòng)車 }

機(jī)動(dòng)車對(duì)象，定義如下：

Class Vehicle {

int currTime; // 上一個(gè)項(xiàng)目檢測(cè)完畢時(shí)刻

boolean wait; // true： 等待狀態(tài) (默認(rèn))； false： 檢測(cè)狀態(tài)

boolean finish; // true： 完成檢測(cè)； false： 未完成檢測(cè) (默認(rèn))

Map> itemMap; // 檢測(cè)項(xiàng)目與工位映射關(guān)系 }

檢測(cè)車間對(duì)象，定義如下：

Class Workshop {

List stations; // 車間包含的檢測(cè)工位列表

boolean idle; // true：空閑狀態(tài) (默認(rèn))； false： 繁忙狀 }

4.1.2 VSABOSP主算法

在機(jī)動(dòng)車檢測(cè)調(diào)度過(guò)程中，建立3個(gè)用于輔助程序調(diào)度的緩存隊(duì)列：

等待隊(duì)列：保存完成項(xiàng)目申請(qǐng)之后，開(kāi)始檢測(cè)之前的機(jī)動(dòng)車集合。隊(duì)列中，機(jī)動(dòng)車按照項(xiàng)目申請(qǐng)完成時(shí)刻的先后順序排列。簡(jiǎn)記為：waitQueue。

一級(jí)緩存：保存正在檢測(cè)工位檢測(cè)的機(jī)動(dòng)車集合。隊(duì)列中，機(jī)動(dòng)車按照進(jìn)入當(dāng)前正在檢測(cè)工位時(shí)刻的先后順序排列。簡(jiǎn)記為：cache1。

二級(jí)緩存：保存一級(jí)緩存中完成檢測(cè)任務(wù)，處于等待狀態(tài)的機(jī)動(dòng)車集合。隊(duì)列中，機(jī)動(dòng)車按照完成上一個(gè)檢測(cè)任務(wù)的先后順序排列。簡(jiǎn)記為：cache2。

VSABOSP主算法偽代碼，如下所示：

VSABOSP主算法：

輸入：waitQueue 等待隊(duì)列， wsList 檢測(cè)車間列表

(1)functionmain (waitQueue, wsList)

(2)cache1和cache2初始化為空

(3)while存在未檢測(cè)完畢的機(jī)動(dòng)車do

(4) 清除cache1中狀態(tài)為finish的所有機(jī)動(dòng)車

(5)foreachworkshop ∈ wsListdo

(6) 調(diào)用findVehicleForWorkshop子算法

(7) 調(diào)用testing子算法

(8)endfor

(9)endwhile

(10)endfunction

4.1.3 testing子算法

testing子算法：

輸入：workshop檢測(cè)車間

(1)functiontesting (workshop)

(2) vehicle ← 在車間首個(gè)工位檢測(cè)的機(jī)動(dòng)車

(3)ifvehicle != nullthen

(4)foreachstation∈ workshop.stationsdo

(5) items ← 獲取vehicle在station工位的檢測(cè)項(xiàng)目

(6)foreachitem∈ itemsdo// 模擬檢測(cè)機(jī)動(dòng)車的每個(gè)檢測(cè)項(xiàng)目

(7) 更新station和vehicle的當(dāng)前時(shí)間.curr-Time

(8)endfor

(9)ifvehicle完成所有檢測(cè)任務(wù)then

(10) vehicle.finish ← true

(11)else

(12) vehicle.wait ← true

(13) 將vehicle添加到cache2

(14)endif

(15) 更新車間狀態(tài)

(16) 工位狀態(tài)更新為空閑

(17)endfor

(18)endif

(19)endfunction

4.1.4 findVehicleForWorkshop子算法

為檢測(cè)車間調(diào)度機(jī)動(dòng)車時(shí)，除了滿足1.2節(jié)的約束條件，機(jī)動(dòng)車還需要滿足兩個(gè)點(diǎn)要求：①機(jī)動(dòng)車在檢測(cè)車間有檢測(cè)項(xiàng)目；②機(jī)動(dòng)車處于等待狀態(tài)。將滿足上述要求的機(jī)動(dòng)車記為：滿足要求的機(jī)動(dòng)車。由3.5節(jié)可知，檢測(cè)車間的狀態(tài)與該車間首個(gè)檢測(cè)工位的狀態(tài)保持一致。

在滿足1.2節(jié)的約束條件下，實(shí)現(xiàn)VSABOSP，將機(jī)動(dòng)車被調(diào)度的優(yōu)先級(jí)[10]由高到低設(shè)置為：

cache1>cache2>waitQueue

findVehicleForWorkshop子算法偽代碼，如下所示：

findVehicleForWorkshop子算法：

輸入：workshop車間,cache1一級(jí)緩存, cache2二級(jí)緩存, waitQ等待隊(duì)列

(1)functionfindVehicleForWorkshop(workshop, cache1, cache2, waitQ)

(2)while車間空閑do

(3) vehicle ← 從cache1選取滿足要求的機(jī)動(dòng)車

(4)ifvehicle存在then

(5) 將機(jī)動(dòng)車調(diào)度到車間第一工位準(zhǔn)備檢測(cè)

(6) 更新車間、工位、機(jī)動(dòng)車的檢測(cè)狀態(tài)

(7)return

(8)else

(9)ifcache2中存在滿足條件的機(jī)動(dòng)車then

(10) 將cache2中滿足要求的機(jī)動(dòng)車，添加到cache1

(11)continue

(12)else

(13)ifwaitQ中存在滿足條件的機(jī)動(dòng)車then

(14) 將waitQ中滿足要求的機(jī)動(dòng)車，添加到cache1

(15)continue

(16)else

(17)return

(18)endif

(19)endif

(20)endif

(21)endwhile

(22)endfunction

4.2 實(shí)驗(yàn)數(shù)據(jù)

參考國(guó)家在機(jī)動(dòng)車檢測(cè)領(lǐng)域的政策法規(guī)[11-14]，機(jī)動(dòng)車檢測(cè)主要分為3種檢測(cè)線：安全性能檢測(cè)線(以下簡(jiǎn)稱：安檢)、綜合性能檢測(cè)線(以下簡(jiǎn)稱：綜檢)、環(huán)保尾氣檢測(cè)線(以下簡(jiǎn)稱：環(huán)檢)。通過(guò)政策解讀發(fā)現(xiàn)：綜檢與安檢，綜檢與環(huán)檢的項(xiàng)目之間發(fā)生重合，例如：尾氣檢測(cè)既要在綜檢進(jìn)行檢測(cè)，又要在環(huán)檢進(jìn)行檢測(cè)。抽取安檢、綜檢、環(huán)檢的公共檢測(cè)項(xiàng)目，對(duì)比政策規(guī)定的項(xiàng)目檢測(cè)最短時(shí)間與項(xiàng)目在工業(yè)實(shí)踐中的檢測(cè)耗時(shí)，將檢測(cè)項(xiàng)目與檢測(cè)耗時(shí)進(jìn)行總結(jié)，見(jiàn)表2。

表2 檢測(cè)項(xiàng)目檢測(cè)耗時(shí)/min

4.3 實(shí)例分析

為了提高算法實(shí)用性，結(jié)合榆林、商洛、咸陽(yáng)機(jī)動(dòng)車檢測(cè)站的布局，采用3個(gè)車間模擬，即環(huán)檢車間、安檢車間、綜檢車間。其中環(huán)檢車間負(fù)責(zé)：尾氣檢測(cè)；安檢車間依次負(fù)責(zé)：外廓尺寸、制動(dòng)、前照燈、轉(zhuǎn)向輪橫向側(cè)滑量的檢測(cè)；綜檢車間依次負(fù)責(zé)：燃料消耗量、車速表誤差、動(dòng)力性、聲級(jí)的檢測(cè)。

對(duì)5輛機(jī)動(dòng)車，針對(duì)表2中的檢測(cè)項(xiàng)目，分別使用VSABOSP和FIFO進(jìn)行調(diào)度。分別得到5輛機(jī)動(dòng)車在各車間的調(diào)度過(guò)程，如圖3、圖4所示。

圖3 FIFO算法

圖4 VSABOSP

在VSABOSP調(diào)度過(guò)程中，機(jī)動(dòng)車在檢測(cè)工位、waitQueue隊(duì)列、cache1隊(duì)列和cache2隊(duì)列中的變化情況，見(jiàn)表3。

4.4 仿真分析

首先，為Vn輛機(jī)動(dòng)車申請(qǐng)表2中的所有檢測(cè)項(xiàng)目，得到Vn輛機(jī)動(dòng)車的檢測(cè)任務(wù)，其中Vn={5,10,20,30,40,50,60,70,80,90}。 然后，將Vn輛機(jī)動(dòng)車分別采用VSABO-SP 和FIFO進(jìn)行調(diào)度，得到檢測(cè)調(diào)度信息。最后，對(duì)檢測(cè)調(diào)度信息進(jìn)行對(duì)比分析，得到算法性能優(yōu)劣對(duì)比相關(guān)圖表，如表4、圖5～圖8所示。

其中，理論耗時(shí)指：Vn輛機(jī)動(dòng)車?yán)碚撋系臋z測(cè)耗時(shí)之和，即每輛機(jī)動(dòng)車的檢測(cè)耗時(shí)通過(guò)表2中項(xiàng)目檢測(cè)耗時(shí)求和得到。調(diào)度結(jié)束時(shí)間指：從開(kāi)始檢測(cè)到完成Vn輛機(jī)動(dòng)車檢測(cè)調(diào)度任務(wù)之間的時(shí)間?？辙D(zhuǎn)時(shí)間指：檢測(cè)過(guò)程中所有工位空轉(zhuǎn)時(shí)間之和。平均調(diào)度時(shí)間指：在完成Vn輛機(jī)動(dòng)車的檢測(cè)調(diào)度任務(wù)后，所有車間結(jié)束檢測(cè)時(shí)間之和與Vn之間的比值。利用率指：在完成Vn輛機(jī)動(dòng)車的檢測(cè)調(diào)度任務(wù)后，Vn輛機(jī)動(dòng)車的理論耗時(shí)與所有檢測(cè)工位運(yùn)行時(shí)間總和之間的比值。

由表4可知，檢測(cè)調(diào)度結(jié)束時(shí)間比理論耗時(shí)短，結(jié)合圖3和圖4，分析可得：同一時(shí)刻，有多輛機(jī)動(dòng)車在多個(gè)檢測(cè)工位上并發(fā)進(jìn)行檢測(cè)。相比于FIFO，VSABOSP將串行化轉(zhuǎn)化為并行化執(zhí)行。根據(jù)文獻(xiàn)[15-17]的研究，并行化方法的效率要優(yōu)于線性化方法，因此 VSABOSP的性能要高于FIFO。

表3 實(shí)例調(diào)度時(shí)刻/min

表4 算法仿真性能對(duì)比/min

為了更直觀的對(duì)比VSABOSP和FIFO的性能差異，將表4數(shù)據(jù)繪制成圖。圖5是調(diào)度完成時(shí)刻對(duì)比圖，圖6是平均調(diào)度時(shí)間對(duì)比圖，圖7是檢測(cè)工位總空閑時(shí)間對(duì)比圖，圖8是資源利用率對(duì)比圖。

如圖5所示，在相同調(diào)度任務(wù)的前提下，VSABOSP比FIFO調(diào)度完成時(shí)間更短。從側(cè)面說(shuō)明，在相同條件下，采用VSABOSP，檢測(cè)機(jī)構(gòu)每天可以完成更多機(jī)動(dòng)車的檢測(cè)任務(wù)，能夠提升檢測(cè)機(jī)構(gòu)的檢測(cè)能力。

圖5 調(diào)度完成時(shí)刻對(duì)比

圖6 平均調(diào)度時(shí)間對(duì)比

如圖6所示，在相同調(diào)度任務(wù)的前提下，VSABOSP的平均調(diào)度時(shí)間遠(yuǎn)低于FIFO。表明，在相同條件下，VSABO-SP的檢測(cè)效率更高，相同時(shí)間內(nèi)，可以完成更多機(jī)動(dòng)車的檢測(cè)調(diào)度任務(wù)。

如圖7所示，在相同調(diào)度任務(wù)的前提下，VSABOSP的工位空轉(zhuǎn)時(shí)間遠(yuǎn)低于FIFO。表明，在相同條件下，采用 VSABOSP 檢測(cè)工位空轉(zhuǎn)時(shí)間更短，檢測(cè)設(shè)備的利用率更高。

圖7 工位空閑時(shí)間對(duì)比

圖8 資源利用率對(duì)比

如圖8所示，在相同調(diào)度任務(wù)的前提下，VSABOSP的資源利用率遠(yuǎn)高于FIFO。表明，在相同條件下，采用 VSABOSP 檢測(cè)設(shè)備的資源利用率更高，減少了資源浪費(fèi)現(xiàn)象。

5 結(jié)束語(yǔ)

針對(duì)當(dāng)前機(jī)動(dòng)車檢測(cè)機(jī)構(gòu)檢測(cè)效率不高，車主等待時(shí)間過(guò)長(zhǎng)的問(wèn)題，基于全局工位優(yōu)先原則，提出了一種基于全局工位優(yōu)先的機(jī)動(dòng)車檢測(cè)調(diào)度算法(VSABOSP)，并對(duì)算法的時(shí)間復(fù)雜和空間復(fù)雜性進(jìn)行了分析。然后，采用數(shù)學(xué)歸納法驗(yàn)證VSABOSP算法在最差情況下性能與FIFO一致，其余情況下要優(yōu)于FIFO。最后，分別采用實(shí)例分析和仿真實(shí)驗(yàn)的方式對(duì)算法性能做進(jìn)一步分析對(duì)比。

研究結(jié)果表明，相比于FIFO，VSABOSP，調(diào)度效率至少提升45%、工位空閑時(shí)間降低50%，資源利用率提升一倍，為機(jī)動(dòng)車檢測(cè)行業(yè)提供了調(diào)度優(yōu)化方案。

在下一階段，將對(duì)多檢測(cè)車間多檢測(cè)線情況下的機(jī)動(dòng)車檢測(cè)調(diào)度進(jìn)行優(yōu)化探索。