没有合适的资源?快使用搜索试试~ 我知道了~
:在满足时序、资源许可的前提下优化调度产品并行设计过程,缩短产品上市时间已成为当前研究的一个重点。 针对并行设计特点建立了设计任务调度的目标函数,提出了一种遗传算法。该算法用矩阵式染色体表示设计任务与设 计单元之间的调度关系,采用突变机制来解决进化过程停滞问题,提高算法的搜索能力,找出全局最优解。算例应用结 果验证了算法的有效性、科学性和实用性。
资源推荐
资源详情
资源评论
并行设计任务调度的遗传算法研究
张金标
(铜陵学院 机械工程系,安徽 铜陵
244000)
并行工程是对产品开发及其相关过程进行并行、一
体化设计的一种系统工作模式,其核心是并行设计。并行
设计要求在产品设计阶段就考虑市场需求、制造、装配、
维护、服务、环保等因素,集成、并行地设计产品,其目的
是缩短产品开发周期,进一步降低生产成本
[1-2]
。然而,这
种新的设计模式给产品设计过程带来更多的时序、信息、
资源等方面的约束,限制了设计任务的并行调度
[3]
。因此
有效地管理各种约束,合理地规划调度设计任务,是实现
并行设计目标的关键。许多研究者在这方面做了大量工
作,针对并行设计任务调度问题,文献[
4- 7]分别给出了
相应的启发式算法,虽算法简便但不易到全局最优解;文
献[
8- 11]结合启发式算法分别提出一种混合遗传算法,
具有并行性、全局性和自适应性,但它们或侧重于资源的
利用率,或强调时序关系,没有考虑时序关系、信息流动、
资源约束对任务调度的综合影响。
本文针对产品并行设计的特点,从任务调度的角度
提出了一种并行设计任务调度的遗传算法,该算法在满
足时序关系、信息流动和资源约束的前提下调度设计任
务,缩短并行设计过程,针对并行设计任务遗传算法易停
滞的问题,引入基因突变、种群突变等策略来解决。
1 并行设计任务分析模型
1.1 并行任务描述
产品并行设计过程是由多个设计任务组成的,这些
任务之间存在着复杂的关系,可以用任务偏序图来表示。
任务偏序图是用一个有向非循环图 (
Directed Acylic
Graph,DAG)表示任务
间的信息依赖和时序关
系的任务关系图,如图
1 所示。任务偏序图可
用四元组
G=(N,prest,
avert,r)来描述,其中:N
为任务集,N=(1,2,…,n),n 是产品并行设计过程的任务
总数;prest 是有向边集,表示任务间的顺序关系;avert 为
任务的平均执行时间集,
avert=(t
1
,t
2
,t
3
,…,t
n
);r 是设计资
源集,现代企业的设计资源主要是设计人员、计算机、网
络和相关软件。根据并行设计的要求,将设计人员及配备
的计算机软硬件划分成若干个设计小组,每个小组能独
自承担全部或部分设计任务,设计小组可以看成是能完
成一定设计任务的设计单元。因此
r 是单一元素的集合,
则 r={m},m 是设计单元数量。
1.2 基本定义
(1)用时序矩阵 prem 表示各设计任务的紧前任务状
况,将每个任务的紧前任务集合作为一个列向量从左至右
依次排列组成一个矩阵,行数表示最多的紧前任务数目,
不足行数的列以零补充。
prem 简便而有效地描述任务时
序关系,便于在计算机上实现
[12]
。图 1 的时序矩阵如下:
任务号
1 2 3 4 5 6 7 8 9 10 11
时序矩阵
0 1 1 1 1 2 3 4 4 7 8
0 0 0 0 0 0 4 0 5 8
! "
9
(2)用关联矩阵 A
n×n
表示任务之间的相关性,A 中的
摘 要:
在满足时序、资源许可的前提下优化调度产品并行设计过程,缩短产品上市时间已成为当前研究的一个重点。
针对并行设计特点建立了设计任务调度的目标函数,提出了一种遗传算法。该算法用矩阵式染色体表示设计任务与设
计单元之间的调度关系,采用突变机制来解决进化过程停滞问题,提高算法的搜索能力,找出全局最优解。算例应用结
果验证了算法的有效性、科学性和实用性。
关键词:
并行设计;任务调度;遗传算法;突变策略
中图分类号:TH122; TP391 文献标识码:A 文章编号:1002- 2333(2008)01- 0059- 04
Resear ch on Genetic Algorithms for Task Scheduling in Concurrent Design
ZHANG Jin- biao
(Dept. of Mechanical, Tongling College, Tongling 244000, China)
Abstract:It is one focus of recent research to how to model and schedule the design tasks of the concurrent design for
higher quality, lower cost and shorter time- to- market, according the design resources and time orders. A target model
of task scheduling is established to minimize the overall time of execution. A genetic algorithm for the task planning is
presented, in which, a matrix chromosome is used to show the distributed relations between the design tasks and the
design groups. A mutation strategy, which can avoid the prematurity, is founded to improve the optimizing capability for
optimal scheduling. An example is employed to illustrate the effectiveness of the prototype.
Key words:concurrent design; task scheduling; genetic algorithms; mutation strategy
1
2
3
4
6
5
7
8
9
10
11
图 1 任务偏序图
59
机械工程师 2008 年第 1 期
学术交流
理论 / 研发 / 设计 / 制造
ACADEMIC COMMUNICATION
资源评论
huaijinpuyu
- 粉丝: 0
- 资源: 3
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功