关键词: 网格计算, 调度, 多处理机任务, 近似算法, 优先性约束

Abstract: This paper is concerned with a new model in deterministic scheduling theory，where certain tasks may require more than one processor at a time.This model is motivated by multiprocessor systems such as grid applications and it has received much attention recently.In the paper it is assumed that each task can be processed on some processor subset and preemption is not allowed in the scheduling.All task have unit processing times and constraints form a set of chains.This problem denoted by P_m|fix，p=1，chain|C_max is proved to be NP-hard.Several very simple and practical polynomial time approximation algorithms are constructed by using the First Fit（FF） and the Width First（WF） technique.Due to the conducted experimental results，it is concluded that the algorithms can perform well in practice.

Key words: grid computation, scheduling, multiprocessor task, approximation algorithm, precedence constraint