回报衰减的多类顾客排队系统的调度方法研究

摘要

伤员分类救治调度、鲜活农产品运输管理以及关于延迟敏感的IT任务处理等系统，具有共同的特征:第一，完成单个任务的收益随等待延迟而降低;第二，问题系统中存在多种类型的服务对象，每类对象具有不同的衰减速率和服务时间等属性。本文将研究问题归纳在一类具有衰减回报和多类顾客的排队系统（简称，衰减多类系统）之中。衰减多类系统，处于生灭过程、拖期调度、多类顾客排队等研究的交叉领域，与当前排队及调度理论中不耐烦顾客和恶化工件等概念，在研究对象和应用领域方面有着本质区别。本文旨在以灾后稀缺耐用性医疗资源调度问题为背景，但不局限于医疗系统，研究衰减多类系统的共同性质和抽象决策模型。 为了深入地分析衰减多类系统，首先，将具体的灾后医疗资源调度系统作为切入点，基于应急医疗理论和运筹优化理论，通过文献研究和典型案例分析的方法，定义和界定灾后医疗资源调度系统，提出系统中有待研究的多灾点医疗资源分配调度(MASP)、多类伤员救治调度优先级(MCCSP)、多名伤员救治调度(MCSP)等三个问题。随后，以灾后医疗资源调度系统及其中调度问题为原型，根据排队理论，在抽象的衰减多类系统中定义顾客群的服务调度、顾客类的服务调度、顾客的服务调度等三个一般性调度优化问题。利用规划论、马尔可夫决策、柔性作业车间等方法和模型，开发解决一般性优化问题的算法。最后，通过模拟数值实验，验证所提出模型及算法的科学性，并将研究成果应用于灾后医疗资源调度算例，证明本研究的应用价值。按照以上研究范式，针对衰减多类系统及其调度决策模型的具体研究内容及结论如下: (1)顾客群的服务调度，以MASP问题为原型。顾客群是多名顾客构成的集合，群内顾客分为多个类型，每个顾客类型具有各自的衰减回报函数。顾客群是MASP问题中灾点的抽象。顾客群的服务调度模型，根据顾客群内顾客数量及结构、固定服务员、派出服务站内派出服务员数量、顾客群与派出服务站的距离等因素，在当前决策点制定决策方案，使系统在当前决策点与下一决策点间的时间段内顾客回报损失最小化。以汶川地震的医疗救援相关文献中的原始数据和统计资料为基础，结合计算机模拟数据，实施数值实验。实验结果表明，在灾后医疗资源调度应用中，顾客群的服务员分配优化算法较现行的主观经验决策方法（灾情优先和距离优先），救援效果有显著提升。 (2)顾客类的服务调度，以MCCSP问题为原型。顾客类是具有相同衰减回报顾客的集合。以顾客类为接受主体的服务调度决策模型，运用运筹优化理论和生存分析理论，研究多种顾客类之间服务优先级的动态规则，根据各顾客类的顾客数量、服务时间分布、回报衰减速率等因素，采用动态规划，在每个当前决策点，制定最优的顾客类服务调度方案，实现系统终止时刻总体回报最大化。数值实验在线性回报函数、一般的回报函数、伤员分类救治三种情形下构建，将提出的LE算法与R(t)rμ，SEST和TCF等经典基准算法比较。实验结果表明，在系统总体回报方面，LE算法显著优于基准算法。除验证算法的效率和可行性外，本研究还对LE算法的敏感性进行了分析。 (3)顾客的服务调度，以MCSP问题为原型。考虑每位顾客服务时间以及服务回报的差异，采用柔性作业车间模型描述调度问题，提出以顾客为接受主体的服务调度算法。顾客服务调度算法的主体是动态遗传算法，考虑了不确定事件对服务调度和决策方案的干扰，具有优秀的全局搜索能力以及健壮性。数值模拟实验以灾后医疗资源调度为例，结合典型重大自然灾害的实际统计数据，验证了顾客服务调度算法的有效性和可行性。实验分析扰动事件对结果的影响时发现，早期发生的计划调整通常会对系统结果产生较大的影响，而后期发生计划调整的影响则相对较小。最后构造比较实验，在相同条件下，发现顾客服务调度算法相较于顾客类服务调度算法在系统回报方面的优势。 衰减多类系统的特征归纳以及系统中三类调度方法的研究，在理论层面，拓展排队和调度理论的研究范围，丰富运筹排队和调度的研究体系;在应用层面，将具有衰减回报和多类顾客的排队系统的共性模型和抽象算法实例化到具体实践领域，可指导研究领域中的决策方案制定，实现资源利用效率的最大化，减少社会损失。

