陈丹^1,2, 朱华波³, 雒兴刚¹
1. 东北大学 信息科学与工程学院，辽宁 沈阳 110819;
2. 辽宁科技学院 管理学院，辽宁 本溪 117004;
3. 辽宁石油化工大学 经济管理学院，辽宁 抚顺 113001
收稿日期：2015-04-09
基金项目：国家自然科学基金青年基金资助项目 (71501033)；国家科技重大专项 (2012ZX07505-002)。
作者简介：陈丹 (1980-)，女，辽宁凤城人，东北大学博士研究生;
雒兴刚 (1971-)，男，新疆奇台人，东北大学教授，博士生导师。

摘要：在调研分析住院病人历史数据和医院业务流程基础上，建立了病人流路由分配的单排队多服务台队列倒V模型.以病房工作负荷公平性为目标，分析了RMI (randomized most-idle) 随机路由分配策略的马尔科夫过程在倒V模型中的应用，得到了系统的阻塞概率及病床占用率等相关性能指标参数，从理论上分析了RMI路由分配策略的公平性.对比了两服务台队列占用率、单位时间内服务的病人数量，结果验证了RMI策略的公平性.
关键词：医疗服务路由分配随机过程马尔科夫公平性
Patient Routing Based on Beds Fairness from Outpatient Department to Internal Wards
CHEN Dan^1,2, ZHU Hua-bo³, LUO Xing-gang¹
1. School of Information Science & Engineering, Northeastern University, Shenyang 110819, China;
2. School of Management, Liaoning Institute of Science and Technology, Benxi 117004, China;
3. School of Economics Mangement, Liaoning Shihua University, Fushun 113001, China
Corresponding author: ZHU Hua-bo, E-mail: hbzhu@mail.neu.edu.cn
Abstract: Based on theoretical analysis of flowchart and mass patient flow data, an inverted-V model with single patient queue and several heterogeneous server pools was established to describe patient routing allocation process. With the goal of routing allocation fairness for the beds of internal wards, the application of Markov process of randomized most-idle (RMI) routing policy in the inverted-V model was analyzed. The occupied and service rates of sever pools under different routing policies were obtained, and the routing policy fairness was analyzed theoretically. The experimental results showed the occupied and service rates for different server pool under RMI policy are more balanced than that of the average allocation policy.
Key Words: healthcarerouting allocationrandomMarkovfairness
本文从病房中每张病床工作负荷的公平性角度考虑动态路由分配策略.服务台的公平性问题会带来因为工作负荷不均衡进而影响服务质量和不同医疗单元之间收益的差距.那么如何分配才能使不同病房之间的病床占用率、每张病床单位时间服务的病人数量等系统性能指标接近呢？这需要进行病人流路由分配策略的研究.
本文研究工作主要以服务台的公平性为对象，文献综述以服务台公平性的研究为主线.最早关于公平性的文献是关于平等性的理论综述性文献[1]，这是研究顾客公平性和服务台公平性前期的理论基础.基于倒V模型路由分配策略，Armony等^[2-3]在QED规则下，分析了入口动态控制策略，利用LISF (longest idle-server-first) 策略，在大规模数据下分析了倒V模型中的路由分配，结果表明LISF策略是服务台公平性较好的策略.Armony^[4]在上述研究的基础上，进一步将动态路由策略扩展到了盲目路由策略 (blind fair routing).Atar等^[5]分析了WLIPF (weighted longest idleness pool first) 策略对于顾客到达的路由分配.Tseytlin^[6]根据以色列一家医院的病人流实际，分析了RMI路由分配规则的理论机理，并利用仿真进行了验证.Mandelbaum等^[7]在上述研究的基础上，分析并比较了LISF, RMI中路由分配的应用.文献[2-4, 6-11]主要研究了服务领域路由分配的效率及公平性.但是以病床工作负荷公平性为目标、考虑大规模数据及中国综合性医院实际流程的情况未见于文献.
1 模型及路由分配策略描述通过对大连某三甲医院实际业务流程调研和历史数据的分析^[12](3年共计7.2万条住院病人数据)，建立倒V模型，如图 1所示.
图 1(Fig. 1)

