多目标任务调度

2024-06-14

多目标任务调度（共8篇）

多目标任务调度篇1

0 引言

近几年来,云计算作为一种新型的技术和商业模式,已经成为各大企业、研究机构关注的重点。云计算是网格计算、并行计算和分布式计算的综合技术,其核心思想是将各种异构的物理资源节点整合在一起,形成一个巨大的虚拟资源池,通过网络向用户提供不同类型的服务,这些服务包括基础设施服务、平台服务、应用服务等等。

云计算所提供的服务面向的用户群是庞大的,因此云中的任务数量是巨大的,系统每时每刻都要处理海量的任务[1]。任务调度的优劣性影响着云系统的整体性能和服务质量,所以任务调度问题是一直是云计算研究中的重点。目前的调度策略的主要优化目标是执行时间、执行费用和负载均衡,其中执行时间和执行费用是为了满足用户的服务质量,而负载均衡是为了保证整个云环境的稳定性。关于云计算的任务调度尚处于初步研究的阶段,发展并不成熟。对于云环境下任务调度这一基本问题的算法研究成果还比较少,而且现有云任务调度算法的考虑因素大部分比较单一。

文献[2]提出了一种基于蚁群算法的云计算资源分配算法,该算法充分地考虑了计算资源本身的固有属性以及计算节点在一定负载的情况下的预测执行速度。在算法设计的过程中,作者虽然将网络带宽、网络延迟和执行时间作为三重约束条件,但是在寻求最优解的时候依旧只考虑了执行时间这一个目标。文献[3]提出了一种基于遗传算法的云任务调度策略,它将任务的最大完工时间最短作为调度策略的优化目标,同时又将任务的平均执行时间作为评价调度算法优劣的重要标准,此调度算法被命名为双适应度的遗传算法。虽然此算法考虑了两个目标,但都是执行时间,没有考虑到其他的约束因素。文献[1]提出了基于云计算的“用户期待”任务调度算法,该算法综合考虑了用户对云资源的服务质量Qo S的要求,将其转化为一个期待值,这样在资源选择的过程中就可以依照用户的期待函数进行选择。但是它只是根据用户期待的函数值选取相应资源,并没有考虑多个Qo S参数之间的依赖关系。文献[4]提出了一种将租借理论和动态多级资源池相结合的云任务调度策略,这个策略的理念是基于云计算虚拟化技术进行设计的;该算法能够有效减少资源的空闲时间,进而提高资源的利用率。作者在文中没有提及具体的寻求最优资源的搜索方法。

本文在研究了云计算任务调度机制和遗传算法的基础上,提出用多目标遗传算法解决任务调度中的目标优化问题。该算法以任务执行时间和执行费用作为优化目标,并结合负载均衡作为约束条件。仿真实验证明,该算法在任务量大、虚拟机多的复杂环境中可以获得比较好的解集,供决策者针对于不同的目标权重选择合适的解。

1 云环境中的任务调度模型

1.1 任务调度结构模型

云计算环境的特点包括了支持基础设施的建模与仿真,支持数据中心、服务代理、调度和分配策略的平台。它提供虚拟化引擎,在数据中心节点上帮助建立和管理多重的、独立的、协同的虚拟化服务。

如图1所示,数据中心是计算资源的集中场所,通过虚拟化技术将物理节点集群转变为虚拟机集群,然后将虚拟机的属性信息交给数据中心代理器。不同用户通过用户接口,将各自的任务提交到数据中心代理器。数据中心代理器则负责任务的具体调度过程。

云环境中的任务调度策略,就是将不同任务分配到合适的虚拟机上的方式,所有的任务分配结束以后,虚拟机开始执行任务,任务执行的结果已经所需要的开销就是评价这个调度策略优劣性的标准。对于N个任务和M个虚拟机的环境,通过计数方法可以知道分配方案的总有MN种。数据中心代理器结合任务属性、虚拟机属性和云系统的优化目标,在所有的分配方案中寻求优秀的个体。任务分配方案确定之后,将该分配方案提交到数据中心。

1.2 任务调度数学模型。

云环境中各个参数的数学描述如下。

(1)虚拟机列表:V={Vm1,Vm2,Vm3,…,Vmm},每个虚拟机的属性定义为处理能力Vmmip,虚拟机价格Vmprice

(2)任务列表:Q={q1,q2,q3,…,qn},每个任务属性定义为任务数据量qlength。

(3)执行时间

总执行时间:

单个虚拟机执行时间:

考虑到虚拟机是并行运行的,所有任务的总执行时间应该去单个虚拟机执行时间中最大的一个。time Vmi表示第i个虚拟机的处理时间,Vmimip表示第i个虚拟机的处理能力,∑qlength为该虚拟机上的总任务数据量。

(4)执行费用

总执行费用:为虚拟机执行费用之和。

单个虚拟机执行费用:为虚拟机单价与该虚拟机上的任务数量之积。

cost Vmi=Vmiprice*Numi

(5)负载失衡值:

在本文的研究范围内,多个任务在同一个资源节点上是并发执行的,云环境中的负载情况是由各个资源节点上的任务数量决定的。因此,虚拟机上的任务越多,该虚拟机负载越大。任务分布越平均,则整个云系统负载越均衡。

本文设计的负载失衡值为所有虚拟机负载的标准差,该值越小,负载越均衡。

2 采用MOGA进行任务调度

云环境里的任务调度问题实际上一个多目标优化的问题.多目标优化问题的各个子目标之间是矛盾的,一个子目标的改善有可能会引起另一个或者另几个子目标的性能降低,也就是要同时使多个子目标一起达到最优值是不可能的,而只能在它们中间进行协调和折中处理,使各个子目标都尽可能地达到最优化[5]。所以,多目标问题不存在唯一的最优解,而是存在一个满足决策者对于不同目标依赖程度的解集。

多目标遗传算法(mutil-objective genetic algorithm)是在遗传算法(genetic algorithm)和多目标优化理论的基础上发展而来。多目标遗传算法既保留遗传算法在全局解空间的强大搜索能力,又利用权重分配、目标规划或ε-约束等方法对多个目标函数进行优化[6],适用于云环境的任务调度场景。

采用多目标遗传算法进行任务调度的过程如下。

2.1 染色体编码

云环境中,一个染色体就代表一个任务分配方案。染色体的编码方式有很多,本算法采用文献[1]中提出的资源—任务间接编码方式。

每个染色体中,基因数目和任务数量相等,基因的值最高为虚拟机数量。第i个基因值为k,则表示将第i个任务分配给第k个虚拟机,假设任务数量为10,虚拟机数量为5,则染色为:

该染色体表示第1、2个任务在第1个虚拟机上,第3、4个任务在第2个虚拟机上…,以此类推。

对该染色体进行解码,可以获得每个资源节点上的任务,即:

Numi表示第i个虚拟机上的任务集合。根据染色体解码后结果,可以获得每个虚拟机上的任务信息。

2.2 适应度函数设计

适应度函数是评价个体优劣的标准,适应度低的个体在遗传过程中将被淘汰,所以一般情况下,适应度函数就是目标优化函数。本文采用加权求和法对两个目标进行关联优化。

在本文场景中有两个优化目标:执行时间和执行费用。由于两个目标值的数量级相差甚远,直接对它们进行加权法,得到的适应度函数误差非常大。因此本文先对各个目标函数进行规范化,再用加权法设计适应度函数。

设种群规模为P,即每一代的个体数量为P。时间函数:

totaltime(i)是序号为i的个体所代表的执行时间,执行时间越小,该函数值越大。

费用函数:

totalcost(i)是序号为i的个体所代表的执行费用,执行费用越小,该函数值越大。

经过规范化以后,取值范围都在0和1以内。

适应度函数:

权值ωt取决于用户对时间的依赖程度。也就是说,用户要求的执行时间越少,ωt越大,反之,用户要求的执行费用越少,ωt越小。ωt为0时,该算法转化为费用的单目标优化算法,ωt为1时,该算法转化为时间的单目标优化算法。

2.3 遗传操作

选择算子

标准遗传算法中选择算子采用轮盘赌选择方法,个体适应度越大,其被选中的概率就越高,反之亦然。但是,由于该方法是基于概率的选择,存在统计误差。同时在种群进化过程中,有时会产生一些超常的个体,这些个体因竞争力太突出而控制了选择运算过程,从而影响算法的全局优化性能,导致算法获得某个局部最优解。

多目标问题中,算法要考虑两个以上的目标函数,选择方案既要维持多样性又要保证收敛性。为了满足这两个特性,本文采用了文献[7]提出的基于排列的选择方案,其原理如下:每一代选取一个参考点,根据参考点先移除当前种群内,劣质的个体。

参考点的选择:

objecti为参考点第i个目标的值,gen为当前代数,Max_gen为最大进化代数。参考点最初从多维目标空间的中心开始,慢慢向原点移动(注意目标函数经过规范化以后,其值在0和1之间),如图2所示。

每一代选择的过程:(1)离参考点最近的一组个体为参考个体,先移除由参考个体支配的个体;(2)在剩下的个体中进行多样性选择,按它与参考点的距离分为优先集合和落后集合,然后取多个不同的个体,作为下一个种群。

交叉算子采用单点交叉重组法,变异算子采用多点变异法。个体需要进行变异的基因位置和变异后的基因值,都随机决定。对于交叉和变异之后的个体,需要经过“环境考验”才能保留到下一代。

一般的遗传算法采用“精英保留法”,该方法虽然保持了种群的多样性,却也降低了种群进化的能力,增加了子代个体中的非优质基因,并且容易引起“返祖现象”[8]。

为了克服上述缺陷,本算法中采用“最优比较法”,交叉和变异之后的个体需要原种群中的最优个体相比较,必须优于最优个体才能进入下一代。这样做能大大增加进化的速度,但同时也失去了一些个体,缩小种群的进化空间。为了弥补这个缺点,可以采用较大的交叉概率和变异概率。

2.4 约束条件

算法将负载失衡值作为个体的约束条件。预先设立一个阈值,在进化过程中,个体的负载失衡值必须小于该阈值,才能保留到下一代。

2.5 终止条件

遗传算法的终止条件一般是适应度达到了要求的值,或是进化到了一定的代数。算法一旦终止,便选择当前种群中的最优个体为最终结果[9]。

3 仿真实验和结果分析

仿真实验主要目的是将本文的多目标遗传算法应用到不同的云计算模拟场景中,分析实验的结果,以验证该算法的适用场合以及有效性。

在Cloudsim仿真平台中,设置两个云场景进行实验。在本文的实验场景中,为了让实验结果更加直观,省略了描述云任务和虚拟机的部分参数,比如带宽、内存等,只选取一些与优化目标相关的参数作为变量。

场景一:种群规模为20,任务数量20个,虚拟机数量10个,变异概率0.5,变异概率0.1,负载失衡值为15,进化代数为2000。任务和虚拟机属性如表1-2所示,实验结果如表3和图3所示。

