面向遠(yuǎn)程實(shí)驗(yàn)設(shè)備的最優(yōu)資源調(diào)度方法

孫 博 俞武嘉 劉光宇

(杭州電子科技大學(xué)自動(dòng)化學(xué)院 浙江 杭州 310018)

0 引 言

隨著數(shù)字孿生技術(shù)與高校實(shí)驗(yàn)室資源的結(jié)合，遠(yuǎn)程共享使用實(shí)驗(yàn)設(shè)備有了新的發(fā)展思路。實(shí)驗(yàn)教學(xué)作為課堂理論知識(shí)的具體化、實(shí)踐化，是高校教學(xué)環(huán)境中的重要一環(huán)，實(shí)驗(yàn)課程的合理安排，關(guān)系到實(shí)驗(yàn)室日常工作的順利進(jìn)行[1]。因此，如何合理地分配有限實(shí)驗(yàn)設(shè)備資源并給出最優(yōu)排課方案成為了新的問題。

目前，實(shí)驗(yàn)室設(shè)備的調(diào)度研究大多聚焦于實(shí)驗(yàn)室本身的設(shè)備預(yù)約和管理[2-3]，或者是實(shí)驗(yàn)課程排課和實(shí)驗(yàn)室用戶之間的關(guān)系[4]，缺乏考慮實(shí)驗(yàn)室的設(shè)備資源調(diào)度與高校的實(shí)驗(yàn)課程排課之間的協(xié)調(diào)問題。鑒于此，本文結(jié)合高校實(shí)驗(yàn)課的排課問題，對(duì)高校實(shí)驗(yàn)室的遠(yuǎn)程實(shí)驗(yàn)設(shè)備調(diào)度進(jìn)行研究。使用改進(jìn)的遺傳算法，將實(shí)驗(yàn)課程、實(shí)驗(yàn)設(shè)備、實(shí)驗(yàn)用戶與實(shí)驗(yàn)時(shí)間相匹配，給出合理的實(shí)驗(yàn)課排布與設(shè)備調(diào)度方案，從而實(shí)現(xiàn)充分利用實(shí)驗(yàn)室資源，提高實(shí)驗(yàn)設(shè)備的使用率。

1 問題描述與假設(shè)

在現(xiàn)實(shí)生活中，通常有一類存在能力限制的服務(wù)系統(tǒng)S，其限制主要體現(xiàn)在系統(tǒng)擁有的資源R有限；需求發(fā)生后，可能由于資源的短缺而需要等待服務(wù)，加之需求的特殊性，只有在合適的時(shí)間段或者地點(diǎn)才能被服務(wù)；需求被滿足后離開系統(tǒng)，釋放所占用資源。

上述情景延伸到高校的實(shí)驗(yàn)課教學(xué)中，將多設(shè)備信息技術(shù)實(shí)驗(yàn)室看作一個(gè)服務(wù)系統(tǒng)，實(shí)驗(yàn)室的實(shí)驗(yàn)設(shè)備是有限的。通常學(xué)生以班級(jí)為單位在特定的時(shí)間做同一個(gè)實(shí)驗(yàn)，每個(gè)班級(jí)的任務(wù)申請(qǐng)為一個(gè)隊(duì)列。學(xué)生在實(shí)驗(yàn)課開始后發(fā)出實(shí)驗(yàn)任務(wù)申請(qǐng)，然后實(shí)驗(yàn)設(shè)備開始工作。某些時(shí)候不同班級(jí)的學(xué)生在同一時(shí)刻進(jìn)行實(shí)驗(yàn)課，但實(shí)驗(yàn)課程的內(nèi)容是不一定相同的，實(shí)驗(yàn)設(shè)備服務(wù)不同實(shí)驗(yàn)課程的能力也是不同的，遠(yuǎn)程實(shí)驗(yàn)設(shè)備調(diào)度示意圖如圖1所示。如果設(shè)備的分配不合理，會(huì)延遲需求量較高學(xué)生的設(shè)備資源供應(yīng)，降低實(shí)驗(yàn)課效果；分配過量的設(shè)備資源，會(huì)造成設(shè)備資源的利用率低。實(shí)驗(yàn)課結(jié)束后，設(shè)備資源被釋放。

圖1 遠(yuǎn)程實(shí)驗(yàn)設(shè)備調(diào)度示意圖

