排队系统的优化目标与最优化问题

排队论,1 排队论过程的相关概念2 输入与服务时间的分布3 生灭过程4 最简单的排队模型5 比较复杂的排队模型6 排队系统的优化目标与最优化问题7 排队系统的模拟,1 排队过程的相关概念,任何排队服务系统可以描述为以下四个方面：,顾客总体,队伍,服务站,服务系统,输出,输入,输入指顾客到达服务系统的情况。按到达的时间间隔分：确定，随机；按到达人数分：单个，成批；按顾客源总体分：有限，无限；etc.输出顾客从得到服务到离开服务机构的情况。服务时间：定长，随机；服务人数：单个，成批。排队服务规则损失制与等待制，在等待的情况下：先到先服务（FCFS）；后到先服务（LCFS）；带优先服务权（PR）；随机服务（SIRO）。服务机构服务设施的个数、排列及服务方式。单站多站；串联并联；etc.,排队服务系统的分类记号（Kendall,1953）： 输入/输出/并联的服务站数,M代表泊松输入或负指数分布的服务时间，D代表定长输入或定长服务时间，Ek代表k阶Erlang distribution的输入与服务，GI代表一般独立输入，G代表一般服务时间分布。如M/M/n代表顾客输入为泊松分布，服务时间为负指数分布，由n个并联服务站的排队服务系统；D/G/1；GI/Ek/1.上述记号都指顾客总体数量无限、系统中的队长可以无限、排队规则为FCFS.,国际排队符号标准会将分类记号扩充到六项： (a/b/c):(d/e/f),d为系统中最多可容纳的顾客数；e为顾客源总数；f为排队服务规则。,系统状态：指一个排队服务系统中的顾客数；队长：系统中等待的顾客数；N(t)：时刻t排队服务系统中的顾客数；Pn(t)：时刻t系统中恰好有n个顾客的概率；n：单位时间内新顾客的到达数；n：整个系统的平均服务率；S：排队服务系统中并联的服务站个数；稳定状态：当一个排队服务系统开始运转时，系统状态在很大程度上取决于系统的初始状态和运转经历的时间，但过了一段时间后，系统的状态独立与初始状态及经历的时间，这时称系统处于稳定状态。,2 输入与服务时间的分布,2.1 最简单流的定义2.2 最简单流的一些性质2.3 负指数分布的服务时间2.4 k阶Erlang分布2.5 关于概率分布的检验,2.1 最简单流的定义,最简单流：是指在t这段时间内有k个顾客来到服务系统的概率vk(t)服从泊松分布，即： 当k=0时有 v0(t)=e-t满足下面三个条件，称为最简单流：平稳性：在一定时间的间隔内，来到服务系统有k个顾客的概率仅与时间的长短有关；无后效性：即在不相交的时间区间内到达的顾客数是相互独立的；普通性：指在足够小的时间区间内只能由一个顾客到达，不可能有两个以上顾客同时到达。,2.2 最简单流的一些性质,参数代表单位时间内到达顾客的平均数。在t,t+t时间内没有顾客到达的概率为：在t,t+t时间内恰好有一个顾客到达的概率为：,2.3 负指数分布的服务时间,若用f(t)代表服务完毕离去的两个顾客的间隔时间t的概率密度函数(t0),F(t)代表t的概率分布函数，则有：,负指数分布具有下列性质：,每个顾客的平均服务时间为1/。当服务设施对顾客的服务时间t为参数的负指数分布时，则有：在t,t+t内没有顾客离去的概率为1- t；在t,t+t内有一个顾客离去的概率为 t；若t足够小的话，在t,t+t内有多于两个以上顾客离去的概率为 (t )(t).如果服务设施对顾客的服务时间服从负指数分布，则不管对某一个顾客的服务已进行了多久，剩下来的服务时间的概率分布仍为同原先一样的负指数分布。,若干独立的负指数分布的最小值是负指数分布；若按依次到达的间隔时间统计，顾客流服从负指数分布，则对同一顾客流若按单位时间到达的数量统计，它服从泊松分布。,2.4 k阶Erlang分布,k个相互独立具有相同参数的负指数分布称为k阶Erlang分布。一般假定组成k阶Erlang分布得k个负指数分布的参数均为k，即每个负指数分布的期望值均为1/ k，因而k阶Erlang分布的概率密度函数：,2.5 关于概率分布的检验,通常采