场景二:种群规模为20,任务数量40个,虚拟机数量20个,变异概率0.5,变异概率0.1,负载失衡值为20,进化代数为2000。虚拟机和任务属性如表4-5所示,实验结果如表6和图4所示。

(1)场景二的负载失衡值明显高于场景一,这表明任务量越多的系统中,想要到达负载均衡越不容易,应该适当给予更宽容的均衡要求。

(2)场景一结果曲线陡峭,随着权值的增大,执行时间和执行费用没有呈现出递增或者递减的趋势,也就说两个目标的优化结果并不明显;而场景二中,优化结果明显,结果曲线平滑。随着权值的增大也就是用户对时间的依赖程度增加,算法的优化方向偏向于对执行时间减少的方向。

本文的算法适合于在多任务、多虚拟机的复杂云环境下进行任务调度,获取多目标优化的优异解集。根据用户对于某个目标的依赖程度,选择合适的权值,即可以获得相应的任务调度方案。

4 结束语

任务调度在整个云系统的设计中占重要地位,这也是本文的研究价值所在。本文提出的MOGA属于多目标优化算法中加权求和法的一种,本算法具有简便直观、时间代价小和优化精度高等的特点。实验结果表明,在云环境中,用该算法作为任务调度的策略是可行的。

摘要：执行时间、执行成本和负载均衡是云环境中的主要优化目标,针对云计算环境中的任务调度问题,提出一种改进的多目标遗传算法。算法对目标进行了规范化,改进了加权求和的过程,并引入基于排列的选择方案和“最优比较法”的变异方案。最后在两个云计算场景中进行实验,对实验结果进行分析和统计,验证了算法的有效性和可行性。

关键词：云计算,任务调度,多目标优化,遗传算法

多目标任务调度篇2

关键词：满意度；多目标；电力调度

1、电力客户满意度分析

客户满意度：在激烈的市场环境竞争中，再加上市场供需结构和企业营销战略的变化，逐渐形成了客户满意的理念。客户满意作为一种感觉，指的是客户对自己的要求被满足程度的感觉，这种感知了综合了多个方面，比如企业提供产品的实现、产品的使用以及处理产品的过程等。客户满意度指的是对用户接受过企业以及企业产品或服务的满意程度进行评价，它是从本质上来对产品或服务的质量进行评价，不仅可以将客户满意的程度给体现出来，又可以将企业提供产品的成效给有效的反映出来。

2、工业用电效率以及污染排放指标分析

通过相关的资料可知，近些年来，我国的排放总量中，有相当一部分比重都是工业污染排放，随着城市化进程加快，工业部门将会越来越多的进行污染和排放，对于环境质量和经济的可持续发展产生很大的影响。目前，我国的能源危机和环境污染问题日趋严重，国家在相关规划中已经在约束性目标中加入了节能和减排的内容。因此，从节能减排的角度上来讲，电力部门应该对那些有着较高能耗和较重污染的企业用电进行限制，鼓励那些污染较轻以及能耗较低的用户多用电，但是，这样就出现了一个问题，因为能耗很高的用户往往有着较高的产值和较高的利润，可以缓解就业问题，那么就需要对工业污染排放的因素进行分析，探讨工业各个行业用电量和污染排放之间的关系。

工业用电效率：通过研究表明，工业用电量和工业总产值都不是孤立存在的，两者存在着互相影响的关系。工业总产值在提高的同时，往往会增加用电量。而工业总产值又会在很大程度上影响到工业用电量。那么，就需要大力研究工业用电效率。

工业污染指标：工业污染是一个综合性很强的名词，它涉及到诸多方面的内容，比如工业废弃、工业废水、工业固体废弃物等等。并且，工业行业的不同，在工业污染特征方面也会呈现出很大的差异。比如冶金、电力、建材等行业主要会产生工业废弃污染，而造纸、化工以及纺织等行业则主要产生工业废水污染，冶金行业如粉煤灰等主要会产生工业固体废弃物污染等等。因此，在核算工业污染排放量时，就需要认真核算水污染排放量、大气污染排放量和固体废弃物污染排放量等。

3、基于满意度的多目标电力调度模型建立及求解

基于满意度的多目标电力调度主要指的是针对各个用电客户的污染排放以及单位产值用电量等情况，相关的电力运行管理部门对各个客户用电量的电量分配目标进行合理确定，在电力客户电量需求得到满足的前提下，保证有最小的环境污染和最高的电力资源利用率。这种思想不仅可以对电力客户的需求进行充分满足，还可以对那些有着较高耗能和污染的企业发展进行限制，可以在很大程度上促进资源的节约和环境的保护。

模型的目标函数：通过分析我们可以将电力客户满意度的函数给得出来，也就是

在这个公式中，客户满意度用S来评价，第j家工业企业的客户满意度就可以用Sj来表示，企业最大的电能需求量则用Yj来表示。

同理，我们结合企业的电力消耗量、电力资源利用效率以及其他污染物的排放量，就可以得到污染排放的函数，进而得出最小的总用电量。

模型的约束条件：电力目前被人们所广泛使用，作为一种二次能源，特殊性比较强，到如今，还没有有效的解决如何来对其进行大规模的存储，这样就需要在生产和供应电力的过程中实现平衡，有着较强的计划性。在电力供应平衡方面，需要保证本区域计划供应给工业企业的电力总量要大于本区域内所有工业客户的用电量之和。在污染排放约束方面，要想保证本区域的环境质量目标可以达到，就需要严格的控制本区域内污染源的允许排放总量，通过环境容量，来合理确定允许排放总量。而环境容量指的是则是环境能承受最大量的污染物质，但是不能够给影响到人类的正常生存，不会损害到自然生态环境。

模型的求解方法：通常情况下，需要遵循三条原则来对多目标决策问题进行处理，一是化多为少，指的是对目标函数进行全面分析，对目标函数的个数进行最大限度的减少，但是需要保证的是不能影响到正常的决策。二是统一量纲原则，指的是为了更加方便的进行比较，在单目标决策中，需要统一不同方案目标函数值的单位。在多目标决策中，因为各个目标都是独立的，并且有着不同的计量单位，那么在进行多目标决策的过程中，为了消除量纲的影响，就虚假要标准化处理这些指标值，然后对两种指标进行比较。目前，应用比较广泛的主要有两种优化方法，分别是经典的多目标优化方法和灰色例子群算法，前者指的是通过处理或者数学转换多目标优化中的各子目标函数，将其转化为简单的单目标函数，然后进行求解。后者则是通过鸟群捕食行为演化来的，首先对一组随机解进行优化，用粒子来称呼每一个备选解，每一个粒子都有一个速度来对它的移动方向和距离进行决定，还有一个被优化的函数决定的适应度，在解空间内，粒子们在搜索时追寻最优粒子的行为，然后寻找最优解。

4、结语

通过上文的叙述我们可以得知，电力调度在电力系统中占据着十分重要的地位；研究发现，工业用电量和工业总产值都不是孤立存在的，那么就需要对工业污染排放的因素进行分析，探讨工业各个行业用电量和污染排放之间的关系；同时，顾客满意度也是非常重要的一个方面。本文简要分析了基于满意度的多目标电力调度优化，希望可以提供一些有价值的参考意见。

参考文献：

[1]贾永基，王长军.基于满意优化的多目标车辆调度问题模型与算法[J].东华大学学报，2009，2（3）：123-125.

多目标任务调度篇3

任务成功概率是装备在规定任务剖面内能完成任务的概率, 是任务成功性的度量指标, 也是重要的装备保障性评估指标。当前任务成功概率评估模型多是针对单系统开展研究, 系统组成结构串联或是并联, 根据系统部件的可修复情况和修复时间分布给出任务成功概率计算公式[2—4]。文献[5, 6]给出了多种任务特点及要求情况下可修系统的任务成功概率评估模型。对多阶段任务则是研究备件保障水平对任务成功概率的影响[7—10]。网络计划技术非常适用于复杂系统的分析, 其中主要的PERT技术主要考虑工序的时间取值对任务工期的影响[11,12], 没有考虑工序单元故障及修复情况;GERT模型根据概率有多个不同的引出端[13,14], 能够很好地描述流程中活动之间的关系及状态转移, 但不适用于逻辑关系要求严格的系统可靠性问题。多数方法研究保障系统本身的可靠性及维修策略问题, 而对保障任务组成及复杂度关注不够。

鉴于此, 本文基于流水网络计划技术提出一种较为通用的任务成功概率评估仿真方法, 面向多任务要求, 在考虑系统故障及维修资源的基础上, 处理诸如弹药调度系统等此类复杂系统的任务可靠性评估问题。

1 面向多任务的调度系统分析

弹药调度系统具有显著的网络计划性质, 多任务调度过程可理解为流水网络计划的任务分段处理, 但时距关系要求严格。分析其特征如下。

(1) 调度系统由多个相互独立的分系统组成, 分系统之间工作不交叉, 都可独自进行调度任务, 只是在管理系统的统一布置下并行工作。

(2) 分系统具有相同的工序组成, 逻辑关系相同并且要求严格, 分系统按照工序关系组成调度网络计划图, 流水网络计划以此为基础。

(3) 根据资源人员等限制, 确定某些分系统参与调度工作, 最后一个分系统完成任务后才算所要求调度任务的结束。

(4) 根据任务批次量及参与调度的分系统数量, 合理分配调度任务, 工作过程中可根据状态实时调整任务分配。

(5) 分系统中工序单元故障服从一定的分布, 可通过更换件等维修工作进行完全修复, 即故障后恢复为初始完整的功能状态。

(6) 暂不考虑修复失败的情况。

通常的解析方法针对的是串 (并) 联系统的单任务成功性, 或是单部件中多任务的成功性。而弹药调度系统由于其网络结构复杂, 且任务批次量多, 尤其是工序自由时差的存在导致工序单元故障率分布函数取值范围各相不同, 系统的故障率分布函数几乎不可整合, 特别是当工序单元分布函数不同的情况下更是如此。故而采用Monte Carlo仿真方法进行任务成功概率评估, 根据各工序单元分布产生随机数, 以此计算所需数据进行统计分析。

2 基于流水网络计划的任务总工期

2.1 分系统时间参数计算

一般流水网络计划是将一个任务计划分解为多个阶段实施, 以利于工程任务连续紧凑地进行。其区别于网络计划技术的特点是工序间存在时距关系, 即某工序只需其紧前工序开始一段时间后即可实施, 而不需要其完全结束, 如图1所示。

满足时距方程的网络计划才具有流水关系, 方程如下:

式 (1) 中, Ki, i+1为开始时距 (Ki, i+1>0) ;Ji, i+1为结束时距 (Ji, i+1>0) ;ti为活动的持续时间 (ti>0) ;i为活动的代号 (i≥0) 。

