  The problem of task scheduling with communication delays is strongly NP-hard.
State-space search algorithms such as A* have been shown to be a promising
approach to solving small to medium sized instances optimally. A recently
proposed state-space model for task scheduling, known as Allocation-Ordering
(AO), allows state-space search methods to be applied without the need for
previously necessary duplicate avoidance mechanisms, and resulted in
significantly improved A* performance. The property of a duplicate-free state
space also holds particular promise for memory limited search algorithms, such
as depth-first branch-and-bound (DFBnB), and parallel search algorithms. This
paper investigates and proposes such algorithms for the AO model and, for
comparison, the older Exhaustive List Scheduling (ELS) state-space model. Our
extensive evaluation shows that AO gives a clear advantage to DFBnB and allows
greater scalability for parallel search algorithms.
