實驗室設備預約管理系統算法研究

牛 亮

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

實驗室設備預約管理系統算法研究

牛 亮

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

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

實驗室管理；預約；算法

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

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

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

1 設備狀態轉換

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

圖1 設備狀態轉換圖

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

2 設備預約約束條件

設備預約的優化調度首先應該滿足一定的調度約束條件，詳細的約束條件如下：

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

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

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

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

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

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

3 設備調度算法

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

圖2 設備調度算法流程圖

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

（1）根據預約數據初始化進行數據格式化；

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

（3）根據排序的序列得到預約調度序列R；

（4）預約用戶循環初始值k：＝0；

（5）預約用戶循環變量自加k：＝k＋1；

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

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

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

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

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

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

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

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

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

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

（16）根據序列，繼續進入（03）；

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

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

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

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

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

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

4 算法分析

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

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

3）在當前預約序列在失敗后可以根據其他的序列進行選擇，在序列更新的地方可以根據適當的算法進行優先級別排序，可以使得找到正確序列的速度更快；

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

5 結束語

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

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

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

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

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

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

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

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

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

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

［10］ 彭復明，夏玉敏.高校機房自動排課策略與算法［J］.南京工業職業技術學院學報，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