而调度任务本身具有多阶段性质, 单个调度分系统任务计划的实施由多个相同的任务流程组成, 每个任务流程都具有相同逻辑顺序关系的网络图, 依照约束条件多个任务流程顺次展开, 最后一个任务流程完成时整个任务计划才算结束。只是其时距关系相对较为严格, 同一流程的工序只有在紧前工序完成后方可开始, 需要对一般流水网络计划的时距方程加上Ki, i+1≥ti条件, 关系如图2所示。此时的工序显然也满足时距关系, 这里仍称作流水网络计划技术。

在此时距关系基础上计算流水网络计划的时间参数, 这里仍以网络计划通常使用的参数作为对象;但需做出调整。假设参与调度任务的分系统共计M个, 第m个调度分系统负责Qm个批次量的任务。双代号网络计划图有n个工作节点组成, 第q个任务流程的工序i-j的时间参数以此表示为:工序持续时间Dm, qi-j、工序最早开始时间Em, qS, i-j、工序最早完成时间Em, qF, i-j、网络计划工期Tm, qp、工序最迟完成时间Lm, qF, i-j、工序最迟开始时间Lm, qS, i-j、工序总时差Tm, qF, i-j等。由于约束条件的变化, 对多任务流程的流水网络计划时间参数的通用计算公式进行修正。

2.1.1 工序最早开始 (完成) 时间

此参数不仅受同一任务流程下其紧前工序的约束, 也受限于前一任务流程的同一工序的完成时间。

(1) 网络计划起始工序:

(2) 其他工序:

式 (3) 中, Em, qS, h-i为工序i-j的各项紧前工序h-i的最早开始时间;Dm, qh-i为工序i-j的紧前工序h-i的持续时间;Em, q-1F, i-j为工序i-j的前一流程的最早完成时间。

计算从网络计划的起节点开始, 各任务流程顺着箭线方向依次逐项计算。

多任务流程的工序最早完成时间计算方法与单流程的网络计划相同, 公式为

2.1.2 网络计划工期

单个调度分系统的任务完成工期为最后一个任务流程的最后一道工序的完成时间, 本文流水网络计划中属于无规定工期情况, 各任务流程的计划工期即等于计算工期Tm, qc=max{Em, qF, i-n}, 其中Em, qF, i-n为第q个流程以终节点为完成节点的工序i-n的最早完成时间。显然此调度分系统的网络计划工期为Tmp=Tm, Qmc。则各任务流程的计划工期为不耽误下一流程完工的完成时间:

2.1.3 工序最迟完成 (开始) 时间

与最早开始时间类似, 受到其紧后工序和下一任务流程中同一工序的最迟开始时间约束。

(1) 以终节点为完成节点的工序:

(2) 其他工序:

多任务流程的工序最迟开始时间计算方法与单流程相同, 公式为

2.1.4 工序总时差

工序总时差表示该工序可以利用的机动时间, 这里仍用单流程计算公式

需要说明的是, 多任务流程工序总时差不仅对其本流程紧前紧后工序有影响, 而且影响到了其他流程工序的可利用时间。正是此参数的存在导致了不同工序相同的故障恢复时间对本分系统任务总工期的影响不同。流水网络计划中, 以各工序最迟开始时间为实际执行时间, 此时可充分利用总时差进行准备工作及任务间的休整。

2.2 总工期确定

基于单个调度分系统流水网络计划时间参数的计算, 确定整个调度任务的总工期。由2.1节可知, 只要确定了调度分系统各任务流程的工序持续时间Dm, qi-j, 就可计算出此系统的任务工期, 因此可将其表示为工序持续时间集合的函数形式:

式 (10) 中, 所有流程工序持续时间集合, 而各任务流程工序时间参数集合

整个调度任务中所有调度分系统全部完成工作后任务才算完成, 亦即是任务总工期由最后完成任务的分系统工期决定, 表示为

2.3 任务分配调整方法

由于各调度分系统组成结构相同, 对每批次调度任务的相同工序持续时间可认为是无差别的, 在任务进展顺利 (即系统各阶段无故障现象发生) 时, 分系统工期与任务批次量有关。此种情况下调度系统可靠性达到100%, 依据对式 (11) 的最小化原则即可确定各分系统的任务批次量。然而, 调度任务风险就是由系统不可预测的故障所造成的, 分析任务成功性则是考虑可能出现的系统故障对任务总工期的影响。

可以设定各分系统的同一工序i-j的故障修复时间为Ri-j。为方便计算操作, 调度任务进行时若分系统m的第q批次任务流程中某工序i-j发生故障, 可任务此时的工序持续时间增加了修复时间的增量, 表示为

考虑修复时间的分系统可形成新的工序持续时间集合, 若任务批次量不作调整, 则其工期表示为。发生故障的情况下, 分系统工期可能显著延长, 必要的情况下则需要向其他分系统转移尚未开始的任务, 其工期又与调度任务量有关, 修正分系统工期表示函数为

设定各分系统的任务量为Q=[Q1…Qm…QM], 依据式 (10) 得到的工期值, 各分系统任务量调整方法如图3所示。

在这种情况下, 以整个调度任务总工期最小化为目标, 以动态调整各分系统的任务批次量为手段来调整调度过程中个别工序故障造成的影响, 在实际可操作情况下获得了任务总工期及各分系统任务量。

3 任务成功概率计算模型

3.1 任务成功率模型

弹药调度的任务成功性表现为调度系统设定保障资源的情况下按时完成规定任务的可能性, 对应的任务成功概率是指其规定任务剖面中成功完成的概率。则可定义弹药调度系统任务成功概率为其任务成功完成总次数与任务执行总次数的比值, 应用蒙特卡罗仿真方法可以简化任务成功概率的计算, 即任务成功概率PMCS=成功完成任务的总次数/仿真总次数。

由第2节的计算可知, 调度任务成功性与上级下达的调度时间有直接关系, 这里要求的调度时间表示为TR, 第w次仿真的任务完成工期为T (w) 。显然, 当T (w) ≤TR时任务成功, 否则失败。统计得出在共计W次仿真中, 按升序关系出现的任务完工期有T=[T1T2…Tc…], 对应出现的频数为N=[N1N2…Nc…], 即有∑Nc=W, 表示其出现概率为P=[P1P2…Pc…]。以要求调度时间TR确定截断位置c', 即当c≤c'时Tc≤TR, 当c>c'时Tc>TR。根据以上描述, 则可得到仿真方法下与TR有关的任务成功概率模型:

式 (14) 表示了任务成功概率与任务要求调度时间的关系, 在加上第2节中考虑到的计划工期与流水网络计划中工序持续时间及故障修复时间的关系, 任务成功概率仿真方法如实反映了调度系统结构组成及可靠性对调度任务的影响。

3.2 仿真操作方法

3.2.1 随机数产生方法

蒙特卡洛仿真的基础工作即是产生合理的随机数, 就本文而言需要产生调度各分系统所有任务流程下的工序持续时间, 以及在此基础上根据工序单元的可靠性分布产生故障点, 进一步修复时间也可随机产生。

设总的调度任务批次量为Q, 各分系统的任务量为Q=[Q1…Qm…QM], 由于调度过程中不可预测故障的出现, Q是动态调整的。而对于每一次仿真过程而言, 各分系统工序的持续时间一旦产生之后就是固定的, 不可随任务量的增减而改变。这里为保证操作方便, 在第w次仿真过程中, 对每个分系统m的工序i-j持续时间都产生Q个, 即, 任务工期计算过程中, 根据分系统的任务量取其前Qm个进行运算, 可保证Qm≤Q。具体的数值根据工序的持续时间分布随机产生。

随机产生的时刻点落在范围内, 表示该工序单元此阶段任务过程中出现故障, 则应用公式 (12) 处理其持续时间。需要说明的是, 由于故障均可通过更换备件等措施予以排除, 可认为单元“修复如新”, 即其累计工作时间需要从0重新开始算起。

以上的相关随机数产生方法确定了各调度分系统的时间参数, 只是的维数全为总任务批次量Q, 通过任务工期的计算及任务量的调整, 可最终确定此次仿真过程中的任务总工期及各分系统的任务量。

3.2.2 仿真流程

根据随机数产生方法及通用Monte Carlo方法, 基于仿真过程的多任务调度系统任务成功概率评估流程如下。

步骤1:设定仿真次数W、调度批次量Q、参与调度的分系统数量M, w=1;

步骤2:产生各分系统工序的Q维持续时间集合, 以此为基础产生随机故障点, 修正持续时间集合为

步骤3:确定各分系统任务量Q=[Q1…Qm…QM];

步骤5:如果需要根据2.3节方法调整Q, 转步骤3, 否则转步骤6;

步骤6:若w<W, w=w+1转步骤2, 否则转步骤7;

步骤7:统计总工期为Tc的次数Nc, 获取各总工期值出现的频率P=[P1P2…Pc…];

步骤8:根据式 (14) 得到任务成功概率与要求调度时间的关系PMCS (TR) ;

步骤9:结束。

3.3 几类情况考虑

考虑到调度系统工序持续时间分布、故障概率分布、修复时间分布以及保障资源配置对任务成功性的影响, 将调度任务可能遇到的情况分为以下几类。

3.3.1 Ⅰ类情况

此类情况属于无故障条件下的任务调度, 调度系统各设施设备可靠性极高, 或设定任务下故障现象不可能发生。则仿真过程中只需确定工序持续时间, 根据均衡化原则确定调度任务分配方案, 以任务总工期最小化为目标静态确定调度时间。

3.3.2 Ⅱ类情况

通常情况下需要考虑工序可能的故障情况。工序单元的可靠性函数与其累计工作时间有关, 实际情况中必须考虑发生故障情况下的调度任务风险。由于故障发生的不可预测性, 工序故障修复时间显然影响了此分系统的任务工期, 进而可能影响调度任务总工期。若分系统的任务工期由于故障而显著延长, 则需随时调整任务分配方案, 仿真过程中这是个动态过程。进一步可讨论工序故障修复持续时间的取值, 通过其分布函数同样随机产生式 (12) 中的Ri-j。

3.3.3 Ⅲ类情况

以上两种情况下没有考虑维修资源的限制, 而有些情况下维修小组数量级备件数量会限制到故障的即是修复。此类情况下可能会出现两种结果: (1) 维修小组的限制, 倘若某工序故障时所有的维修小组已经处于忙的状态, 则修复时间Ri-j还需加上等待时间; (2) 备件数量的限制, 如果某工序故障时缺乏相应备件, 则其处于不可修复状态, 此分系统只能完成本工序之后业已开始的任务, 之前的乔杜批次量需要调整给其他分系统。

4 算例

某调度系统包括6个工序逻辑关系相同的分系统, 网络计划关系如图5所示。系统中各工序执行小组兼有维修职责, 故可不考虑维修资源对任务进度的影响, 显然属于Ⅱ类情况。下面对调度任务批次量为Q=20的任务成功概率进行仿真分析。