從以上的描述中可以看出,通過先來先服務(wù)的規(guī)則無法保證實(shí)驗(yàn)課的設(shè)備使用效率最大化。因此,本文的目標(biāo)是尋求使實(shí)驗(yàn)室遠(yuǎn)程實(shí)驗(yàn)設(shè)備效率最大化的設(shè)備調(diào)度和排課方法。為系統(tǒng)地分析和評(píng)價(jià)調(diào)度安排，本文提出兩個(gè)假設(shè)：(1) 實(shí)驗(yàn)產(chǎn)生的服務(wù)申請(qǐng)不會(huì)消失；(2) 服務(wù)申請(qǐng)的到達(dá)服從泊松分布。在滿足這些假設(shè)后，方能構(gòu)建相應(yīng)的調(diào)度模型，并設(shè)計(jì)遺傳算法尋優(yōu)。

2 最優(yōu)化調(diào)度模型

通過多設(shè)備實(shí)驗(yàn)室調(diào)度與生產(chǎn)調(diào)度的比較，采用生產(chǎn)線調(diào)度中常用的三元問題描述方法(α,β,γ)來描述多設(shè)備實(shí)驗(yàn)課程的調(diào)度問題以及最優(yōu)化模型[5]。實(shí)驗(yàn)室的儀器設(shè)備資源是有限的，在進(jìn)行實(shí)驗(yàn)課安排前除了要考慮人為因素, 還要考慮設(shè)備資源的約束[6]。假設(shè)班級(jí)c在實(shí)驗(yàn)i中需要調(diào)用m類設(shè)備n臺(tái)，多個(gè)時(shí)間條件已經(jīng)給定，例如：實(shí)驗(yàn)開始時(shí)間ri、實(shí)驗(yàn)處理時(shí)間pi，以及實(shí)驗(yàn)截止時(shí)間di。

采用α描述設(shè)備環(huán)境：在實(shí)驗(yàn)過程中，學(xué)生s需要調(diào)用m類每類n臺(tái)設(shè)備，所以存在流水車間調(diào)度問題；在只有1個(gè)班級(jí)實(shí)驗(yàn)的情況下，存在并行同性能機(jī)器調(diào)度問題處理；在多個(gè)班級(jí)同時(shí)實(shí)驗(yàn)的情況下，存在并行不同性能機(jī)器調(diào)度問題。綜上所述，采用柔性車間作業(yè)調(diào)度問題將零散的調(diào)度問題進(jìn)行統(tǒng)一處理。

采用β描述實(shí)驗(yàn)過程的約束：使用Mi設(shè)備作為任務(wù)分配的約束，集合Mi表示實(shí)驗(yàn)i的可選設(shè)備集合，集合Mi不出現(xiàn)，表示實(shí)驗(yàn)i可以在任何設(shè)備上進(jìn)行實(shí)驗(yàn)；使用優(yōu)先(偏序)約束作為流水約束，學(xué)生s必須等待設(shè)備釋放，才能繼續(xù)實(shí)驗(yàn)。

采用γ描述實(shí)驗(yàn)教學(xué)安排的目標(biāo)：面向?qū)嶒?yàn)過程中的設(shè)備資源的調(diào)用，需要保證不同規(guī)格的實(shí)驗(yàn)設(shè)備根據(jù)實(shí)驗(yàn)任務(wù)分配合理化，將此優(yōu)化目標(biāo)定位為負(fù)載均衡最優(yōu)調(diào)度問題。在Mi等約束條件下，使用Wj表示單個(gè)設(shè)備的負(fù)載率，采用min max最優(yōu)化模型來描述：

min max{1-Wj}

(1)

面向?qū)嶒?yàn)課在日常教學(xué)中的分配，需要保證班級(jí)、課程、實(shí)驗(yàn)時(shí)間，以及根據(jù)實(shí)驗(yàn)類別調(diào)用的實(shí)驗(yàn)設(shè)備等元素不發(fā)生沖突，以時(shí)間ti表示各個(gè)日常教學(xué)中的必要時(shí)間，給出時(shí)間排序的數(shù)學(xué)問題：

sequence{t1,t2,t3}

(2)

此外，需要對(duì)所有實(shí)驗(yàn)設(shè)備總使用時(shí)間進(jìn)行優(yōu)化，以提高設(shè)備的利用率：

min{∑Li}

(3)

式中：Li表示單個(gè)設(shè)備的使用時(shí)間。因此，本項(xiàng)目的多個(gè)調(diào)度問題可以歸納為多目標(biāo)優(yōu)化NP-Hard問題。