图 1 倒V模型下病人分配过程Fig.1 Flowchart for patient allocation under inverted-V model

本文主要选用了RMI策略，其定义为每个到达的病人分到哪个服务台的概率等于服务台队列里空闲服务台占总空闲服务台的比例.定义I_i(t) 为在t时刻服务台队列i的空闲服务台数量.新到达的一个病人将会以概率 (如果I_i>0，对于任意的i=1, 2, …, K) 进入不同的服务台队列，称这个路由规则为随机路由最大空闲策略.
2 随机过程分析利用马尔科夫过程刻画RMI策略在倒V模型中的应用过程.这个模型系统是一个连续时间的马尔科夫链，状态空间为Y={Y_t, t≥0}，每一个状态是一个K维向量y=(y₁, y₂, …, y_K)，y_i是在服务台队列i处于忙期的服务台数量，y_i∈{0, 1, …, N_i}.状态 (N₁, N₂, …, N_i) 意味着整个系统处于忙期，定义此时的状态为 (N).定义为状态y时所有处于忙期的服务台数量.系统的状态空间S={0, 1, …, N₁}×{0, 1, …, N₂}×…×{0, 1, …, N_i}，即系统状态转移变化见图 2.
图 2(Fig. 2)

图 2 RMI策略下无等待倒V模型状态转移Fig.2 Markov process under RMI policy in no-waiting room inverted-V model

从图 2可以看出每个状态下服务台队列中处于忙期的服务台及其数量.令π_i表示状态y时服务台处于忙期的概率；π₁₃²¹表示在服务台队列1中有2个服务台处于忙期，服务台队列3中有1个服务台处于忙期.生灭过程状态转移关系如下：
每一个状态是一个k维的向量y=(y₁, y₂, …, y_k)，y_i是在服务台队列i处于忙期的服务台数量，为状态y时所有处于忙期的服务台数量.
由于
利用马尔科夫过程分析队列部分，假设在状态l，顾客的到达率为λ_l，服务率为u_l，其状态转移过程如图 3所示.
图 3(Fig. 3)

图 3 队列部分状态转移过程Fig.3 Markov process with waiting queue

假设排队队列的最大容量为c，系统状态是可逆的，由平衡公式可得
由于,
针对存在排队系统的多服务台队列系统，由图 4可知，,
图 4(Fig. 4)

图 4 RMI策略下倒V模型状态转移Fig.4 Markov process under RMI policy in inverted-V model

由于
定义系统在稳态下的队长为L_q，平均等待时间为W_q，P(W_q>0) 意味着系统所有的服务台处于忙期，因此病人的平均等待时间W_q概率分布满足
系统中队长的分布为
式中，
当系统所有服务台都处于忙期时，即在无等待队列中出现阻塞的概率为
系统的服务强度可以用ρ来表示：
按照系统稳态的必要条件，要求ρ＜1，假设系统的排队可以无限长，则，
又因为
所以，
假设排队队列的最大容量c→∞，
进而,
3 RMI公平性的实验分析1) 实验设计:以两服务台队列的倒V模型为例，假设病人为同质，进入系统符合参数为λ的泊松分布，λ>0，有K=2个平行并列的服务台，每个队列的数量为N_i, i=1, 2，N₁+N₂=N.服务台为异质，即每个服务台的服务时间不同.假设服务台i=1, 2符合参数为u_i的指数分布，u₁>u₂，整个系统队列的等待时间是无限的.其参数设计为λ=(10, 500)，u₁=2, u₂=1，N₂=2N₁=(6, 80).
比较对象：平均路由分配策略与RMI策略.
需要计算对比的指标：两服务台队列占用率及单位时间内每个服务台服务的病人数量及系统的阻塞率.
2) 计算结果:利用Matlab计算在RMI策略下每个服务台队列的占用率及单位时间内服务的病人数量 (服务效率) 及系统的阻塞率.选取的参数为N₁=10，N₂=20，λ=(10, 500).
首先对RMI策略和平均分配策略下服务台队列的占用数进行对比，选取N₂=2N₁=10，N₂=2N₁=20两组实例进行分析.从图 5可以清晰地看到，RMI策略下两服务台队列占用数对比接近于1，说明两服务台队列的占用数十分均衡，这是RMI策略对于服务台公平性的最好体现.平均分配策略虽然在传统意义上认为是公平性比较好的路由分配策略，但是由于两服务队列服务数的差距，导致占用数出现较大差距.因为不论是理论分析还是数值实验，RMI策略都是公平性最好的路由分配策略，而平均分配策略却不是.
图 5(Fig. 5)

