基于FJSP的医疗救治系统调度优化研究_鹿国伟.pdf

基金项目:军队医学科技青年培育项目(19QNP108);军内科研计划重点项目(JK20182A030086);军内科研计划重点项目(JK20182A020170)收稿日期:2021-08-11 修回日期:2021-08-30 第 40 卷 第 4 期计 算 机 仿 真2023 年 4 月 文章编号:1006-9348(2023)04-0031-07基于 FJSP 的医疗救治系统调度优化研究鹿国伟,段德光,陶学强,张泽瑞(军事科学院系统工程研究院,天津 300161)摘要:将柔性作业车间调度(Flexible Job-shop Scheduling Problem,FJSP)模型引入到军队医疗救治系统调度研究中,构建起伤员排程和装备选择的数学模型;融合遗传算法和变邻域搜索算法改进粒子群算法,实现了伤员救治排程和装备分配选择的合理优化;以伤员救治及时率为目标,通过多次仿真调度实验对比,发现了军队医疗救治系统规律,为指挥员调度决策提供了参考,也验证了医疗救治系统调度模型的合理性和有效性。关键词:医疗救治系统;柔性作业车间调度;改进粒子群算法;调度优化中图分类号:R318;TP391 文献标识码:BResearch on Scheduling Optimization of Medical Treatment SystemBased on Flexible Job-Shop Scheduling ProblemLU Guo-wei,DUAN De-guang,TAO Xue-qiang,ZHANG Zer-ui(Institute of Systems Engineering,Academy of Military Sciences,Tianjin 300161,China)ABSTRACT:In this paper,the Flexible job-shop Scheduling Problem(FJSP)model was introduced into the re-search of military medical treatment system scheduling,and the mathematical models of wounded sorting and equip-ment selection were constructed.Secondly,the genetic algorithm and the variable neighborhood search algorithm werecombined to improve the particle swarm optimization algorithm,which realized the reasonable optimization of thetreatment schedule and equipment allocation.Finally,with the timely rate of wounded treatment as the target,the lawof military medical treatment system was found through multiple simulation and scheduling experiments,which pro-vides a reference for the commanders scheduling decision.KEYWORDS:Medical treatment system;Flexible job shop scheduling;Improved particle swarm optimization algo-rithm;Schedule optimization1 引言军队医疗救治系统涉及大量医护人员和各型医疗装备,它们共同作用构成了一个复杂系统,广泛运用于作战行动、自然灾害、传染病救治等突发紧急救援情景1。特别是战时伤病员大量集中产生,由于医疗救治系统装备类型和数量有限,经常出现伤员拥挤状况,造成伤员救治不及时,错过最佳处置时间。多类别装备资源和多样化装备数目需求组成的伤员救治排序构成了多资源调度问题,以往关于军队医疗救治系统调度研究较少,且缺乏系统性、整体性1-2,因此,如何立足现有军队医疗救治系统编配装备进行伤员救治排程,发掘医疗救治系统运用潜力具有重要研究价值。2 医疗救治系统数学模型2.1 问题描述伤员由救护车辆运送至军队医疗救治系统后,根据其伤情主要占用医疗救治系统的检伤分类模块、紧急救治模块、基本检查模块、外科手术模块、重症监护模块和伤员留治模块,总体过程如图 1。伤员救治过程是一个对于连续性和协调性要求很高的活动,前一个救治步骤没有完成,都不能进行下一个救治步骤。由于轻伤员对时间敏感性较小,时效性要求不高,对于伤员救治及时率影响不大,且涉及的装备较少,因此为了便于研究,本文以重伤员在医疗救治系统中调度优化为研究目标,并根据装备分类将伤员救治简化为检伤分类、紧急救治、基本检查、外科手术、重症监护等 5 个阶段,13各伤员根据其伤情对应不同的装备选择和处置时间。图 1 伤员在医疗救治系统内流转情况医疗救治系统中不仅涉及到大量医疗装备资源,而且伤员类型多样性和个体的差异性造成了医疗救治过程和装备占用时间不尽相同。因此,如何对伤员救治进行排程,发挥医疗救治系统装备的最大效能至关重要。军队医疗救治系统调度实质是在现有装备编配基础上对到达系统的各类伤员分配最佳救治顺序和装备资源,是非确定性多项式难题(NP-hard)的组合优化问题。由于上述多类别资源和多样化的资源数目需求组成的伤员救治排序构成了多资源的调度问题,可以将其抽象成多资源约束的柔性作业车间调度模型3-6。2.2 模型对比医疗救治系统调度与柔性作业车间调度对比见表 1,可以看出两者在调度对象、约束和规则等方面具有非常大的相似性,医疗救治系统调度是柔性作业车间调度问题在多重医疗装备资源约束条件下的变形和扩展。医疗救治系统调度问题不仅涉及多类装备资源,而且不同伤员占用各类资源时间不尽相同,同时由于伤员救治的特殊性,相对于车间调度增加了一些实际约束,比如救治时效窗口问题、伤员到达和死亡问题。表 1 医疗救治系统调度与柔性作业车间调度问题对比对比项医疗救治系统调度柔性作业车间调度调度对象伤员、流程、装备工件、工序、设备资源约束各类救治装备各类加工设备时间约束伤员存在救治时效窗口且受救治装备可用时间约束工序开始加工时间受到所选机器可用时间约束调度目标伤员救治及时率加工总完成时间操作顺序同伤员救治顺序不能颠倒,且不能同时占用多装备同工件加工顺序不能颠倒,且不能同时占用多设备可否中断某个救治阶段一旦开始不能中断某个加工工序一旦开始不能中断有无缓冲救治阶段之间存在缓冲,本过程完成后资源释放工件工序之间存在缓冲,本过程完成后资源释放2.3 模型构建医疗救治系统调度问题的数学模型可做如下描述:I 为救治伤员集合,M 为装备类型集合,J 为救治阶段集合,EJ 为伤员的核心处置阶段,ET 为伤员的最佳处置时间;Sijm表示伤员 i 在 j 阶段在装备 m 上的开始救治时间;Tijm为伤员 i 在 j阶段在装备 m 上的处置时间(处置时间随伤情变化);在建模过程中对于该调度问题做出如下假设:1)所有装备、伤员是相互独立的,不会相互影响;2)救治装备资源数量及状态在调度开始前已知;3)救治装备不会发生故障,准备时间忽略不计;4)伤员所需装备和时间在调度前已知,且不会随着排序而发生变化;5)再调度时,装备是非抢占式的,正被占用装备不受影响。假设该模型的调度目标是在考虑装备资源类型、数量变化和可用时间的相互约束影响下,确定伤员救治排程以使得伤员救治及时率最大。定义救治及时率为 F,即F=maxiIxiN(1)xi=1,j=EJj=1(Sijmyijm+Tijmyijm)2)(4)3)连续性约束:装备在任一阶段被占用时不能中断。3 改进粒子群算法3.1 算法整体流程基于柔性作业车间调度的医疗救治系统调度问题为离散的组合优化问题,目前求解算法主要分为人工智能算法和局部搜索算法等类型7,这些算法各有优劣,采用单一算法23很难实现快速求解目标函数的最优解。本文以粒子群算法(Partical Swarm Optimization,PSO)为基础4,8-10,融合遗传算法(Genetic Algorithm,GA)和 变 邻 域 搜 索 算 法(VariableNeighborhood Search,VNS)11思想,PSO 具有计算简单和效率高特点,但存在易早熟和陷入局部最优的缺点,而 GA 具有较强的多样性和群体寻优能力,同时考虑到两种算法都存在局部寻优能力差的缺点,引入 VNS,从而提高算法的效率和准确性。算法流程如图 2,首先,设置粒子群大小 N、迭代次数 gen等相关参数;然后,随机产生 N 个调度方案初始化粒子群,并计算适应度,记录个体最优粒子 pBest 和全局最优粒子gBest;其次,在粒子位置迭代更新时,将粒子作为 GA 的初始种群,通过选择、变异和交叉等方式更新粒子位置,产生性能更优的新一代群体,并计算适应度,更新 pBest 和 gBest;接着,采用 VNS 算法的插入、交换、倒置等方式进行局部寻优,更新 pBest 和 gBest;最后,判断是否到达最大迭代次,输出最优解和调度方案,并画出甘特图。图 2 算法流程图3.2 算法原理描述3.2.1 粒子编码与解码良好的编码与解码是实现调度优化算法的首要问题。本文中伤员各阶段之间联系紧密,前一阶段对后续阶段的影响较大,借鉴目前柔性作业车间调度中大多数采用基于工件排列的单层实数编码方式,将伤员救治按照顺序排队,即每个粒 子 编 码 位 为 伤 员 顺 序 号。如 图 3,粒 子 编 码 为“13231321”,编码出现的次数代表阶段数,即在第 1 阶段伤员救治排序为“J11J31J21”,在第 2 阶段伤员救治排序为“J32J12J22”,在第 3 阶段伤员救治排序为“J33J13”。基于伤员排序的编码只是用于确定伤员在每个阶段的救治顺序,没有确定各阶段选择的装备。在解码时,考虑到图 3 粒子编码虽然本文中各类型装备数量不同,但是装备性能基本一致,采用随机分配方法,伤员在某一救治阶段时采取占用各空闲装备的概率相等。3.2.2 粒子初始化与位置更新相较于经典粒子群优化算法,本文中粒子群变化是离散的12-15,初始化时首先将粒子进行伤员救治排序的随机赋值;然后,重新定义离散粒子群优化算法的位置更新式(5),模拟当前状态、认知模式以及社会模式三部分对新位置的作用,并用工序顺序链表的更新代替新位置,同样记录 pBest 和gBest,通过不断迭代产生最优解。Xk+1i=c2 f2(c1 f1(h(Xki),pBestki),gBestk)(5)其中,Xki表示粒子第 k 次迭代中的位置(对应新产生的伤员排序列表),Xk+1i表示粒子第 k+1 次局部迭代中的位置,pBestki和 gBestk表示粒子第 k 次迭代中所经历的个体最优位置和全局最优位置;c1、c2分别表示认知系数和社会系数,表示惯性权重,随着迭代次数递减,三个参数取值均在区间0,1内。令 Aki=h(Xki),代表当前状态更新,表示当前状态 Xki对个体新位置的影响,体现了当前状态 Xki对新位置的影响强度。具体操作为:r1为区间0,1的随机数,当 r1小于 时执行 h 变异操作,否则保留原粒子。Aki=h(Xki),r1 Xki,其它(6)令 Bki=c1f1(Aki,pBestki),代表粒子对自身历史最优解 pBestki的学习,c1体现了个体对自身历史最优解的学习强度。具体操作为:r2为区间0,1的随机数,当 r2小于 c1时,执行 f1交叉操作,否则保留原粒子。Bki=f1(Aki,pBestki),r2 c1Aki,其它(7)令 Xk+1i=c2f2(Bki,gBest