孫 博 俞武嘉 劉光宇

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

0 引 言

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

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

1 問題描述與假設

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

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

圖1 遠程實驗設備調(diào)度示意圖

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

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

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

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

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

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

min max{1-Wj}

(1)

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

sequence{t1,t2,t3}

(2)

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

min{∑Li}

(3)

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

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

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

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

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

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

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

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

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

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

3.1 編碼規(guī)則

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

圖2 染色體結構示意圖

3.2 適應度函數(shù)設計

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

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

E(L)=λE(S)

(4)

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

(5)

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

(6)

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

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

(7)

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

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

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

表1 實驗課程特征規(guī)律期望值

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

FET=∑FET(i)

(8)

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

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

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

FEP=∑FEP(i)

(9)

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

(10)

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

3.3 算法步驟

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

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

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

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

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

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

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

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

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

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

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

4 實驗驗證

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

圖4 設備服務能力分布圖

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

表3 遺傳算法結果

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

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

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

圖7 實驗設備需求圖

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

5 結 語

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