3 基于遺傳算法的調(diào)度安排優(yōu)化

根據(jù)上述的調(diào)度問題描述以及假設(shè)，本文采用遺傳算法對(duì)實(shí)驗(yàn)課程的資源調(diào)度進(jìn)行優(yōu)化。其中包含遠(yuǎn)程實(shí)驗(yàn)設(shè)備和實(shí)驗(yàn)用戶的分配，以及高校的日常教學(xué)中實(shí)驗(yàn)課的合理安排。使用下列集合表示這些調(diào)度所需因素：

設(shè)備集合：S={S1,S2,…,Sn}，在某一個(gè)實(shí)驗(yàn)課程內(nèi)，需要N臺(tái)設(shè)備，N≥1。

任務(wù)集合：T={T1,T2,…,Tn}，每臺(tái)客戶端發(fā)送的服務(wù)申請(qǐng)為一個(gè)任務(wù)Ti。

實(shí)驗(yàn)集合：E={E1,E2,…,En}。

班級(jí)集合：C={C1,C2,…,Cn}。

專業(yè)集合：M={M1,M2,…,Mn}。

課程段集合：P={P1,P2,…,Pn}，Ti表示課程段，例如T1為周一的1～2節(jié)課，T2為周一的3～5節(jié)課。

時(shí)間段集合：W={W1,W2,…,Wn}，Wi表示星期數(shù)，例如W1為第一周，W2為第二周。

3.1 編碼規(guī)則

要實(shí)施遺傳算法，第一步就是對(duì)需要解決的問題進(jìn)行基因編碼。在本系統(tǒng)中，每種基因段采用二進(jìn)制編碼，例如時(shí)間段一共是16個(gè)，代表16個(gè)星期，Wi(i=1,2,…,16)為16個(gè)變量。Wi=1表示在第i周有實(shí)驗(yàn)課，Wi=0表示第i周沒有實(shí)驗(yàn)課。根據(jù)以上分析，染色體結(jié)構(gòu)如圖2所示。

圖2 染色體結(jié)構(gòu)示意圖

3.2 適應(yīng)度函數(shù)設(shè)計(jì)

在遺傳算法中，遺傳的方向需要適應(yīng)度來決定，適應(yīng)度表示整個(gè)實(shí)驗(yàn)課程調(diào)度的優(yōu)秀程度。相對(duì)于常見的基于遺傳算法的排課算法中的適應(yīng)度函數(shù)設(shè)計(jì)[7-8]，在實(shí)驗(yàn)課程的排課中需要關(guān)注設(shè)備調(diào)度和排課兩個(gè)部分。因此，在本文適應(yīng)度函數(shù)的設(shè)計(jì)中，適應(yīng)度的期望由兩個(gè)部分組成：實(shí)驗(yàn)設(shè)備調(diào)度和實(shí)驗(yàn)課程安排。

(1) 實(shí)驗(yàn)設(shè)備調(diào)度。由上述的調(diào)度分析，在一個(gè)實(shí)驗(yàn)課期間，用戶提交任務(wù)的過程是相互獨(dú)立的泊松過程，設(shè)備處理任務(wù)的過程仍然是泊松過程。那么可以將實(shí)驗(yàn)設(shè)備的調(diào)度抽象成一個(gè)M/M/n模型。根據(jù)Little公式，系統(tǒng)中平均顧客數(shù)量(在上述模型中是客戶端發(fā)起任務(wù)的數(shù)量)E(L)與平均逗留時(shí)間(在上述模型中是設(shè)備的使用時(shí)間)E(S)和到達(dá)速率λ之間的關(guān)系為：

E(L)=λE(S)

(4)

對(duì)于M/M/n隊(duì)列，通過求解生滅過程的穩(wěn)定概率和應(yīng)用Little公式，可以得到：

(5)

式中：K是泊松比率函數(shù)；n是服務(wù)器(上述模型中設(shè)備的數(shù)量)數(shù)量；μ是平均服務(wù)速率；ρ是設(shè)備利用率，并且：

(6)

通過式(5)和式(6)計(jì)算任務(wù)平均使用時(shí)間和設(shè)備利用率。對(duì)于線上資源調(diào)度合理程度的期望函數(shù)公式為：

FUL=t1·E(S)+t2·ρ

(7)

式中：t1和t2用于調(diào)控任務(wù)平均響應(yīng)時(shí)間和設(shè)備資源利用率對(duì)線上資源調(diào)度合理程度的影響。