目录

声明

摘要

图目录

表目录

主要符号表

1 绪论

1．1 问题的提出

1．1．1 研究的背景

1．1．2 问题提出

1．1．3 研究的意义

1．2 相关研究

1．2．1 排队和调度研究中的回报函数形式

1．2．2 考虑衰减回报和多类顾客的调度研究

1．2．3 灾后医疗资源调度研究

1．2．4 研究评述

1．3 研究内容与技术路线

1．3．1 研究内容

1．3．2 技术路线

2 衰减多类系统分析：以灾后医疗系统为例

2．1 衰减多类系统与动态规划

2．1．1 排队系统

2．1．2 动态规划

2．2 灾后医疗系统的特征分析

2．2．1 灾后医疗中的检伤分类

2．2．2 生存分析理论与伤情演化

2．2．3 具有衰减回报的GIX／G／c／∞伤员排队系统

2．3 灾后医疗系统的调度问题

2．3．1 灾后医疗系统的目标

2．3．2 稀缺耐用性医疗资源界定

2．3．3 MASP问题

2．3．4 MCCSP问题

2．3．5 MCSP问题

2．4 本章小结

3 衰减多类系统中基于顾客群的服务调度优化

3．1 以MASP为原型的顾客群的服务分配问题

3．2 顾客群的衰减回报函数

3．2．1 顾客群的回报函数

3．2．2 灾点的伤员幸存期望函数

3．3 服务分配的效用模型

3．3．1 分配原则分析

3．3．2 效用模型

3．4 INLP的Lingo实现

3．4．1 Lingo介绍

3．4．2 顾客群服务调度的算法实现

3．5 模拟实验

3．5．1 实验参数

3．5．2 四川地震模拟实验

3．5．3 策略比较

3．5．4 具体算例

3．6 本章小结

4 衰减多类系统中基于顾客类的服务调度优化

4．1 以MCCSP为原型的顾客类服务调度问题

4．2 马尔可夫决策模型

4．2．1 损失模型

4．2．2 收益模型

4．3 启发式指数算法

4．3．1 LE算法

4．3．2 R(t)rμ算法

4．3．3 SEST算法

4．3．4 TCF算法

4．4 模拟实验

4．4．1 实验1：线性回报函数

4．4．2 实验2：一般回报函数

4．4．3 实验3：MCI检伤分类应用

4．4．4 敏感性分析

4．5 本章小结

5 衰减多类系统中基于顾客的服务调度优化

5．1 以MCSP为原型的基于顾客的服务调度问题

5．2 柔性作业车间模型

5．2．1 模型约束

5．2．2 优化模型

5．3 启发式遗传算法

5．3．1 染色体编码与解码

5．3．2 初始种群

5．3．3 适应度函数

5．3．4 选择算子

5．3．5 交叉算子

5．3．6 突变算子

5．3．7 算法步骤

5．4 模拟实验

5．4．1 实验说明

5．4．2 实验设计

5．4．3 结果讨论

5．5 本章小结

6 结论与展望

6．1 研究结论

6．2 主要创新点

6．3 研究展望

参考文献

攻读博士学位期间科研项目及科研成果

致谢

作者简介