模型近似解析解求解思路在线视频

上述的排队网络模型

是单类别顾客的半开排队网络

这里顾客指的是订单 指令 任务

真实顾客等广义上的顾客

可以用基于近似平均值的方法 (简称为AMVA方法)

来获得近似解析解

该方法允许网络中的每个服务站点

具有 c_s 个平行的服务台

在前面的模型中

move 1 move 2 move 3服务站点的服务台数量 c_s

等于机器人的数量

AMVA是一种近似方法

因为它主要以服务时间的一阶矩和二阶矩作为输入

不限定服务时间的具体分布形式

允许服务时间服从一般分布

模型中各个服务站点服务时间的一阶矩和二阶矩

可以通过分析 move 1 move 2 move 3

三个运动的行程时间获得

接下来介绍如何来计算这三个运动的行程时间

各个运动的行程时间对应服务站点的服务时间

各种情况下的行程时间获得后

计算服务时间的一阶矩和二阶矩就水到渠成

执行move 1和move 3时

机器人驮载着pod移动

称为负载运输

而执行move 2时

机器人则在没有驮载pod的状态下移动的

称为非负载运输

机器人没有驮载pod时

可以在pod下方自由穿梭

不一定非得按照巷道行驶

因此在非负载运输的行程距离

可通过简单的Manhattan 距离获得

但要考虑单向路径限制的影响

负载运输时

机器人只能沿着巷道行驶

同样要考虑单向路径的限制

因此计算负载运输的行程距离则较为复杂

是我们的关注重点

获得了行程距离

除以机器人速度

即获得行程时间

非运输的环节也需要消耗时间

可以将这些时间消耗

归并到对应服务站点的服务时间中考虑

move 1增加存储pod所需的时间

move 3增加机器人提升pod所需的时间

假设存储pod的时间

提升pod的时间和机器人的速度均为常数

机器人不需要加速或减速

重点分析move 1和move 3对应的负载运输

负载运输是直线的

每条巷道都是单向的

货位入口是位于该货位前面巷道上的点

机器人通过货位入口进入存储货位

工作站入口点是大厅中

机器人进入工作站缓冲区的位置

这里介绍一个start intersection点的概念

Start intersection指的是机器人在行驶路径中

第一个使得距离目标位置距离减少的点

这个点往往在两个正交巷道(主巷道和横向巷道)的交叉点上

例如图中的存储货位SL

位于东向巷道上

工作站WS位于存储区的西侧

Start intersection就是在SL和WL 间最短路径上

第一个与西向巷道的交叉点

即图中红色圆点处

从存储货位SL到工作站WS的最短路径距离

可划分为四部分

1. 从存储货位SL到货位入口的距离

假设每个货位和巷道的宽度都是 u

这个距离也等于u

2. 从货位入口到start intersection的距离

3. start intersection 和工作站入口之间的 Manhattan 距离

等于|x_(si) -x_(WS) | + |y_(si) -y_(WS) |

其中 (x_(si) y_(si)) (x_(WS)y_(WS))

分别为start intersection 和工作站入口的坐标值

4. 第四部分是工作站处机器人的绕行距离 ∆_(lews)

该距离要么等于2u

要么等于 0

这取决于于工作站入口的位置

及工作站与存储区之间路径的方向

所有存储货位和工作站之间的最短路距离

可分四种基本情形来获得

情形1 工作站位于存储区的西(东)侧

货位入口位于西(东)向的巷道上

情形2 工作站位于存储区的西(东)侧

货位入口位于东(西)向的巷道上

情形3 工作站位于存储区域的北(南)侧

遇到的第一个交叉巷道是北(南)向的

情形4 工作站位于存储区域的北(南)侧

遇到的第一个交叉通道是南(北)向的

在第一种情形下

存储货位(x_(le)y_(le))位于朝WS方向的巷道上

例如存储货位(x_(le)y_(le))位于西向的巷道上

而WS位于存储区的西侧

则最短路距离D表示为 等式(1)

在第二种情形下

存储货位(x_(le)y_(le))不在朝WS方向的巷道上

例如存储货位(x_(le)y_(le))位于西向的巷道上

而WS位于存储区的西侧

在本例中start intersection是最短路径上

向东行进方向的第一个交叉口

如果存储货位(x_(le)y_(le))西侧第一个交叉巷道是北向的

则start intersection为西北方向的十字路口

如果存储货位(x_(le)y_(le))西侧第一个交叉巷道是南向的

则start intersection为西南方向的十字路口

在这两种情况下

d_(lesi)= d_(cale)+l+2u+w

最短路距离D表示为等式(2)

在第三种情况下

工作站WS位于仓储区北侧或南侧

第一个交叉通道的方向朝向工作站

例如假设工作站WS位于存储货位以北

存储货位(x_(le)y_(le))位于西向的巷道上

存储货位SL以西的第一个交叉巷道为北向

start intersection是存储货位(x_(le)y_(le))西侧的交叉口

一般情况下

d_(lesi)= d_(cale)

最短路距离D表示为等式(3)

在第四种情况下

工作站WS位于仓储区北侧或南侧

第一个交叉通道的方向不朝向工作站

例如假设工作站WS位于存储货位以北

存储货位(x_(le)y_(le))位于西向的巷道上

存储货位SL以西的第一个交叉巷道为南向

一般情况下

