排队论在烟草自动化立体仓库调度中的应用

排队论在烟草自动化立体仓库调度中的应用

1仓库输送系统的调度自动化立体仓是现代工业社会发展的高科技产物。它集存储、配送和分销于一体，代表了当今物流的发展趋势，并越来越多地应用。在烟草行业中,物料流量大、运送环节多、生产线自动化水平非常高,因此物流技术的自动化程度直接影响其生产的效率。作为高性能工业机器人的一个典型产品,AGV(AutomatedGuidedVehicle)是现代工业生产,现代自动化仓库以至现代物流系统的枢纽和核心。在自动化仓库中,输送系统作为连结操作端与货架的纽带,是整个仓库的重要组成部分。实际应用中,如果要求作业的任务很多,堆垛机往往可以进行高速工作,基本可以满足要求,而这时对输送系统的调度就显得很重要,如果调度不合理,就会出现“瓶颈”,甚至“死锁”状态。本仓库输送系统的核心是由一台AGV构成的服务系统(仓库简图见图1),对AGV进行合理调度,提高其输送效率,对于减小“瓶颈效应”、提高该仓库的整体运行效率具有重要的意义。排队论又称为随机服务系统理论。在这类系统中,顾客到来的时间和服务所需的时间都是随机的,都会出现“排队等待”现象,问题是如何解决服务机构容量和等待队长之间的矛盾,以求最优服务。本文中以AGV为核心的输送系统,可以看作一个单服务台排队系统,其服务台是AGV,顾客是各终端提交的作业(运输任务)。由此可见建立排队系统模型,并根据系统实际要求用数学方法分析此模型的合理性和可靠性,以达到对AGV最佳的调度效果,提高系统整体效率。2仓库输送系统的调度本文所描述的立体仓库主要由立体货架区,入库区和出库区组成,其平面布置简图如图1所示:货架区共有6排立体货架,分3个巷道,货架的货格内放有烟包或者空托盘组。在每一巷道内有一台双叉堆垛机负责两侧货架上的烟包或者空托盘组的存取,各巷道口处分别有出库台和入库台,堆垛机可以从入库台取得货物放到相应位置,也可以将取出的货物放到出库台上,然后由AGV负责各操作台间的烟包或托盘组的传输。在整个输送系统中,入库是由专门的辊道和链条输送机以及其它相关设备送至仓库入库台的(本文不作具体描述),出库以及托盘回收的主要运输任务均由一辆直线导轨型AGV承担:它负责将3个巷道口出库台的烟包送至出库缓冲区链;在回收的托盘达到码垛数量后运回空托盘组,空托盘组根据需要通过入库系统入库存放(出库流量>入库流量)或者直接供入库使用(入库流量>出库流量);当入库所需托盘不够时,需要从仓库中调出空托盘组直接运送到入库系统。此外AGV还负责一些特殊任务如紧急补料(不入库,直接经过AGV将烟包送至出库缓冲链)和出错处理(退库)等。由上述分析可见AGV的调度是整个仓库输送系统调度的关键。在大批量拣选出入库时,3台堆垛机同时高速工作,出入库系统任务增加,托盘和烟包流量增大,再加上特殊情况处理,此时AGV的工作效率就成为制约整个仓库工作效率的重要因素。如果调度不合理,各出库台和空托盘组上货处(出库口)很可能出现堵塞,此时如何有效调度AGV,使系统在运行过程中不出现“瓶颈”状态,就具有非常重要的意义。针对此服务系统的特点,本文利用排队论方法对其进行建模,并计算出相应的性能指标,然后根据排队模型的仿真曲线和系统需求分析调度的合理性。3工艺排队模型排队系统模型是为了研究排队系统运行的效率,确定系统参数的最优值,以决定系统结构是否合理,研究改进措施等。本系统中,定义顾客为各操作台在任意时刻请求AGV运送烟包或托盘组的任务;服务指AGV将货物运送到指定操作台的整个过程;服务员为AGV。由于任务到达的随机性,对各个任务AGV所提供的服务也不是匀速的,因此可以假设顾客到达过程服从泊松分布,服务员的服务时间服从指数分布,而服务员只有1个,按照排队论相关理论,我们可以用M/M/1模型进行简单等效。需要说明的是,实际系统中任务是分多优先级的。由于从烟叶到成品烟的制烟流程中,烟叶库仅为制丝车间服务,所以一般情况下为保证生产,出库任务应该优先于入库任务,相应的即为烟包出库任务优先于空托盘组出库任务,当然也优先于回收托盘组到入库口的任务。此外,发现霉变烟叶后,紧急补料任务又优先于普通出库任务。在发现入库错误后的退库任务一般在系统负担较轻的时候进行,所以优先级最低。这里为了分析处理方便,将不同级别的任务进入人为排序处理来实现其优先级,同级别的任务排队规则为先进先出(FIFO)。处理后该排队模型可当作单级别处理,如图2所示:图2中给出了排队模型中的一些重要参数。其中λ为任务的平均到达率;n为等待服务的任务数量;TW为某任务等待服务的时间;TS为服务员(AGV)对某任务的服务时间;ρ为服务员的利用率即服务员忙的比例;q为系统中总的任务数;Tq为每个任务在系统中的逗留时间,包括等待时间和服务时间。其中ρ=λ/μ,参数μ表示单位时间内能被服务完的顾客数,即平均服务率,其值为1/E(TS)。一个稳定的排队系统,队列的长度有限,顾客的等待时间也有限,ρ应满足0≤ρ<1。本系统采用的性能指标为E(n)和E(Tq)—E(n)表示平均队列长度,它描述了在系统中等待服务的任务的平均数量,可反映系统在有限队列容量的情况下,产生阻塞的可能性;E(Tq)指任务的平均逗留时间,它能表达平均时延,其大小反映了AGV对各任务的响应的速度。因此这两个参数的值能比较合理地和有效地反映系统的性能。由泊松过程和排队论的基本理论公式可以推出M/M/1排队模型各参数之间的主要基本关系如下:4agv能力需求估算下面是在MATLAB6.5环境下根据上述(2)式和(3)式实现的M/M/1模型的仿真曲线,这里取的横坐标为服务员利用率ρ,为了在同一副图中比较两个性能指标,将(3)式左右同时乘以μ,则有:μE(Tq)=1/(1-ρ)。由图3很容易看到,在ρ<0.8时,E(n)和μE(Tq)的数值都很小,且变化不大,平均队长不超过3个任务,此时烟包和托盘组在进行排队操作时,因缓存区占满而引起堵塞的概率就非常小,任务在系统中的逗留时间也很短。当ρ>0.8以后,E(n)和μE(Tq)都变大,且上升趋势很快,当任务到达速率接近于其最大处理能力时,将会引起阻塞,增加顾客的等待时间。因此,系统需要有一个合适的ρ值才可能达到较高的运行效率。下面按照上述排队模型,根据系统最大出入库需求以及AGV相关参数来求ρ值及相应的性能指标,并判断结果是否合理。M/M/1排队模型最常用的应用是:已知客户平均到达率λ和服务员平均服务时间TS,计算其他所有参数,这也是本文估算系统性能指标的方式。尽管M/M/1排队模型参数比较多,但只要已知任意两个不相关的参数,就能计算出其他所有参数。本系统中的λ和TS值可由实际要求估出。系统对穿梭车AGV的能力需求是48+11+8=67托盘/h,其中每小时烟包出库流量为48包/h,空托盘组出库流量为11组/h,从出库系统返回到入库系统的托盘组为8组/h。系统设计能力要求70托盘/h,这里考虑到可能的出错和紧急供料情况。所以取λ=70托盘/h即7/360托盘/s进行计算。另外,本系统中AGV一次服务的流程是:控制位待命—接受命令—到取货台—取货—到上货台—上货—回控制位待命(控制位位置见图1所示),已知取货和上货交接的时间均为15s左右,AGV速度为10/3(m/s),根据AGV运行导轨长度和取货上货时间,可以推断一次服务的时间即TS约为40s。现在已知λ和TS,由(1)式可计算得ρ=7/9;代入(2)式,可得E(n)≈2.7;代入(3)式,可得E(Tq)=180s=3分钟;再代入(4)式,q=3.5。从上面的分析可以知道,只要将服务员利用率ρ控制在80%以下,就可大大减小输送系统阻塞的可能性,从而改善整个自动化立体仓库系统的运行效率。现在求得在λ取系统所需最大值的情况下(系统最忙的情况),等待服务的平均任务数为2.7,每个任务在系统中的平均逗留时间为3分钟,而由本系统的缓冲站个数可知等待的任务数即队长最大可达8个,显然上述结果是满足系统要求的。而且一般情况下,λ值小于70,此时求得的ρ值会减小,相应求得的逗留时间也会变小,等待队长变短,系统可以达到比较令人满意的效率。5m/m/1排队模式文中所描述的烟叶自动化立体仓库控制系统中的一个重要部分就是直线导轨型AGV的调度问题。以AGV为核心的输送系统可以看作一个M/M/1型排队