牛 亮

（貴州大學土木建筑工程學院 貴州 貴陽：550025）

實驗室設備預約管理系統(tǒng)算法研究

牛 亮

（貴州大學土木建筑工程學院 貴州 貴陽：550025）

在分析國內(nèi)外研制開發(fā)的排課和預約管理系統(tǒng)的基礎上，針對其存在的不足，依據(jù)高校教學和實驗室特點，對實驗室預約管理系統(tǒng)所涉及的技術(shù)、重點難點問題和相應的設計方案進行了詳細論述，給出了預約管理系統(tǒng)的算法。

實驗室管理；預約；算法

儀器設備是高等學校從事教學與科研工作的重要物質(zhì)基礎，隨著科學技術(shù)的不斷進步，儀器設備不斷更新，現(xiàn)代化水平也越來越高。如何合理高效地使用儀器設備，特別是大型精密儀器設備，提高利用率，使其充分發(fā)揮效能，更好地為教學與科研服務是設備管理部門要解決的關(guān)鍵問題。設備預約模式極大地激活了實驗室設備的資源，預約服務也應運而生。如何利用現(xiàn)代化技術(shù)最大限度地滿足學生對實驗設備的需求，讓設備盡可能多地產(chǎn)生效益是值得設備管理部門探索和研究的問題。

預約部分是系統(tǒng)的核心部分，設備調(diào)度算法是系統(tǒng)的重中之重。目前，實驗室設備調(diào)度算法還比較少，對于排課算法的系統(tǒng)相對較多［1－3］，主要是根據(jù)實驗室占用情況，得出是否占用實驗室的方式。根據(jù)實驗室直接占用方式進行預約浪費了實驗室的部分資源，使得實驗室資源不能充分利用起來。直接使用排課算法又不適合實驗室的實際情況。預約系統(tǒng)算法［4－6］是根據(jù)當前實驗室和當前時間是否空閑進行預約，但是在并發(fā)較高時系統(tǒng)存在崩潰問題。同時這樣的預約實際上存在資源的浪費和多個用戶同時預約設備時存在設備共享競爭問題。

一般算法沒有考慮到系統(tǒng)并發(fā)和資源浪費的問題，為達到節(jié)約資源和共享資源的目的，本文開發(fā)了一套實驗室設備預約管理方案。

1 設備狀態(tài)轉(zhuǎn)換

首先介紹設備狀態(tài)在管理的過程中存在幾個狀態(tài)，從系統(tǒng)入庫狀態(tài)，錄入設備的詳細信息，如：設備廠商、價格、數(shù)量、合同信息、說明書等必要的信息。設備在入庫后的狀態(tài)轉(zhuǎn)移圖見圖1所示：

圖1 設備狀態(tài)轉(zhuǎn)換圖

設備入庫后進入空閑狀態(tài)。設備在某個時間處于空閑狀態(tài)時可以進行預約，或緊急使用而無需預約。當設備陳舊時可以提出報廢、并進入了出庫階段。實驗教師可以向部門領導提出申請。如果申請通過，進入預約狀態(tài)。當設備處于預約狀態(tài)時，申請教師可以提出預約取消或等待預約調(diào)度。用戶等待系統(tǒng)調(diào)度，設備處于等待調(diào)度狀態(tài)。調(diào)度結(jié)束后，申請教師可以使用相應的設備進行使用，此時設備處于占用狀態(tài)。使用結(jié)束后歸還，此時系統(tǒng)又置于空閑狀態(tài)。設備的狀態(tài)就這樣循環(huán)進行，直到設備報廢或出庫為止。

2 設備預約約束條件

設備預約的優(yōu)化調(diào)度首先應該滿足一定的調(diào)度約束條件，詳細的約束條件如下：

（1）設備異常補償：設備調(diào)度最基本的約束條件是預約設備有一定比例的備用設備，但是并不能空閑太多設備。設備完全調(diào)度存在臨時增加用戶和設備異常不能工作等多方面的風險。經(jīng)過長期實踐，臨時增加用戶屬于用戶自身違約問題，而設備屬于設備提供方問題，設備調(diào)度時需要在預約基礎上增加設備異常概率補償。

（2）時間規(guī)范：每臺設備都必須在基本的工作日才對外開放，非正常工作日設備處于限制狀態(tài)。一臺設備在一個時刻只能完成一個作業(yè)。設備的使用必須在規(guī)范的時間段。

（3）功能限制：對于固定的設備只能完成特定的設備作業(yè)任務，同類設備可以完成類似的任務，但是在性能和準確度上有一定的區(qū)別。