可以选择两种可能的start intersection

一是第一个朝西的交叉巷道

其方向是朝向工作站WS的

二是第一个朝东的交叉巷道

其方向是朝向工作站WS的

如果选择第一种的start intersection

则最短路距离D表示为等式(4)

如果选择第二种的start intersection

则最短路距离D表示为等式(5)

第四种情形下

最短路距离D为D1和D2的最小值

上述公式适用于从存储货位SL

到工作站WS的最短路计算

也适用于从工作站WS到存储货位SL的最短路计算

根据上述公式

给定任一存储货位

都能够计算获得move 1和move 3的行程时间

即对应服务站点的服务时间

所有货位的行程时间已知后

即所有的服务时间都已知后

就能计算出行程时间对应的一阶矩和二阶矩了

排队网络中

一般闭合排队网络(CQN)求解方法比较成熟

因此求解SOQN的解析解时

往往先将SOQN按照一定规则

转化为等价的CQN模型后

再进行求解

按照以下步骤来求解SOQN模型

第一步

首先将SOQN中的同步站点去掉

转化为第一个闭合排队网络 CQN1

采用AMVA方法对CQN 1分析

得到 CQN 1的系统吞吐量 τ_(CQN 1)

第二步

将原来SOQN中的同步站点

替换为一个依赖于负荷的服务时间

服从指数分布的服务站点

转化为第二个闭合排队网络 CQN2

替换后的站点记为第S+1个站点

S是CQN 1中站点的数量

第S+1个站点的服务率v(r)= afor r > 1

与站点中机器人数量r成函数关系

这里a指的是订单的到达率

排队网络只有当a < τ_(CQN 1) 时

才处于稳态状态

即系统处理订单的速度要大于订单到达的速度

否则系统就会瘫痪

当 r= 1

即站点机器人没有空余排队时

该站点的服务率为v(1) = (1-a/τ_(CQN 1))a

采用同样的AMVA算法对CQN 2进行分析

可以得到CQN 2的系统吞吐量 τ_(CQN 2)

和站点s在有r个机器人时的排队长度L_s (r)s=12…S

第三步 单独分析站点S+1

计算该单站点系统的平均客户排队长度

即对应外部订单的平均排队长度

其他的评价指标也可以计算出来

机器人的利用率ρ_r=1 -L_r/R

这里L_r为第S+1个站点机器人队列的平均队长

R为系统中总的机器人数量

平均订单执行周期t_(oc)

记 L_i 为除S+1站点外

其他站点平均排队长度之和

即 L_i等于s从12到S的L_s (R)之和

然后平均订单执行周期为t_(oc)=(L_0+L_i)/a

工作站利用率ρ_(ws)

ρ_(ws)=τ_(CQN 2)*v_(ws) *ES_(ws)

这里v_(ws)是工作站的访问率

ES_(ws)是工作站的平均服务时间

接下来简单介绍下AMVA算法的基本思路

AMVA算法中用到以下符号约定

S 为服务站点的数量

R为机器人的数量

ES_(rems)为服务站点s处

完成第一个任务还需要的时间的期望值

ES_s为服务站点s的服务时间的一阶矩

即均值

ES_s^2为服务站点s的服务时间的二阶矩

L_s (r)为当系统里有r台机器人时

服务站点s

包括正在服务的机器人在内的

机器人排队长度的期望值

L̃_s(r)为当系统里有r台机器人时

服务站点s

不包括正在服务的机器人在内的

机器人排队长度的期望值

Q_s (r)为系统中有r台机器人时

服务站点s中所有服务台都处于忙碌状态的概率

p_s (i│r)为当系统里有r台机器人时

服务站点s中有i台机器人的概率

τ(r) 为当系统里有r台机器人时

系统的吞吐量

ET_s (r)为当系统里有r台机器人时

服务站点s的提前期

即服务站点s完成当前已经到达的订单所需要的时间

c_s为服务站点s中的服务台的数量

v_s为服务站点s中的访问率

首先进行初始化

并进行预处理

计算各个服务站s处

完成第一个任务还需要的时间的期望值

然后依次对每一个并行服务台进行迭代求解相关参数

步骤(a)计算每个服务站点

完成当前已经到达的订单所需要的时间

该时间包括三个部分

一 正在接受服务的订单完成所需剩余时间

二 完成队列前方正在等待服务的订单所需时间

三 当前订单自身所需的服务时间

步骤(b)计算系统里有r台机器人时

系统的吞吐量

当系统包含r个机器人时

其吞吐量也等于单位时间所处理的任务数

分母为将CQN中所有的任务

都处理完所需要的时间

分子为任务的数量

步骤(c)在假设 p_m (k│r)=p_m (k│r-1) 时

根据稳态系统中流入系统的流量

等于流出系统的流量关系式

计算获得 p_s (b│r)

即当系统里有r台机器人时

服务站点s中有b台机器人的概率

步骤(d)计算当系统里有r台机器人时

服务站点s中所有服务台都处于忙碌状态的概率

这里有两种可以转变为全忙的情形

如图所示

仍然考虑系统均衡状态下

流入流量等于流出流量的关系式

推导出全忙概率

步骤(f)和步骤(g)则根据稳态系统中的little法则

计算出对应的机器人排队长度的期望值

以上就是本讲的内容

下一讲将介绍AVS/RS系统的建模分析方法