摘要
研究三个并行处理器环境中,具有递减链约束的多处理器任务的调度问题,调度目标是最小化总处理时间,假设单项任务需单位处理时间.首先给出了减链调度问题的最优化性质与条件,并说明了减链调度问题仍然是NP难的.随后基于两段flow-shop问题的Johnson's算法的修正和减链调度问题最优化性质,提出了一个启发式算法,并从分析和仿真计算两方面说明该算法是有效的和高效的.
This paper focuses on scheduling unit length multiprocessor tasks with decreasing chain precedence constrains on three identical processors so as to minimize makespan. First, a few properties for optimally scheduling decreasing chains are given. However, that optimally solving the problem is NP-hard is illustrated. Then, a heuristic algorithm is proposed which is based on a revision of well-known Johnson's algorithm for two-stage flow-shop problem and the optimal properties for scheduling decreasing chains. Finally, simulation illustrates that the heuristic algorithm is effective and efficient.
出处
《自动化学报》
EI
CSCD
北大核心
2004年第4期583-587,共5页
Acta Automatica Sinica
基金
国家自然科学基金(60174009)
西安交通大学机械制造系统工程国家重点实验室开放基金资助~~
关键词
调度
多处理器任务
前提约束
启发算法
Computational complexity
Computer simulation
Constraint theory
Heuristic methods
Multitasking
Optimization
Scheduling
