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

摘要： 网格计算是网络并行计算的发展新趋势，网格系统中的分布式资源管理和调度一直是研究的热点和难点。对于网格应用作业的多资源调度问题，一个网格作业往往要分成多步骤进行，每个步骤都需要占用多个资源。首先将该问题抽象为典型的多处理机任务调度模型P_m|fix，p=1，chain|C_max，即在m个处理机系统中调度n个多处理机任务，每个任务指派到所需一组处理机上不可剥夺地执行，而且每个任务都需要一个单位的处理时间，并根据优先关系形成链约束。该问题被证明为NP难问题。利用宽度优先技术和首次满足方法，构建了几个多项式时间近似算法，并通过模拟实验分析算法性能，实验结果显示算法是实用的。

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