电能计量设备自动检定流水线调度优化研究.pdf

电能计量设备自动检定流水线调度优化研究 倡 黄友朋 ，方彦军，唐猛，孙卫明 （ 广东电网有限责任公司电力科学研究院 广东省智能电网新技术企业重点实验室，广州 ； 武汉大学 自动化系，武汉 ） 摘要：针对检定流水线易出现拥塞和饥饿现象的问题，提出了一种基于可拓层次法的改进动态优先级调度策略 （）。 首先通过对问题模型进行分析，得出影响流水线运行效率的因素；其次运用可拓层次法得到各并行 队列的动态优先级，控制器则选择优先级最高的队列作为服务队列；最后将提出 策略与 、 进 行分析比较，表明 充分考虑了任务队列的变化及系统的需求，将队列的 和 保持在一定范围 内，能够提高检定线及立库的运行效率。 关键词：检定线；动态优先级；可拓层次法 中图分类号： 文献标识码：文章编号：- （）- - research on automatic verification flow- shop optimization scheduling of electric energy metering equipment ， ， ， （1guangdong provincial key laboratory of smart grid technology， electric power research institute of guangdong power grid corp， guangzhou 510080， china 2 department of automation， wuhan university， wuhan 430072， china） abstract： ， （） ， - ， - ， - ， ， ， - - keywords： - ， ， 倡 基金项目：国家自然科学基金资助项目（）；中央高校基本 科研业务费专项资金（）；广东电网公司电力科学研究院（- - - ）；广东省智能电网新技术企业重点实验室资助项目 （） 引 言 自 年智能电网与智能用电概念的提出，各 省级电力公司相继建立起电能设备计量中心，为实 现计量装置试验、检定和仓储配送的“一体化、集约 化和自动化”，全面提升计量装置的集约化、精细化 管理水平，提供了坚实的软硬件平台基础 。 电能 设备计量检定中心将自动化仓储技术、物流输送技 术与电能计量器具的自动检定流水线系统有机的结 合起来，实现仪表的集中采购、集中检定、集中仓储、 集中配送等一系列作业的智能化、自动化。 由于涉及的电能计量器具数量之大，检定程序 之繁琐，并存在多条并行且不同类别的检定线（单相 表、三相表、计量自动化终端及互感器），因此需要对 各检定线的任务分配进行优化，来实现检定线与仓 储之间的衔接，也是提高整个系统运行效率的关键。 目前对于此类多队列调度问题，常用的策略有：先来 先服务调度法（）、优先级调度法（）、加权轮 第 52 卷 第 18 期电测与仪表vol 52 no 18 2015 年 9 月 25 日electrical measurement instrumentationsep 25，2015 转调度（）、加权公平队列轮询算法（）、基 于服务曲线的队列调度法等 。 另外，一些学者根 据这些方法的不足也提出了一些改进算法，如：胡塞 等 提出了一种改进的动态轮转算法，该算法对时 间片长度的选取进行改进，缩短了任务的平均等待 时间。 教授分析了任务的服务时间与每次 轮转完成的任务数量之间的关系，提出了一种两级 队列的时间片轮转算法。 汤灿恩等 提出了一种基 于先验知识的动态分配资源调度策略，缩短了任务 的平均带权周转时间，从而提高了系统的资源利用 率。 上述方法虽然已经进行了一些改进，但不适应 于所有情况，因此针对不同的问题需要对调度策略 进行调整。 文中运用基于非抢占式的动态优先级排 队模型来解决检定线的调度问题，该模型对系统各 通道的状态进行检测，分析得出影响检定线效率的 因素，并运用层次分析法综合确定各个队列的服务 等级，最终选择服务等级最高的节点进行服务。 从 而实现智能立库与四条流水线之间的 “无缝对接”， 并防止各流水线出现“停滞”及“饥饿”现象。 模型的建立 调度问题的描述 如图 所示，系统中有四条检定线，每条检定线 分别含有进、出两条通道，横向 小车负责八条通 道的任务分配，其中每条通道有两个缓存区且容量 均为 q。 图 系统示意图 将四条检定流水线共八条通道（各含有两个进 出通道）看成八个不同的任务队列，每个任务队列都 有各自的优先级，系统在进行四条流水线调度时，会 按照优先级的先后来响应任务队列：具有最高优先 级的通道先被响应，优先级排位靠后的通道只有等 待优先级排位靠前的任务队列完成后才能被响应。 若两个任务队列的优先级相同，则系统按照先来先 服务的原则进行响应。 模型由 个中心控制器和 个任务队列组成，对 队列的服务采用单一服务，即控制器只对被选中的 队列内的 个任务进行响应，服务过程中到达的任务 只能在下一轮查询到该队列满足条件时才进行服 务。 模型控制原理图如图 所示。 由于每个通道缓存区的容量都是有限的，即现 有任务队列的长度是有约束条件的（不能超过其最 大容量），因此队列优先级的分配要同时考虑到任务 队列的现有长度、未来一段时段内任务队列的变化、 及系统的需求。 图 模型控制原理图 影响因素及其无量纲化处理 影响因素 令 t 时刻八个队列缓存区中的任务数量为 mi（i ， ），在 t t t 时段（即：时间片）内（如： ）缓存区中的任务队列长度变化量为 ki（ki），（i ， ），各队列的初始综合优先级为 pi（i ， ， ），t 时刻的综合优先级为 p i t（i ， ），系 统中各队列的优先级的更新间隔为 t，各缓存区的 容量均为 q。 （）当前任务队列长度 x 对于 类队列，属于等待队列越长优先级越高 型，即极大型，则令此类队列中的任务数为 ai； 对于 类队列，属于等待队列越短优先级越高 型，即极小型，则令此类队列中的任务数为 bi。 （）在 t t t 时段内任务队列变化量 第 52 卷 第 18 期电测与仪表vol 52 no 18 2015 年 9 月 25 日electrical measurement instrumentationsep 25，2015 对于 类队列，只考虑将要到达缓存区的任务 数量，属于极大型因素，则此类队列的任务变化量 为 k i； 对于 类队列，只考虑将要离开缓存区的任务 数量，属于极大型因素，则此类队列的任务变化量 为 k 。 （） 立库侧队列缓存区任务变化的时间能耗 积 x 由于系统按照时间能耗积来进行货位分配，因 此所有出入库货物所需的时间能耗积已知，且时间 能耗积越小，表示系统对其需求越大，需优先考虑。 对于立库侧 类队列，只考虑 t t t 内将 要进入该缓存区任务所需的时间能耗积的总和 ai（i ，）； 对于立库侧b 类队列，只考虑 内将要 离开该缓存区任务所需时间能耗积的总和 b（ ， ，）。 影响因素的无量纲化 对于成本型（极小型）指标，其数值越小，越优 先，其无量纲化的处理公式为： xm xm尘 a （b x m b a ） a x mb xm辰 b （） 对于效益型（极大型）指标，其数值越大，越优 先，其无量纲化的处理公式为： xm xm辰 a （x mb a b ） b x ma xm尘 b （） 式中 xm为第 m 项影响因素的无量纲化值；xm为该 影响因素的实际值； 为该指标统计样本的最优值， 为该指标统计样本的最差值；为 为参数变化对优 先级的影响程度，本文取为 。 可拓层次法 可拓层次评估法的步骤 （）确定物元经典域、节域及待评估物元 确定综合评估各影响因素的可能量值范围，并 根据需要确定各影响因素所对应状态的量值范围， 再确定物元模型的经典域及节域 。 经典域及节 域的合理确定是影响评估准确性的重要因素。 待评估物元是根据待评估物元所监测到的数据 或分析结果量化确定的。 （）确定各影响因素权重 各影响因素的权重需满足如下条件： n i wi（） （）计算各影响因素优先等级的关联度 要计算待评估物元关于各优先等级的关联度 时，首先必须计算各影响因素关于各优先等级的关 联度，然后再对之求加权和即可得到。 令： kj（vi） （vi，vji） （vi，vpi） （vi，vji）， （v i，vpi） （vi，vji） （vi，vji） ， （vi，vpi） （vi，vji） （） 式中 （vi，vij）、（vi，vpi）分别表示点与区间 vij和 vpi 的距；kj（vi）表示第 i 个影响因素关于优先等级的关 联度，关联度的取值范围是整个实数轴。 （）计算各优先等级关联度 对于待评估物元，其各优先等级的关联度为： kj（p） kj（p）， j （，m）（） 式中 kj（p）是待评估物元中各指标关于各优先等级 的关联度在考虑指标重要性下的综合值，表示待评 估物元属于状态集合的程度。 （）由底层至上层可拓综合评估 设由下层物元到上层物元的评判变换矩阵为： j j（r）j（r）jm（r） j（r）j（r）jm（r） 筹 j（rn）j（rn）jm（rn） （） 各子层物元r，r，rn 的分权重为 w （w，w，wn），则上层物元的可拓综合评判模型 为： k a j （k，k，km）（） 流水线优先级评估的过程与在建立多级物元模 型的发散思维方式相反，是对发散过程中得到的大 量物元进行至下而上的综合评价，最终给出各流水 线任务队列的优先级大小。 可拓层次决策模型 系统通过综合考虑队列的当前长度、t 时间内 的任务数量变化值及其时间能耗积，来计算得到每 一个队列的综合优先级。 系统服务队列决策模型图如图 所示。 第 52 卷 第 18 期电测与仪表vol 52 no 18 2015 年 9 月 25 日electrical measurement instrumentationsep 25，2015 图 系统服务队列决策模型图 指标权重确定方法 目前，指标权重确定方法主要有主观评估中的 层次分析法和客观评估中的权重评定法。 主观评估中的层次分析法（）虽在国内得到 了广泛的应用，但其评估过程依赖于判断矩阵的一 致性，文献 提出采用无需检验判断矩阵一致性的 群组判断。 评估权重的主要步骤是首先聘请 若干位行业内专家对同层的各指标依据相对重要性 进行排序，然后根据一定的分级比例标度对重要性 相邻的两个指标进行重要性程度的量化，最后综合 所有专家判断的结果确定出最终的指标权重。 客观的权重评定方法，文献 提出采用熵权法。 熵权法是一种根据各项指标观测值所提供的信息量 的大小来确定指标权重的方法。 熵权法首先是根据 各指标的变异程度，利用信息熵计算出各指标的熵 权，然后通过熵权对各指标的权重进行修正，进而得 到较为客观的指标权重。 基于 群组判断的指标主观评估方法摆脱不 了评估过程中的随机性和评估专家主观上的不确定 性及认识上的模糊性，使评估过程存在很大程度的 主观臆断性，造成结果的可信度下降。 本文采用主观与客观相结合的定权方法：首先 采用层次分析法确定主观权重 倡 m，然后运用熵权 法得到各指标的客观权重，最后得到其综合权重。 采用熵权法时，若某项指标的熵值越小，则该指 标对对整体评价体系的作用越大，其权重就越大。 具体步骤如下： （） 计算第 m 项指标的信息熵 emk n m zm zm（） 式中 k n，n 为指标个数； zm xm n m xm，m 为 第 m 项指标无量纲化值。 （） 计算第 项指标的熵权 amgm n m gm（） 式中 gm表示指标之间的差异度，gm em。 （） 确定综合权重 m 倡 m m n m 倡 m m（） 式中 倡 m为层次分析法确定的主观权重，且满足： n m m。 实例分析比较 本节分别将文中提出的动态优先级调度策略与 策略、动态轮询策略 分别从平均等待时间 （， ）和平均队列长度（， ）两个方面对三种系统的调度策 略进行分析比较。 系具体参数如下： 队列个数 n ，各队列的初始长度为 li（i ， ，），各队列缓冲区的容量 limi（i ，）均 为， t 。 运用第 节所述方法可得到三个影响因素的综 合权重分别为：w ，w ，w 。 图 为平均等待时间比较图，图 为平均队列长 度比较图。 图 平均等待时间比较 从图 和图 可以看出，在一个小时的时间内， 虽然采用文中提出的改进动态优先级调度策略在最 第 52 卷 第 18 期电测与仪表vol 52 no 18 2015 年 9 月 25 日electrical measurement instrumentationsep 25，2015 初阶段的队列平均等待时间（） 和平均长度 （）较长，但由于考虑了未来 分钟内队列的变 化及系统的需求，因此在调度后期可以将系统的平 均队列等待时间好及队列平均长度保持在一定范围 内，具有较强的优越性，反之另外两种调度策略由于 忽略了系统的整体需求及实时变化，从而导致调度 后期队列的平均等待时间和平均队列长度逐步增 大，容易造成系统拥塞及“饥饿”现象的出现。 图 平均队列长度比较 结束语 针对检定流水线调度优化问题，提出了一种基 于可拓层次法的改进的动态优先级调度策略（- ）。 首先通过对问题模型进行分析；其次运用可拓 层次法得到各并行队列的优先级，选择最高优先级 的队列作为服务队列；最后将提出的 策略与 、 进行分析比较，表明 充分考虑了 任务队列的变化及系统的需求，将队列的 和 保持在一定范围内，能够防止系统出现拥塞或 饥饿现象。 参 考 文 献 肖勇， 孙勇， 孔政敏， 等基于 技术的电能智能计量 系统电力设备的全生命周期管理研究 科技管理研究， （）：- ， ， ， - - - - ， ， （）： - 龙贵山， 刘磊， 刘颖， 等电能表自动化检定及智能仓储系统研 究电测与仪表， ， （）： - ， ， ， - - - - ， ， （）：- ， ，“ ”， ， ， ， ， ， ，“ - ， ， - ， ， - ， （ ）： - 胡赛， 赵碧海， 熊慧军一种公平