孫 博 俞武嘉 劉光宇

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

0 引 言

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

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

1 問題描述與假設

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

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

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

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

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

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

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

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

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

min max{1-Wj}

(1)

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

sequence{t1,t2,t3}

(2)

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

min{∑Li}

(3)

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

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

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

設備集合：S={S1,S2,…,Sn}，在某一個實驗課程內，需要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ù)設計

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

(1) 實驗設備調度。由上述的調度分析，在一個實驗課期間，用戶提交任務的過程是相互獨立的泊松過程，設備處理任務的過程仍然是泊松過程。那么可以將實驗設備的調度抽象成一個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)計算任務平均使用時間和設備利用率。對于線上資源調度合理程度的期望函數(shù)公式為：

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

(7)

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

(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用于調控各期望值對總適應度的影響。

3.3 算法步驟

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

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

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

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

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

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

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

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

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

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

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

4 實驗驗證

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

圖4 設備服務能力分布圖

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

表3 遺傳算法結果

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

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

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

圖7 實驗設備需求圖

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

5 結 語

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