Scheduling Problems in a Practical Allocation Model

A parallel computational model is defined which addresses I/O contention,latency, and pipe-lined message passing between tasks allocated to differentprocessors. The model can be used for parallel task-allocation on either anetwork of workstations or on a multi-stage inter-connected parallel machine.To study performance bounds more closely, basic properties are developed forwhen the precedence constraints form a directed tree. It is shown that theproblem of optimally scheduling a directed one-level precedence tree on anunlimited number of identical processors in this model is NP-hard. Theproblem of scheduling a directed two-level precedence tree is also shown tobe NP-hard even when the system latency is zero. An approximation algorithm is then presented for scheduling directedone-level task trees on an unlimited number of processors with anapproximation ratio of 3. Simulation results show that this algorithm is, infact, much faster than its worst-case performance bound. Better simulationresults are obtained by improving our approximation algorithm usingheusistics. Restricting the problem to the case of equal task executiontimes, a linear-time algorithm is presented to find an optimal schedule.