面向遠程實驗設備的最優資源調度方法

孫 博 俞武嘉 劉光宇

(杭州電子科技大學自動化學院 浙江 杭州 310018)

0 引 言

隨著數字孿生技術與高校實驗室資源的結合，遠程共享使用實驗設備有了新的發展思路。實驗教學作為課堂理論知識的具體化、實踐化，是高校教學環境中的重要一環，實驗課程的合理安排，關系到實驗室日常工作的順利進行[1]。因此，如何合理地分配有限實驗設備資源并給出最優排課方案成為了新的問題。

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

1 問題描述與假設

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

上述情景延伸到高校的實驗課教學中，將多設備信息技術實驗室看作一個服務系統，實驗室的實驗設備是有限的。通常學生以班級為單位在特定的時間做同一個實驗，每個班級的任務申請為一個隊列。學生在實驗課開始后發出實驗任務申請，然后實驗設備開始工作。某些時候不同班級的學生在同一時刻進行實驗課，但實驗課程的內容是不一定相同的，實驗設備服務不同實驗課程的能力也是不同的，遠程實驗設備調度示意圖如圖1所示。如果設備的分配不合理，會延遲需求量較高學生的設備資源供應，降低實驗課效果；分配過量的設備資源，會造成設備資源的利用率低。實驗課結束后，設備資源被釋放。

圖1 遠程實驗設備調度示意圖

從以上的描述中可以看出,通過先來先服務的規則無法保證實驗課的設備使用效率最大化。因此,本文的目標是尋求使實驗室遠程實驗設備效率最大化的設備調度和排課方法。為系統地分析和評價調度安排，本文提出兩個假設：(1) 實驗產生的服務申請不會消失；(2) 服務申請的到達服從泊松分布。在滿足這些假設后，方能構建相應的調度模型，并設計遺傳算法尋優。

2 最優化調度模型

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

采用α描述設備環境：在實驗過程中，學生s需要調用m類每類n臺設備，所以存在流水車間調度問題；在只有1個班級實驗的情況下，存在并行同性能機器調度問題處理；在多個班級同時實驗的情況下，存在并行不同性能機器調度問題。綜上所述，采用柔性車間作業調度問題將零散的調度問題進行統一處理。

采用β描述實驗過程的約束：使用Mi設備作為任務分配的約束，集合Mi表示實驗i的可選設備集合，集合Mi不出現，表示實驗i可以在任何設備上進行實驗；使用優先(偏序)約束作為流水約束，學生s必須等待設備釋放，才能繼續實驗。

采用γ描述實驗教學安排的目標：面向實驗過程中的設備資源的調用，需要保證不同規格的實驗設備根據實驗任務分配合理化，將此優化目標定位為負載均衡最優調度問題。在Mi等約束條件下，使用Wj表示單個設備的負載率，采用min max最優化模型來描述：

min max{1-Wj}

(1)

面向實驗課在日常教學中的分配，需要保證班級、課程、實驗時間，以及根據實驗類別調用的實驗設備等元素不發生沖突，以時間ti表示各個日常教學中的必要時間，給出時間排序的數學問題：

sequence{t1,t2,t3}

(2)

此外，需要對所有實驗設備總使用時間進行優化，以提高設備的利用率：

min{∑Li}

(3)

式中：Li表示單個設備的使用時間。因此，本項目的多個調度問題可以歸納為多目標優化NP-Hard問題。

3 基于遺傳算法的調度安排優化

根據上述的調度問題描述以及假設，本文采用遺傳算法對實驗課程的資源調度進行優化。其中包含遠程實驗設備和實驗用戶的分配，以及高校的日常教學中實驗課的合理安排。使用下列集合表示這些調度所需因素：

設備集合：S={S1,S2,…,Sn}，在某一個實驗課程內，需要N臺設備，N≥1。

任務集合：T={T1,T2,…,Tn}，每臺客戶端發送的服務申請為一個任務Ti。

實驗集合：E={E1,E2,…,En}。

班級集合：C={C1,C2,…,Cn}。

專業集合：M={M1,M2,…,Mn}。

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

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

3.1 編碼規則

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

圖2 染色體結構示意圖

3.2 適應度函數設計