(2) 實(shí)驗(yàn)課程安排。實(shí)驗(yàn)課程安排的合理程度可由兩個(gè)部分組成：

① 實(shí)驗(yàn)課程特征規(guī)律。學(xué)生邏輯思維活躍的時(shí)間段一般在早晨，所以早晨適宜安排理論課程，而且實(shí)驗(yàn)課通常需要更長(zhǎng)的時(shí)間。根據(jù)實(shí)驗(yàn)課程的特征規(guī)律，不同課程段的期望值不同，如表1所示。

表1 實(shí)驗(yàn)課程特征規(guī)律期望值

對(duì)于特征規(guī)律的期望函數(shù)公式為：

FET=∑FET(i)

(8)

② 教學(xué)規(guī)劃適宜度。在高校教學(xué)中，實(shí)驗(yàn)課的安排應(yīng)分布于學(xué)期中間。因?yàn)閷W(xué)期開始時(shí)，學(xué)生處于放假歸來的狀態(tài)，此時(shí)教學(xué)效果并不是很好；而在學(xué)期末和期中考試前，學(xué)生面臨考試周主要工作為復(fù)習(xí)應(yīng)對(duì)考試，此時(shí)的實(shí)驗(yàn)課效果也不理想。根據(jù)這樣的規(guī)律，實(shí)驗(yàn)時(shí)間安排的教學(xué)規(guī)劃適宜度也不同，如表2所示。

表2 教學(xué)規(guī)劃適宜度期望值

對(duì)于規(guī)劃適宜度的期望函數(shù)公式為：

FEP=∑FEP(i)

(9)

根據(jù)以上分析可以得出適應(yīng)度函數(shù)F：

(10)

式中：k1、k2和k3用于調(diào)控各期望值對(duì)總適應(yīng)度的影響。

3.3 算法步驟

遺傳算法的整體流程如圖3所示。它的主要流程通過遺傳算法程序產(chǎn)生Np組可行解，之后計(jì)算各個(gè)可行解的適應(yīng)度，通過交叉、變異產(chǎn)生新的可行解。如此迭代，直到達(dá)到預(yù)先設(shè)定的最大代數(shù)，退出程序，輸出最優(yōu)結(jié)果。

根據(jù)以上的算法思路，傳統(tǒng)遺傳算法步驟如下：

(1) 參數(shù)定義：設(shè)定遺傳算法中需要的種群數(shù)量、個(gè)體的染色體數(shù)量、染色體長(zhǎng)度、交叉概率、變異概率、最大繁殖代數(shù)等參數(shù)。

(2) 產(chǎn)生初始種群：生成Np個(gè)隨機(jī)向量，每個(gè)向量上的分量，根據(jù)一定的概率被賦值為0或1，得到一條染色體。按照個(gè)體染色體數(shù)量，將Nm個(gè)隨機(jī)向量設(shè)定為一個(gè)個(gè)體，種群中共Nt個(gè)個(gè)體，并計(jì)算每個(gè)個(gè)體的適應(yīng)度。

(3) 產(chǎn)生新的種群：通過輪盤賭選擇從父代種群中選擇兩個(gè)個(gè)體，通過直接遺傳、交叉和變異的方式產(chǎn)生兩個(gè)子代個(gè)體。計(jì)算新生子代適應(yīng)度，替換原先父代種群中適應(yīng)度較低的個(gè)體。如果滿足退出條件(達(dá)到最大繁殖代數(shù))，退出計(jì)算，輸出最優(yōu)解；否則，重復(fù)步驟3。

在傳統(tǒng)的遺傳算法中，是設(shè)定上一代的全部個(gè)體的基因進(jìn)行重組、交叉、變異得到下一代基因。但是因?yàn)閷?shí)際算法運(yùn)行中，兩代個(gè)體之間有著一個(gè)過渡期，在這個(gè)期間，兩代個(gè)體都存在，雖然避免了父代與子代間的基因傳遞變動(dòng)太大，但是會(huì)導(dǎo)致尋優(yōu)的“深度”不足。因此，在改進(jìn)的遺傳算法中，在父代與子代的種群融合前，只保留父代種群中一半適應(yīng)度較好的個(gè)體，另一半較差的直接刪除。這樣可以提高收斂速度，增加搜索深度。

根據(jù)以上描述，本文采用的改進(jìn)遺傳算法步驟如下：

(1) 參數(shù)定義：同傳統(tǒng)算法步驟1。

