b9000A

We consider the problem of scheduling a set of tasks whose precedence relation is representable as a directed forest, on two identical machines, in order to minimize the total completion time. A new heuristic algorithm is presented which provides a 14 approximate solution. This algorithm is based on the idea of critical jobs, where a job is a set of tasks corresponding to a maximal tree in the forest. A critical job is one whose total duration exceeds the total duration of all other jobs. In the paper, first a 14 approximate algorithm for the case in which no job is critical is presented, then this algorithm is extended to the general case. The 14 approximate bound is proved to be tight. The complexity of the proposed algorithm is studied.