In this paper, a new heuristic method called deadline
early tree (DET) is proposed for cost minimization with
deadline constraints. An early feasible schedule, defined
as early tree (ET), is constructed. According to ET, the
whole deadline is divided into activity deadlines
without destroying activity precedence constraints in
DAG. In addition, the workflow execution cost can be
better optimized in DET than in leveling methods by
fully taking into account the workflow total float.
The remainder of the paper is structured as follows.
Section 2 formulates the scheduling problem. An early
feasible schedule and its related definitions are
introduced in Section 3. Section 4 describes the
proposed algorithm DET. In Section 5, experimental
results are given followed by conclusions in Section 6