
Scheduling Problems in a Practical Allocation Model Lisa Hollermann, Tsansheng Hsu, Dian Lopez, Keith Vertanen Journal of Combinatorial Optimization, 1997. A parallel computational model is defined which addresses I/O contention, latency, and pipelined message passing between tasks allocated to different processors. The model can be used for parallel taskallocation on either a network of workstations or on a multistage interconnected parallel machine. To study performance bounds more closely, basic properties are developed for when the precedence constraints form a directed tree. It is shown that the problem of optimally scheduling a directed onelevel precedence tree on an unlimited number of identical processors in this model is NPhard. The problem of scheduling a directed twolevel precedence tree is also shown to be NPhard even when the system latency is zero.
An approximation algorithm is then presented for scheduling directed onelevel task trees on an unlimited number of processors with an approximation ratio of 3. Simulation results show that this algorithm is, in fact, much faster than its worstcase performance bound. Better simulation results are obtained by improving our approximation algorithm using heuristics. Restricting the problem to the case of equal task execution times, a lineartime algorithm is presented to find an optimal schedule.