(2) 產(chǎn)生初始種群：同傳統(tǒng)算法步驟2。

(3) 產(chǎn)生新的種群：通過輪盤賭選擇從父代種群中選擇兩個(gè)個(gè)體，通過直接遺傳、交叉和變異的方式產(chǎn)生兩個(gè)子代個(gè)體。計(jì)算新生子代適應(yīng)度，替換原先父代種群中適應(yīng)度較低的個(gè)體。

(4) 刪除處理：對(duì)父代種群按照適應(yīng)度排序，保留較優(yōu)的一半父代個(gè)體。重復(fù)步驟3，直到滿足退出條件(達(dá)到最大繁殖代數(shù))，退出計(jì)算，輸出最優(yōu)解。

4 實(shí)驗(yàn)驗(yàn)證

在Visual Studio.net環(huán)境下用C#語言編寫整個(gè)調(diào)度算法的仿真實(shí)現(xiàn)。仿真中設(shè)定一共有5類設(shè)備，每類20臺(tái)，隨機(jī)生成15類實(shí)驗(yàn)課程，設(shè)備的服務(wù)能力如圖4所示。按照10個(gè)專業(yè)20個(gè)班級(jí)每個(gè)班級(jí)30名學(xué)生，每個(gè)專業(yè)隨機(jī)選擇10類實(shí)驗(yàn)進(jìn)行調(diào)度安排。

圖4 設(shè)備服務(wù)能力分布圖

在遺傳算法中設(shè)置生育率為0.8，基因變異率為0.08。分別使用未改進(jìn)算法和改進(jìn)算法迭代200次，得到5次出現(xiàn)最優(yōu)解的世代和最優(yōu)解的適應(yīng)度，求平均后如表3所示。

表3 遺傳算法結(jié)果

遺傳算法最優(yōu)解曲線如圖5所示，可以看出改進(jìn)后遺傳算法相對(duì)于原算法收斂速度明顯提高，染色體經(jīng)過迭代進(jìn)化后可以得到最優(yōu)解。按照班級(jí)分類設(shè)備使用情況可以看出，可以很好地調(diào)度設(shè)備的使用，如圖6所示。從調(diào)度結(jié)果中隨機(jī)調(diào)取兩個(gè)班級(jí)a和b，其實(shí)驗(yàn)設(shè)備需求如圖7所示(課程時(shí)間按照“時(shí)間段.課程段.實(shí)驗(yàn)類型”表示)。可以看出，在第十周第九節(jié)的時(shí)間點(diǎn)，兩個(gè)班級(jí)同時(shí)進(jìn)行實(shí)驗(yàn)課，分別是實(shí)驗(yàn)11和實(shí)驗(yàn)13，兩者所需求的設(shè)備資源不同，其中：設(shè)備1是a班著重需要的，b班沒有需求所以沒有進(jìn)行分配；設(shè)備5是b班所需設(shè)備，同樣的a班不需要該類設(shè)備，也沒有進(jìn)行分配，結(jié)果符合算法的預(yù)期。圖8為優(yōu)化前后設(shè)備使用率對(duì)比圖，可以看出，改進(jìn)遺傳算法的實(shí)驗(yàn)課程資源調(diào)度相對(duì)于傳統(tǒng)的先來先服務(wù)設(shè)備調(diào)度的方法，設(shè)備的使用率有著明顯的提升。

圖5 遺傳算法最優(yōu)解曲線圖

圖6 各班級(jí)按時(shí)間段所需設(shè)備分布圖

圖7 實(shí)驗(yàn)設(shè)備需求圖

圖8 優(yōu)化前后設(shè)備使用率對(duì)比圖

5 結(jié) 語

本文論述了應(yīng)對(duì)遠(yuǎn)程實(shí)驗(yàn)設(shè)備的調(diào)度問題，從“設(shè)備調(diào)度”、“課程安排”等多個(gè)維度建立調(diào)度優(yōu)化模型，并提出基于改進(jìn)遺傳算法的最優(yōu)化求解方法。仿真實(shí)驗(yàn)證明，改進(jìn)型遺傳算法在收斂速度和算法結(jié)果上優(yōu)于傳統(tǒng)遺傳算法。優(yōu)化后的設(shè)備使用率相較傳統(tǒng)調(diào)度方式有著明顯的提升，對(duì)遠(yuǎn)程實(shí)驗(yàn)設(shè)備資源的調(diào)度和實(shí)驗(yàn)課排課有著可借鑒的積極意義。