實(shí)驗(yàn)室設(shè)備預(yù)約管理系統(tǒng)算法研究

牛 亮

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

實(shí)驗(yàn)室設(shè)備預(yù)約管理系統(tǒng)算法研究

牛 亮

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

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

實(shí)驗(yàn)室管理；預(yù)約；算法

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

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

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

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

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

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

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

2 設(shè)備預(yù)約約束條件

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

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

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

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

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

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

（6）附加約束：如盡量減少費(fèi)用等，當(dāng)各設(shè)備都在不同實(shí)驗(yàn)室時(shí)，盡量減少開放的機(jī)房數(shù)量等。

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

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

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

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

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

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

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

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

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

（6）當(dāng)前得到的預(yù)約申請為Rk＝｛＜type，number，Ti＞｝；

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

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

（9）得到預(yù)約申請Rk的第j類型的設(shè)備信息；

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

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

（12）記錄失敗信息，清除本次預(yù)約的臨時(shí)信息，記錄預(yù)約信息，進(jìn)入（13）；

（13）根據(jù)失敗原因和價(jià)值函數(shù)得到一個(gè)目標(biāo)函數(shù)值，進(jìn)入（14）；

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

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

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

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

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

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

（20）記錄預(yù)約情況，更新設(shè)備使用狀態(tài)，進(jìn)入（21）；

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

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

4 算法分析

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

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

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

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

5 結(jié)束語

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

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

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

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

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

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

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

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

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

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

［10］ 彭復(fù)明，夏玉敏.高校機(jī)房自動排課策略與算法［J］.南京工業(yè)職業(yè)技術(shù)學(xué)院學(xué)報(bào)，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

（責(zé)任編輯：李文英）

2012－04－26

2012－05－20

牛 亮（1970～），男，碩士，實(shí)驗(yàn)師.E－mail：ca.lniu＠gzu.edu.cn