并行调度（精选七篇）
并行调度 篇1
并行多机调度问题是NP-Hard问题，它既有丰富的研究内容，同时在生产调度，机械制造等方面有广泛的实际应用价值。但是在实际操作中，人们常常按经验法则 (如处理时间短优先调度或到期日早优先调度) 进行调度，这样得到的调度结果一般不能满足实际环境的需求，而且当并行机数和工件数增加时，问题的复杂度成指数增加，传统方法不适合解决此类问题。目前的并行机调度问题研究大部分是集中于简化问题，然后寻找最优解或次优解。
如何使并行机调度问题更接近实际生产状况并找到次优解成为本问题研究热点之一。遗传算法由于其固有的全局搜索与收敛特性，能够较好地解决此类优化组合问题。用遗传算法解决并行机调度问题已经有相关研究，其中Cheng提出一套方案，利用特殊符号 (*) 和工件号组成染色体，特殊符号为分隔符，将工件分成不同的组，每个工件组指派到不同的并行机中。本文对Cheng的方案进行了改进，并且把工件延迟与提前完成成本、机器闲置时间成本和机器设备启动成本等列入考虑因素，使多机调度问题的解决更接近实际的生产状况，目的在于求得考虑实际因素下的次优调度结果，以降低存货存储、交货延迟的违约、设备及人力等成本。
（二）遗传算法与并行机调度问题
1. 遗传算法
遗传算法是一种模仿自然界中优胜劣汰自然选择规则的随机搜索方法，该算法是从一系列的初始点 (被称为初始种群) 开始，通过循环执行选择、交叉和变异等遗传操作，逐步得到问题接近全局的最优解。
2. 并行机调度问题
考虑并行机调度中的实际需求定义如下并行机调度问题：设有m (m>1) 台并行机M1, M2, …Mm，需要加工n个工件，F时调度工作结束，每个工件订单零时刻到达，可在任一台机器上完成加工。工件一旦分配给某机器加工就必须加工完毕，不许中断。工件i在机器j上加工前准备时间为Zij，加工时间为Tij，工件i的到期时间为Qi，机器j一天的工作时间为Wj，启动成本为Sj，闲置成本权重比例为Rj，则工件i的完成日期Ci为本身加工前准备时间Zij (j为工件i的加工机器) 、加工时间Tij与机器j中i工件之前所有工件消耗时间之和，提前完成时间Bi为max (0, Qi-Ci) ，延迟时间Di为max (0, Ci-Qi) ，机器j的闲置时间为Ij (F减j上最后一个工件完工时间) 。问如何安排每台机器上所加工的工件及加工顺序使成本最小。
（三）算法设计
在Cheng的方案基础上，提出了一个染色体的改进的编码组成方式，重新设计了适应度函数和进化机制。
1. 染色体编码与适应度函数设计
并行机调度问题的染色体必须表示两个方面的信息：一方面确定工件加工所在的机器，另一方面确定每台机器上工件的加工顺序。本算法中染色体编码时用自然数序列表示工件排列，用含数字下标的分隔符*i (0
遗传算法演化过程的目的在于使适应度函数最小化，如果用B, D, S, I分别表示提前、延迟、重启和闲置成本，则演化的目的是要找到最好的排列使得：
F (B*, D*, S*, I*) =min{F (B, D, S, I) }, 适应度函数为F,
Bi, Di, Sj, Rj, Ij意义同上，α (Bi) , β (Di) 分别为提前和延迟完工成本函数，γj的值在机器j上有工件分配时等于1，否则为0。
2. 种群初始化
初始种群的个体分为两类，第一类个体随机生成;另一类个体可以按一定经验法则生成，比如可以把处理时间作为考虑因素，处理时间越短越先安排，确保在最短的时间里做尽可能多的工件，或者按到期日期为标准，越早到期的工件越早安排，可以使大部分工件如期完成。
3. 选择
选择过程的目的是为了从当前群体中选出优良个体，使他们有机会作为父代将其优良的个体信息传递给下一代，使子代向最优解逼近[1]。判断个体优良与否的标准是各自的适应值。每个个体的选择概率采用基于排序的适应度分配 (rank-based fitness assignment) 方法，种群按适应度进行排序，个体的生存概率使用Baker提出的线性排序计算公式求得：其中i为个体排序序号，N为种群大小，1<=η+<=2, η–=2–η+。然后用轮盘赌选择法 (roulette wheel selection) 来决定每个个体的选择份数，选择后的N个个体送到配对库，以备配对繁殖。
4. 交叉
交叉是结合来自父代种群的信息产生新的个体，依据个体基因编码表示方法的不同有多种交叉算法。这里采用两点顺序交叉 (OX) ，顺序交叉能够保留排列并融合不同排列的有序结构单元。如有下面两个父个体，交叉操作步骤如下：
(1) 随机选择两个交叉点”|”，保留交叉点之间的中间段不变。
(2) 把父个体2从第2个交叉点作排列，到达表尾时返回表头继续，得到排列*3 2 7*4 8 4 1*2 5*1 3 6，减去父个体1中已有基因部分4 5*1*3 2得到排列顺序7*4 8 1*2 36，再将这个顺序从第2个交叉点开始复制给子个体1，以此决定子个体1对应位置的未知码x，生成子个体1即q1: (3 64 5*1*3 2 7*4 8 1*2) ，同样产生子个体q2: (*3 2*2 5*13 6 7*4 8 1 4) 。
5. 变异
变异是子代基因按小概率产生的变化。同样可以采用多种方法实现基因变异，如可以采用交换两个基因位置实现变异，但是这种方法个体变异较小，不利于新个体的生成，特别是当交换的两个基因都是数字时，新个体只是改变了两个工件的加工位置。这里使用另外一种方法实现变异操作即首先随机选取父代中的某优秀染色体，对照染色体基因个数 (m+n) 随机生成一个二进制序列，将染色体中对应0的基因选为一组，对应1的基因选为另一组，两组基因重新组合得到子个体。变异操作如下：
6. 种群进化与停止准则
标准遗传算法若在群体选择前 (或后) 保留当前最优值，则最终能收敛到全局最优值。本算法通过改进标准遗传算法，在群体选择作用前保留当前最优解，则保证本算法在某些情况下收敛到全局最优解。
停止准则一般预先设定一个最大的繁殖代数Nmax，在繁殖过程中进行到最大的繁殖代数则停止运行。
综上所述，本并机行排序问题的遗传算法伪码如下：
（四）结果
设有45个工件要在3台机器上加工。在工作提早与延迟完成成本方面，按照工件的重要性将提前与延迟完成成本公式分为三类：
对重要性不高的工件成本公式为：
对重要性一般的工件成本公式为：
对优先权高的工作成本公式为：
工件在不同机器上的加工时间，加工前准备时间，机器启动和闲置成本表略。种群大小为50，最大遗传代数为80，交叉概率为0.6，变异概率为0.01。按本文与Cheng所提算法分别演算，所得结果如表1所示：
由表1可知，本文算法有助于使最后解答的染色体之间的差异性小，每次运算后的解接近最优解。
（五）结束语
本文重新设计了染色体的组成方式，问题的解空间表示得更明确，设计了算法进化机制，求解效率得到提升，考虑了并行机调度问题中的更多实际因素，本算法有一定的实用价值。然而实际影响并行机调度的因素并不限于本文所讨论的范围，另外适应度函数中的权重比例，也需要根据不同工厂的需求做适当的调整。今后将研究影响并行机调度的其它一些因素，使并行机调度问题与实际应用紧密结合，并且考虑把遗传算法与其它算法结合，使遗传算法收敛更快更高效。
摘要：为解决接近实际生产状况的并行机调度问题, 将工件延迟与提前完成成本、机器闲置时间成本、机器启动成本列入考虑因素。在遗传算法的设计上, 提出了一套染色体的组成方式, 设计了适应度函数和进化机制, 使其能较好地表示问题的解空间并提升求解效率, 具有一定的实用价值。
关键词：并行机调度,遗传算法,适应度
参考文献
[1]何军辉, 周泓.求解含调整时间并行机排序问题的遗传算法[J].系统工程理论方法应用, 2002, 12.
[2]欧锦文, 施保昌.平行机排序邻域搜索算法设计[J].计算机工程与应用, 2003, 18.
[3]Cheng, Runwei.Minmax Earliness/Tardiness Scheduling in Identical Parallel Machine System Using Genetic Algorithms[J].International Conference on computers and industrial Engineering, 1995:29:513-517.
[4]张聚, 李平.基于演化算法的车间作业调度问题的求解方法[J].浙江大学学报, 2004, 12.
一种并行任务的调度方法 篇2
关键词：并行任务,调度逻辑,流量控制
1 背景分析
在实际的逻辑设计中, 执行1个任务, 可能会使用N个并行任务的处理结果, 而这N个任务的执行时间无法预测, 且任务执行时彼此独立。需要任务调度逻辑对这N个任务的执行情况进行检测, 并进行流量控制。原始的设计结构要求如图1所示, 调度逻辑需要管理N个并行任务的调度, 因为每个并行的执行时间并不可预知, 也就是任务0~N-1的完成先后顺序并不能固定, 造成调度器的设计会比较复杂。
为了简化调度器的设计, 我们可以采用这N个任务顺序执行的结构, 先执行任务0, 当任务0执行完成后, 再调度任务1执行…;直到任务N-1执行完成后, 再调度最终任务的执行。如图2所示, 顺序执行的结构非常简单, 这种方法显然在任务数比较少的时候可以使用, 如果任务很多那么执行的延时将增加很多, 工作效率变得非常低。
例如, 系统中会有多个用户并行处理, 每个用户既需要task0计算的BIT级数据和task1计算出的符号级数据, 又需要task2来请求保存在外部存储区中的任务参数, 当task0, task1和task2都准备好后, 才能进行用户的后续译码或者编码操作。如果按照图2的方式进行设计, task0准备好后, 推动task1执行, task1执行完毕, 再推动task2执行, 每个任务执行的时间长度不固定, 导致每个用户译码的时延很大, 如果用户数多达512的时候, 根本不能满足系统的要求。
2 设计思路
为了简化调度逻辑的设计, 需要减少调度器监测的模块;同时为了提高效率, 任务处理尽量采用并行结构。如果能够对1个任务做流量控制, 且保证其他的任务在不做流量控制时也不会出现异常, 就是比较好的方案。
如果仅仅对任务0进行流控, 而不对任务1~N-1做流控, 我们需要保证任务1~N-1的输入和输出都不能产生溢出, 于是计算出任务0这个支路最多能够处理的未完成状态的任务个数M, 在任务1~N-1的输入和输出缓冲区都不小于M的情况下, 就能保证都不溢出。
为了方便计算M, 我们将任务支路0设计为一个任务队列, 不需要执行任何的任务, 仅仅用于对outstanding的任务数m进行监控, 使其不能超过上限M。根据上述的考虑, 我们得出一个优化的任务调度方案, 如图3所示。
调度器监测事件队列EQ的空满状态, 在任务参数准备好 (param_valid) 后, 将ready信息写入EQ, 并将相应的任务参数写入对应的任务队列TQ1~TQN-1, 行为级设计如下:
在最终任务N中实现事件队列EQ和完成队列FQ1~FQN-1对齐等待, 当最终任务N有执行资源、EQ和FQ1~FQN-1都为非空的时候, 到所有的队列中读取最终任务N执行时所需的结果。行为级设计如下:
在将EQ和FQ1~FQN-1中的结果读取后, 就可以执行最终任务N;在EQ状态为非满状态时, 并行任务1~N-1在通路上的outstanding的任务个数不会超过事件队列深度M, 这个时候并行的任务的执行是完全独立的, 提高了电路工作效率。
3 结语
本文描述的方法, 减少了任务间的等待时延, 电路的工作效率较高;任务能并行执行, 逻辑的处理时延也比较小;不需要对每个并行任务进行流控, 降低了调度器的逻辑设计复杂度;用队列隔离了模块的输入输出, 模块的移植性增强, 还可以很容易地增加或者去除其中的某个并行任务, 可扩展性增强。本设计方法对多数并行多任务处理都有较强的借鉴意义。
参考文献
[1]刘波.精通Verilog HDL语言编程[M].北京:电子工业出版社, 2007
[2]夏宇闻.Verilog数字系统设计教程 (第2版) [M].北京:北京航空航天大学出版社, 2008
[3]徐欣, 余红期, 易凡, 卢启中.基于FPGA的嵌入式系统设计[M].北京:机械工业出版社, 2005
[4]EDA先锋工作室, 王诚, 蔡海宁, 吴继华.Altera FPGA/CPLD设计 (基础篇) (第2版) [M].北京:人民邮电出版社, 2011
[5]西瑞克斯 (北京) 通信设备有限公司.无线通信的MATLAB和FPGA实现[M].人民邮电出版社, 2009, 6
[6]KILTS STEVE.Advanced FPGA design:Architecture, Implementation, and Optimization.John Wiley&Sons, Inc., Hoboken, New Jersey.2007
[7]KEN COFFMAN.Real World FPGA Design with Verilog.Prentice Hall, Upper Saddle River, NJ, 2000
基于遗传算法的并行生产调度的研究 篇3
关键词：退火算法,遗传算法,并行,生产调度
作业调度问题在CIM中受到了广泛的关注[1,2]。作业调度在生产中发挥着两方面重要作用:一方面,接受计划决策信息,在空间和时间上合理配置任务和资源,形成具体生产实施方案,驱动整个生产系统高效运作,保证计划的实现;另一方面,接受生产过程的实际信息,通过统计分析,有机协调整个生产系统,并向决策层反馈计划执行情况。
研究表明,调度问题中的绝大多数属于NP难题[3,4],不存在有效的最优求解算法。有鉴于此,本文提出了一种基于改进的人机交互式的并行作业调度的求解方法,并在遗传算法初始种群中允许用户输入有效的作业调度安排,从而提高了初始种群的染色体的质量并且增加了染色体来源的多样性,提高遗传算法的效率。本文采用遗传算法,对并行生产车间作业调度属于静态调度领域中的Job Shop调度问题进行了研究,并用软件实现了算法。
1 并行生产模式
传统的生产调度模式,可以理解为一种垂直的方式,即有了新的生产任务,就把它安排到已有生产任务的后面。在市场竞争日益激烈和经济全球化的今天,这种生产调度模式已经不受欢迎了。这种模式的缺点是:不能从全局优化生产作业,使得产品生产周期延长,设备利用率低,造成企业资源浪费,影响企业的市场反应能力和竞争能力。
并行生产任务的调度,在我国是一种常见的生产组织方式,它区别于连续型生产。生产制造的各个环节往往是并行进行的,各个环节之间通过工艺要求来相互衔接,并行生产车间作业调度实际就是车间生产作业的排序问题,它可以描述为:已知N个工件按确定的工艺路线通过M台设备加工,要求确定各台机器上工件的加工顺序,使得预定目标达到最优。但是现有的作业调度模式,缺乏整体的优化,仍然会出现整体效率低的情况,并且不能从全局考虑,利润最高的任务得不到及时的完成,实现企业利益的最大化。
2 作业调度的数学模型
车间作业调度的优化数学模型可以有许多不同的优化目标,以完成加工所需时间最短为优化目标的数学模型如下式[5,6]。
式中,tMi,j为第i设备上的第j加工的加工时间;tWi,j为第i设备上的第j加工的等待时间;p为设备数;qi为第i设备上的最大加工数;tSr,l为第r工件的第l工序的加工开始时间;tEr,l为第r工件的第l工序的加工结束时间;tUi,j为第i设备上第j加工的开始时间;tVi,j为第i设备上第j加工的结束时间;m为工件数;nr为第r工件的最大工序。
目标函数中,表示安排在设备i上进行加工的所有加工工序(qi个加工工序)的加工时间tMij和等待时间tWij之和。也就是完成加工任务,设备i所应该服务的时间。此服务时间不仅包含设备的加工时间也包含设备的等待时间。目标函数式(1)代表最长服务时间,因为加工是并行进行的,所以这个最长服务时间也就代表整个加工任务完成所需的时间。整个加工任务完成所需的时间是指加工完成时间和加工开始时间之差,代表加工完成所需的等待时间。
约束tSr,l>tEr,l-1表示第r工件的第l工序的加工开始时间必须大于第r工件的第l-1工序的加工结束时间。这个约束保证了同一工件的加工工序前后不会颠倒。
如果所有的任务都可以按时完成,就可以满足企业最大化利润。但是如果时间不允许完成所有加工任务,则可以按照时间最短和利润最大化来优化。按照每个生产任务的利润进行加权,然后再进行任务调度。
3 遗传算法相关算子的设计
3.1 编码
我们直接将生产任务编号作为基因进行编码,并且保证每个任务编号在染色体中只出现一次。如六个生产任务,用6 2 1 5 4 3来表示一条染色体。初始染色体的获得我们通过自动生成和手工输入相结合的交互式输入方式获得。自动获取的方式为:通过分析各个任务的优先级来生成,所生成的染色体优良率高,而且也易于编程实现。
3.2 选择算子
选择算子从群体中选择优胜的个体,淘汰劣质的个体,其目的是把优化的个体(或解)直接遗传到下一代或者通过配对交叉算子产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。常用的选择算子有以下几种:适应值比例选择、排序选择、联赛选择等。
并行生产调度中,会有许多非优的方案(其适应度值较低),此时仅有一个或少数几个较优解,若选择压力得不到控制,群体就过早收敛,无法得到进一步优化的解。因此,本文使用选择压力可有效控制排序选择算子。
3.3 交叉算子设计
交叉的作用在于将群体中原有的优良基因遗传给下一代个体,并生成包含更复杂基因结构的新个体。常用的交叉算子有一点交叉、两点交叉、多点交叉、一致交叉等。本文对任务的编码属于单纯方式,仅采用实数编码,不包括符号编码,针对这种级联编码的特点,以下设计了相应的交叉算子。
交叉与局部调整相结合的思想类似于多点交叉,具体实现如下:(1)交叉实现加工任务的互换,就是采用一点或两点交叉,交叉点选择在染色体上随机任务与任务之间,然后互换被选中的染色体片段;(2)局部调整只针对单个任务的染色体片段。在交叉中被选中的染色体片段上(包含一个或多个任务的编码),以一定的概率对加工任务实施一次单点交叉。
上述方法既能实现染色体的部分互换,又能进行个别的调整,改变了单一的染色体片段整串交换的模式,有利于为遗传算法探索新的解空间。
3.4 变异算子设计
基本遗传算法进行的变异操作是对每一个等位基因进行均匀变异,即以一个很小的变异概率对每一位基因实施变异操作。由于并行生产调度中的全部解都是可行的,问题是找出最优解,所以简单增大均匀变异的概率会破坏算法到最优解附近的搜索效果,可以通过附加新的变异方式来达到探索新的解空间的目的。
本文对生产任务的编码方式是统一的,当随意抽出一个或几个编码放到另一位置时,其物理意义相当于移动某一个或几个生产任务的先后顺序。根据这种特点,可以设计如下几种变异算子[7]:(1)随机抽取一个或连续几个任务,插入到另一位置;(2)随机选择两个任务,将它们互换;(3)随机选择一个或连续几个任务,将它们逆序排列,放回原位置或插入到新的位置;(4)随机选择一个或连续几个任务,将它们乱序排列,放回原位置或插入到新的位置。
3.5 保留策略
从遗传算法的选择策略上讲,精英保留策略是群体以概率1收敛到最优解的一种基本保障。精英保留策略以如下方式实现:如果上一代群体最佳个体的适应值大于当前群体最佳个体的适应值,则将上一代群体中最佳个体或者适应值大于当前代最佳个体适应值的多个个体直接复制到当前代,随机替代或者替代当前代中相应数量的最差个体。这样的策略,既保存了大部分优良个体,让算法始终保持探索新的解空间的能力,再结合冷却进度表来防止早熟。
冷却进度表是用于控制算法进程的一组参数的集合,包括控制参数的初值t及其衰减因子Δt、对应的Mapkov链的长度L和停止准则S,其选取原则参见文献[8]。
4 应用实例
图1是5个任务在3台设备加工的例子,5个任务的利润加权值排序为1、2、3、4、5,最后本算法得到的排序为1、2、5、3、4。假设本文给工件编号为01,02,…,n,设备编号为01,02,…,m,工件的每一步工序编号为01,02,…,则符号05.04.03符号表示工件05的04工序在设备03上完成。所在格的跨度代表所需时间的长短。
运用本算法的求解结果为见图2。
5 结语
从测试结果来看,混合遗传模拟退火算法在搜优率上较遗传算法和模拟退火算法有了较大的提高。从运算过程中的数据可以看出,由于混合遗传模拟退火算法中邻域的选择、变异发生的概率都取自模拟退火的接受概率,再加上它采取了适应度拉伸系数λ,使得遗传算法的“早熟”现象得到很好的解决。另外本文所采用的混合遗传模拟算法的还具有以下优点:(1)优化行为的增强。它具有GA算法的优化时间性能和SA算法可以最终趋于全局最优的优点,克服了GA算法“过早收敛”问题和SA算法优化时间性能较差的缺点。(2)优化效率的提高。它是一种并行而且具有自动保优功能的算法,同时利用GA和SA各自不同的邻域搜索结构相结合,这样使得算法在解空间中的搜索能力所增强,优化效率得到提高。(3)鲁棒性的提高。它的多点搜索消弱了SA算法对初值的依赖性,同时它还利用GA算法不影响平稳分布的特性,提高了整个算法的鲁棒性。如何自动提取任务的信息并计算器加权值,将是我们下一步对该方法进行改进的重点。
参考文献
[1]Barker J R,Mcmahon G B.Scheduling the general jobshop[J].Management Science,1985,31(1):594-598.
[2]Helena R L.Job-shop scheduling:computational study oflocal search and larger-step optimization methods[J].European Journal of Operational Research,1995,83(1):347-364.
[3]董斌,李颖,邵惠鹤.基于遗传算法的类Jop-Shop调度[J].控制与决策,1998,13(1):71-75.
[4]邢文训,谢金星.现代优化计算方法[M].北京:清华大学出版社,1999:104-193.
[5]李军,边肇祺.用于最优化的计算智能[M].北京:清华大学出版社,1999:49-116.
[6]Gold berg D E,Richardson J.Genetic algorithms with sharing for multimodal function optimization[C]//Proc.2nd Int.Conf.Genetic Algorithms and Their Applications.Hillsdale:Lawrence Erlbaum,1987:41-49.
[7]Larranaga P,Kuijpers C M H,Murga R H,Yur-ramendi Y.Learning Bayesian network structures by searching for the bestorderingwith genetic algorithms[J].Systems,Man and Cybernetics,PartA,IEEE Transactions,1996,26(4):478-493.
并行调度 篇4
车间调度问题JSP是一类满足任务配置和顺序约束要求的组合优化问题,是许多实际生产调度问题的简化模型,也是一类典型的NP完全问题,其研究具有重要的理论意义和工程价值。众多学者对此问题采用了各种方法进行解决,有一些传统优化方法如分枝定界法,Lagrangian松驰法。这些算法可以解决一些规模较小的JSP问题,但是随着问题的规模扩大,其计算量大量增加,例如15×15的JSP问题,是这些传统优化方法所无法解决的,于是一些研究者将一些人工智能优化方法应用于JSP问题的解决,如模拟退火[1]、禁忌搜索[2]、遗传算法[3]、移动瓶颈法[4]等。后来许多研究表明单一的算法对于解决一些NP问题,有时效果并不是很好,于是发展了很多混合算法。而对于遗传算法而言,它的全局搜索能力较强,而局部搜索能力较弱,于是往往会与一些启发式算法相结合,增强局部搜索能力。诸如将模拟退火与遗传算法结合[5]、禁忌搜索与遗传算法[6] 、禁忌搜索与模拟退火结合[7]等。
文献[8]中将JSP问题的调度分为半活动调度、活动调度和非延迟调度,三者关系是半活动调度包含活动调度,活动调度包含非延迟调度,活动调度的调度时间要优于半活动调度。他们证明了最优解包含在活动调度中,并提出G-T算法,它能产生所有的活动调度。文献[6]中提出了完全活动调度,完全活动调度是活动调度的一个子集,它的调度时间要优于活动调度,且包含了最优解。
JSP问题解的编码方式有多种,有基于工序的编码、基于优先规则的编码、基于先后表的编码和基于完成时间的编码等[9]。本文采用基于先后表编码的一个变种按机器分段编码的编码方法,此编码方法具有易于理解,便于遗传算子对同一机器的加工工序操作,解空间小的优点。但有一缺点:不是所有编码都是可行解,而本文PLFA算法,可以将可行解与不可行解均转化为完全活动调度。由于遗传算法本身具有良好并行特性,本文采用了主从模式的并行遗传算法模型,使用改进的启发算法PLFA G-T算法来产生完全活动调度的初始种群,使用LOX交叉算子与基于PLFA G-T算法的变异算子,最终形成了一种应用于JSP求解的并行混合遗传算法。
1 问题描述
假设现在m台机器,要加工n个产品,每件产品有若干gi(0<i≤n)道工序需加工。
已知条件如下:
(1) 产品每道工序加工的机器号,用矩阵M表示,其中mij表示i产品的第j道工序加工的机器号。
(2) 产品每道工序加工所需时间,用矩阵T表示,其中tij表示i产品的第j道工序加工所需的时间。
约束条件如下:
(1) 每件产品必须按规定的工序加工;
(2) 每一台机器同一时间只能加工一个产品。
优化目标是安排每台机器上所应加工产品的加工顺序,使得在尽可能短时间内完成所有产品的加工任务。
2 编码设计
将每个染色体R用分别对应于m台不同机器的m个子串构成,各子串是一个长度为n的符号串,每个符号由产品号与工序号组成i-j,表示i号产品的第j道工序,若产品的调度顺序严格按照各符号排列的先后顺序进行,则可能会与约束条件冲突而产生不可行解。例如一个两台机器和两件产品的JSP,若调度矩阵R为:
该矩阵表示,在机器1上加工顺序是产品2的第2道工序、产品1的第1道工序,在机器2上的加工顺序是产品1的第2道工序、产品2的第1道工序,这与约束条件1冲突,因此这是非可行解。要解决此问题有两种方法,一是在最终解码时,将此调度表看成优先表,当调度无法进行下去时,将后面最早可调度的工序提前调度,这种编码方式叫基于先后表的编码。例如对上面调度的解码,当发现机器1和2上都无法调度产品的第2道工序时,优先调度排在后面的产品1的第1道工序与产品2的第1道工序,然后再调度产品的第2道工序;另一方面,仍严格按照各符号先后顺序进行,修改遗传算子,保证产生的解是可行解。为区别于基于先后表编码,本文称之为按机器分段编码。由于PLFA算法不仅能将可行解转化为完全活动调度,也可以将不可行解转化为完全活动调度。因为,在解码时都是可行解,无须在解码时将不可行解转化为可行解了,所以本文将采用按机器分段编码,此编码方式更直观、更易于理解。假设每道产品有m道工序,每台机器加工n道工序,按机器分段编码的解空间为(n!)m。由于问题最终目标是安排每台机器上产品的加工顺序,因此,交叉算子和变异算子只有对每台机器上产品的加工顺序进行操作才是有效的。本文所采用的编码相对于按工序编码而言,便于对同机器上的工序顺序进行交叉和变异操作。
3 调度类型
如果在不改变机器加工顺序的条件下,没有工序可以提前,就称一个调度为半活动调度。如果在不推迟其他工序或破坏优先顺序的条件下,没有一个工序可以提前加工,就称一个调度为活动调度。若一个调度为半活动调度,则一定可以找到某些操作,在不推迟其他操作或破坏优先顺序的条件下,将其左移,插入到同一机器的空闲时间内,将其转化为活动调度。因此,活动调度的调度时间优于半活动调度,且最优解包含在活动调度中。在文献[6]中提出了完全活动调度,如果将一个活动调度的工序调度顺序倒转过来,即产品的最后一道工序先调度,该调度仍是活动调度,则称此调度为完全活动调度。图1所示为将一个活动调度转化为完全调度的过程,其中:(a)为一活动调度;(b)为将工序调度顺序倒转过来,从产品的最后一道工序开始调度,即半活动调度;(c)是将工序1-1左移,将(b)转化为活动调度;最后将(c)的工序调度顺序倒转回来便是(d)了。通过上述四个步骤将活动调度转化为完全活动调度,其调度总时间缩小了,由原来的11变为现在的9。完全活动调度的调度时间小于等于活动调度,且包含了最优解。
下面给出将一个按机器分段编码的可行解转化为活动调度的算法,该算法称之为Active算法:
算法1 Active算法
其中fijk表示产品i的j道工序在机器k上的完成时间;oijk表示产品i的j道工序在机器k加工的工序;r(oijk)表示oijk对应的产品i的j道工序到机器k的时间;S表示各台机器可加工的工序集合;f(o*)表示在S中o*是完成时间最早的工序;半活动调度的染色体为Rsemi,记转化后为活动调度的染色体为Ractive,两者都是按机器分段编码。
(1) 初始化S为所有产品的第1道工序集合;
(2) while(还有工序未被加工){
o*为满足f(o*)=min{f(oijk), oijk∈S}的工序,对o*所在的机器m*进行如下操作:
a) 若半活动调度染色体Rsemi的m*机器当前第一道工
工序在集合中{oijm∈S ,r(oijm)<f(o*)},则选择此工
序;否则,选择o*。记选中的工序为oi*j*m*
b) 在半活动调度染色体Rsemi中第m*行除去i*-j*,即
除去工序oi*j*m*,在活动调度染色体Ractive的第m* 行添加i*-j*,在S集合中除去oi*j*m*,添加产品i*的下道工序到S中。
}
下面给出将一个按机器分段编码的不可行解转化为活动调度的算法。由于该算法具有修复不可行解与将调度转化为活动调度的双重功能,因此,将该算法称之Repair and Active算法:
算法2 Repair and Active算法
(1) 初始化S为所有产品的第1道工序集合;
(2) while(还有工序未被加工){
o*为满足f(o*)=min{f(oijk), oijk∈S}的工序,对o*所在的机器m*进行如下操作:
a) 从半活动调度染色体Rsemi的m*机器加工工序中选一个最早出现的工序oi*j*m*,该工序且要在集合中{oijm∈S ,r(oijm)<f(o*)}
b) 在半活动调度染色体Rsemi中第m*行除去i*-j*,即除去工序oi*j*m*,在活动调度染色体Ractive的第m*行添加i*-j*,在S集合中除去oi*j*m*,添加产品i*的下道工序到S中
}
以上两个算法主要区别在于对o*所在的机器的工序选择上。Active算法选择的是当前第一道工序且要在集合{oijm∈S ,r(oijm)<f(o*)}中或o*,其结果是在不推迟其他操作或破坏优先顺序的条件下,将一些工序左移,插入到同一机器的空闲时间内,将半活动调度转化为活动调度。Active算法也能将不可行解转化为活动调度,但是一些不可行解转化后可能出现同质化,因为不可行解的当前第一道工序经常不在集合{oijm∈S ,r(oijm)<f(o*)}中,使得只能选择o*。例如一不可解某机器的加工工序是(1-6,2-3,4-5,3-2,6-4,5-1),工序1-6要较晚才能被加入到可调度集合S中,因此只能选择o*。Repair and active算法选择的是最早出现在m*机器的加工工序中且在集合{oijm∈S ,r(oijm)<f(o*)}中的工序,可以保持原有调度的加工工序的大部分调度排序,保证种群的多样性。Repair and Active算法也可应用于可行解,将其转化为活动调度,但可能在将一些工序左移时,会推迟其他操作或破坏优先顺序,相当于原可行解有可能产生变异。在没法判断原调度是可行解还是不可行解时,若想增加解的多样性,可用Repair and Active算法,若想保持可行解的优质特性,可用Active算法。在遗传算法迭代前期,可用Repair and Active算法,增加种群多样性,在后期可用Active算法加速收敛。
下面是将一个按机器分段编码转化为完全调度的算法,将该算法称之为基于按机器分段编码的完全活动调度算法PLFA:
算法3 PLFA算法
(1) 若原调度是可行解用Active算法,是不可行解用Repair and Active算法,将该调度变为活动调度;
(2) 将活动调度染色体编码倒转过来;
(3) 加工顺序更改为从产品最后一道工序开始加工,第一道工序最后加工,调用Active算法;
(4) 将编码倒转回来。
4 初始种群
初始解对最终的搜索结果有着重要的影响,不好的初始解将可能导致需要更长的搜索时间得到最优解,还可能降低获得最优解的可能性。G-T算法是J. Giffler 和 G.L. Thompson 在1963年提出的,生成的解都是活动调度的[8]。本文对G-T算法进行了改进,使之产生的解都是完全活动调度,我们把改进的G-T算法称为PLFA G-T算法。本文便用PLFA G-T算法来产生初始种群,具体算法描述如下:
算法4 PLFA G-T算法
(1) 将S初始化为所有产品第1道工序的集合;
(2) while(还有工序未被加工){
o*为满足f(o*)=min{f(oijk), oijk∈S}的工序,对o*所在的机器m*进行如下操作:
a) 从集合中{oijm∈S ,r(oijm)<f(o*)}中随机确定一个操 作oijm,在矩阵R的m*行中添加i-j;
b) 并在集合S中除去oijm,添加产品i的下道工序到S中;
}
(3) 调用PLFA算法作用于R。
5 交叉算子
交叉算子是遗传算法的主要算子,直接决定了遗传算法的全局搜索能力,它需要能够很好地继承父代染色体的一些特性。本文采用的线性次序交叉(LOX)算子[10],就可较好地继承父母的基因。具体而言,首先随机确定两个交叉位置,交换交叉点之间的片段,并在原先父代个体中删除将从另一父代个体交换过来的基因,然后从第1个基因位置起依次在两交叉位置外填入剩余基因。例如,先随机选择一对父母染色体,然后随机选择要进行交叉的机器号,使用LOX算子交叉在这些机器号上加工的工序。如选出一对父母染色体p1、p2分别为:
选出的机器号是2,则对2号机器的加工工序执行LOX交叉,交叉点的位置为2和4,则片段(1-2,2-2,2-4)与(1-2,3-1,3-5)将交换,在p1的2号机器的加工工序上删除(1-2,3-1,3-5)后剩余(2-2,2-4,1-5),然后将片段2在剩余基因的位置2处填入,得到后代1的2号机器加工工序(2-2,2-4,1-2,3-1,3-5,1-5),相应的后代2的2号机器加工序为(3-1,3-5,1-2,2-2,2-4,1-5),生成的子代为:
此交叉算子能较好继承父母的优秀基因。但由于采用的是按机器分段编码,交叉有可能产生非可行解,所以须对交叉结果进行矫正,将产生的非可行解变为可行解。由于PLFA算法不仅能将可行解转化为完全活动调度,也可以将不可行解转化为完全活动调度,因此本文将对交叉后产生的后代运用PLFA算法,这样可以改将可行解转化为完全活动调度,改善解的调度时间,而将不可行解矫正为完全活动调度。
6 变异算子
变异算子决定了遗传算法的局部搜索能力,它是对染色体做一些扰动,以增加种群的多样性,避免过早收敛,突破局部最优。本文采用基于PLFA G-T算法的变异算子[11],该算法与PLFA G-T算法不同的是,PLFA G-T算法是随机产生完全活动调度解,而在该变异算子中PLFA G-T算法在为每台机器选择加工工序时,随机选择的概率是变异概率pm,1- pm的概率要依据变异母染色体进行选择。染色体变异产生的后代,都是可行解,都是完全活动调度,大大提高了变异后代的质量。具体算法如下:
算法5 基于PLFA G-T算法的变异算子
pm为基因变异概率:
(1) 随机选一条染色体作为变异染色体的母染色体Rold,初始化S为所有产品的第1道工序集合;
(2) while(还有工序未被加工){
o*为满足f(o*)=min{f(oijk), oijk∈S}的工序,对o*所在的机器m*进行如下操作:
a) 产生一个(0,1)随机数δ,如果δ<pm,从变异染色体 Rold的m机器加工工序中选一个最早出现的工序oijm,该工序且要在集合中{oijm∈S ,r(oijm)<f(o*)},否则,从集合中{oijm∈S ,r(oijm)<f(o*)}中随机确定一个操作oijm;
b) 在新染色体Rnew的第m*行添加i-j,在S集合中除去oijm,添加产品i的下道工序到S中;
}
(3) 调用PLFA算法作用Rnew
7 并行遗传算法
目前并行遗传算法模型主要分为四类:主从式模式、粗粒度模式、细粒度模式和混合模式。主从模式是遗传算法的直接并行化方案,不改变遗传算法的基本结构特点,它只有一个群体,个体之间可以任意匹配,每个个体都有机会和其他个体杂交而竞争,因而在种群上所作的选择和匹配是全局的。选择、交叉和变异等全局操作由主节点机(或主处理器)串行进行,而适应度的评价和计算由各从节点机(或主处理器)并行执行,主节点机(或主处理器)和从节点机(或主处理器)的通信表现在两个方面:一方面主节点机(或主处理器)把选择的群体部分个体发送给从节点(或主处理器);另一方面从节点机(或主处理器)把适应度的评价结果发送给主节点机(或主处理器)[12]。
根据实验,发现用遗传算法解决JSP时,主要的计算时间用在了适应度值的计算上,因此应用主从模型解决JSP将是一种非常有效的并行方法。
8 应用实例分析
本文的并行混合遗传算法选择遗传代数作为终止条件,采用Java编程实现,在双核1.6GHZ的平台运行,并行遗传算法使用双线程计算适应度值。采用Fisher和Thompson(1963年)提出的FT06、FT10和FT20,与Lawrence(1984年)提出的LA系列作为检验算法优劣的测试实例。表1对九个测试实例先用随机算法产生300个随机解,然后再用Active算法、PLFA算法对随机解进行改进得到活动调度解和完全活动调度解,最后求出这300个随机解、活动调度解和完全活动调度解的平均值。表中所列的就是这些平均值。从计算结果可看出,Active算法相对随机解改进约20%～30%, PLFA算法相对活动调度解改进约6%～7%。表2比较了并行混合遗传算法(PHGA)与串行混合遗传算法(HGA)的运行时间。表3比较了融入PLFA算法(PLFA-GA)与没有融入PLFA算法(Non PLFA-GA)的遗传算法的运行结果。Non PLFA-GA算法就是在初始种群产生,以及交叉,变异算子中不将调度转化为完全活动调度。表2和表3的运行参数如下,种群规模100,遗传代数为100代,交叉概率0.7,染色体变异概率0.3(将选择30%的染色体进变异),基因变异概率0.1(变异算法中pm的值),并把前10%的精英染色体拷贝到下一代。表3对每个测试案例进行了20次计算,得到了20次解的最优值Best,平均值Average,从表中可看出在一些较复杂的JSP问题的计算结果,如FT10,LA16,PLFA-GA比Non PLFA-GA上有了明显的改进。表2对每个测试案例进行了20次计算得到平均时间,处理器结点为2个,并行混合遗传算法的加速比约为1.3～1.4。
9 结 论
本文设计了基于按机器分段编码的完全活动调度算法PLFA,并将该算法融合于遗传算法,形成了并行混合遗传算法。通过PLFA G-T启发算法来产生全是完全活动调度的初始种群,良好的初始种群提高了算法的搜索性能。采用的LOX交叉算子可以很好地继承父染色体的特性,以及基于PLFA G-T算法的变异算子可以很好地增加种群的多样性,并且交叉算子与变异算子都结合了PLFA算法,产生的后代都是完全活动调度。最后,结合了主从模式的并行遗传算法模型。实验结果表明,Active算法与PLFA算法对随机解有显著的改进,在较复杂JSP的计算结果上PLFA-GA比Non PLFA-GA有明显的改进,并行混合遗传算法比非并行混合遗传算法,在计算时间上可以减少20%～30%,其加速比约为1.3～1.4。
摘要：结合先后表编码和完全活动调度概念,设计了基于先后表的完全活动调度算法PLFA,该算法能将可行解与不可行解转化为完全活动调度。并将PLFA算法与遗传算法结合,提出了一种并行混合遗传算法,初始种群由PLFA G-T算法产生,其产生的解都是完全活动调度,采用LOX的交叉算子与基于PLFA G-T算法的变异算子,并使用主从模型的并行遗传算法模型。最后JSP基准实例验证了算法的有效性。
关键词：车间调度,遗传算法,完全活动调度
参考文献
[1]Laarhoven P J MV,Aarts E HL,Lenstra J K.Job shop scheduling bysimulated annealing[J].Operations Research,1992,40:113125.
[2]Taillard E D.Parallel taboo search techniques for the job shop schedu-ling problem[J].ORSA Journal on Computing,1994,6(2):108117.
[3]Davis L.Job shop scheduling with genetic algorithms[C]//Proceedingsof the First International Conference on Genetic Algorithms and theirApplications.Morgan Kaufmann,1985:136140.
[4]Adams J,Balas E,Zawack D.The shifting bottleneck procedure for jobshop scheduling[J].Management Science,1988,34:391401.
[5]Cai L W,WUQH,Yong Z Z.Agenetic algorithm with local search forsolving job shop problems.Lecture Notes in Computer Science,2000:107116.
[6]Chaoyong Zhang,Yunqing Rao,Peigen Li.An effective hybrid geneticalgorithm for the job shop scheduling problem[J].The InternationalJournal of Advanced Manufacturing Technology,2008:965974.
[7]Chao Yong Zhang,PeiGen Lia,YunQing Raoa,et al.A very fast TS/SA algorithm for the job shop scheduling problem[J].Computers&Operations Research,2006:282294.
[8]Giffler J,Thompson G L.Algorithms for solving production schedulingproblems[J].Operations Research,1960.
[9]Cheng R,Gen M,Tsujimura Y.A tutorial survey of job-shop schedulingproblems using genetic algorithms,part I:representation[J].InternationalJournal of Computers and Industrial Engineering,1996,30:983997.
[10]Cheng R,Gen M,Tsujimura Y.Atutorial survey of job-shop schedulingproblems using genetic algorithms,part II:hybrid genetic search strate-gies[J].International Journal of Computers and Industrial Engineer-ing,1999,30:343364.
[11]Yamada T,Nakano R.A genetic algorithm applicable to large-scale job-shop problems[C]//R Manner,B Manderick.Proceedings of the SecondInternational Conference on Parallel Problem Solving,Nature ElsevierScience Publishers,North-Holland,1992:281290.
并行调度 篇5
本文设计的并行系统任务调度算法是基于列表的, 着重优化了传统算法中的节点等级计算方法, 并改善了通信的调度, 与HEFT算法相比在性能上有一定进步。
1 任务调度相关原理
并行系统的任务调度S可以抽象地表示为下列式子:S∶M=f (T, D) , 其中f表示任务调度算法, 可看成一个复杂的函数;T代表硬件平台结构, 用拓扑图来表示;D表示任务的DAG描述;M表示任务调度结果 (Makespan) , 它可以抽象地看成硬件结构T和任务D在调度算法f下的一个函数值。
1.1 硬件平台结构
硬件平台结构一般是一个拓扑图, 用T= (N, P, L, b) 表示[1];N表示处理器和路由的集合;P表示处理器的集合;L表示所有链路的集合;b代表链路上的数据通信速率;在同构系统中, 每条链路的通信速率都相同, b反映的是通信时间。本文的硬件平台采用总线式多核处理器结构。
图1中所示的总线式多核结构由n个协处理器挂载在系统总线上构成[2]。本文设定每个协处理器同构, 具有相同的处理速度, 任意两个协处理器之间的通信速率相等, 且考虑通信拥堵。
1.2 任务的DAG描述
任务的描述方法有多种, 文中采用基于有向无环图描述方法, 其又称为DAG, 如图2所示, 是一个简单的DAG图。
DAG图可表示为:D= (V, E, w, c) , 其中V={nini是有序任务节点, i=1, 2, 3, …, V}, V表示节点数目;E={eijeij是任务ni到nj的边}, E表示边的个数[3]。节点代表运算, 它的权值w (ni) 代表运算时间;边代表两个节点之间的通信, 它的权值c (eij) 代表通信时间。前驱节点定义为pred (ni) ={nx∈V∶exi∶E}, 后继节点定义为succ (ni) ={nx∈V∶eix∈E}。满足pred (ni) =Ø的节点ni称为源点, 满足succ (ni) =Ø的节点称为汇点。
1.3 考虑通信拥堵的调度相关规则
调度一个DAG图就是要为DAG中每一个节点分配一个处理器并赋予一个开始时刻, 在考虑通信拥堵时, 还需要将每条边分配到相应的通信链路上并赋予合适的开始时刻。在一般硬件结构下考虑通信拥堵的任务调度相关规则已经在文献[1]中给出, 将这些规则演变成同构环境中, 则在拓扑图T上对任务图D的调度相关规则可描述如下。
记proc (ni) 为分配给ni的处理器;st (ni, p) 为ni在处理器上p的开始时间;w (ni) 为ni在任一处理器上的运算时间;ft (ni, p) 为ni在处理器p上的结束时间;则有ft (ni, p) =st (ni, p) +w (ni) 。所有节点都完成调度的最晚结束时间被称为调度完成时间, 记为makespan, 有。本文设定通信只有在关联节点处于不同的处理器上时才发生, 同一处理器上的任务通信可以忽略。边eij在链路Lm上的开始时间为st (eij, Lm) , 结束时间为ft (eij, Lm) , 则在同构环境中有ft (eij, Lm) =st (eij, Lm) +c (eij) 。某节点的数据就绪时间是指该节点所有前驱节点的数据都输出完毕的时间, 记为DRT (Data Ready Time) , 节点ni在处理器p上的数据就绪时间DRT (ni, p) =max{max{ft (exi, R (exi) ) }, max{ft (pred (ni) ) }}, 其中R代表为对应通信分配的链路, exi指来自不同处理器上的节点通信。只有在DRT时刻后, ni才可以在分配的处理器上开始运算。
1.4 节点的等级量度
调度列表的生成依据是节点的等级, 等级量度方法所考虑前后继因素的全面程度对调度效率的影响较大。在传统的调度算法研究中使用较多的两种等级量度方法分别是u_rcomp/d_rcomp和u_r/d_r。调度算法的思想是根据节点等级生成调度列表, 依此列表顺序将每一个节点安排给结束时间最早的处理器。但这两组等级量度方式的缺点是考虑的因素较为单一, 是比较粗糙的量度方式。为解决这个问题, 文献[1]提出了较全面的等级量度方法, 其中之一是u_rout/d_rout, 分别定义如下
这种定义方式充分考虑了去往后继节点的通信时间。后继节点的情况在一定程度上影响着节点调度的紧迫性, 有较多后继的节点若未能得到及时调度, 将影响其所有后继节点的及时调度, 故应该赋予较高的等级。另外, 除了能准确描述节点调度的紧迫性以外, 一个好的节点等级量度方式还应具有较好的区分度, 在数学上意味着较大的方差, 这可在一定程度上避免偶然因素对调度次序的影响。以选取的u_rout/d_rout为例, 将文献[1]中列出的经典任务图的u_rcomp/d_rcomp、u_r/d_r和u_rout/d_rout值计算其方差列出如表1所示。
由表1可知, 使用u_rout/d_rout比传统的量度方式具有更高的区分度。
2 调度算法描述
2.1 调度列表生成
在任务调度中, 节点的等级反映了该节点到汇点和源点距离的远近, 任务调度的一般思路是汇点距离远的节点都应尽早地调度[4], 故存在两种理论上的调度列表生成方式, 即按照u_rout从大到小, 或d_rout从小到大排列, 同等级节点则随机排列。由于后继部分是属于未调度部分, 前驱部分属于已调度部分, 而未调度部分对节点调度紧迫性的影响要大于已调度部分对紧迫性的影响, 故本文采用u_rout从大到小排列的方式。
2.2 通信的调度
在通信的调度过程中采用了链路空闲区间插入方法[5]。链路上的空闲区间记为eidle, 设eidle (k) 是某通信链路上的空闲区间, eij为待调度通信, 则当max{st (eidle (k) ) , ft (ni, proc (ni) ) }+c (eij) ≤ft (eidle (k) ) 时, eij就可以安排在空闲区间eidle (k) 上进行, 对应的开始时间和结束时间用下式计算
链路空闲区间插入方法如图3所示。
图3 (a) 中, est (e4) 指e4的最早开始时间, 在e2之前存在一个可利用的空闲区间;图3 (b) 中将e4安排到该空闲区间内进行。对比图3 (a) 和图3 (b) 可知, 使用链路空闲区间插入方法可以减小调度完成时间。
2.3 处理器选择
一般的调度算法大部分针对异构环境, 故将结束时间最早的处理器作为目标处理器, 演变为同构环境时, 可以选取开始时间最早的处理器作为目标处理器。在建立待调度节点在每一个处理器上开始时间的过程中, 使用传统HEFT算法中的处理器空闲区间插入方法, 该方法与链路空闲区间插入方法类似。处理器上的空闲区间记为idle, 设idle (k) 是某处理器p上的空闲区间;ni为待调度节点, 则当max{st (idle (k) ) , DRT (ni, p) }+w (ni) ≤ft (idle (k) ) 时, ni就可以安排在空闲区间idle (k) 上进行, 对应的开始时间和结束时间用下式计算
记目标处理器为pbest (ni) (即proc (ni) ) , 则pbest (ni) ←min{st (ni, p) }。
这里使用一个满足插入条件的DAG任务图, 并与调度时刻图结合描述, 如图4所示。
图4中带数字的箭头代表任务图中各边的权值, 图4 (a) 图中阴影部分表示可以利用的空闲区间, 图4 (b) 图中将n4、n5和n6安放到空闲区间内执行。由图可知, 使用空闲区间插入的方法可以减小调度完成时间。
3 实验结果
本文采用同构的四核总线结构作为实验环境, 且考虑通信拥堵。为直观说明本文算法在调度性能上的提高, 采用调度下界比SLR (Schedule Length Ratio) 作为性能评估的参数[6]。SLR的定义为
其中, makespan为调度完成时间;cp为关键路径节点。SLR的数值越小, 表明算法的调度效率越高。
由于调度算法的调度效率实际反应的是一个数学期望, 需大量的实例取平均结果来进行比较, 故本文采用对随机任务图进行验证的方法。通过设置任务图的相关参数, 利用TGFF 3.5软件工具[7]可产生符合条件的随机任务图, 相关参数选取如表2所示。
其中, dei/o为平均入度与平均出度的比值, CCR为平均通信-计算时间比[8,9,10]
dei/o在取固定值1后, 节点个数V和CCR两个参数通过控制变量得到的实验结果如图5所示。
由图5可知, 无论是传统的HEFT算法还是本文的算法, 随着节点数量的增加, SLR都呈现下降趋势, 表现为调度性能的增强, 其主要原因是节点数目增多, 任务图规模增大, 任意两个节点之间的平均距离增加, 相关程度降低, 直接通信的可能性降低, 使得任务调度的并行度增加;调度性能随着CCR的增大而迅速减弱, 其主要原因是通信时间占调度时间的比重在增大。另外, 结合两图还可以看出, 本文的调度算法相比HEFT具有一定的性能优势, 其主要原因就是更全面的节点等级量度方式和对通信调度的改善。
为进一步说明实验结果, 计算出每一种组合下的SLRHEFT/SLRproposed值, 列表如图6所示。
由图6可知, 在30种组合中只有5种组合下的调度实验显示本文算法性能弱于传统HEFT算法, 大部分情况下, 本文的算法性能要优于或接近HEFT算法。在考虑偶然因素对调度结果影响的情况下, 可以认为本文的调度算法在一定程度上优于HEFT算法。
4 结束语
在多核并行系统中, 任务调度算法的效率对系统性能有着重要影响。本文在同构的总线式多核系统环境下采用文献[1]中提出的3种新的等级量度方式之一———u_rout/d_rout, 更全面地考查了节点调度的紧迫程度, 并且具有更高的区分度;在通信调度过程中使用链路空闲区间插入方法避免了链路的空闲;在任务分配的过程中沿用了HEFT算法中的处理器空闲区间插入方法, 充分利用了处理器的资源。利用随机生成的任务图进行实验结果的统计, 并对比传统HEFT算法, 表明该算法一定程度上提高了任务调度的效率。本文考察的同构系统模型较为理想化, 但在使用DAG图进行任务调度算法的研究设计中, 对于异构系统环境也有一定的参考价值。
摘要：设计了一种适用于同构总线式多核环境的任务调度算法, 着重优化了传统静态列表算法中对于任务节点等级较为粗糙的计算方式, 并改善了对通信的调度。通过统计性调度实验, 表明该任务调度算法相比传统的调度方法具有一定的优化效果。
关键词：任务调度,总线,同构,列表
参考文献
[1]穆鹏程.并行嵌入式系统中具有通信竞争任务调度问题的高级列表调度方法[J].中国科学:信息科学, 2011, 41 (3) :349-364.
[2]王颖锋, 张彦周, 高韬.多核嵌入式系统总线冲突避免的节能调度综述[J].计算应用研究, 2014, 31 (4) :961-969.
[3]李召妮, 雷丽晖, 李永明.多处理器任务调度算法TDS的建模与验证[J].计算机科学, 2012, 39 (11) :301-305.
[4]OLIVER S.Task scheduling for parallel system[M].New Jersey:John Press, 2007.
[5]LI Long, LI Dongsheng, SONG Yukun, et al.An effective list scheduling algorithm for homogeneous multi-core processor[C].Shanghai:ASID2013, 2013:80-84.
[6]尹杨美.一种改进的异构多处理器实时任务调度算法研究[D].长沙:湖南大学, 2010.
[7]ROBERT P, DAVID L.RHODS TGFF:Task graph for free[D].New Jersey:Department of Electrical Engineering Princeton University, 1998.
[8]刘勇.嵌入式可重构系统及其任务调度机制的研究[D].上海:中国科学院研究生院, 2005.
[9]王永亮, 李秀娟.嵌入式多任务程序设计[J].电子科技, 2010, 23 (1) :94-96.
并行调度 篇6
关键词：电网调度,调度运行,运行指挥,网络信息化
1 前言
传统单一电话指挥模式下存在电话堵塞现象严重、应急处置过程中的信息收集不够快速、调度员工作效率不高、语音存在歧义等安全风险。需要创建“电话+网络”并行的电网调度实时运行指挥新模式, 网络有着“一对多、多维性、集成性”的优势:
1) “一对多”:网络可以同时与多个厂站单位通讯;
2) “多维性”。电话通讯的内容只有声音, 而网络的内容可包括文字、图像、声音等多种形式。
3) “集成性”:可以与计算机技术集成和整合, 自动生成过程记录, 省去手工记录的环节, 提高工作效率。
电话通讯有着“真实、直接、灵活”的特点。建设电网调度运行指挥平台 (以下简称:平台) , 以调度指令和实时业务消息为核心, 可支持云南电网省、地、县 (配) 三级调度机构与各自管辖多个调度对象之间并行开展电网运行业务网络实时通讯, 再以平台和原有的调度电话为依托, 创建“电话+网络”并行的电网调度实时运行指挥新模式, 可有效的解决传统单一电话通讯模式下所存在的问题。
2 建设方法
1) 将调度运行指挥业务中的部分环节通过网络进行。将调度运行指挥业务中, 安全风险相对较小、同一个任务需要批量下发、带有一定重复性的环节通过平台进行;将调度运行指挥业务中一些紧急的、高风险的工作仍然通过调度电话进行, 如事故处理、一经下达立即操作的调度命令等。
2) 通过网络下发指令内容, 诠释调度指令。
3) 利用模板化的信息收集方式, 提高应急处置效率, , 不需要手工记录, 可立即将各个厂站上报的信息实现自动汇总, 并根据汇总后的信息制定决策。
4) 利用技术手段确保网络指挥的顺利进行
a.平台运行在省调管理信息大区 (Ⅲ区) , 其后台数据受到专用防火墙保护, 不会受到调度数据网以外的信息干扰。
b.平台将登陆账号和使用权限管理与调度系统运行人员受令资格进行动态管理, 只有具备调度机构受令资格的运行人员才有登录账号和使用权限, 有效保证了平台使用过程中的安全性。
c.平台调度业务消息在网络传送过程中, 利用对象闭锁机制, 将消息的发送主体与接收端进行点对点的闭锁控制, 规范消息行走路径。
d.消息接收端采用消息托盘技术, 建立消息总线与托盘程序的实时通讯, 实现消息的类型定义、多媒体展示、消息面板提醒、语音提示报警等, 确保消息接收者第一时间察觉并判断消息发送的主体和其所包含的业务内容。
e.将调度管辖范围置入了基础数据库, 可确保省地县三级调度机构分别与各自管辖调度对象同时开展业务过程中的消息准确、规范、清晰、相互不影响。
5) 从制度上确保“电话+网络”并行的电网调度实时运行指挥模式开展
3 实际应用
调度运行操作是为进行设备检修、消缺、技改、电网事故及缺陷处理、电网运行方式变更所进行的设备由一种状态向另一种状态转换的行为, 由厂站运行人员在调度机构调度员指挥下统一进行。传统调度电话单一运行指挥模式下, 电网调度运行操作业务各环节的指挥均通过电话来完成, 如图1所示, 共有五个环节, 其中的第1、3、5环节均是属于通知、通报的工作内容。
采用“电话+网络”并行的电网调度实时运行指挥模式, 将第1、3、5环节通过网络进行可取的良好的效果:
1) 通过“电话+网络”并行模式中第a个过程代替传统模式中的第1个过程, 使调度员不需要将次日的检修申请逐个电话通知到工作相关单位的运行部门和操作相关厂站, 不需要和相关单位核对检修申请票号和工作内容;仅通过平台一次性完成, 还能给相关单位以票面的形式直观展示, 既节省了双方的时间, 又提高了效率。
2) 通过“电话+网络”并行模式中第c个过程代替传统模式中第3个过程, 使调度员不需要通过电话将预令逐个下至操作相关厂站, 仅通过平台即可将调度操作票以预令票的形式一次性发布到所有操作相关厂站, 给操作相关厂站以票面的形式直观展示, 一方面能够又有效的利用现场运行人员对整个操作流程实施监护, 一方面节省了时间, 提高了效率。
3) 通过“电话+网络”并行模式中第e个过程代替传统模式中第5个过程, 使调度员不需要通过电话将设备停复电信息逐个通知到申请工作的相关单位, 仅通过平台即可一次性完成, 节省了调度员的时间。
“电话+网络”并行模式中第d个过程和传统模式中第4个过程并没有通过网络进行, 它属于一经下达立即操作的调度命令, 这类工作仍然通过调度电话进行。
实际应用表明, “电话+网络”并行的电网调度实时运行指挥新模式, 使得电话通讯通道得到了有效释放, 应急处置速度明显提升, 调度员工作效率有所提高, 能够有效解决了传统单一电话通讯模式下所存在的问题见表1。
4 结束语
综上所述, “电话+网络”并行的电网调度实时运行指挥新模式在省地县三级调度机构和调管厂站中投入生产运行, 有效的解决了传统单一电话指挥模式下所存在的电话堵塞现象严重、应急处置信息收集不快、语音歧义存在安全风险等实际问题, 加强了电网运行的一体化管理, 保障了电网安全, 提高了工作效率。
参考文献
并行调度 篇7
生产计划与调度问题是制造企业最基础也最核心的问题,是在满足某些约束条件 (如有限生产能力及资源、任务释放时间和截止期等) 下对任务进行合理排序,并安排各个任务开工时间,最终实现企业一个或多个目标的最优化。实际中对调度的评价大致可归为三类:最大能力指标、成本指标、客户满意度指标[1],其中最大能力指标大多应用在需求固定或需求无上限的情况下,传统生产调度应用较多,但实际却是提前完成生产的成品需入成品仓库需要支付一笔不小的仓储费用,延期生产产品则会有损企业声誉,同时企业还需支付违约金,因此实际中更多的综合考虑库存成本以及延期惩罚费用。
考虑库存成本、延期惩罚生产调度问题的核心是准时化生产。专家学者对其进行大量研究:Held[2]和Bagchi U[3]研究了单机环境下的提前、拖期调度问题;Prabuddha De[4]探讨了单机调度完成时间偏差最小化问题,调度中考虑了不同任务的加权系数情况;Coleman[5]针对考虑任务准备时间与加工顺序相关这一实际情况研究单机调度问题;Fry and Armstrong[6],Garey and Tarjan[7]和Yano and Kim[8]研究了给定排序下的开工时间优化问题,但对惩罚权重有一定的限制;Cheng T C E[9]讨论了互不相关的任务在多机的并行调度问题,阐述流程时间加成本最小、提前拖期惩罚费用最小两个问题。
多机并行调度问题虽得到一定研究,但调度的任务间大多是无关的,然实际中会由于生产容量限制需要将订单拆分为加工任务,这些任务间实际上存在一定关系的,这对调度有一定的影响。本文以某酒企业生产为研究背景,研究已知交货期的订单在生产容量限制分割为子订单后的多机并行调度问题,尽量实现各订单的准时化生产。
1问题描述
本文研究的酒生产调度是在一般车间调度问题上简化的,不考虑具体的工艺路线,整套的工艺路线在一台机器上即可生产完;其中加入了生产中容量限制这一约束,在可能情况下都以最大容量组织生产,最后不够最大容量的人任为一批组织生产, 这就要求先要对生产订单进行分割,在此基础上进行调度。本文的计划排程描述如下:实现i个订单在m台机器上并行调度, 其中涉及订单拆分情况。排产调度要做的是: (1) 根据产品的最大生产容量将i个订单分割为各子订单即要排产的任务。 (2) 把各子订单安排到m台机器上生产并确定产线上子订单的生产顺序和生产时间;调度的目标是使得所有订单能够在交货期附近结束生产,使得批生产、库存成本、延期惩罚费用最小。生产计划流程图如图1所示:
2数学模型
对多产品批处理的多机并行调度问题作如下假设:
(1) 每个订单只包含一种产品,并指定交货期、生产数量;
(2) 每种产品可以在多台机器上生产;
(3) 生产中不允许出现中断;
(4) 每一次生产都以最大容量生产,不够最大容量仍组织一次生产;
(5) 产品在机器上的批处理时间依产品种类不同;
(6) 产品之间的转换时间依产品种类不同,不同产线上相同转换顺序的转换时间相同。
该模型中使用的符号索引、决策变量及参数如表1所示:
问题的数学模型为:
式 (1) 是计划排产的目标,表达式中依次为批生产费用、延期惩罚费用、生产库存惩罚,其中库存费用与单位库存成本及库存时间成正比,而延期费用与订单的生产数量成正比。表达式中的完成时间Cik与决策变量TSikj关系为Cik=TSikj+tSikj;式 (2) 表示分割后的每个子订单智能安排在一条产线上约束;式 (3) 表示任务间加工顺序约束,前驱任务完工后才能开始后继任务; 式 (4) 表示订单的分割子订单的开始时间与完成时间之间的约束关系。
3遗传算法优化求解
本文调度借鉴一般调度问题的解决工具遗传算法,利用遗传算法能同时使用多个搜索点,有能力在各种调度方案之间进行选择交叉和变异等运算,可以跳出局部最优的陷阱,使解集性能不断得到优化。但本文求解过程不似一般调度问题,存在区别为:调度任务间不是相互独立的。一般调度问题中各任务间相互独立,在使用遗传算法确定其生产顺序后,采用线性规划方法即可求解;但本文中调度任务间并不完全独立,存在多个任务来自同一订单情况,而目标函数中库存、延期惩罚分别与任务以及订单相关,两者之间有关联,采用线性规划问题不能得以解决,故在采用遗传算法优化任务的排序顺序后嵌套遗传算法确定优化排产顺序下的各任务开始生产时间使得生产、库存、延期惩罚费用最小。其算法流程如图2所示。
(1) 个体编码
外层遗传算法求解任务的机台号及其顺序,采用向量组的编码方法,任务k在产线m上加工,则位基因表示为个体基因则为其中第一行为随机排列的任务,第二行为任务的产线编号,任务间的加工顺序则遵循在基因第一行中的排列顺序。
内层遗传算法求解各任务开始加工时间,采用一般向量编码方法,任务单k开始加工的时间Sk,则个体基因为(S1S2… SN)。
(2) 适应度函数的选取
两层遗传算法均取模型目标函数为适应函数即适应值越小染色体对应的目标值就越小。
(3) 选择
两层遗传算法均选取最优保存策略为选择机制,保证适应性好的个体保留到下一代中。
(4) 交叉
外层遗传算法中向量组基因若采用传统的交叉方法,可能会产生任务加工产线不满足约束条件的不合法个体,基于此外层采用EOX交叉法:在交叉操作的两父代个体 (A、B) 中选择父代个体 (A),随机取其中的一段基因串 (S),将B中的第一行元素与S的第一行元素进行比较,如果存在相同的则从B中删除掉对应元素的基因,将S插入到B中被删除掉的基因第一行元素中与S中第一行第一个元素相同的地方,形成新的个体。依上述交叉过程反过来即可产生另一新个体。
内层遗传算法中的位基因涉及浮点数,采用中间交叉即子个体i=父个体Ai+F×父个体Bi-父个体Ai,直至交叉产生满足时间约束关系的个体。
(5) 变异
外层算法中的个体基因包含任务加工产线及其顺序,变异时要考虑任务加工产线以及任务加工顺序变异,采用单点变异 (改变任务的加工产线) 及交换变异 (改变任务的加工顺序) 相结合的方法保证变异的多样性。
内层算法中根据任务的加工顺序计算其开始加工时间范围,在此范围内对开始加工时间变异。
(6) 终止条件
设定循环最大次数。
4实验结果分析比较
上述数学模型中目标函数考虑了库存、拖期惩罚以及生产启动三种费用,将该模型与目标中只考虑其中一项比较,研究不同费用目标对调度结果以及各项性能指标改变,本文主要考虑目标中只有拖期惩罚费用。为了方便,简记两种模型目标为:考虑三种费用记为费用和模型,只考虑拖期惩罚记为拖期模型。
采用Balakrishnan N[10]中参数设置规则设置实验数据:生产启动费用满足U [0,5 0];产品间的转换时间满足U[25,75];产品生产批量及批处理时间均满足N 100,100 ;产品的库存成本及拖期惩罚满足U [0,4]、U [0,6];订单中产品生产数量满足U [0,N],其中N=批次容量 * 产线数;订单截止期则满足U [1.2*processtime,3*processtime],其中processtime是产品的批处理时间。
参数设置完后,比较不同模型中三种费用及各项性能指标,然后改变拖期惩罚系数进行相同实验。不同模型的三种费用结果如表2、表3所示:
不同模型的各项性能指标结果如表4、表5所示。
通过表4、表5的数据对比可知,相同惩罚系数下拖期模型的延迟订单数小于费用和模型,订单最大完成时间、最大拖期时间均小但是最大在库时间大,因为拖期模型只考虑拖期费用要求订单尽量不延期,任务调度时任务间的时间间隙会减小,相应订单延迟数、最大完成时间、最大拖期时间均小,但会形成大量成品的在库积压,牺牲在制品库存积压缩减订单延期;且随着惩罚系数增大,延迟订单数、最大完成时间、最大拖期时间减小、最大库存时间增大,因为随着惩罚系数增大,惩罚费用在总费用中占的比例逐渐增大,这要求排产时订单不延期,任务间的时隙会渐渐变小直至为0,成品的在库时间也会增大。特别说明,表3中延迟订单数并没有明显变化因为订单量N=6情况下各订单间截止日期比较相近,在最小化拖期惩罚下排产会造成较多的订单延迟且变化不大;表4中延迟订单数变化比较明显因为订单N=9情况下订单间截止期有比较大的差距,随着惩罚系数增大,提前生产的订单数量会增大延迟的订单数就会逐渐减少。
不同订单量,不同拖期惩罚系数下各费用如图3、图4所示。
由图3、图4可知,不同惩罚系数下,拖期模型的拖期惩罚费用小于费用和模型,但是库存费用、总费用均大,因为拖期模型只考虑拖期费用要求订单尽量不延期但是允许提前生产存在,对比下会造成更多的库存费用,拖期模型是通过增大库存费用来减少惩罚费用,又由于惩罚费用小时库存费用在总费用占有较大比例会造成最终总费用增大;且随着惩罚系数的增大,不同目标下费用之间的差距减小,因为随着惩罚系数的增大,惩罚费用在总费用中占的比例逐渐增大。相比只考虑拖期费用,准时化生产的费用和模型为企业提供良好的选择。
5结束语
针对多产品生产调度问题,结合准时化生产理念,提出了一种混合整数数学模型,模型中考虑批量生产约束、生产启动时间以及多机并行等实际问题。比较不同拖期惩罚系数及不同目标下的各项性能指标。通过实验对比数据,考虑提前/拖期惩罚费用、生产启动费用之和优于只考虑拖期惩罚,从利润角度出发为企业提供一个良好的解决方案,且为不同指标需求提供选择。 进一步的研究可考虑结合启发式规则排产缩短计算时间。
摘要：针对多品种批量生产类型,基于准时化生产理念,研究在生产能力有限约束下将各订单拆分为各子订单,实现各子订单在多机器上的并行调度问题,以最小化生产费用、库存成本、延期惩罚之和为目标,提出了一种混合整数数学模型并采用遗传算法求解,对比了模拟实验结果并讨论了不同延期惩罚系数对不同目标函数的各项性能指标的影响。