分组网络调度算法研究
电网经济调度方法研究与应用
电网经济调度方法研究与应用 发表时间：2019-09-11T09:45:53.767Z 来源：《中国电业》2019年第10期作者：沈宗宝 [导读] 电能因具有瞬时性而难以保存，但作为现代工业社会的支柱性能源，必须对其进行有效调度，才能较好地加以利用。 四川西昌电力股份有限公司四川省 615000 摘要：电能因具有瞬时性而难以保存，但作为现代工业社会的支柱性能源，必须对其进行有效调度，才能较好地加以利用。 关键词：电网经济；调度方法；研究；应用 1电网经济调度概述 1.1基本概念 电网经济调度是根据电网运行的基本原理，在保证安全、可靠运行和满足用电需要、电能质量的前提下，通过调整电网运行方式，制定各站(厂)或线路之间的最优负荷分配方案等多种技术方法和管理手段，对电网资源进行优化配置，以降低运行成本。近年来，随着用电量的逐年增加，电力系统也在快速发展。在保障电网安全、稳定运行的条件下，增强电网的经济运行能力，即是调度运行人员的重要工作，也是电力企业经营行为的关键内容。 1.2经济调度一般采取的措施 1.2.1根据电网传输需要，采取实时经济调度在保证电力供应量与实际相符的情况下，调度部门应尽可能降低能量损失，提高电网的经济性，如在用电低谷时期减少电网的电力供应量，在用电高峰时期增加电网的电力供应量。 1.2.2根据电网运行状况，采取运转备用调度在满足电力传输高峰要求的情况下，主要选用运转备用调度的形式增强电网的经济性。在保证电力线路正常运行、维护、维修的同时，适时关闭某些电力线路，可以减少电网自身产生的损失。 1.2.3根据对环境的污染状况，采取环境保护调度在生产及传输电能的过程中，为了减少其对环境的污染，需要参考电网的实际污染状况进行环境保护调度，以增强电网的经济性，同时降低电能损失。 1.2.4根据电网负荷状况，采取稳定约束调度在确保电网安全运转的条件下，需要根据电网的负荷情况，对电网进行负荷预测和安全控制。可采取安全约束调度的方式，减小电网负荷，降低电能损失，提高电网的经济性。 1.3存在的问题 随着电力工业的发展，手工管理方式已不再适应电力生产的需要，信息的收集、存储、传输、查询、加工及决策等工作量越来越大。这就要求我们必须提高管理水平，通过建立计算机信息系统，改变原有的管理方式、体制和手段，以增加经济和社会效益。因此，安康供电分公司充分利用现有的PAS高级应用软件，研究开发了经济调度软件系统。 2PAS高级应用简介 PAS高级应用软件利用电网的各类实时数据进行在线分析，如开关状态、有功功率、无功功率等信息，辅助调度员通过制定最优的电网运行方式。安康供电分公司PAS高级应用软件是东方电子有限公司开发的系统，主要由调度员潮流、状态估计、网络拓扑和负荷预测四部分组成。 2.1网络拓扑 网络拓扑是PAS高级应用软件中的最基本功能，主要用于网络分析。它根据电网的遥信信息和多种元件的关系，确定地区电网的电气连接状态，产生调度员处理数据所需要的网络模型。为了保证计算结果的正确性，必须使所建的模型和实际的运行方式相一致。 2.2状态估计 状态估计是调度员潮流功能的基础。利用SCADA实时遥测遥信数据进行计算、分析和校验，可辩识出不良数据。不但能估计开关的功率、母线电压等，而且能计算出某些无法量测的电气量，对准确的运行方式。最终得到一个完整且相对准确的运行方式。自动化运维人员根据状态估计提供的可疑数据功能，能及时发现并处理系统缺陷。调度运行值班人员则通过状态估计掌握电网的实时运行状态，如电网运行方式、潮流分布等。 2.3调度员潮流 这是PAS高级应用最基本的应用之一。调度员潮流既可以对电网当前的运行状态进行分析，也可以对历史和未来的运行方式进行分析，还可以用来校核调度计划的安全性和合理性。调度员潮流能得到电网的实时运行状态。首先利用SCADA实时数据和提前设定的计算条件进行数据初始化；网络拓扑根据系统的遥信信息确定电网的电气连接状态；状态估计经过一系列的专业计算剔除其中的坏数据，最后建立研究态。 2.4负荷预测 人工预测主要根据前几日的负荷或历史同期数据进行分析预测。工作既繁琐又复杂，结果还不理想。负荷预测能够根据历史数据，预报未来的电网负荷，通过分析预测值与实际值之间的误差，自动修正预测模型的参数。该软件的应用节省了大量人工预测时间，能根据历史数据预测未来一至多天的负荷，还能从多种角度自动检测不正常的历史数据，并对坏数据进行报警。 3经济调度软件功能分析 针对安康网内小水电资源丰富的特点安康供电分公司研究开发的经济调度软件，对系统内小水电、变电站的运行状况进行实时监测和分析，为辅助调度员经济、科学、合理调度，最大限度实现电网安全、优质、经济运行。 3.1电置统计分析模块 从SCADA系统获取联络线有功功率、无功功率、当日电量、小水电有功功率等实时数据；从关系数据库中读取各个联络线的月／年累积电量等。然后，人工输入联络线的月／年关口交易计划电量、水电站月／年发电计划电量等。此模块利用SCADA提供的用户控制语言编程实现。 3.2有功功率实时平衡模块 监视联络线断面的实时有功功率。当超过人工设置的限额时，采用特定分配算法，将超限差值自动分配到相关的各个水电站中，以报警提示的方式告知调度人员。(1)采用网络拓扑、潮流计算和灵敏度分析算法，按照水电站当前发电功率等比例分配，将差值功率分配到灵敏度较高的各个水电站中。此算法比较精确，但条件苛刻，要求网络拓扑、潮流计算等模块正常运行，需要加强PAS软件的日常维护工作。
(完整版)智能算法在柔性车间调度中的应用
智能算法在柔性作业车间调度中的应用摘要：为提高企业生产效率，合理的流水车间生产调度显得尤为重要。本文介绍了三种智能算法（蚁群算法、遗传算法、改进粒子群算法）在车间生产调度中的应用，主要介绍了算法的基本思想、模型结构、算法实现以及运用前景。对智能算法在生产调度中的应用做出总结。 关键字：智能算法；蚁群算法；遗传算法；改进粒子群算法；生产调度 0.前言 柔性作业车间调度问题(Flexible job-shop sche- duling problem, FJSP)是传统作业车间调度 问题的扩展，是实际生产中迫切需要解决的一类问 题。在传统的作业车间调度问题中，工件的每道工序只能在一台确定的机床上加工。而在柔性作业车间调度问题中，每道工序可以在多台机床上加工，并且在不同的机床上加工所需时间不同。柔性作业车间调度问题减少了机器约束，扩大了可行解的搜索范围，增加了问题的难度。 作业车间的主要特点是：n个工件需要在m台机器上进行加工，每个工件都有其独特的加工步骤，但无明显的顺序约束，并且加工时间是已知的，调度的目标是在不允许两个工件同时在同一台机器上加工的前提下，如何安排工件在每台机器上的加工顺序使这些工件能够尽快加工完毕[1]。 1.蚁群算法在作业车间的应用[2] 以3个工件2台机器的问题作为例子，如图1。 图1 三个工件两台机器的JSP问题 为确定先对哪个工件进行加工，需要设置一个初始节点O0，所有的蚂蚁最初都放置在O0。图1中除与O0相连的有向弧表示同一个工件的加工顺序，工件必须按照该顺序进行加工。其它则为无向弧。每个弧与表示节点间信息素的量和启发式距离的一对 值{αij, d ij}有关。d ij 通常为对节点 j 的第 i 步操作的加工时间，τij使用蚁周方式进行更新：其中，ρ是个系数，1?ρ表示在时间t和t+1之间信息素的蒸发，Q为常数，Tk为完成所有加工步骤后最短的总加工时间。初始时刻τij(0)= c（c为常数）。 这个规则包含了两个方面：(1)图1中所有边缘上的信息素都要蒸发；(2)完成所有的加工后要将该解的效果加到各边缘上。蒸发可以防止搜索局限在局部最小的邻域中，另一方面又能根据已有解的效果好坏来更新信息素，进行增强学习。 另一个关键的问题就是如何保证蚂蚁按照工件的工艺路线产生一组可行解。这里用到3个集合：对每个蚂蚁 k，首先要有集合G k，表示没有访问过的节点集合；S k 表示根据技术路线下一步允许访问的节点集合；还需要一个禁忌表，存放已经访问过的节点。在我们的例子中， G k ={1，2 ，3，4，5 ，6}，S k ={1，2 ，3}。转移概率是通过下式计算的： T ij 为工件i在机器j上的加工时间。每选择一个节点，该节点就被追加到禁忌表中并从G k和 S k中删除；如果被选的节点不是工件的最后一步，那该工件中紧邻的下一个节点会被加到Sk中。该过程一直重复到G k = φ。最后禁忌表中得到的节点的排列顺序就是蚂蚁 k 找到的解。 参数α和β决定了算法的收敛速度并对解的性能好坏有重要影响，同时蒸发常数也需要进行适当的调整以使搜索能在好的搜索空间中进行，并防止陷入局部最优的邻域中。
无线网络分组调度算法研究
无线网络分组调度算法研究 吴宇 【摘要】：移动通信和互联网的高速发展,使人们对宽带无线接入的需求越来越迫切。人们期望未来移动通信系统在支持更高传输速率的基础上,能够容纳更多用户并且满足不同业务的服务质量(QoS)要求,而有效的无线分组调度算法正是实现这一目标的关键。在很多应用环境下,无线信道具有明显的资源受限和时变衰落特性,基于有线网络或无线静态信道的分组调度算法无法保证无线网络用户获得很好的QoS。针对无线时变环境下无线信道的传输特性,设计能够在保证用户QoS的同时提高无线网络容量的分组调度算法是当前无线通信领域的一个热点。在多用户共享的无线网络中,利用不同用户独立的时变信道条件进行机会调度(O pportunistic Scheduling)可以显著提高无线信道的利用率。尽管每次调度总选择信道条件(通常以接收信噪比表示)最好的用户进行传输可以使系统吞吐量达到最大,但由于无线网络中不同用户的信道条件往往具有很大差别,为了使系统中每个用户均获得较好的QoS,在调度过程中必须选择合理的公平准则。在无线刚络中,调度的有效性和公平性通常是两个相互矛盾的性能指标,而有效的机会调度算法必须根据用户的QoS要求,在这两个指标之间获得最佳的折中性能。论文主要针对时变信道环境下时分复用(TDM)的无线网络分组调度机制展开了深入研究。首先,对无线网络非实时业务分组调度算法进行了研究。论文在对现有Max-rSNR 算法进行改进的基础上,提出了一种具有小尺度服务时间保证的无线非实时业务分组调度算法(M-Max-rSNR)。M-Max-rSNR算法在很好的继承了Max-rSNR算法的大尺度服务时间公平性质的同时,能够使每个用户在预先规定的较短时间内获得服务,从而满足了一些非实时用户对访问时延上限的特殊要求。在此基础上,通过充分利用多用户分集(Multiuser Diversity)的机会调度策略,M-Max-rSNR能够获得较比例公平(PF)算法更好的吞吐量性能。同时,论文还针对现有机会调度算法无法为用户提供加权服务时间公平性的缺陷,提出了一种具有小尺度加权服务时间公平性的无线非实时业务分组调度算法(SFOS)。该算法同时利用虚拟时间机制和Max-rSNR准则,能够在进行有效机会调度的同时,使每个用户在任意短的时间内获得与其权重成正比的服务时间。其次,对无线网络实时业务分组调度算法进行了研究。实时业务具有非常严格的端到端传输时延要求,为了提高实时用户的QoS,实时业务分组调度算法应该通过机会调度策略尽量减小实时业务分组在基站发送队列中的等待时间,为此,论文提出了一种机会的实时业务分组调度算法(ORS)。在ORS算法中,每个用户的优先函数同时包含该用户的相对信噪比和一个随该用户发送队列的队首(Head-Of-Line,HOL)分组等待时间递增的凹函数。在此情况下,当所有用户的等待时间均较小时,具有最大相对信噪比的用户将得到调度;而当某个用户的等待时间逐渐接近其超时期限时,迅速增加的等待时间函数值将使其获得调度。与目前在HDR、HSDPA网络中得到广泛应用的EXP和M-LWDF算法相比,ORS 算法能够显著降低系统中所有实时用户的平均等待时间和分组超时率。第三,对实时和非实时业务共存的无线网络混合业务分组调度算法进行了研究。由于实时业务和非实时业务具有不同的QoS要求,如何设计合理的资源调度策略,使不同类型用户获得较高的QoS,是未来无线网络调度算法需要解决的关键问题。论文提出了一种基于PFQ策略的分级调度算法(PFQ-HS),该算法具有独立、分级的调度结构:在第一级调度器中可以使用任何两种调度算法分别
城市公共自行车调度方法研究
城市公共自行车调度方法研究 随着社会经济的不断发展,人们的交通出行需求越来越大,城市交通问题也越来越严重。面对这样的形势,低能耗、低排放、低污染的绿色交通理念被越来越多的人认同。 公共自行车在缓解交通拥堵,解决出行“最后一公里”问题方面具有突出优势。但是由于公共自行车站点规划布局的不合理,以及运营管理部门对公共自行车系统的调度不合理等原因,在公共自行车系统运行过程中经常出现“无车可借,无桩位可还”的问题,这种现象制约着城市绿色交通的有序发展。 基于这种现象,本文对城市公共自行车运营调度问题进行了研究。首先,本文在总结归纳国内外现有研究成果的基础上,阐述了城市公共自行车的使用特征,并分析了公共自行车调度的必要性。 同时,对公共自行车调度系统的调度内容、调度模式、调度成本等进行了深入分析。在调度模式方面,分析了传统多车场简单分区调度模式的特点以及存在的不足,提出了多调度车场协同运输的调度模式。 其次,分析了多车场协同运输调度模式的特点以及需要考虑的因素,在此基础上构建了一个以综合调度运输成本最低的多车场协同调度模型。该模型将系统内所有调度车场进行协同考虑,优化公共自行车静态调度的最优路径问题。 在模型求解方面,本文通过对不同启发式算法适用性的分析,最终构造了一种融合遗传算法和禁忌搜索算法的启发式算法,并通过Matlab软件编程实现模型的求解。最后,以中山市公共自行车租赁系统为例,分别采用多车场协同运输调度模式和传统多车场简单分区调度模式进行调度。 以综合调度成本最低为目标,对两种调度模式下的最优调度方案进行对比分
析,验证了本文所构建的多车场协同运输的调度模型以及求解算法的适用性。
作业车间调度模型
基于WSA算法的作业车间低碳调度方法研究 1.1 引言 本章主要研究了以最大化完工时间和能耗指标为目标的作业车间低碳调度模型的求解方法。首先，建立了多目标作业车间低碳调度模型；然后基于Pareto 支配理论，设计了一种高效的MODWSA算法获得满意的Pareto非支配解；最后，设计了一套测试算例，将MODWSA算法与其它经典多目标算法进行比较分析，验证了MODWSA算法的优越性。在本研究中，作者完成了两项工作：首先，构建了一个新的多目标作业车间低碳数学模型；其次，设计了一种高效的MODWSA算法获得满意的Pareto非支配解。 1.2 作业车间低碳调度模型 本章研究的作业车间低碳调度问题可描述如下：对给定的n个工件及k台机器，一个工件的加工需要经过m道工序，每道工序允许在特定的机器上加工，任意一台机器在任意一个时刻仅能加工某一工件的某一道工序，并且一个工件只能在其上道工序完成后下一道工序才能开始加工[插入文献]。 考虑机器的准备时间，准备时间与同一机器上相邻两工件的加工顺序相关，并且机器的启动和工件的加工是相连的。对应于不同工序，机器具有不同的速率档位进行加工，并且可以进行调节。从能耗的角度来看，机器有四种不同的状态：加工状态(机器在加工工件)，启动状态（机器在准备加工一个新的工件），待机状态（机器处于空转中），以及关机状态（机器被关机）。通常情况下，当机器在较高速率运作时，工件的加工时间会被缩短，但是相应的能耗会增加。因此本问题以最大化完工时间和能耗指标为目标，由于本章所研究问题的特点，该问题要比传统的作业车间调度问题要复杂的多。在该问题中，其它设定如下： ●工件在车间里被连续加工。也就是说，加工过程不能被中断。 ●机器允许有空闲时间，并且各阶段间具有容量无限的缓冲区。 ●当有第一个工件在机器上加工时，机器开机；当在该机器上加工的所有工件 加工完毕后，机器关机。 ●机器速度在工件加工过程中不能进行调整。 1.2.1 混合整数规划模型 为了提出问题的数学模型，根据上面对问题的描述，我们首先定义了下面的相关数学符号。
02流水线车间生产调度的遗传算法MATLAB源代码
流水线车间生产调度的遗传算法MATLAB源代码 n个任务在流水线上进行m个阶段的加工，每一阶段至少有一台机器且至少有一个阶段存在多台机器，并且同一阶段上各机器的处理性能相同，在每一阶段各任务均要完成一道工序，各任务的每道工序可以在相应阶段上的任意一台机器上加工，已知任务各道工序的处理时间，要求确定所有任务的排序以及每一阶段上机器的分配情况，使得调度指标(一般求Makespan)最小。 function [Zp,Y1p,Y2p,Y3p,Xp,LC1,LC2]=JSPGA(M,N,Pm,T,P) %-------------------------------------------------------------------------- % JSPGA.m % 流水线型车间作业调度遗传算法 % GreenSim团队——专业级算法设计&代写程序 % 欢迎访问GreenSim团队主页→https://www.wendangku.net/doc/ee4832125.html,/greensim %-------------------------------------------------------------------------- % 输入参数列表 % M 遗传进化迭代次数 % N 种群规模(取偶数) % Pm 变异概率 % T m×n的矩阵，存储m个工件n个工序的加工时间 % P 1×n的向量，n个工序中，每一个工序所具有的机床数目 % 输出参数列表 % Zp 最优的Makespan值 % Y1p 最优方案中，各工件各工序的开始时刻，可根据它绘出甘特图 % Y2p 最优方案中，各工件各工序的结束时刻，可根据它绘出甘特图 % Y3p 最优方案中，各工件各工序使用的机器编号 % Xp 最优决策变量的值，决策变量是一个实数编码的m×n矩阵 % LC1 收敛曲线1，各代最优个体适应值的记录 % LC2 收敛曲线2，各代群体平均适应值的记录 % 最后，程序还将绘出三副图片：两条收敛曲线图和甘特图（各工件的调度时序图） %第一步：变量初始化 [m,n]=size(T);%m是总工件数，n是总工序数 Xp=zeros(m,n);%最优决策变量 LC1=zeros(1,M);%收敛曲线1 LC2=zeros(1,N);%收敛曲线2 %第二步：随机产生初始种群 farm=cell(1,N);%采用细胞结构存储种群 for k=1:N X=zeros(m,n); for j=1:n for i=1:m X(i,j)=1+(P(j)-eps)*rand;
常用的分组调度算法
[编辑本段]常用的分组调度算法 对于调度算法有两个重要的设计参数：一个是吞吐量，另一个是公平性。调度算法是数据业务系统的一个特色，目的是充分利用信道的时变特性，得到多用户分集增益，提高系统的吞吐量。吞吐量一般用小区单位时间内传输的数据量来衡量。公平性指小区所有用户是否都获得一定的服务机会，最公平的算法是所有用户享有相同的服务机会。奸的调度算法应该兼顾吞吐量和公平性，根据算法的特点，调度算法主要可分为：轮询(Round Robin， RR)算法；最大C／I算法(MaxC／1)；正比公平(Proportional Fair，PP)算法。 (1)轮询算法 在考虑公平性时，一般都把循环调度算法作为衡量的标准。这种算法循环地调用每个用户，即从调度概率上说，每个用户都以同样的概率占用服务资源(时隙、功率等)。循环调度算法每次调度时，与最大C／I算法相同，并不考虑用户以往被服务的情况，即是无记忆性方式。循环调度算法是最公平的算法，但算法的资源利用率不高，因为当某些用户的信道条件非常恶劣时也可能会得到服务，因此系统的吞吐量比较低。 图7-35给出了以时分方式使用高速下行共享信道(High Speed Downlink Share CHannel， HS-DSCH)信道的一种可能的资源分配方式。从图中可以看出，尽管UEl和UE2的信道环境不同(与基站的距离不同)，但是分配了相同的信道使用时间给UEl和UE2。 (2)最大C／I算法 最大C／I算法在选择传输用户时，只选择最大载干比C／I的用户，即让信道条件最好的用户占用资源传输数据，当该用户信道变差后，再选择其他信道最好的用户。基站始终为该传输时刻信道条件最好的用户服务。 最大C／I算法获取的吞吐量是吞吐量的极限值，但在移动通信中，用户所处的位置不同，其所接收的信号强度不一样，最大C／I算法必然照顾了离基站近、信道好的用户，而其他离基站较远的用户则无法得到服务，基站的服务覆盖范围非常小。这种调度算法是最不公平的。 图7-36给出了以时分方式使用HS-DSCH信道的一种可能的资源分配方式。该图假定了服务过程中UEl的信道条件始终好于UE2。从图中可以看出，只有当信道条件较好的UEI缓冲区数据全部传输完毕，系统才调度UE2服务。
多核处理器调度方法研究
多核处理器调度方法研究 【摘要】在多核处理器蓬勃发展的今天，温度过高成为制约其性能和稳定的关键因素。本文首先在单核处理器上，以热传递理论为基础，以温度与时间的一个简明等式详细分析了任务组的各种排列方式对单核处理器的峰值温度可能造成的影响，并提出了简单易行免于复杂计算的调度方法；然后将该方法拓展到多核处理器环境，通过合理分配、核上调度和核间迁移，达到了降低各核峰值温度的目的。 【关键词】多核；温度感知；调度；热传递 0.引言 多核处理器是当前及未来处理器发展的主要趋势。单个处理器中集成的核的数量已经由两个发展到四个、八个甚至更多。核的数量的增多提高了处理器的计算能力，但也带来了处理器功耗过大和温度过高的问题。有一些研究致力于减少多核处理器的功耗，而另一些研究则着眼于解决温度过高的问题。功耗问题和温度问题并不完全相同，两个处理器的功耗总量相同时温度的变化曲线却不一定相同。减耗的直接目的是节能，通过减耗有可能间接实现降温的目的，但不能保证没有温度过高的时刻。一个过高的温度会直接导致处理器性能降低及故障率升高，所以相对而言，降低温度比减少功耗有更为重要的意义。本文着眼于解决峰值温度过高的问题。 为了解决这一问题，在硬件上一般常采用动态电压调节(DVS)和clock gating 等技术。DVS适时地降低电压与频率以减少功耗，clock gating当温度达到某个阈值时暂时停止指令的执行。这两种方法尤其是后者严重牺牲了处理器性能，只能在必要时刻合理使用。国内外也有一些文献提出软件方法，但往往没有与温度直接相关的模型，或只是通过简单的迁移进程来降温，而且常以取得较低的平均温度或平坦的温度曲线为目标。然而为保证处理器正常工作，重要的是保证温度不超过某个阈值，平均温度的高低相对次要。有实验表明，不同任务对处理器的温度有不同程度的影响，其差别甚至十分巨大，所以通过任务在不同核间切换和单个核上的调度降低处理器的峰值温度是可行。本文以数字温度传感器(DTS)为硬件基础, 以基于热传递原理的模型为理论出发点，以任务调度为手段，以降低处理器的峰值温度为目标。首先探讨任务调度在单核上的性质，提出了热优先排序和冷任务插入方法，然后将得到的结论扩展为多核，提出了任务分配原则和冷任务迁入方法。该方法性能损失较小，而且可与DVS和clock gating方法共同使用。 1.多核调度 多核调度是单核调度的扩展，多核处理器每个核上的调度都保有上节所讲的性质。多核调度从一般可以分为全局调度和局部调度。目前局部调度应用较广泛，本文采用局部调度，将调度步骤主要划分为分配、核上调度和核间迁移。
嵌入式实时操作系统中实时调度算法综述
嵌入式实时操作系统中实时调度算法综述 摘要：实时调度是指在有限的系统资源下，为一系列任务决定何时运行，并分配任务运 行除CPU之外的资源，以保证其时间约束、时序约束和资源约束得到满足。一个实时系统可以由单处理器系统来实现，也可以用多处理器系统来实现。实时调度算法是保障实时系统时限性和高可靠性的最重要手段之一。 关键词：嵌入式；实时操作系统；实时调度算法；RTOS；RMS 引言 嵌入式系统在当今的生产和生活中得到了广泛的应用,鉴于嵌入式实时系统的特点,要求任务调度等实时内核功能精简和高效。综合了EDF 和RM调度策略的CSD 调度策略,更加适合嵌入式系统的特点,满足其内核的要求。任务调度策略是实时系统内核的关键部分,如何进行任务调度,使得各个任务能在其期限之内得以完成是实时操作系统的一个重要的研究领域。它的精简和高效,对提高低处理能力,小内存系统整体性能具有重大的意义。 RTOS概述 RTOS，即：实时系统（Real-time operating system），实时系统能够在指定或者确定的时间内完成系统功能和外部或内部、同步或异步时间做出响应的系统。它的正确性不仅依赖系统计算的逻辑结果，还依赖于产生这个结果的时间。因此实时系统应该在事先先定义的时间范围内识别和处理离散事件的能力；系统能够处理和储存控制系统所需要的大量数据。对一般的程序来说，大多数是考虑指令执行的逻辑顺序，指令何时执行并不重要。而对实时应用系统的程序就不一样，当外部某激励出现时，系统必须以一定的方式和在限定的时间内响应它，如果已超时，那怕执行结果是正确的，系统也认为是失效的。实时操作系统通常被分为软实时操作系统和硬实时操作系统。前者意味着偶尔错过时限是可以容忍的；后者意味着执行过程不但必须正确而且必须准时。在实时操作系统中，系统将程序分成许多任务(或进程)，而每个任务的行为都预先可知，或者是有明确的功能，系统根据一定的调度原则，决定谁可取得执行权，这就是RTOS的核心所在。 实时调度算法 实时调度算法可以分为4类：单处理器静态调度算法、多处理器静态调度算法、单处理器动态调度算法、多处理器动态调度算法。下面分别分析嵌入式操作系统中采用的各种调度方法，以及这些调度方法是如何满足实时性应用的实时要求的。 1 速率单调算法 速率单调算法是一个经典的算法，它是针对那些响应和处理周期性事件的实时任务的，它事先为每个这样的实时任务分配一个与事件频率成正比的优先级。 实现时，就绪队列中的所有任务按照优先级Priority排队，优先级最高的任务排在队首，当处于运行态的任务，由于某种原因挂起时，只要把就绪队列的首元素从就绪队列中取下，使运行任务指针pRunTask指向该元素即可，如果是处于其他状态的任务变为就绪状态，而挂
分组调度分类
分组调度算法分类 1. 基于静态优先级的算法：PQ和QLT（queue length threshold）算法。 PQ算法给每个队列赋予不同的优先级，每次需要调度时，具有最高优先级的非空队列中的分组最先被选择服务。算法简单，容易实现，然而在高优先级队列源源不断地有分组到达时，低优先级的队列容易被“饿死”，公平性很差。 QLT给每个队列设置调度阈值，需要进行调度时从最高优先级开始比较队列的长度和调度阈值。当最高优先级队列的长度大于其调度阈值时，该队列头部的分组首先被选择服务；当最高优先级队列的长度小于其调度阈值时，不再服务该队列，而是首先检查具有此高优先级的队列，如此类推。通过合理的调度阈值，QLT算法在保证优先级关系的基础上，提高的公平性。 2. 基于轮循的算法：RR，WRR（weighted round-robin），DDR等 RR只是简单的对所有队列进行轮循调度，一次调度发送一个分组，使得不同队列在某种程度上“平等”的使用带宽资源。由于分组长度不固定，使得长分组队列可能比短分组队列得到更多的服务，获得更高的带宽，公平性受到很大限制，不能提供时延保证。 WRR给队列赋予不同的权值，代表一次完整循环队列被服务的分组数。同时为每个队列维护一个计数器，初始化为权值。每次轮循时，计数器为非零的队列允许发送一个分组，并将计数器减一。当所有队列的计数器均为零时，重置权值。能够以比较平滑的方式调度输出业务，但仍存在由于分组变长带来的不公平性。 DDR算法以字节为单位为每个队列分配一个带宽配额，该配额的比例对应于队列服务速率的比例。同时，为每个队列维护一个计数器，初始化为其带宽配额。每次轮循时，如果待发分组长度小于或等于计数器值，则允许发送，并把计数器减去此分组的长度值；如果待发分组长度大于计数器值，则检查下一个队列，同时，把该队列计数器的差值累计到下一次循环（即下次调度该队列之前，把此剩余值和配额之和赋予计数器）。很好的解决了带宽分配的公平性问题，但不能很好地满足业务地时延特性。 其他算法：URR（urgency-based round-robin），SRR（surplus round-robin）等。 3. 基于GPS模型地算法（PFQ算法）：常见的基于GPS模型的算法有：WFQ，WF2Q （worst-case fair weighted fair queuing），WF2Q+，VC（virtual clock），SCFQ（self-clocked fair queueing），SFQ（stochastic fair queueing），SPFQ（starting potential fair queueing），FFQ（frame-based fair queueing）等。此类算法是对理想流体模型GPS的逼近，成为PFQ（packet fair queueing）算法。 GPS模型是一个理想化的流模型，假定每一个队列中的业务元可以无限小，队列
基于贡献度的项目调度方法研究
第14卷第12期计算机集成制造系统 Vol.14No.122008年12月 Computer Integrated Manufacturing Systems Dec.2008 文章编号:1006-5911(2008)12-2431-05 收稿日期:2007-12-24;修订日期:2008-04-28。Received 24Dec.2007;accep ted 28Apr.2008. 基金项目:国家973计划资助项目(2005CB724100);国家863计划资助项目(2007AA04Z110,2007AA04Z190);国家自然科学基金资助项目 (70271053,70772056)。Foundation items:Project supported by the National Basic Resear ch Program ,China(No.2005CB724100),th e N ational H igh -T ech.R&D Program,China(No.2007AA04Z110,2007AA04Z190),and the National Natural Science Founda -tion,China(No.70271053,70772056). 作者简介:管在林(1966-),男,江苏高邮人,华中科技大学机械科学与工程学院副教授,博士,主要从事约束理论、制造系统建模与仿真等的研 究。E -mail:zlgu an@h https://www.wendangku.net/doc/ee4832125.html, 。 基于贡献度的项目调度方法研究 管在林1,马 力1,何 敏2,邵新宇1 (1.华中科技大学机械科学与工程学院数字制造装备与技术国家重点实验室,湖北 武汉 430074; 2.武汉烽火通信科技股份有限公司,湖北 武汉 430074) 摘 要:为改进传统的项目管理方法,提出了一种由统计理论得出的指标)贡献度来决定在关键链识别过程中的冲突解决策略,以达到识别出项目关键链的目的。为使调度计划在不确定性环境下能够顺利实施,该调度方法充分考虑了项目执行过程中工序的随机性。在此基础上,提出了一种关键链识别方法,最后针对标准问题库PSPL IB 中的典型算例,应用M atlab 进行了仿真验证。 关键词:项目管理;项目调度;关键链;瓶颈;贡献度中图分类号:T P391 文献标识码:A Project scheduling method based on the contribution index G UA N Zai -lin 1 ,MA Li 1 ,H E M in 2 ,SH A O X in -yu 1 (1.Stat e K ey L ab of Digital M anufact ur ing Equipment &T echnolo gy ,School of M echanical Science &Eng ineering ,H uazhong U niversit y of Science &T echno lo gy ,W uhan 430074,China; 2.Fiber Ho me T elecommunication T echnolo gies Co.,L td.,Wuhan 430074,China) Abstract:T o improv e tr aditional pro ject manag ement methods,a conflict r eso lutio n strateg y in identify ing the cr itical chain of the pr oject by using the contributio n index co ming fr om the st atistical t heo ry was pro po sed.T o r ealize smo oth implementatio n o f project scheduling under uncer tain env ir onment,the r andomness o f the pro ject procedur e during the pr oject ex ecution pr ocess w as taken into consideratio n in this method.Based o n the str ategy ,a new crit-i cal chain identificat ion metho d was int roduced.Finally ,based o n one standar d instance f rom the w ell know n PSPL IB benchmar k set,simulatio n ev aluatio n to this method in M atlab env ir onment w as pr esented.Key words:pr oject management;pro ject scheduling ;critical chain;bott leneck;co nt ribution index 0 引言 在当前装备制造业成为我国重点发展方向的背 景下,有必要改善传统的项目管理理论与方法,验证新方法的可行性,并最终将其应用在大型机电装备的设计、加工和装配过程的规划与管理过程中。 高德拉特(Goldratt)博士于1986年提出了约束理论(T heo ry of Co nstraints,TOC),强调以系统 整体的观点进行生产管理。之后,他将TOC 引入到项目管理领域,提出了一种基于瓶颈识别及缓冲管理的新方法)))关键链项目管理(Critical Chain Project M anag em ent,CCPM )方法[1]。传统的关键路径法(Critical Path Metho d,CPM )在确定关键路径时,主要依据预先估计的任务时间与任务间的逻辑关系,并没有充分考虑资源约束对项目计划的影响 [2] 。而CCPM 方法则认为决定整个项目效率的
流水车间调度问题的研究-周杭超
流水车间调度问题的研究-周杭超
流水车间调度问题的研究 机械工程学院 2111302120 周杭超 如今，为了满足客户多样化与个性化的需求，多品种、小批量生产己经为一种重要的生产方式。与过去大批量、单一的生产方式相比，多品种、小批量生产可以快速响应市场，满足不同客户的不同需求，因此，受到越来越多的企业管理者的重视。特别是以流水线生产为主要作业方式的企业，企业管理者致力于研究如何使得生产均衡化，以实现生产批次的最小化，这样可以在不同批次生产不同品种的产品。在这种环境下，对于不同批次的产品生产进行合理调度排序就显得十分重要。 在传统的生产方式中，企业生产者总是力求通过增加批量来减小设备的转换次数，因此在生产不同种类的产品时，以产品的顺序逐次生产或用多条生产线同时生产。这样，必然会一次大批量生产同一产品，很容易造成库存的积压。在实际生产中如果需要生产A, B, C, D 四种产品各100件，各种产品的节拍都是1分钟，如果按照传统的做法，先生产出100件A产品，其次是B，然后是C，最后生产产品D。在这种情况下，这四种产品的总循环时间是400分钟。然而，假设客户要求的循环时间为200分钟(四种产品的需求量为50件)，那么在200分钟的时间内就只能生产出产品A和产品B，因而不能满足客户需求，同时还会过量生产产品A和B，造成库存积压的浪费。这种生产就是非均衡的，如图1所示。 比较均衡的生产方式(图2 )是:在一条流水线上同时将四种产品
混在一起生产，并且确定每种品种一次生产的批量。当然，如果在混合生产时不需要对设备进行转换，那么单件流的生产方式是最好的。然而，在实际生产A, B, C ， D 四种不同产品时，往往需要对流水线上的某些设备进行工装转换。单件流的生产方式在此难以实现，需要根据换装时间来确定每种产品一次生产的批量。同时，由于现实生产中不同产品在流水线上各台机器的加工时间很难相同，因此，流水线的瓶颈会随着产品组合的不同而发生变化。当同一流水线加工多产品，并且每种产品在各道工序(各台机器)的加工时间差异较大时，瓶颈就会在各道工序中发生变化，如何对各种产品的投产顺序进行优化以协调这些变化的瓶颈是生产管理中一个很重要的问题。 图1 图2 因而对流水线调度问题的研究正是迎合这种多品种、小批量生产方式的需要，我们要讨论得是如何对流水线上生产的不同产品的调度顺序进行优要化。 流水车间调度问题一般可以描述为n 个工件要在 m 台机器上加工，每个工件需要经过 m 道工序，每道工序要求不同的机器，n 个工件在 m 台机器上的加工顺序相同。工件在机器上的加工时间是给定的，设为(1,,;1,,)ij t i n j m ==。问题的目标是确定个工件在每台机器上的最优加工顺序，使最大流程时间达到最小。
面向LTE-V调度方法研究
技术 专栏5G与车联网5G and Internet of Vehicles特约主编朱雪田 面向LTE-V调度方法研究 李艳芬，朱雪田 (中国电信股份有限公司智能网络与终端研究院，北京102209) 摘要：智能出行推进车联网从支持车载信息服务向支持V2X服务的下一代车联网发展，为了满足车联网发展需求,3GPP标准针对LTE-V制定了PC5接口和Uu两种通信方式。结合LTE-V业务特点，介绍了Mode3、Mode4、SPS 增强调度算法及各算法优缺点，为车联网车车、车路、车人之间低时延、高可靠性的通信需求奠定基础。 关键词：PC5；Uu；Mode3；Mode4；SPS增强 中图分类号：TN929.5文献标识码：A DOI:10.16157/j.issn.0258-7998.190882 中文引用格式：李艳芬，朱雪田.面向LTE-V调度方法研究[J].电子技术应用，2019,45(9):8-12. 英文引用格式：Li Yanfen,Zhu Xuetian.Research on LTE-V scheduling method[J].Application of Electronic Technique,2019,45 (9):8-12. Research on LTE-V scheduling method Li Yanfen,Zhu Xuetian (Intelligent Network and Terminal Research Institute of China Telecom Co.,Ltd.,Beijing102209,China) Abstract:Intelligent outgoing promotes vehicles networks from supporting on-board information services to the next generation that supports V2X services.In order to meet the development needs of Vehicles networks,the3GPP standard has developed two com-munication modes,PC5interface and Uu,for https://www.wendangku.net/doc/ee4832125.html,bined with the characteristics of LTE-V services,this paper introduces the Mode3,Mode4and SPS enhanced scheduling algorithms,and the advantages and disadvantages of each algorithm,which lays a foundation for the communication requirements of low-latency and high-reliability among V2V,V2I and V2P. Key words:PC5；Uu;Mode3；Mode4；SPS enhanced 0引言 车联网的提出和发展可以有效缓解或解决由于车辆快速增长而带来的各种问题，并有可能彻底改变人们未来的岀行模式，大大提升道路交通网络的运输效率、安全水平、智能化水平及环保水平，对支撑汽车产业升级转型具有重要意义。车联网是以车内网、车际网和车载移动互联网为基础，按照约定的通信协议和数据交互标准,在V2X(Vehicle to Everything)之间进行无线通信和信息交换的大系统网络，是能够实现智能化交通管理、智能动态信息服务和车辆智能化控制的一体化网络。 1LTE-V标准进展及业务需求 国际上车联网标准包括两大通信阵营，一种是DSRC(Dedicated Short Range Communications)方案，作为WiFi的升级版技术。美国在1998年将5850-5925 MHz用于DSRC无线电服务，也是多数企业普遍采用的标准。另外一种是以LTE为基础的车联网专用的LTE-V方案，实现车辆与周边环境节点低时延、高可靠的直接通信，满足行车安全需求。 3GPP标准进展如图1所示，2015年12月，3GPP RAN启动LTE-V的第1个工作项目，主要完成基于LTE PC5接口的V2V(PC5-based V2V)的标准化工作。2016年6月，3GPP RAN启动第2个LTE-V工作，主要完成基于Uu接口的LTE-V,以及其他第1阶段遗留的标准化工作。2017年3月,3GPP RAN启动基于Rel-14 LTE-V的增强(Rel-15)的标准化工作，截止到2018年6月完成了LTE-V R15标准制定，同时6月份正式将eV2X列为R16标准化研究内容。5G eV2X可为自动驾驶汽车提供更多的无线通信功能以支持多种前沿用例，如车辆间高吞吐量传感器数据及地图共享，将车辆摄像头捕捉到的信息流传输至其他车辆以实现“透视”功能，或实现宽带测距以改善定位服务。3GPP主张未来5G eV2X是LTE-V的一个补充，而不是后向兼容。 目前主要产品形态还是基于R14,在R14中针对LTE-V定义了三类业务场景，分别是安全应用场景、交通效率提升应用场景、信息娱乐服务场景，共计27种用例⑴。对网络有如下需求： (1)速度：支持最高相对速度为500km/h,最高绝对速度为250km/h； 8欢迎网上投稿www.ChinaAET.c om《电子技术应用》2019年第45卷第9期