一种业务实例完成时间负载相关估计方法-信息系统与工程研究所.ppt

一种业务实例完成时间的负载相关估计方法 作者:蒋新华,聂作先 报告人:聂作先 zxnie@163.com 中南大学信息科学与工程学院 1 问题背景 机械设备的订单式生产 流程 下单,采购,铸造,粗加工,精加工,装配,调试,完成 问题:下单到制造完成需要多长时间? 意义 合同期限 制造企业正确估计产能,改善生产组织 便于订货企业进行相关生产活动组织 1 问题背景 准确估计下单到制造完成需要的时间? 完成每个生产阶段所需时间是随机变量，因此估计结果也是一个概率期望值。 企业任务饱和程度和当前承担的任务在各生产阶段的分布（系统负载）决定了特定订单任务在各阶段的等待时间长短，增加了估计任务完成时间的变数。 2 问题描述 服务系统结构 又称串联排队网络 2 问题描述 服务系统约定： 1）业务实例按泊松过程单个到达； 2）系统允许排队，业务实例不会因为系统忙而自行离去，对已排队的业务实例按FIFO规则提供服务； 3）每个服务站仅有一个服务台； 4）每个服务台的等待队列长度不受限制； 5）不同业务实例在同一服务台上所需的服务时间相互独立且服从同一指数分布，服务台每次仅对一个业务实例提供服务。 2 问题描述 符号 ：t时刻第i个服务台的等待队列长度(含正在接受服务的业务实例) ，其中i=1,2,…,N； ：t时刻串联排队服务系统的状态，其中 表示某个业务实例C到达服务台1时看到的各服务台的排队情况 2 问题描述 符号 业务实例编号: 可以对业务实例C到达时看到的各服务台上等待队列中的每个业务实例编号，按照离C的距离由近至远的原则，恰好排在C前面的业务实例编号为C1，离C最远的业务实例编号为CM-1，特别地，业务实例C被编号为C0。 ：业务实例Ci离开第j个服务台的时间。 本文所需解决的问题可以描述为： 已知 ，求 。 3 问题分析 两级串联排队系统是最基本也是研究得最广泛的串联排队服务系统，本文也以此做为研究的切入点。 当前对串联排队网络系统的研究集中在统计平衡下系统各服务台的平均队长[9]、服务台空闲概率[10]以及系统吞吐量与业务实例平均逗留时间等[11]。 本文着重研究的问题是：对于特定业务实例，给定其到达串联排队服务系统时看到的各服务台的排队情况（称为该业务实例本次遇到的特定负载），估计其穿越串联排队系统所需时间。 3 问题分析 初始状态: 服务站 1 服务站 2 服务过程: 图2 服务台1服务过程 图3服务台2服务过程 3 问题分析 随机空闲时间分析 每个 IDLEi是一个随机变量，代表服务台为业务实例 提供服务结束后的一段随机空闲时间，注意到只有服务台2存在空闲时间，且空闲时间仅在为业务实例 提供服务结束后才开始出现，此后每为一个业务实例提供服务后，随后都存在一段随机的空闲时间。 3 问题分析 随机空闲时间分析 假设服务台1与服务台2对业务实例Ci的服务时间分别为X1i和X2i. 服务台2第一次出现的空闲时间 大于0的前提是服务台2将初始等待队列中的 个业务实例均服务完成后，等待了一段时间服务台1才将其初始等待队列中的第一个业务实例服务完成。 Y 的数学期望也不难求得，但其分布已不是指数分布。 3 问题分析 随机空闲时间分析 服务台2第二次出现的随机空闲时间 的情况. 大于0的前提是服务台2将初始等待队列中的 个业务实例及业务实例 均服务完成后，等待了一段时间服务台1才将其初始等待队列中的业务实例 服务完成。 Y1 3 问题分析 随机空闲时间分析 服务台2第n个空闲时间 数学计算的困难: 求取IDLEn的分布需要建立在 IDLEL1（0）+1, IDLEL1（0）, ……, IDLEn-1的基础之上,且服务台2的各个随机空闲时间不满足特殊的分布，其计算难度迅速上升，因此，利用概率公式求解本文提出的问题十分困难。 计算公式与业务系统结构及系统初始状态相关,难以给出一个统一的计算公式. 4 业务实例排队系统的蒙特卡罗仿真 蒙特卡罗方法是利用随机数进行随机模拟的一般方法, 求解时通过大量重复实验得到问题的解。 借助于计算机，蒙特卡罗方法可以快速求解数学分析难以求解的问题，且其收敛速度不受问题的维数影响. 被运用于复杂数学问题的计算、随机过程的模拟、交通控制、网络管理等许多领域