Article Preview
Top1. Introduction
Process scheduling in a multiprocessor environment refers to the assignment of tasks to different processors, satisfying a given set of constraints, so that the schedule length or overall task completion time is minimized. A process (or an application) consists a set of interdependent tasks and may be represented by a directed acyclic graph (DAG), 
where the set of nodes V, represents the set of tasks, and the set of edges E, represents the communication between tasks. If 
then 
is called the immediate predecessor of 
, and 
is called the immediate successor of 
. Given a task 
its set of immediate predecessors, denoted by 
is defined as
. If 
has two or more immediate predecessors then 
is referred to as a join task. The immediate successors of 
is denoted by 
and is defined as 
. 
is the set of all the descendants of task
, and is defined as
. It is assumed that there is one entry task 
and one exit task 
for the DAG.
In both homogeneous and heterogeneous environments the process scheduling problem is NP-complete (Garey & Johnson, 1979; Graham, Lawler, Lenstra, & Kan, 1979; Kasahara & Narita, 1984; Ullman, 1975). In homogeneous environments several heuristics were proposed using both list scheduling without task duplication (Ahmad & Kwok, 1996; Wu & Gajski, 1990) and list scheduling using task duplication (Ahmad & Kwok, 1998; Bansal, Kumar & Singh, 2003; Chaudhuri & Elcock, 2005; Park & Choe, 2002). In list scheduling, tasks are assigned a priority and based on that priority a task is scheduled. In task duplication, some tasks are deliberately scheduled on more than one processor to reduce inter-processor communication.