工序持续时间采用三时估计法确定, 其概率分布可认为是正态分布, 分布形状可由乐观时间a、最可能时间m和悲观时间b确定, 计算公式:期望、方差。工序单元故障率服从指数分布F (t) =1-e-t/λ, 故障修复时间认为是固定的。相关时间参数见表1, 时间单位为同一量纲。

仿真次数设置为W=10 000, 图6所示为当参与调度任务的分系统数量为3时的一次仿真结果, 进度条中间的数字表示此分系统的第几批次任务, 3个分系统的任务批次量依次为7、7、6, 调度时间由分系统1决定, 进度条中浅颜色为故障修复时间。调度任务成功概率随要求调度时间的变化情况如图7所示。

当参与调度的分系统数量不同时, 对应的任务成功概率及要求任务工期显然不同, 图8所示为任务成功概率分别为99.9%、99.0%和90.0%时不同分系统数量对应的要求任务工期大小。参与调度的分系统数量要求越多, 需要的资源及人员也就越多, 此参数的意义在于可供指挥决策人员综合任务工期、可靠性要求以及调度资源来确定调度方案。

5 总结

从弹药调度系统执行多任务情况出发, 分析提取了此类复杂系统的特征。应用流水网络计划技术确定了分系统固定任务下的进度时间参数, 在确定任务总工期的基础上建立了任务成功概率仿真模型。此模型具有广泛的通用性, 工序单元可服从不同的可靠性函数, 甚至只需知道工序持续时间及故障时间的取值规则和范围便可进行仿真分析, 系统结构越复杂越能体现其优越性。此方法给出了几类不同保障情形下的应用形式, 正确评估了复杂多任务下的任务成功概率, 为弹药调度方案的制定及保障资源的优化配置提供决策依据。

摘要：正确评估弹药调度系统的任务成功概率, 作为装备可靠性分析的重要内容, 是制定装备保障方案和优化配置保障资源的重要依据。针对多任务调度系统的复杂性, 以流水网络计划为框架, 计算分系统调度进度时间参数。考虑工序单元故障及修复时间的情况下动态调整分系统的任务量, 最终确定任务总工期。以此将任务总工期作为任务成功概率的比较数据, 根据工序持续时间及故障时间分布产生随机数据, 应用蒙特卡洛方法对仿真结果进行统计分析, 建立了任务成功概率评估模型。并且分析了几类维修资源配置情形下的仿真操作方法, 提高了评估方法的实际应用能力。最后, 通过一个算例验证评估方法的有效性和实用性。

多目标任务调度篇4

关键词：多任务,调度,Delphi,事件

在多任务处理的相关应用中,经常需要用到多线程技术。多线程应用程序将程序划分为多个独立的任务,主要作用有以下几点:1)对于带有界面的应用程序,通过将密集计算模块放入后台工作线程,可以使程序界面一直处于活动状态,避免程序“假死”,改善用户体验。2)多个任务需要并行处理时,可以通过多线程技术轮流获得CPU时间。3)当多个任务重要程度不相同时,可以通过线程的优先级设定来优先满足重要任务的资源需要。

虽然多线程技术有诸多优点,但是大量线程的创建、切换、销毁会额外占用不少宝贵的CPU资源。因此为了最大限度的减少线程的创建和销毁次数,笔者在Delphi开发环境下,运用Windows API和Object Pascal编程语言设计了一种通用的、资源占用率较低的多任务调度模型。主要设计思路是将处理同一类任务的线程抽象成处理机类,另外设计一种调度类来负责任务的指派,处理机的管理。调度类的对象将根据用户预先设定的处理机数目创建并管理处理机对象,每个处理机处理完当前任务之后将排队等待调度对象分配后续任务。这样将最大限度的减少线程的创建和销毁的次数,增加有效任务的CPU时间,提高程序效率。

1 模型说明

此多任务调度模型主要由三个部分组成,运用面向对象的思想将此三个对象抽象成为三个类,分别为调度类TScheduler、处理机类TAgent、任务类TMission。模型体系结构如图1所示。

1.1 调度类TScheduler

调度类在整个系统中只能实例化一个对象,它可以指定并行任务的数目,然后生成相应数量的TAgent对象,并控制任务资源的合理分配以保持多个TAgent对象对资源竞争时的同步和互斥。如果某个TAgent获取任务后长期得不到CPU时间,会产生线程假死现象,本模型采用如下处理策略:如果某一TAgent对象对某一任务的处理时间超过了一个时间阈值,那么就强行中止该TAgent对象的运行,清空其处理结果,并将其正在处理的任务放回任务队列。TSched-uler类声明的主要逻辑代码如下:

本模型为了提高通用性引入了事件机制,事件表示某个动作的发生,诸如单击一个按钮、按下键盘上的一个键等。在模型中,通过引入事件机制可以灵活指定在某个动作发生时需要执行的操作。本模型共定义了三个事件:OnAgentInitializing、OnProcessMission和OnAgentFinalizing,分别在Agent对象初始化时、得到任务进行处理时、结束所有任务时触发。现以OnProcessMission事件为例,详细介绍事件机制在本模型中的应用。事件句柄的类型为:TProcessMission=procedure(Sender:TScheduler;Mission:TMission;Agent:T Agent)of object;事件句柄实际上就是一个函数指针,规定了函数的类型和返回值。此处通过事件句柄传递了三个信息:当前调度对象、当前任务对象和当前处理机对象。在Agent对象的Execute方法中触发此事件,就可以对指定的任务调用指定的算法模块。

1.2 处理机类TAgent

TAgent类继承自Delphi封装的线程类TThread,TAgent类型的对象由TScheduler对象统一管理和调度,对外部对象来说是透明的。一个TAgent对象本质上是一个内核级的线程,是由操作系统感知和调度的。

TAgent类的主要处理逻辑都在Execute方法中,此方法主要完成了排队申请任务,处理任务,状态反馈,通知TScheduler实例定时清理死线程的功能。其主要处理流程如图2。

1.3 任务类TMission

由于不同的应用场合的任务形式有所不同,因此在此模型中将TMission类定义为了抽象类,在具体应用时需要根据具体应用来继承扩展TMission类。

2 模型应用

笔者在参与开发的飞机排班系统中对此模型进行了应用验证。飞机排班就是以机型为唯一的任务号,为每个机型的飞机安排每天的飞行任务。具体应用过程如下:1)将用MATLAB语言编写的飞机排班算法编译成DLL文件。2)实例化一个TScheduler对象,指定初始化参数,指定各个自定义事件的事件处理函数。3)在OnProcessMission事件中调用飞机排班算法DLL,算法根据得到的机型去数据库中取出相应数据,编排完成后将数据存入数据库。通过多个任务的并行编排,明显提高了飞机排班速度,达到了预期的运行效果。

3 总结

本文提出了一种在Delphi开发环境下实现的线程调度模型,通过自定义事件的机制提高了该模型的通用性和灵活性,同时引入了死亡线程检测机制,避免了CPU资源的浪费。本模型在需要同时开启大量任务的场合具有一定的实用性。

参考文献

[1]罗宇,商临锋.操作系统多线程实现技术研究[J].小型微型计算机系统,2000,21(5):500-503.

[2]黄德才,钱能.多机相关任务均衡调度问题的复杂性与新算法[J].计算机工程与科学,2000,22(2):15-17.

多目标任务调度篇5

在网格计算中, 资源管理、任务管理、任务调度是必须具备的三个最基本功能。作为一种新生的计算技术, 系统中的计算资源动态分布, 异构多样, 具有诸多独特的特点, 这也使得在网格计算中的任务调度策略比传统的高性能计算系统更加复杂。众所周知网格计算任务调度是一个NP完全问题, 吸引了众多学者的关注, 成为当前网格计算研究领域的一个热点问题[1]。在目前的网格任务调度中被广泛采用的主要有Min-Min算法[2]、Max-Min算法[3]、遗传算法 (GA) [4,5]、模拟退火算法 (SA) 等。在文献[6]中对11种启发式调度算法的比较中可以看出无论是哪种调度算法都有其适用的范围, 同时也都有不足之处, 在特定的应用情况下优劣皆有。随着网格任务、计算资源类型越来越复杂, 在任务调度时需要考虑的因素也越来越多。针对异构网络环境下独立任务调度问题, 在分析网格任务和处理资源的各种属性基础上, 综合考虑任务优先级、任务工作量、任务类型, 执行效率、负载均衡、服务质量等诸多因素[7], 提出了一种基于批模式的多属性任务调度算法MASA (Multiple Attribute Scheduling Algorithm) 。此算法运用统计学的归一化处理, 截断处理等方法计算出任务与处理资源之间的匹配概率矩阵指导任务映射。综合考虑各属性因素, 达到更优的任务调度。

1 网格任务模型定义

从多个任务中每次取一定数量的任务到任务队列, 这些任务已经不可再划分, 任务间彼此独立无依赖关系, 每个任务有一系列给定的属性, 这些属性影响任务的调度。另有多个异构网格[8]资源来处理任务[9], 这些网格资源是动态变化的, 可能增加也可能减少[10,11]。每个资源串行的处理任务, 每个资源也有一系列属性, 这些属性影响对任务的调度或处理。把所有的属性分为两类影响调度的因素: (1) 影响执行顺序的因素, 通常此因素只与任务属性有关。 (2) 影响任务映射到处理单元的因素, 这类因素与任务属性和资源属性皆有关。又把后一类因素分为限制因素和影响因素, 限制因素决定某任务是否可以映射到该网格资源, 影响因素则影响任务映射到某个网格资源。

调度模型形式化描述如下[12]:

(1) 任务采用批模式进行调度, 每次从多个任务中取n个独立任务到任务队列, 处理资源队列中有m个异构资源可用;

(2) 参与调度的任务集合T={T1, T2, T3…Tn};

(3) 可用资源集合R={R1, R2, R3…Rm};

(4) 任务Ti的属性集合TPi={t Pi1, t Pi2, t Pi3…t Pik};

(5) 资源Rj的属性集合RPj={r Pj1, r Pj2, r Pj3…r Pjk};

(6) 由n个任务的某一相同属性t Pik组成影响执行顺序的因素向量Fk;

(7) n个任务映射到m个计算资源的匹配因素矩阵TMk。

2 多属性调度算法描述

2.1 影响执行顺序因素处理

假如在任务T中有x个影响执行顺序的因素 (通常此因素只与任务属性有关) , 当有m个任务时, 每个因素由m个任务的同一属性组成。所以每个因素可表示成1行m列的向量。则第k个影响执行顺序的因素可表示为:

fki表示第k个影响执行顺序因素中的第i个任务属性分量。为方便后续因素的综合计算, 利用归一化处理方法把各因素分量归一化到设定的η到1之间, 并且最后都成为越大越好的因素, 方便于统一考虑。按消极因素 (越小越好) 和积极因素 (越大越好) 分别做归一化处理, 消极因素归一化处理方法:

积极因素归一化处理方法:

当有多个影响执行顺序的因素时, 可根据需求设置影响执行顺序各因素的权值Wi:

则综上所述x个影响顺序的因素可得到每个任务执行顺序概率POi:

2.2 影响任务映射因素处理

假设有y个影响任务和处理单元映射的因素, 其中又分为两类因素: (1) y0个限制映射因素。 (2) y1个影响映射因素。每个因素均为m×n的矩阵, 则对于第k个因素有如下矩阵:

fkij表示:把第i行的任务映射到第j列资源处理时的第k个映射因素分量。为防止任务映射到不满足条件的处理资源上, 对于y0个限制映射因素先需要对其进行截断处理, 然后再归一化, 截断处理仅针对于限制性因素, 在截断处理时也分为积极因素和消极因素。消极因素截断处理方法:

积极因素截断处理:

这样就使得消极因素中不满足限制条件的元素成为最大元, 而其他满足前提性条件的元素均小于它。而积极因素中不满足前提条件的元素成为最小元, 而且其它满足前提性条件的元素均大于它。这样就在后面归一过程中取η=0, 使得不满足限制条件的元素成为0, 而其它元至少大于0。在求最后匹配概率时, 这个对应的概率为0的调度就不会实现, 也就避免了不满足限制条件的调度发生。

归一化处理则在三种类型因素下均有使用, 通过分为消极因素和积极因素的归一化处理, 将各因素均化为0到1之间, 并且都成为越大越好的因素。y1个影响因素也分为积极因素和消极因素, 对影响因素做处理将他们归一化到η到1之间。同上已述归一化处理方法。当有多个影响映射的因素时, 可根据需求设置各影响因素权值:

由限制映射因素和影响映射因素计算每个任务与可用资源的匹配概率:

最后在得到综合概率时, 实际上希望匹配概率和执行顺序概率都比较大时理想概率也越大。这时综合考虑处理顺序概率和匹配概率, 就得到理想状态下各任务映射到处理资源的综合概率Pij, 以此匹配概率为基础来指导任务映射到哪一个处理器单元。

2.3 算法伪码描述

该算法首先取一批任务task_num个到队列, 对所取任务相关属性因素进行归一化处理, 计算执行顺序概率, 并按概率由大到小排序任务。之后初始化计算资源, 根据资源空闲情况从任务队列中取前k个任务计算匹配概率。最后计算综合概率完成任务分配。任务分配后刷新资源, 准备下一轮调度。伪代码描述如下[9]:

1:Procedure task_mapping

2:Get Task (task_num) //取task_num个任务到队列

3:Calc PO () //计算任务顺序概率POi

4:Sort PO () //按概率由大到小排序任务

5:Init CompResou () //初始化计算资源

6:While (task_num!=0)

7:Calc PPMatr (k) //取k个任务计算匹配概率PPij

8:Calc PMatr (k) //计算所取k个任务的综合概率Pij

9:Assigning_Task () //分配任务

10:Refresh CompResou () //刷新计算资源

11:End While

12:End

3 仿真实验及结果分析

在对MASA算法实验的过程中, 为满足任务的多属性和处理资源的异构特征, 对Grid Sim工具进行了二次开发。将Grid Sim原有任务类型Gridlet和新加入的任务属性封装成新的任务类, 包含了任务优先级、任务类型、需达到的准确率[13]等属性。将Grid Sim原有的资源类型封装成对各类任务有不同处理速度和处理准确率的新资源类。在仿真实验中各资源都采用Solaris系统;带宽值从[100M, 200M]中随机选择。在试验中假定有三类任务, 各资源对每一类任务的执行速率MIPS (每秒百万条指令) 表示, 从[100, 500]范围随机选择。对于MASA算法, 用两个标准来评价其性能:

(1) 所有任务完成总时间Make Span。

(2) w1 (任务长度) :w2 (优先级) 的权值不同时, 具有高权值属性的任务普遍先于低权值属性的任务执行。

根据评价标准, 仿真实验如下:

实验1任务数分别为100、200、300、400、500。资源数由5依次增加到20。分别用Min-min、Maxmin以及MASA算法做任务调度仿真。多次执行获取平均值。

实验2任务数为100、资源数为10。分别设置w1 (任务长度) :w2 (优先级) 为0.8:0.2和0.2:0.8。对比研究属性权重对调度结果的影响。

本文首先分析实验1, 三种调度算法在任务数分别为100、200、300、400、500的情况下, 随资源数增加, 平均总调度长度Make Span变化情况如图1所示。

通过图1对比可以看出MASA算法的Make S-pan比Min-min算法和Max-min算法的Make Span都要小。实验2中不同属性权值对调度结果的影响如图2所示。

从图2统计的散点图中可以看出当任务长度所占权值为0.8时, 任务长度较小的最先被映射, 长任务普遍映射较晚。当优先级权值增加到0.8时, 优先级高任务先被映射。通过此实验说明给定不同的权值, 能够有效地权衡各属性, 灵活地调度任务, 在考虑多属性的基础上也能有所侧重地得到所期待的调度结果。

4 结束语

多目标任务调度篇6

VxWorks是美国Windriver公司设计开发的一种嵌入式实时操作系统 (RTOS) , 实时内核Wind提供了多任务的环境。随着发展, Vxworks稳定、可靠, 且实时性好, 在航空航天、电力电子等领域, 越来越多嵌入式控制设备采用了Vxworks操作系统。

RTOS研究的关键是实时任务调度的设计。RTOS中实时调度技术通常划分为抢占式调度和非抢占式调度, 前者为静态表驱动策略, 后者为优先级驱动策略一种观点提出:抢占式调度算法相对简单, 运算速度快, 实时性好, 高优先级任务可优先保证, 但上下文切换较多。而非抢占式调度虽然上下文切换少, 但通常处理器的资源利用率低。

Liu和Layland两人共同提出的速率单调 (RateMonotonic—RM) 算法是典型的静态调度算法。在一种典动态优先级调度算法是截止期限优先 (EDF) 算法。直到目前, 在实时调度算法领域的研究, 学术界都是在RM或EDF两种算法的基础上发展而来。

RM调度的原理是为每一个任务指定优先级, 周期越短的任务, 优先级越高, 调度最先运行优先级高的任务, 种可预测方法, 要求对任务相关约束参数必需预知, 如执行时间、时序约束、截止期限等。

EDF调度同样为任务指定优先级, 具有最早截止期限的任务赋与最高优先级, 调度最先运行有最早截止期限的任务, 即具有最高优先级的任务。EDF调度的周期任务的优先级是变化的, 对每一个可调度时刻, 将根据变化的任务最早截止期限, 随时改变其优先级。

Vxworks系统的特点是给出了两种任务调度方法:时间片轮转调度和抢占式调度, 后者基于优先级。工程经验显示, 固定优先级调度方法常被采用, 但对于有周期任务存在的SPDA系统, 采用时间片轮转调度的优势是可以保证周期任务的及时运行。由于高实时性要求任务之间不能存在大量数据传输、不便与网络相连, 所以, 任务之间采取Vxworks系统简单的高速的信号量通信方式。

本文提出了一种单CPU下时间片轮转与和优先级抢占相结合的混合调度算法。

2、语音控制系统的功能

该语音控制系统的主要功能是为电力负载提供电源控制管理, 根据人工声音命令和负载设备的电气状态调整电源的通断, 保证电力系统的安全运行。

按照系统功能要求, 其软件的运行流程图如图1所示:

根据上图可将系统分为9个任务, 分别是:

(TASK1) 循环读取环形缓存区 (ReadFor_Order) :人工声音命令被采样数字化后存于环形缓存区中, 对该缓存区进行不间断查询;

(TASK2) 循环发也命令对状态电流值进行索取 (AskFor_Va lu) :通过数据总线不间断向负载发送命令对即时负载状态和电流值进行索取;

(TASK3) 保存电流值, 计算I2t延迟时间 (Save_Data_CountT ime) :将负载通过数据总线传输的状态电流值保存到ROM中, 并监控实时采集的状态电流值变化情况, 发现负载电流值过载时, 计算并关断负载电源的时间;

(TASK 4) 判断串口命令 (Deal_Order) :对读出的人工数据进行解析, 包括去噪、识别等处理;

(TASK 5) 上传状态电流值 (Send_Valu) :根据人工命令将保存在ROM中的当前负载的状态电流值显示于显示屏上;

(TASK 6) 发送开通命令 (Send_Order_1) :根据人工命令控制负载电源的开通;

(TASK 7) 发送断开命令 (Send_Order_2) :根据人工命令控制负载电源的断开;

(TASK 8) 采集模拟及I/O信号量 (For_ADIO) :根据人工命令对外接的模拟信号量和I/O信号量进行采集并显示于显示屏上;

(TASK 9) BIT自检 (BIT) :在系统运行时对一些系统模块进行自检测。

从图中可以看出, 能否及时的执行命令要求操作直接关系着整个电力系统的安全运行。

3、系统多任务调度算法冗) �

3.1 任务优先级的划分

周期任务的优先级的划分遵从的原则如下:H��

(1) 为确保高优先级任务优先抢占临界资源, 采用时间片轮转

调度的任务的优先级原则上为最低;堗) �

(2) 依据周期任务在系统中的重要性划分优先级, 任务越重要, 优先级就越高, 反之则优先级越低。

依据任务的权重, 优先级的划分见下表:

说明:如上表所示, 优先级数值越小, 优先级确越高。ReadFor_Order、BIT和AskFor_Value三个周期命令的优先级相同, 均采用时间片轮转调度。Send_Order_1与Send_Order_2这两个任务不会被同时要求执行的, 可以设置为相同优先级, 图2为调度算法示意图:

3.2 信号量通信

系统运行时, 低优先级的周期任务要比高优先级的非周期任务先运行, 非周期任务等待周期任务执行完时才可以进入排队状态, 具备抢占临界资源的资格, 开始运行, 运行完成之后要再次阻塞, 让出临界资源, 使得周期任务能够运行。这一阻塞/运行/阻塞的过程可以通过信号量的通信机制达到理想的效果。信号量通信示意图如图3所示。

说明:信号量Sem_i的初始状态为不可用 (EMPTY) , 各非周期任务一开始就调用函数semTake (Sem_i) 将自己阻塞, 周期任务在一定的条件下调用函数semGive (Sem_i) 来释放相应的信号量, 使得需要执行的非周期任务进入就绪状态。

4、调度算法仿真测试