在遺傳算法中，遺傳的方向需要適應度來決定，適應度表示整個實驗課程調度的優秀程度。相對于常見的基于遺傳算法的排課算法中的適應度函數設計[7-8]，在實驗課程的排課中需要關注設備調度和排課兩個部分。因此，在本文適應度函數的設計中，適應度的期望由兩個部分組成：實驗設備調度和實驗課程安排。

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

E(L)=λE(S)

(4)

對于M/M/n隊列，通過求解生滅過程的穩定概率和應用Little公式，可以得到：

(5)

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

(6)

通過式(5)和式(6)計算任務平均使用時間和設備利用率。對于線上資源調度合理程度的期望函數公式為：

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

(7)

式中：t1和t2用于調控任務平均響應時間和設備資源利用率對線上資源調度合理程度的影響。

(2) 實驗課程安排。實驗課程安排的合理程度可由兩個部分組成：

① 實驗課程特征規律。學生邏輯思維活躍的時間段一般在早晨，所以早晨適宜安排理論課程，而且實驗課通常需要更長的時間。根據實驗課程的特征規律，不同課程段的期望值不同，如表1所示。

表1 實驗課程特征規律期望值

對于特征規律的期望函數公式為：

FET=∑FET(i)

(8)

② 教學規劃適宜度。在高校教學中，實驗課的安排應分布于學期中間。因為學期開始時，學生處于放假歸來的狀態，此時教學效果并不是很好；而在學期末和期中考試前，學生面臨考試周主要工作為復習應對考試，此時的實驗課效果也不理想。根據這樣的規律，實驗時間安排的教學規劃適宜度也不同，如表2所示。

表2 教學規劃適宜度期望值

對于規劃適宜度的期望函數公式為：

FEP=∑FEP(i)

(9)

根據以上分析可以得出適應度函數F：

(10)

式中：k1、k2和k3用于調控各期望值對總適應度的影響。

3.3 算法步驟

遺傳算法的整體流程如圖3所示。它的主要流程通過遺傳算法程序產生Np組可行解，之后計算各個可行解的適應度，通過交叉、變異產生新的可行解。如此迭代，直到達到預先設定的最大代數，退出程序，輸出最優結果。

根據以上的算法思路，傳統遺傳算法步驟如下：

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

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

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

在傳統的遺傳算法中，是設定上一代的全部個體的基因進行重組、交叉、變異得到下一代基因。但是因為實際算法運行中，兩代個體之間有著一個過渡期，在這個期間，兩代個體都存在，雖然避免了父代與子代間的基因傳遞變動太大，但是會導致尋優的“深度”不足。因此，在改進的遺傳算法中，在父代與子代的種群融合前，只保留父代種群中一半適應度較好的個體，另一半較差的直接刪除。這樣可以提高收斂速度，增加搜索深度。

根據以上描述，本文采用的改進遺傳算法步驟如下：

(1) 參數定義：同傳統算法步驟1。

(2) 產生初始種群：同傳統算法步驟2。

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

(4) 刪除處理：對父代種群按照適應度排序，保留較優的一半父代個體。重復步驟3，直到滿足退出條件(達到最大繁殖代數)，退出計算，輸出最優解。

4 實驗驗證

在Visual Studio.net環境下用C#語言編寫整個調度算法的仿真實現。仿真中設定一共有5類設備，每類20臺，隨機生成15類實驗課程，設備的服務能力如圖4所示。按照10個專業20個班級每個班級30名學生，每個專業隨機選擇10類實驗進行調度安排。

圖4 設備服務能力分布圖

在遺傳算法中設置生育率為0.8，基因變異率為0.08。分別使用未改進算法和改進算法迭代200次，得到5次出現最優解的世代和最優解的適應度，求平均后如表3所示。

表3 遺傳算法結果

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

圖5 遺傳算法最優解曲線圖

圖6 各班級按時間段所需設備分布圖

圖7 實驗設備需求圖

圖8 優化前后設備使用率對比圖

5 結 語

本文論述了應對遠程實驗設備的調度問題，從“設備調度”、“課程安排”等多個維度建立調度優化模型，并提出基于改進遺傳算法的最優化求解方法。仿真實驗證明，改進型遺傳算法在收斂速度和算法結果上優于傳統遺傳算法。優化后的設備使用率相較傳統調度方式有著明顯的提升，對遠程實驗設備資源的調度和實驗課排課有著可借鑒的積極意義。