（4）優(yōu)先級別控制：對于不同的用戶優(yōu)先級別的不同，給與不同的優(yōu)先級別。對于本院教師的實驗課程、其他學院的實驗課程，甚至其他學校的實驗課程的優(yōu)先程度不同。系統(tǒng)分為10個等級的優(yōu)先級別，正常情況下為5，緊急使用為10。

（5）閑置設備控制：當提供的實驗室設備過多，而實驗室用戶相對很少時，較多的設備處于空閑狀態(tài)，然而實驗室的額外費用，如電費、水費、實驗耗材等盡可能節(jié)約時，可以使得閑置設備較少、額外費用較少時，使得系統(tǒng)更合理分配設備使用。

（6）附加約束：如盡量減少費用等，當各設備都在不同實驗室時，盡量減少開放的機房數(shù)量等。

3 設備調(diào)度算法

上面的假設可以知道，設備狀態(tài)可以唯一表示任何時刻的設備預約情況，下面將設計預約調(diào)度的詳細算法。系統(tǒng)首先必須按照算法假設的信息進行數(shù)據(jù)格式化.預約數(shù)據(jù)格式化以后進入預約調(diào)度部分，算法設計的詳細流程見圖2所示：

圖2 設備調(diào)度算法流程圖

本算法結(jié)合了貪心算法和近距離搜索法的思想［7－10］，提供了貪心算法的接口，解決了預約調(diào)度無解的情況和相應的解決方法。下面詳細介紹預約調(diào)度的詳細算法：

（1）根據(jù)預約數(shù)據(jù)初始化進行數(shù)據(jù)格式化；

（2）根據(jù)貪心級別產(chǎn)生預約申請序列Request＝＜R1，R2，…，RK＞，如根據(jù)預約優(yōu)先級別排序，或根據(jù)預約設備的數(shù)量進行排序，或根據(jù)緊缺設備的數(shù)量排序，或結(jié)合任意幾項進行排序，或根據(jù)管理員定制排序方法等等排序方法進行排序，產(chǎn)生的序列將盡量滿足的情況下進行搜索較為優(yōu)化的解法；

（3）根據(jù)排序的序列得到預約調(diào)度序列R；

（4）預約用戶循環(huán)初始值k：＝0；

（5）預約用戶循環(huán)變量自加k：＝k＋1；

（6）當前得到的預約申請為Rk＝｛＜type，number，Ti＞｝；

（7）預約申請Rk的設備的循環(huán)序號j：＝0；

（8）預約申請Rk的設備的循環(huán)序號j：＝j＋1；

（9）得到預約申請Rk的第j類型的設備信息；

（10）在設備狀態(tài)中，判斷type類型的可用設備在Ti時刻是否滿足Rk的要求，如果滿足，則進入步（11），否則進入步（12）；

（11）如果可用的設備滿足用戶預約條件，記錄設備預約情況，標記系統(tǒng)狀態(tài)為type類型的可用設備在Ti時刻被預約系統(tǒng)更新系統(tǒng)狀態(tài)，進入步（19）；

（12）記錄失敗信息，清除本次預約的臨時信息，記錄預約信息，進入（13）；

（13）根據(jù)失敗原因和價值函數(shù)得到一個目標函數(shù)值，進入（14）；

（14）根據(jù)失敗序列交換Rk與Rk＋1，進入步（15）；

（15）交換后的序列是否使用過，如果使用過，則繼續(xù)查找，直到序列查找結(jié)束，如果存在沒有使用過的序列，則進入（16），否則進入（17）；

（16）根據(jù)序列，繼續(xù)進入（03）；

（17）系統(tǒng)已經(jīng)完成了所有查找，根據(jù)預約的設備無法得到解答，根據(jù)生成的價值函數(shù)值進行排序，取價值較大的值進行適當修改，進入（18）；

（18）查看修改結(jié)果是否滿意，如果滿意則進入人工調(diào)整階段，結(jié)著打印和形成表報階段，如果需要繼續(xù)計算，則進入（03）；

（19）查看Rk是否結(jié)束，如果結(jié)束，則進入（20），否則進入（08）；

（20）記錄預約情況，更新設備使用狀態(tài)，進入（21）；

（21）查看預約全過程是否結(jié)束，如果結(jié)束則進入（22），否則進入（05）；

（22）預約找到了預約結(jié)果，打印和輸出結(jié)果。

4 算法分析

