An exact scheduling algorithm for two, linear-nonlinear clusters, with a common communication delay

In parallel and distributed processing, tasks are ordinarily clustered and assigned to different processors before they are scheduled. The assignment of tasks to processors is called clustering. Within each cluster, the ordering of tasks for execution, including the specification of the starting time of each task, is called clustering schedule. The set of tasks is typically modelled as a directed acyclic task graph, capturing the partial order relationship among the tasks. As a result of the clustering process, with respect to the DAG, the set of tasks in each cluster either forms a total ordering or it doesn't. A cluster is called linear if the tasks in it are totally ordered, otherwise it is called nonlinear. Due to inter-processor communication delay, when T ₁ ≺ T ₂ and T ₁ and T ₂ are processed by different processors, the execution of T ₂ cannot start right away once T ₁ finishes and it must wait τ steps, τ is called communication delay. It has been shown that the problem of finding an optimal schedule for two clusters with one cluster being linear and the other nonlinear with a common communication delay is strongly NP-hard. In this paper, we develop an exact, polynomial time algorithm to solve the above problem when tasks are restricted to unit tasks.