仿真实验中周期任务调度非常频繁, 大量调度数据在仿真环境中无法全部存储, 所以, 我们把调度显示图分成两部分, 横轴为时间轴, 纵轴为任务集。图4中, 三个任务的调度算法为时间片轮转调度, 可以看出, 周期任务的时间片轮转调度切换时间非常短;图5显示了高优先级任务抢占调度的情况, 也可以看出, 多任务在抢占资源时切换时间也非常短, 几乎无法分辩。与RM算法不同, 仿真实验中周期任务之间的调度与各任务的执行时间、时序约束以及截止时间等参数没有关系, 需要指出的是, 即使这些参数未知和不稳定, 本系统所用的算法也可以实现高实时性的任务调度。而且在经过3个小时的连续试验中, 系统工作正常。

5、结语

本文描述了一种语音控制系统软件的设计与应用, 着重分析了在Vxworks操作系统中基于系统权重的任务调度算法的实现与仿真。采用信号量通信来激活/阻塞任务, 上下文切换时间在毫秒级, 在3个小时的连续动行中, 系统工作正常, 算法顺利实现系统的高实时性和高稳定性。对于SPDA系统新的功能和更多任务的调度算法设计, 待进一步研究。

参考文献

[1]张友生:系统分析与设计技术, P282:清华大学出版社出版, 2005, ISBN 7302101604, 9787302101604.

[2]道格拉斯, Bruce Powel Douglass, 柳翔.嵌入式与实时系统开发/使用UML、对象技术、框架与模式/计算机科学丛书/Doing HardTime:使用UML、对象技术、框架与模式:机械工业出版社出版, 2005, ISBN 7111155920, 9787111155928.

[3]Liu C L, Layland J.Scheduling algorithms for multiprogrammingin a hard real-time environment[J].J.ACM, 1973, 20 (1) :46-61.

[4]Scott A Brandt, Scott Banachowski, Caixue Lin, et al.Dynamicintegrated scheduling of hard real-time, soft real-time and non-real-time Processes[R].Proceedings of the 24th IEEE Real-TimeSystems Symposium (RTSS 2003) , 2003.

[5]Batptiste P, Pape C L, Nuijten W.Constraint-based scheduling:Applying constraint programming to scheduling problems[M].Boston:Kluwer Academic Publishers, 2001.

[6]Mahmood A.A hybrid genetic algorithm for task schedulingin-multiprocessor real-time systems[J].Studies in Informaticsand Control, 2000, 9 (3) :207-218.

[7]乔颖, 王宏安, 戴国忠.一种新的实时多处理器系统的动态调度算法[J].软件学报, 2002, 13 (1) :51-58.

[8]Peng Liu, Ming Cai, Tingting Fu, and Jinxiang Dong:An EDFInterrupt Handling Scheme for Real-Time Kernel:Design andTask Simulation:Y.Shi et al. (Eds.) :ICCS 2007, Part IV, LNCS4490, pp.969–972, 2007.

[9]Zhou, Lei;Shin, Kang G.;Rundensteiner, Elke A.:Rate-monotonic scheduling in the presence of timing unpredictability:Real-Time Technology and Applications–Proceedings, 1998

多目标任务调度篇7

随着电力系统向大规模发展以及全国联网的初步形成,互联大系统的分解协调计算越来越受到关注[1,2]。解决大系统优化问题的基本思路是将总体问题设法分解为一系列的子问题,通过对子问题各自进行局部优化,使问题得以简化。经典的方法有Benders分解法[3],Dantzig-Wolfe分解法[4]和拉格朗日松弛分解法[5]。文献[6]基于部分对偶理论把全局最优潮流求解问题分解成为多个区域协同优化求解的问题,取得了良好的计算效果。上述文献中,大系统分解协调优化都是基于单目标数学模型。然而实际问题往往面临着多个目标之间的权衡与协调,即多目标决策。如目前电力工业面临的节能环保问题,就是兼顾经济性与环保效果的多目标优化决策。

国外学者对发电调度中的多目标决策研究较早。文献[7]对考虑环境与经济性的多目标调度算法做了一个比较全面的综述。文献[8]采用多目标进化算法求解此类问题。但是这些研究均没有涉及多区域发电调度的多目标决策问题。在实际系统中,各区域的环境质量状况、生产成本、排放基数等客观情况不尽相同,如果各区域采取相同的多目标决策偏好,那么结果与全局优化一致,只能在计算精度和收敛速度上得到一定的提高。

本文提出了一种新的多目标协同优化方法。将大系统分解为多个区域后,各区域根据自身的实际情况设置多目标决策偏好,进行分布式并行优化,并将该方法用于求解考虑经济和环保的互联区域发电调度决策。算例仿真表明,该方法能够以尽量小的经济损失达到环境保护的效果,得到更优的多目标协调解。在电力行业节能减排等环保政策的背景下,具有现实意义。

1 互联区域分解协同优化

在电力系统中,大电网分解成多个相对独立的区域进行协调调度。将电网分区后,模型如图1所示,子系统通过边界节点互联。将变量X分为XA,XB,XAB,XBA这4个部分,其中XA和XB分别表示2个分区内的变量,XAB为A区与B区间联络线上的变量,XBA为B区与A区间联络线上的变量。其中,解列点XAB和XBA为电气上相同的点,具有相同的电气量。

互联电网发电调度的数学模型可表示为:

${\begin{cases} \min F (X_{A}, X_{B}) = f (X_{A}, X_{B}) \\ s . t . h_{L A} (X_{A}, X_{A B}) = 0 \\ h_{L B} (X_{B}, X_{B A}) = 0 \\ g_{A} (X_{A}) \leq 0 \\ g_{B} (X_{B}) \leq 0 \end{cases} (1)$

式中:F为目标函数,一般为发电费用最小;hLA和hLB分别为区域A和B的耦合约束;gA和gB分别为A和B区域内的等式或不等式约束。

如图1所示,电网分区后,断开区域联络线ij(i∈A,j∈B),引入联络线变量TABij 表示由A区内节点i流向开断点的有功潮流,变量T $_{j i}^{B A}$ 表示由B区内节点j流向开断点的有功潮流。因此,区域耦合约束可表示为:

${\begin{cases} h_{L A} (X_{A}, X_{A B}) = \frac{θ_{i}^{A} - θ_{j}^{B}}{x_{i j}^{A B}} - Τ_{i j}^{A B} = 0 \\ h_{L B} (X_{B}, X_{B A}) = \frac{θ_{j}^{B} - θ_{i}^{A}}{x_{j i}^{B A}} - Τ_{j i}^{B A} = 0 \end{cases} (2)$

式中:θAi 和θBj 分别为节点i和j的相位角;x $_{i j}^{A B}$ 和x $_{j i}^{B A}$ 分别为节点i和j到开断点这段线路的电抗;i∈A;j∈B。

应用部分对偶理论,分解后区域A的数学模型可以表示为:

${\begin{cases} \min F_{A} = f_{A} (X_{A}) - \hat{η}^{A B} h_{L B} (X_{B}, \hat{X}_{B A}) \\ s . t . g_{A} (X_{A}) \leq 0 \end{cases} (3)$

式中: $\hat{η}^{A B}$ 的物理意义为AB之间联络线的传输价格; $\hat{X}$ BA为与B区交换边界数据后得到的参数。

同理,可以写出区域B的数学模型。

互联区域协调优化的收敛判据为:每个区域计算出的联络线潮流与毗邻区域计算出的该联络线潮流 $\hat{Τ}_{j i}^{B A}$ 之差小于一个给定的收敛精度ε,即

$| Τ_{i j}^{A B} - \hat{Τ}_{j i}^{B A} | \leq ε i \in A, j \in B (4)$

2 多目标发电调度模型

传统的发电调度一般是以发电费用最小为目标。在环境污染日趋严重的全球背景下,发电调度决策越来越多地考虑经济性与环境保护的相互协调,从而成为一个多目标问题。多目标决策中,各目标函数往往相互矛盾、具有不可公度性。发电调度决策中,生产费用与污染排放是2个相互矛盾的目标,体现了环境与经济相互制约与协调的关系,数学表达如下:

$\begin{array}{l} \min f_{1} = \sum_{i = 1}^{Ν_{G}} C_{i} (Ρ_{i}) Ρ_{i} (5) \\ \min f_{2} = \sum_{i = 1}^{Ν_{G}} α_{i} + β_{i} Ρ_{i} + γ_{i} Ρ_{i}^{2} (6) \end{array}$

式中:Pi为发电机i的有功出力;Ci(Pi)为生产费用函数,表示为Ci(Pi)=aiPi+bi;f1为总生产费用;αi,βi,γi分别为机组i的污染气体排放系数;f2为总污染排放量。

按照线性加权和方法,将多目标优化问题转化为单目标问题[9]:

$f (Ρ) = \min ω f_{1} (Ρ) + (1 - ω) χ f_{2} (Ρ) (7)$

式中:ω和1-ω分别为f1和f2的决策偏好系数,体现决策者对2个目标函数的重视程度;χ为2个目标函数的单位转换系数,采用系统最优生产费用与系统最小排放量之间的比值,χ=min C/min E;min C表示系统最优生产费用,以单独求解目标函数f1得到生产费用的最小值;min E表示系统最小排放量,以单独求解目标函数f2得到污染排放的最小量。

3 互联区域多目标发电调度模型及求解

电力系统中各区域的实际情况往往不同,有的区域中污染轻但发电成本高的大机组占主要比例,有的区域中污染重但发电成本低的老机组较多,而有的区域中2类机组数量相当。以往的多目标决策通常从全局的角度,设定统一的决策偏好系数,没有分别考虑各区域的不同情况。本文尝试了一种新的互联区域多目标求解方法,将各区域的决策偏好系数视为变量,由拉格朗日函数求导得到最优的偏好系数,即由各区域的自身客观情况决定其偏好取值,从而优化整个系统的结果。

将多目标函数(式(7))与区域耦合约束(式(2))代入式((3))(略去常数项),并具体写出区域A内的等式与不等式约束,如下[10]:

$\begin{array}{l} \min F_{A} = ω_{A} \sum_{i \in A} (a_{i} Ρ_{i} + b_{i}) Ρ_{i} + χ_{A} (1 - ω_{A}) \cdot \\ \sum_{i \in A} (γ_{i} Ρ_{i}^{2} + β_{i} Ρ_{i} + α_{i}) - \sum_{\begin{array}{l} i \in A \\ j \in B \end{array}} \hat{η}_{i j}^{A B} \frac{θ_{i}^{A}}{x_{j i}^{B A}} (8) \\ s . t . Μ^{A} θ^{A} + Η_{t i e}^{A} Τ^{A B} = Ρ^{A} - D^{A} (9) \\ Ρ_{i}^{A, \min} \leq Ρ_{i}^{A} \leq Ρ_{i}^{A, \max} i \in A (10) \\ | \frac{θ_{i} - θ_{j}}{x_{i j}} | \leq F_{i j}^{\max} i, j \in A (11) \\ \frac{θ_{i}^{A} - \hat{θ}_{j}^{B}}{x_{i j}^{A B}} = Τ_{i j}^{A B} i \in A, j \in B (12) \\ | Τ_{i j}^{A B} | \leq Τ_{i j}^{A B m a x} i \in A, j \in B (13) \\ 0 \leq ω_{A} \leq 1 (14) \end{array}$

式中:MA为A区内线路的电纳矩阵(去除联络线);θA为A区内节点的电压相角向量;HAtie 为A区内节点与联络线的关联矩阵,A区内节点为联络线始节点时相应值为1,为联络线末节点时相应值为-1,非联络线节点时相应值为0;TAB表示由T $_{i j}^{A B}$ 组成的向量;PA与DA分别为A区内有功出力与负荷向量;xij(i,j∈A)为A区内线路电抗;Fmaxij(i,j∈A)为A区内线路最大传输功率; $\hat{θ}_{j}^{B}$ 为相毗邻区域B计算得到的边界节点j的相角;TABmaxij (i∈A,j∈B)为联络线的传输功率上限。

式(9)表示A区内的有功功率平衡约束。式(10)表示A区内节点有功上下限约束。式(11)表示A区内的线路有功传输约束。式(12)～(13)表示区域A与B之间联络线的传输功率约束。

将式(8)～式(14)写成拉格朗日函数,并分别对PA,θA,TAB,ωA求导(求导过程见附录A),对方程组联立求解得:

$ω_{A} = \frac{χ_{A} (2 e^{Τ} γ Ρ^{A} + e^{Τ} β) - e^{Τ} \hat{η}^{A B} (W_{t i e}^{A})^{Τ} \tilde{Μ}^{A}}{χ_{A} (2 e^{Τ} γ Ρ^{A} + e^{Τ} β) - (2 e^{Τ} Λ Ρ^{A} + e^{Τ} b)} (15)$

式中:eT为单位向量;Λ为由生产费用函数的二阶系数ai为主元的对角阵;b为由生产费用函数的一阶系数bi组成的向量;γ为由污染排放函数的二阶系数γi为主元的对角阵;β为由污染排放函数的一阶系数βi组成的向量; $\tilde{Μ}$ A表示MA的修正矩阵(联络线电纳被加入与之相关的边界节点的主对角元中)(见附录B);WAtie=HAtie(XAtie)-1,XAtie为AB联络线的电抗矩阵。

将式(15)简化为:

$ω_{A} = \frac{R_{A} - S_{A}}{R_{A} - Q_{A}}$

式中:RA为A区中与污染排放系数相关的项;QA为A区中与生产费用相关的项;SA为A区中与传输价格和网络参数相关的项。

由式(15)可知,当该区域机组的污染排放系数较大而生产费用较低时,ωA趋于一个较小的值,即该区域的多目标决策倾向于重点控制污染排放。反之,当该区域机组的污染排放系数较小,而生产费用较高时,ωA趋于一个较大的值,即A区的多目标决策倾向于重点控制生产费用。

由于决策偏好的不同,使得污染小、成本高的机组多发电,从而造成某些区域生产费用增加,可以通过市场机制或政策(如电价折算或税收补偿等)进行弥补,这方面内容不属于本文的重点,在此不进行深入讨论。

互联区域协同优化的步骤[11]如图2所示。各分区之间的参数协调通过交换边界变量来实现,包括边界点的相位角 $\hat{θ}_{i}^{A} (\hat{θ}_{j}^{B})$ 和传输价格 $\hat{η}_{i j}^{A B} (\hat{η}_{j i}^{B A})$ 。

4 算例分析

本文以16节点9机组系统作为算例[12](见附录C),将统一设置偏好系数与分区设置偏好系数进行比较。统一设置偏好系数时,ω是预先给出的确定常量,本文将ω设定为0～1之间的5个常量进行计算,表达决策者对不同目标函数采取不同偏好。单位转换系数χ=0.139 9美元/t,不同权系数的计算结果如表1及附录D所示。

按分区原则,将系统分为4个区,如附录C图C1所示。观察各分区的初始参数,评估结果如表2所示。

各分区单位转换系数为χ1=0.164 9美元/t,χ2=0.095 4美元/t,χ3=0.206 7美元/t,χ4=0.101 8美元/t。根据式(15)计算出分区1～4的偏好系数ω分别为0.414 3,0.567 4,0.702 1,0.241 7。基于MATLAB[13],对各分区进行协同计算的结果如表3所示。

对比表1和表3的计算结果,分区设置ω时总污染排放为10 533 200 t/h,与统一设置ω=0.2时污染排放量相接近。但是分区优化的生产成本为1 476 678美元/h,而统一设置ω=0.2时得到的生产成本为1 493 522美元/h,远高于前者。

5 结语

本文探讨了考虑经济与环保多目标的互联区域协调调度策略,提出了不同区域不同决策偏好系数的控制方案,以达到经济与环境保护的双目标协调。算例仿真表明,所提方案有利于实现电力行业中SO2等污染气体排放总量的控制目标。

多目标任务调度篇8

柔性车间调度问题(Flexible Job-Shop Scheduling Problem,FJSP)是带有机器可选柔性的车间调度问题。由于该类问题的重要性和复杂性,国内外相关人士一直进行着多方面研究。为了求解更符合实际的调度问题或者使一般调度问题求解更加实用和高效,各种算法都在不断的改进和发展。

王笑蓉[1]提出了柔性生产线的加工路径蚁群优化和作业排序遗传算法优化的两级递阶进化优化方法;Parviz Fattahi[2]对柔性车间调度问题建立了一个数学线性规划模型,用模拟退火启发式和禁忌搜索启发式方法分别提出了两种遗传算法;Andrea Rossi[3]提出了用蚁群优化算法来解决带柔性路径的车间调度问题;Jie Gao[4]将移动瓶颈法用于基因算法,求解多目标的柔性车间调度问题;Ghasem Moslehi[5]提出了一种粒子群优化算法与局部搜索混合的算法;Celia Gutierrez[6]对启发式遗传算法进行了修正,模块化设计混合遗传算法;Li-Ning Xing[7]提出了一种基于知识的蚁群优化算法来求解柔性车间调度问题;Kyoung Seok Shin[8]采用共生进化算法求解多目标柔性车间调度问题;亓凌[9]提出具有路径柔性的作业车间调度模型,并给出了求解模型的自适应蚁群算法。

由于柔性车间调度问题具有其复杂性,传统遗传算法在求解时存在搜索效率低,易过早收敛等缺点,现有的各种优化方法都有一定的局限性,因此针对这些缺点,笔者提出了一种改进遗传算法。用均匀设计法、最短加工时间机器指配法、随机生成法三种方式产生初始种群,以提高种群的多样性;由锦标赛方式、最优保存策略和新生策略进行选择操作,以避免早熟;以传统交叉,面向瓶颈机器的交叉和面向瓶颈工件的交叉三种方式进行交叉操作,以避免盲目交叉;以变动概率的方式进行变异操作;用启发式规则控制解码过程,以提高搜索效率。仿真结果证实了该算法的有效性。

1 初始条件不为零的柔性车间调度问题

本研究主要考虑各工件可能先后到达,有些机器由于各种原因在调度开始不能马上使用的柔性车间多目标调度优化问题。设有n种待加工工件:

式中:Ai—工件Ji到达系统时间,Ri—工件Ji要求完成时间,Oij—工件Ji加工工序,ni(i=1,2,…,n)—工件Ji的工序数,总工序数。

有m台可用于加工的机器Ml(l=1,2,…,m),其可用的开始时间为Sl;工序Oij可用的加工机器集为Mij{M1,M2,…,Mm},设Mij中的机器数为Wij;Oij的加工时间为tlij(i=1,2,…,n;j=1,2,…,ni;l=1,2,…,Wij)。

例如有3种工件J1、J2、J3,工序数分别为3、3、4道;各道工序的可选机器及对应的加工时间如表1所示,4台机器可开始使用的时间分别为5、0、10、0。

调度的任务是在m台机器上安排n种工件的所有工序oij的加工,同时优化既定的目标。本研究主要考虑的目标函数有:

(1)“最后完工工件的完工时间最短”,即:

式中:Ci—工件Ji完成时间。

(2)“所有工件延误时间之和最少”,即:

式中:Ri—工件Ji需求时间。

(3)“所有机器总负载最小”,即:

式中:Li—机器Mi需要承担的加工时间。

为了简化问题,假定每台机器同一时刻只能加工一个工件;每个工件同一时刻只能被一台机器加工;某道工序一旦在某台机器上开始加工就不能中断;工件Ji(i=1,2,…,n)的加工过程需符合预先给定的工艺路径,即:Oi1→Oi2→…→Oini。

2 调度解空间分析

求解柔性车间调度问题,首先要确定N道工序的机器指派,总的指派组合数为:。

以表1数据为例,机器可选组合数为:。

其次要确定N道工序的加工次序。考虑到同一种工件的各道工序必须满足给定的工艺要求,因此表1问题的10道工序总的排序组合数为:。

因此该类柔性车间调度的可行解全组合数为:Z=Z1Z2;如表1所示调度问题的全组合数为:Z=Z1Z2=3 225 600。

该类问题已被证明为NP完全问题,即使用现今最快的计算装置来运行最好的算法,也不可能在人们可接受的时间内得到问题的解,因此只能运用一些近似求解的算法找出次优解。遗传算法就是其中一种简单易行的智能算法,但是也存在着早熟收敛和快速收敛的矛盾,为解决这个问题,本研究提出了一种改进遗传算法。

3 改进遗传算法

3.1 调度解编码

编码问题是设计遗传算法的首要和关键问题。在编码方面有以下3个基本准则:

(1)完备性:问题空间中的所有解都能作为GA空间中的染色体来表现。

(2)健全性:GA空间中的染色体能对应所有问题空间中的候选解。

(3)非冗余性:染色体和候选解一一对应。

基于这3个基本准则,本研究采用双链结构进行编码。第1条链V1表示各加工工序Oij(i=1,2,…,n;j=1,2,…,ni)对应分配的机器号Ml,每个基因代表各道工序选择加工的机器号,链的长度等于工序总数N;第2条链V2表示各工序Oij的加工顺序,每个基因代表各道工序的加工顺序,并满足工件给定的工艺顺序要求,链的长度也是等于工序总数N。

本研究以表1为例具体说明双链结构编码方式。其中机器分配链的解释为:工序O11从其可选机器集M11={M1,M2,M3}中选择M1,因此对应基因编码为1;工序O12所选的机器为M3,因此对应基因编码为3,依次类推得到此链。工序顺序链的解释为:各工序的加工顺序为O21、O11、O22、O31、O12、O32、O13、O23、O33、O34。工序顺序链必须满足各工件的工艺路线顺序,即满足O11→O12→O13、O21→O22→O23、O31→O32→O33→O34,同一工件的后道工序不能先于前道工序进行加工。

3.2 混合方式种群初始化

设种群规模为P,本研究采用3种不同的方法产生P个初始染色体[10],具体描述如下:

方法一:采用Ur(rs)均匀设计表[11]的方式。

步骤1计算单链的编码长度L;

步骤2 L为奇数时,取试验数r=L;L为偶数时,取试验数r=L+1;

步骤3寻找比r小的正整数h,且使r和h的最大公约数为1。将符合条件的正整数生成一个向量h=(h1,h2,…,hs);

步骤4均匀设计表Ur(rs)的第j(j=1,2,…,s)列由同余运算规律生成uij=i·hj(mod)r,其中mod为取余运算,i为行号(i=1,2,…,r);

步骤5如果r=L+1,则将设计表Ur(rs)的最后一行去掉;

步骤6从所构造的设计表中选取第j列数(j=1,2,…,s)。将元素uij(i=1,2,…,L)通过表1中统一编号的第i号工序的可选机器数进行余运算,确定第i号工序的分配机器,从而形成染色体的机器分配链;再按该列数值初始化工序顺序链;共可以得到s个均匀分布的染色体。

方法二:选取最短工序时间的机器。

染色体的机器分配链选取最短工序时间的机器,使得机器总体负载最小,同时有意识地缩短任务加工时间。以表1模型为例,得到染色体具有最短工序时间的机器分配链如表2所示。

方法三:随机编码方式。

机器分配链随机地从各工序Oij的可加工机器集Mij(i=1,2,…,n;j=1,2,…,ni)中选取机器号;工序顺序链随机安排工序顺序,并满足工件给定的工艺路线顺序。

上述混合方式初始化种群的目的是,均匀设计初始化方式使个体具有均匀分布的统计特性;指配最短工序时间机器的初始化方式能有意识地在最短加工时间内指配机器,提高算法寻优效率;随机初始化方式能提高初始种群的多样性。

3.3 混合选择策略

本研究采用的选择策略是最优保存策略[12]、锦标赛选择法[13]和新生策略相结合。

最优保存策略的具体流程:记录当前种群中适应度最高的个体,经过选择、交叉和变异后,若下一代种群中所有个体的适应度均小于当前最佳个体的适应度,则用当前最佳个体替代下一代种群中最差的个体。

锦标赛选择法的具体流程:在种群中随机选取e个个体,e为锦标赛规模(e≥2),然后选择适应度最优的个体。如果要通过该方法选择E个个体,则重复E次。

新生策略的具体流程:当连续几代都没有更新最优个体时,为了避免陷入局部优化,种群中随机产生若干新的个体,以开辟新的寻优空间;当种群的最优个体又得到更新时,再返回到原先的选择策略。

采用上述混合选择策略的目的是,最优保存策略能使当前最优个体不遭破坏,是保证遗传算法收敛性的一个重要条件;锦标赛选择法将种群中适应度较高的个体以较大概率选择到下一代,而适应度较低的个体以较小的概率选择到下一代;新生策略使算法避免局部优化。

3.4 混合式交叉

考虑到优化目标是最后完工工件(机器)的完成时间最短,因此最后完工工件(机器)即为调度问题的瓶颈工件(机器)。除了传统的交叉方法以外,笔者设计了一种优化瓶颈的交叉方式,分别对瓶颈工件和瓶颈机器进行优化。根据不同比例个体数,采用3种不同的交叉方式产生新的个体:

方法一:两条链分别采用传统的交叉方式。

机器分配链采用两点交叉法[14],具体流程:在两个父代中,随机选取两个交叉位置,并相互交换这两个位置之间的基因串,以得到两条新的可行链。

工序顺序链采用顺序交叉法[15],具体流程:在父染色体1中,首先随机选取两个交叉位置,将两个位置之间的基因串作为子染色体1对应位置的基因;然后在配对的父染色体2中删除与所选基因串中基因值相同的基因,并从左到右依次填入子染色体1的空白基因位;以同样方式获得子染色体2。

方法二:采用瓶颈机器优化的交叉方式。

步骤1随机产生(0,1]内的数p,如果p

步骤2通过解码得到该个体的瓶颈机器号;

步骤3将该个体的瓶颈机器所加工的全部工序找出;

步骤4对这些工序重新分配机器,得到新的可行个体;

步骤5重复步骤1~4,可以得到多个个体。

方法三:采用瓶颈工件优化的交叉方式。

步骤1随机产生(0,1]内的数p,如果p

步骤2通过解码得到该个体的瓶颈工件号;

步骤3将该个体的瓶颈工件的各道工序所选的机器找出;

步骤4对这些工序重新分配机器,得到新的可行个体;

步骤5重复步骤1~4,可以得到多个个体。

改进的优化瓶颈交叉方法主要思想就是消除目前调度方案的瓶颈,以优化当前解。该交叉方式比传统交叉方式更具有目的性,而不是完全的盲目随机。为了提高种群的多样性,将优化瓶颈交叉方法与传统交叉方法混合。

3.5 变动概率的变异策略

机器分配链采用单点变异法,具体流程:在父染色体中,随机选取一个基因位,考察该基因位上的其他可选机器号,从中随机选取一机器号来替换该基因值。

工序顺序链采用反转变异法[16],具体流程:在父染色体中,随机选取两个变异位置,然后将其之间的子基因串反转。

笔者提出的变动概率的变异策略的具体方法为:在优化前期变异概率为pm,当连续几代最优个体都没更新时,为了避免陷入局部优化,变异概率增大到1;当最优个体又得到更新时,变异概率回到原值。

3.6 启发式规则控制解码

为了减少无效的解码计算工作,在解码过程中增加了两条启发式规则,具体流程如下:

(1)规则一。

步骤1假设每种工件每道工序都采用具有最短工序加工时间的机器,以表1为例,所分配机器及其工序时间如表2所示;

步骤2根据所选机器对应的加工时间tlij(i=1,2,…,n;j=1,2,…,ni),分别计算各工件的工序总时间Ti(i=1,2,…,n),表2各工件的工序总时间分别为:T1=34、T2=27、T3=48;

步骤3由各工件的工序总时间Ti(i=1,2,…,n)求得最大的工序总时间T=max Ti(i=1,2,…,n),上述各工件工序总时间中,最大的工序总时间T=T3=48,该值即为该调度问题在没有考虑机器资源短缺情况下的“极限最优适应度值”;

步骤4每个个体解码得出的适应度值与“极限最优适应度值”比较,如果解码得到的适应度值已经达到该极限值,则算法结束,因为不可能再得到比“极限最优适应度值”更小的值。

该规则能及时停止遗传计算,提高调度优化效率。

(2)规则二。

步骤1个体的机器分配链确定后,由机器分配链汇总各台机器Mj(j=1,2,…,m)所要加工的工序,以表1的机器分配链为例,该个体各机器分配的加工工序情况如表3所示。

步骤2根据所对应的加工工序时间tlij(i=1,2,…,n;j=1,2,…,ni),分别计算各机器的工序总时间Lj(j=1,2,…,m),表3中各机器承担的工序总时间分别为:L1=22、L2=44、L3=49、L4=19;

步骤3求得最大的机器加工时间L=max Lj(j=1,2,…,m),表1中最大的机器加工时间L=L3=49;

步骤4如果L大于当前已求得的最优适应度值,那么该个体被认定为淘汰个体,不需要再进行解码,因为无论工序顺序链如何变动,该个体解码得到的适应度值都不可能小于L,也即不可能优于当前已求得的最优适应度值;

步骤5为了保证种群的规模大小不发生变化,被淘汰个体要由新个体取代,并按照上述方法进行分析和解码。

规则二在解码前事先判断并淘汰劣势个体,既减少了解码的计算量,又能保证种群的性能向更优的方向发展。

具体解码算法根据调度解的双链V1、V2,同时考虑各工件的不同到达时间Ai,以及各台机器的可取时间Si,求出每道工序的起始和结束时间及其使用的机器号,并进一步求出多目标值f1、f2、f3等。用户可以选择上述某个单目标进行优化,也可以选择两个目标的组合优化。

4 算例验证和分析

在本研究中,改进的遗传算法用Visual Basic语言编程实现,运行计算机的CPU为Intel Core 2 Duo,主频2.53 GHz,内存为2.0 GB。15×10问题调度优化过程的一个运行界面如图1所示。

为了验证本研究算法的有效性,选择了很多文献所采用的8×8、10×10、15×10算例[17,18]。本研究对8×8、10×10、15×10问题分别进行多次实验运行。由于遗传算法的随机性,所得到的最优结果非唯一确定。3种调度问题的典型优化结果甘特图如图2~图4所示。

本算法与其它算法的比较结果如表4所示[19,20]。对比结果表明,对8×8问题,本算法不但得到目前文献最好的结果f1=14,f3=77,而且可以得到更好的f3=73,虽然f1=16有所变差;同样对10×10问题,本算法不但得到目前文献最好的结果f1=7,f3=42,而且可以得到更好的f3=41,虽然f1=8有所变差。

下面针对表1给出的例子进行多目标优化调度分析。5种优化目标的运行结果如表5所示,从表中可知,组合优化往往可以得到更满意的结果。以f1+f2最小为优化目标情况下的调度甘特图如图5所示,其中实框部分代表机器不可取时间段。从图中也可看出,工件1在它到达时刻(6单位时间)后才安排加工[21,22,23]。

5 结束语

本研究针对工件到达时间和机器可用时间不为零的柔性车间多目标优化调度问题,开发了相应的改进遗传算法。提出的混合种群初始化方法,既能提高初始种群的多样性,又能使得个体有意识地在最短加工时间中搜索最优解;提出的混合选择策略能提高收敛速度,并保证优质个体不被破坏;提出的优化瓶颈交叉方法比传统的交叉方法目标更明确;变异概率随优化过程变动,可以有效避免陷入局优;在解码过程中增加启发式规则,能有效地判断算法结果是否已达到极限最优,并能在解码前及时淘汰明显劣质个体。通过典型案例的实验计算和分析比较,验证了该算法具有良好的收敛性和优化能力。

摘要：针对工件投料时间和机器起用时间不为零的柔性车间多目标优化调度问题,提出了一种改进遗传算法。染色体编码采用机器分配链和工序顺序链的双链结构;用均匀设计法、最短加工时间机器指配法、随机生成法三种方式产生初始种群;由锦标赛方法、最优保存策略和新生策略混合进行选择操作;以传统交叉方式、面向瓶颈机器的交叉方式,以及面向瓶颈工件的交叉方式混合进行交叉操作;以变动概率的方式进行变异操作;用启发式规则控制解码过程。最后,对典型算例进行了验证计算。研究结果表明该算法具有较强的寻优能力,并具有较快的求解速度。

【多目标任务调度】推荐阅读：

任务目标定向05-15

目标任务法06-07

目标任务完稿08-18