1）算法在步（2）中設置了申請序列的設置，可以根據(jù)預約優(yōu)先級別排序，或根據(jù)預約設備的數(shù)量進行排序，或根據(jù)緊缺設備的數(shù)量排序，或結(jié)合任意幾項進行排序，或根據(jù)管理員定制排序方法等等排序方法進行排序，在初始化時，可以根據(jù)預約情況的結(jié)果大致設置較好的初值，可以提高預約調(diào)度是速度。如：當預約緊缺設備的教師較多時，可以根據(jù)需要預約的緊缺設備排序；預約申請教師中可能會有院、校領導或其他學院教師，預約教師優(yōu)先程度不同，可以先根據(jù)預約教師的優(yōu)先程度為第一排序、設備緊缺程度為第二排序方式，或混合排序方式等等的排序方法使得盡可能地達到切合實際的合理的預約方式；

2）算法在步（13）上設置了價值函數(shù)值同時記錄下失敗信息，在以后的搜索中可以盡量提高記錄下了失敗信息，并且類似于給與適當?shù)脑u價，為以后的搜索起來指導作用；

3）在當前預約序列在失敗后可以根據(jù)其他的序列進行選擇，在序列更新的地方可以根據(jù)適當?shù)乃惴ㄟM行優(yōu)先級別排序，可以使得找到正確序列的速度更快；

4）如果系統(tǒng)根本就沒有解時，又希望找到較好的結(jié)果進行分析然后修改，步（13）為系統(tǒng)提供了較好的修改原始預約信息。

5 結(jié)束語

本算法結(jié)合了貪心算法和圖論搜索法的思想，提供了貪心算法的接口，解決了預約調(diào)度無解的情況和相應的解決方法。必須指出，這里的價值函數(shù)應該直接反應如何盡可能滿足用戶需求，例如：最大化安排作業(yè)在的總價值，符合必要的約束條件，盡量滿足附加條件等?？偨Y(jié)了原有的一些排課算法、貪心算法的一些思想，結(jié)合實際情況得出了當前系統(tǒng)需要的算法，給出了詳細的算法。同時算法也產(chǎn)生了數(shù)據(jù)共享與沖突和性能較差的問題，在以后的應用中將不斷完善系統(tǒng)設計和算法。

［1］ 蔡明山，彭楚武.基于課元與回溯算法的實驗室智能排課與預約［J］.長春工業(yè)大學學報：自然科學版，2004，25（4）：52－54.

［2］ 宋曉悅.高校開放式實驗室管理系統(tǒng)的設計與實現(xiàn)［D］.天津：天津師范大學，2008.

［3］ 王娜娜.基于UML建模語言的排課系統(tǒng)的設計與實現(xiàn)［D］.青島：中國海洋大學，2009.

［4］ 佟 林.基于專家系統(tǒng)的排課軟件的研究與設計［D］.哈爾濱：哈爾濱工程大學，2004.

［5］ 李志強.中職學校教務管理排課系統(tǒng)的研究與開發(fā)［D］.山東泰安：山東科技大學，2004.

［6］ 章玉政，李世杰，李慶男，等.實驗中心排課系統(tǒng)的設計與實現(xiàn)［J］.實驗室科學，2011，（6）：131－133.

［7］ 馬保國，李華剛，王連鋒.基于WebService預約系統(tǒng)的研究及實現(xiàn)方案［J］.福建電腦，2006，（11）：8－9.

［8］ 王 力.高校通用排課管理信息系統(tǒng)的設計與實現(xiàn)［J］.貴州工業(yè)大學學報，1999，（2）：89－92.

［9］ 韓承雙，張春梅，王開友.自動排課系統(tǒng)迭代算法設計與實現(xiàn)［J］.合肥學院學報：自然科學版，2005，15（3）：52－56.

［10］ 彭復明，夏玉敏.高校機房自動排課策略與算法［J］.南京工業(yè)職業(yè)技術(shù)學院學報，2007，17（2）：70－72.

Proposed Algorithm for Laboratory Equipment Reservation Management System

NIU Liang

Efficient use of resources，rational management，shared resources，application of information technology tend to replace the cumbersome manual operation，which may improve the experiment booking，equipment reservation management effectiveness，and the development of the online booking function.On the basis of the analysis of domestic and foreign research and development of the Course Scheduling and Reservation Management System，laboratory appointment management system，in accordance with the actual teaching and laboratory features and programs in universities，are elaborated.Key and difficult problems and the corresponding design are discussed in detail.The algorithm of reservation Management System is put forward.Booking system algorithm design and implementation is part of this core algorithm.

Laboratory management；appointment；algorithm

TP391.7

A

1671－3524（2012）02－0029－04

（責任編輯：李文英）

2012－04－26

2012－05－20

牛 亮（1970～），男，碩士，實驗師.E－mail：ca.lniu＠gzu.edu.cn