基于状态矩阵降阶算法自动化药房发药模式设计.doc

基于状态矩阵降阶算法自动化药房发药模式设计 　　摘要：介绍一种常见的自动化药房系统模式，设计一种提高发药效率的状态矩阵降阶算法。分析自动化药房系统的运动时间算式并确定优化目标。基于状态压缩矩阵，利用降阶算法解决集合覆盖问题给出降阶切入点与具体流程。结合分支界限法解决一个问题实例。利用Matlab仿真分析该算法在自动化药房发药过程中的优化作用。计算该算法的时间复杂度和空间复杂度，结合实际问题与其他算法对比优劣性。 　　关键词：状态压缩矩阵；降阶算法；集合覆盖问题；自动化药房 　　中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2013）28-6392-06 　　自动化药房是一种能够利用软件分析电子处方，控制电机运动，从而驱动自动化药房设备自动发放药品的装置。该发药设备共有15层，每层35～42个储药槽。设备前侧的升降机平台运行到某一层后，该层的待出药品会自动由电磁铁弹出。药品储位布局如图1所示。 　　由于不同药品的需求量有差异，对于经常使用的药品，可以分配多个储位以保证库存量足够，从而减少上药作业的频率。在这种情况下，对一种药品就可以有多个储位可以选取，为快速出药算法的优化提供了可能。 　　1 优化目标的确定 　　1.1 自动化药房运行模式 　　药品出库时，出药模式程序会不断访问数据库的处方表，该表存有待处理的处方药品信息。一旦数据库接收到新的处方，出药模式程序就会读取处方中的药品信息，再根据用户选择的出药模式和各储位药品库存，计算出一个出药拣选路径，其中包含待出药的储位和每个储位的出药数量，并将这些信息写入出药表中。工控机上的出药运行程序根据出药表中的信息，控制出药升降机、电磁铁、出药口翻版电机和传送带电机运动，从而将药品按储药层依次打出，最后由传送带送至出药口。 　　出药拣选路径的设计由出药模式程序计算得出。出药程序对每种药品依次进行拣选计算：从储位信息表中获取该药品的所有储位及各储位库存，然后从储位号最小的储位开始取药，一个储位药品不够时会继续取下一个储位的药，直到药品全部取完。全部药品选好储位后将储位信息写入数据库。出药运行程序根据出药数据库中所有要出的储位及其出药数量，控制升降机从高层到低层逐层出药，升降机平台运行到某一层后，该层不同的储药口可同时出药。升降机启动前和停止后都在第5层，即出药口的位置。 　　1.2 优化目标 　　根据上述运行模式建立模型：忽略升降机平台的加减速过程和储药层高的微小差异，即认为升降机运行任一层时间均为Tlayer，设出每盒药的时间为Tmed，则一个处方出药的总时间为 　　由公式（1）可以看出，出药时间的长度取决于Lmax和Lmin的取值，以及对应每一个L的MLn的最大值。在快速发药系统中，由于药品的使用频率不同，用户会给使用频率高的药品分配更多的储位，这使得出药过程有多种拣选路径可选择。算法优化前，任何一种药品都会优先拣选储位号最小的储位。根据公式分析，可以从以下方面进行优化： 　　1）应尽量使Tlayer的因子更小：如果一种药品在第5层有储位，从第5层拣选将是最优的选择，可以省去升降机平台为该药品做额外的运动。 　　2）应尽量使L的取值更少，即减少总拣选行数。如果多种药品同时在某一层有分配，从这一层拣选可以使升降机停留更少的储药层。 　　3）应尽量使同一层中MLn的最大值更小，如果某种药的出药数量较大，则应将这种药分散到多个储位同时出。 　　该文将介绍选取最少的发药层数的算法。 　　2 状态压缩矩阵的降阶 　　2.1 集合覆盖问题的提出 　　最小拣选层数策略要求对于一个处方的药品，尽量从更少的层拣选，这样可以使同一层同时出尽量多的药品。根据公式（1），减小其中的表达式（2）可以使设备拣选更少的层数。当L的值越小，在每种药品只出一盒的情况下，表达式（2）值就会越小。 　　这个问题可以描述为：对于给定的若干种药品，选中最少的储药行，在这些行中可以包含所有药品。该问题可以抽象成集合覆盖问题，即给定一个实例[]，X为一个有限集，F为X的一个子集族且覆盖了有限集X，即[X=S∈FS]。对于F中的一个子集[C?F]，如果[X=S∈CS]，则称C覆盖了X。集合覆盖问题的目标是找到F中覆盖X的最小子集Cmin，使[Cmin=min{C|C?F，X=S∈CS]。该抽象模型对应到原问题：集合F的元素是各储药层，每个储药层是一个集合，其元素是该层所含的待出药品；集合X为所有待出药品的集合。 　　集合覆盖问题（SCP，Set Covering Problem）是运筹学和计算机科学领域的NP难解问题，对此问题，目前已有的算法如启发式算法[4]，近似算法[3]，穷举法等，这两种算法的软件实现较为复杂，尤其是穷举法，其算法复杂度为O（n！）级，随着药品