通用型移液及自动化平台(以下简称移液平台)具备标准化的液体转移能力，并能够提供一系列自动化解决方案，是生命科学研究、化学研究和临床诊断实验室自动化的重要设备．移液平台既可以作为独立的产品直接为实验室用户提供系统的移液及自动化服务，又可以通过定制模块扩展为定制化仪器．在实验室应用中，每个完整的实验过程均可被视为一个项目，而随着实验室自动化需求的发展，几乎总是同时执行多个项目．为了更好地发挥平台效能，优化调度算法、提高平台的处理能力势在必行．多个检测过程(或样品处理过程)作为项目集合，彼此之间不存在紧前关系，且不同项目的任务之间也不存在紧前关系[1]．多个项目运行于移液平台之上，由平台统一调度，共享并竞争该平台的资源，是一个典型的集中式资源约束多项目调度问题(CRCMPSP)．资源约束多项目调度问题(RCMPSP)是强NP-Hard问题，其求解算法可分为精确算法、近似算法和智能优化算法等几大类．早期的研究一般采取如0-1规划、整数规划法、枚举法和分支定界法等精确算法[2]，但随着项目数量增加，计算量急剧增加，以上算法难以实施．近似算法主要采取基于优先级规则为基础的启发式算法，通过各种调度策略来实现近似最优调度[3-4]．智能优化算法通过种群进化的形式，给出最优调度方案，解决多种约束条件下的柔性作业车间调度问题，对特定的问题都给出了较好的结果[5-6]．操作系统的任务调度是另一类常见的任务调度问题，主要解决计算机资源在随机任务访问情况下的调度问题．在调度过程中一般须要考虑调度策略的公平性、可实施性和系统的负载均衡等评判标准[7]．操作系统常用的任务调度策略包括先来先服务(FCFS)、最短任务优先、最短剩余时间优先、轮转调度、优先级调度、多队列调度和基于多级反馈队列的轮转调度等[7-8]．而对于实时操作系统，常见的调度策略还有最早截止时间任务优先(EDF)[9]和最小裕度优先(LLF)[10]等．目前移液平台调度问题研究较多的算法有流水式随机调度算法、样品进样顺序优化算法和分层调度算法等．流水式随机调度算法，即“随机组合、随机进样”，样品信息根据终端用户的输入顺序依次随机进入仪器控制系统，对于待执行任务，根据“FCFS”策略进行调度[11]．与流水式随机调度算法相比，样品进样顺序优化算法通过优化样品进样顺序改善仪器效率．文献[12-13]以最短完成时间为目标，将多项目调度问题转化为非对称旅行商问题(ATSP)，并采用遗传算法对已知检测作业对应的多个项目进行求解．作业分组优化算法，针对大量采用批处理型模块的应用从作业分组方式的角度进行作业调度问题研究[11,14]．本研究在流水式随机调度算法基础上，参考计算机实时操作系统的任务调度策略，采用基于延迟时间的动态优先级优化调度策略，提高有限资源约束下的平台服务能力．1 移液平台调度问题模型1.1　问题分析与一般的资源约束多项目优化问题相比，移液平台调度问题具备如下特点．a．任务低延迟需求．在通常的任务调度问题研究中，一般不独立考虑任务延迟，但由于试剂反应过程对于反应时间的敏感性，因此移液平台对任务的计划外延迟有较高的要求．b．任务工期不确定．样品多样性及一些简单的即时异常处理流程带来任务工期的不确定性．c．任务不可分性．项目的各子任务可以在实施前根据用户实际需求进行粒度规划，将较复杂的任务分割为若干个连续任务，而任务在执行过程中的意外中断将给系统带来非必要的复杂性．d．及时性要求．由于样品处理过程的多样性和随机性及运行过程中的多种情况，因此须要仪器及时进行处理，给出调度结果．1.2　问题一般描述本研究结合移液平台的一般需求，将服务的对象确定为若干独立的项目，而项目是由多个任务组成的序列．各任务的期望开始时间由其前置任务的完成时间与期望时间间隔确定，对于特定任务其实际工期可认为符合正态分布．在此基础上建立移液平台的调度模型．基本符号及说明如表1所示．10.13245/j.hust.240622.T001表1移液平台项目调度模型的符号及说明符号说明i项目序号，i=1，2，…，I，其中I为项目个数j任务序号，j=1，2，…，Ni，其中Ni为项目i的任务数，(i，j)表示项目i的活动jEij任务(i，j)的计划开始时间Sij任务(i，j)的开始时间Fij任务(i，j)的完成时间Dij任务(i，j)的可接受延迟上限Rij任务(i，j)的相对任务延迟T最小化项目总完成时间A平均相对任务延迟L资源负载移液平台调度模型为min  f(Ω)={T,A}，式中：Ω为调度策略；T=maxi∈I(maxj∈Ni(Fij))-mini∈I(minj∈Ni(Sij))；(1)A=1∑i∈I(Ni-1)∑i∈I∑j∈Ni,j≠1Rij，(2)Rij=(Sij-Eij)/Dij. (3)上述移液平台调度模型的目标函数是项目总完成时间和平均相对任务延迟的最优．项目总完成时间(T)，即最晚结束的项目的结束时间与最早开始的项目的开始时间的差，如式(1)[15]．由于不同任务对于延迟敏感程度不同，因此通过相对延迟描述延迟的实际影响，如式(3)．平均相对任务延迟(A)为各项目所有任务的相对延迟的均值．由于相对任务延迟主要反映任务延迟对项目质量(试剂反应过程)的影响，因此不考虑项目起始任务的相对延迟，只对除了各项目的首个任务以外的全部任务的相对延迟进行求和，并计算均值，如式(2)．除了上述目标，资源利用率(即负载)也是反映系统运行状态的重要指标．对于特定资源约束的项目群而言，资源利用率为资源总实际使用时间与项目完成时间的比值，即L=1T∑i∈I∑j∈Ni(Fij-Sij)．2 研究方法2.1　调度算法基本框架如图1所示，参考操作系统中多优先级队列调度算法，新建任务提交请求，根据期望的执行时间由近及远进行排序，转移至就绪任务队列；在到达期望执行时间后，任务转移至待执行队列；在待执行任务队列中选择优先级最高的任务执行；而优先级相同的任务基于先来先服务(FCFS)的原则进行调度；执行后，任务完成．10.13245/j.hust.240622.F001图 1任务状态及其变迁图为了满足问题的实时性需求，根据基于当前延迟时间和基础优先级的动态优先级进行调度．当任务状态转换为待执行状态时为基础优先级，而后根据设定的动态优先级函数进行映射获得逐渐增高的即时的动态优先级，直至到达(或接近)可接受延迟上限，此时达到最大动态优先级．2.2　动态优先级函数拟分别采用Sigmoid，Tanh，ReLU，Leaky ReLu和SoftPlus函数作为基于延迟时间的确定动态优先级的函数．延迟时间的理想定义域宽度为可接受延迟上限值，即Dij，参考正态分布的相关知识，将Dij的1/6作为系数，有x=t-(Eij+forgDij)Dij/6  (x≥Eij)，式中：t为当前时间；forg为零点偏移系数．经上述变换后，x对应的区间最大值与最小值差为6．若forg取0.5，则x对应的区间为(-3，3)．对当前延迟时间进行标准化处理，函数图像如图2所示．10.13245/j.hust.240622.F002图 2动态优先级函数图像3 实验及结果分析3.1　实验内容对选定的不同数量的项目进行模拟调度，对比不同数量项目和动态优先级函数情况下的最小化项目总完成时间、资源负载、平均相对任务延迟和最大相对任务延迟(Rmax)．项目数据集包括1 200个随机项目，每个项目包括依次执行的8个随机任务，任务间的预期间隔为随机值(期望值为10 min，标准差为2 min)，任务的实际作业时间也为随机数(期望值为5 s，标准差为1 s)，与应用的实际数据大致相当，可接受延迟上限设置为预期间隔的5%．动态优先级调度算法分别采用Sigmoid，Tanh，ReLU，Leaky ReLU和SoftPlus作为动态优先级函数进行调度，同时与固定优先级算法进行对比．测试过程中，在上述随机项目数据集中依次选取多个项目，初始数量为12，步长为12，最大值为1 200．3.2　实验结果程序在Windows 10操作系统(64位)下运行，基于Qt平台(版本号5.14.2)，采用C++语言开发，硬件平台为中央处理器(CPU) Intel Core i7-10750H，内存容量为16 GiB．仿真运行结果如图3所示，可以看出：系统负载随项目数增加迅速增加，直至接近100%．平均相对任务延迟前期随项目数缓慢增长，后期迅速增长；当采用固定优先级时，平均相对任务延迟高于采用其他函数时的数值；Tanh和Sigmod函数后期性能与采用固定优先级时相当．最大相对任务延迟的变化趋势与平均相对任务延迟的变化趋势基本一致，且后期增加更为明显．10.13245/j.hust.240622.F003图 3不同动态优先级调度算法数据实验结果(1)设定初始项目数为20，步长为2，最终值为300，重新进行上述实验，结果如图4所示．10.13245/j.hust.240622.F004图 4不同动态优先级调度算法数据实验结果(2)由图4可以看出：初始时各种调度算法的平均相对任务延迟结果相近，随着项目数量增加，动态优先级算法明显优于固定优先级算法，而各种动态优先级算法性能相近．当项目数量较少时最大相对任务延迟数据频繁波动，当项目数量较多时趋于稳定，性能由高到低依次为LeakyReLUSigmoid≈Tanh≈SoftPlus≈ReLU固定优先级．根据可接受延迟上限的定义，取最大相对延迟小于100%的最大项目数，则以上算法支持的项目数由多至少依次为LeakyReLU(174)Sigmoid(170)≈Tanh(170)≈SoftPlus(170)ReLU(168)固定优先级(152)．当项目数增加至176时，所有调度策略的最大相对任务延迟达到实验可接受延迟上限(100%)．当项目数增加至246时，所有调度策略的平均相对任务延迟达到实验可接受延迟上限(100%)．其中，采用LeakyReLU做动态优先级函数的调度算法所支持的最大项目数比采用固定优先级的算法高14.47%，而当采用其他动态优先级函数进行调度并达到最大项目数时，资源负载也达到95.66%~96.23%，高于固定优先级的93.14%．如表2所示，当项目数量为固定优先级调度算法的处理能力上限(152)时，LeakyReLU的最大相对任务延迟为84.87%，较固定优先级算法改善13.41%，而实验中的其他算法该项指标为88.08%，较固定优先级算法改善10.14%．10.13245/j.hust.240622.T002表 2相同项目数量下不同动态优先级调度算法性能对比序号优先级函数IL/%A/%RMax/%1Sigmoid15295.4124.4688.082Tanh15295.4124.4688.083ReLU15295.1224.3888.084LeakyReLU15295.4224.4284.875SoftPlus15295.4124.4688.086常数15293.1425.8998.02当采用固定优先级算法时，资源负载率最低，为93.14%，而对于其他算法，此时的资源负载率为95.12%~95.42%，与固定优先级算法时的负载率相比，上升2.13%~2.45%．当采用ReLU作为动态优先级函数调度时，平均相对任务延迟最小，为24.38%，比固定优先级算法小5.83%，而其他算法该项指标值为24.42%~24.46%，优于固定优先级算法，性能与采用ReLU函数时相近．3.3　结果分析通过以上实验数据分析可知：采用动态优先级调度算法能有效改善系统性能，在有限的资源配置和可接受最大延迟限定下可以完成更多项目．如表2所示，当动态优先级调度算法采用LeakyReLU函数时，最大相对任务延迟数值最小，平均相对任务延迟的数值与该项指标最优的ReLU函数相近．Sigmoid与Tanh均为单调递增函数，且其导数先增后减，但后期增速缓慢，对延迟较大的项目调节作用下降．ReLU函数无上界，在前期为常数，不能及时反映延迟的影响，无法通过动态优先级算法的调节机制及时改善系统性能．SoftPlus函数与ReLU函数相对接近，其对应算法的性能表现也比较接近．Leaky ReLU函数无上界也无下界，是单调递增函数．在调度过程中，随延迟的增加，初期优先级增加缓慢，后期增速明显增快，可以有效改善待调度项目集合的延迟分布情况．4 结语本研究参考计算机操作系统调度算法，开发适用于通用型移液及自动化平台的基于动态优先级的调度算法，性能高于传统的先来先服务调度算法；同时，对比了多种不同的动态优先级函数在不同项目数量下的性能，实验结果显示Leaky ReLU函数性能总体较优．当前的调度算法实现随机作业的实时调度，在单一资源情况下，满足任务低延迟需求，并在任务工期不确定时仍有稳定表现．但随着项目数量增加，致资源负载过大的情况下，无法满足任务的低延迟需求，服务质量下降，有待进一步优化．后续的工作将尝试解决有限资源条件下的柔性作业调度问题，通过柔性调度关键资源改善系统服务质量下降的问题．当前的调度算法对任务进行尽早响应，也客观上导致后续任务环节造成任务积压．今后的研究工作将综合考虑最小化项目总完成时间和相对平均任务延迟，通过多目标优化改善有限资源条件下的系统服务能力．