|
资源受限单机动态调度的并行GA算法研究
A Parallel Genetic Algorithm for a Single-Machine Dynamic Scheduling Problem with Resource-Constraints
查看参考文献8篇
文摘
|
研究资源受限系统动态调度问题,针对时序约束问题提出一种并行遗传算法(PGA).给出满足排序优先次序约束的一种基因编码方法;采用不破坏优先级可行性的交叉操作,并予以证明;建立一种并行处理机制,使搜索避免出现局优现象.在技术允许情况下,单机动态调度引入抢占式加工方式,会一定程度上提高系统的性能.通过仿真试验验证,并行GA算法可兼顾优化效果和计算效率,解决单机动态调度问题. |
其他语种文摘
|
We consider the resource-constrained dynamic scheduling problem. Traditional genetic algorithms (GA) often meet the occurrence of slow convergence. We introduce the parallel search mechanism into genetic algorithms to avoid the shortage above-mentioned. Parallel genetic algorithm (PGA) is proposed for solving sequence-constrained problems. We adopt the permutation-based coding with satisfaction of priority requirements. An individual chromosome is given by an activity sequence. The crossover operator is customized by the research project. We also prove that the crossover operator results in a precedence feasible offspring genotype if applied to precedence feasible parent individuals. With the technological permission, single-machine preemptive scheduling will improve the performance of scheduling system. Simulation results show that our parallel genetic algorithm gains excellent effectiveness and efficiency for single-machine dynamic scheduling. |
来源
|
系统仿真学报
,2005,17(4):827-830 【核心库】
|
关键词
|
资源受限
;
遗传算法
;
单机动态调度
;
平均拖期
;
抢占式调度
|
地址
|
中国科学院沈阳自动化所, 辽宁, 沈阳, 110016
|
语种
|
中文 |
文献类型
|
研究性论文 |
ISSN
|
1004-731X |
学科
|
自动化技术、计算机技术 |
基金
|
国家973计划
;
国家“十五”科技攻关重点项目
|
文献收藏号
|
CSCD:2025671
|
参考文献 共
8
共1页
|
1.
Andreas S Schulz. Martin Skutella The power of -points in preemptive single machine scheduling [J].
Journal of Scheduling,2002,5:121-133
|
被引
1
次
|
|
|
|
2.
王万良. 基于遗传算法的混合Flow-shop调度方法.
系统仿真学报,2002,14(2):863-865
|
被引
27
次
|
|
|
|
3.
Sonke Hartmann. A Competitive Genetic Algorithm for Resource- Constrained Project Scheduling [J].
Naval Research Logistics,1998,45:733-750
|
被引
37
次
|
|
|
|
4.
玄光南. 遗传算法与工程设计[M].
遗传算法与工程设计,2000
|
被引
40
次
|
|
|
|
5.
Miyashita K. Job-Shop Scheduling with Genetic Programming [A].
Proceeding of the Genetic and Evolutionary Computation Conference (GECCO),2000:505-512
|
被引
1
次
|
|
|
|
6.
何霆. 车间生产调度问题研究.
机械工程学报,2000,36(5):97-102
|
被引
24
次
|
|
|
|
7.
孙志峻. 智能制造系统车间生产优化调度[D].
智能制造系统车间生产优化调度[博士学位论文],2002
|
被引
1
次
|
|
|
|
8.
刘民. 带特殊工艺约束的并行机器生产线调度问题的一种遗传算法.
自动化学报,2001,27(3):381-386
|
被引
7
次
|
|
|
|
|
|