牛 亮

（贵州大学土木建筑工程学院 贵州 贵阳：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