图 5 不同策略服务台队列的占用数Fig.5 Occupied number of sever pools under different routing policies (a)—N2=2N1=10；(b)—N2=2N1=20.

对RMI策略和平均分配策略下服务台队列的服务人数进行对比，依然选取N₂=2N₁=10，N₂=2N₁=20两组实例进行分析，如图 6所示. RMI策略下两服务台队列占用人数对比接近于2，服务台队列1的服务人数是服务台队列2的近2倍，这和理论分析结果类似.
图 6(Fig. 6)

图 6 不同策略服务台队列的服务效率Fig.6 Service rate of sever pools under different routing policies (a)—N2=2N1=10；(b)—N2=2N1=20.

4 结论结合医院的实际业务流程，针对病人流从门诊到住院过程的路由分配问题，以病房中病床工作负荷公平性为目标，进行了RMI随机路由分配策略的马尔科夫过程分析.对RMI随机路由分配策略的公平性进行了理论和数值实验分析，验证了RMI随机路由分配策略对于病房工作负荷均衡的公平性.
参考文献

[1]	Huseman R C. A new perspective on equity theory:the equity sensitivity construction[J].The Academy of Management Review, 1987, 12(2): 222–234.
[2]	Armony M. Queueing dynamics and maximal throughput scheduling in switched processing systems[J].Queueing Systems, 2003, 44: 209–252.DOI:10.1023/A:1024714024248
[3]	Armony M. Dynamic routing in large-scale service systems with heterogeneous servers[J].Queueing Systems, 2005, 51: 287–329.DOI:10.1007/s11134-005-3760-7
[4]	Armony M. Blind fair routing in large-scale service systems with heterogeneous customers and servers[J].Operations Research, 2013, 61(1): 228–243.DOI:10.1287/opre.1120.1129
[5]	Atar R.Mandelbaum A, Reiman M. Scheduling a multi-class queue with many exponential servers:asymptotic optimality in heavy traffic[J].Annals of Applied Probability, 2004, 14(3): 1084–1134.DOI:10.1214/105051604000000233
[6]	Tseytlin Y.Queueing systems with heterogeneous servers:improving patients' flow in hospitals[D].Haifa :Haifa Technion, 2007.
[7]	Mandelbaum M, Tseytlin Y. On fair routing from EDs to hospital wards[J].Management Science, 2012, 58(7): 1273–1291.DOI:10.1287/mnsc.1110.1491
[8]	Armony M, Mandelbaum A. Routing and staffing in large scale service systems:the case of homogeneous impatient customers and heterogeneous servers[J].Operations Research, 2012, 59(1): 50–65.
[9]	Atar R. A diffusion model of scheduling control in queueing systems with many servers[J].Annals of Applied Probability, 2005, 15(1B): 820–852.DOI:10.1214/105051604000000963
[10]	Atar R. Central limit theorem for a many-server queue with random service rates[J].Annals of Applied Probability, 2008, 18(4): 1548–1568.DOI:10.1214/07-AAP497
[11]	Atar R.Shwartz A. Efficient routing in heavy traffic under partial sampling of service times[J].Mathematics of Operations Research, 2008, 33(4): 899–909.DOI:10.1287/moor.1080.0325
[12]	朱华波, 唐加福, 宫俊. 一类存在堵塞无等待串联排队的医院病床配置方法[J].东北大学学报 (自然科学版), 2014, 35(8): 1088–1092. ( Zhu Hua-bo, Tang Jia-fu, Gong Jun. Beds allocation in no-buffer tandem queuing system with blocking for healthcare unit[J].Journal of Northeastern University (Natural Science) , 2014, 35(8): 1088–1092.)