Many NP-hard scheduling problems are so difficult that heuristics are employed even for small problem instances. Scheduling tasks graphs with communication delays on a set of processors, P|prec,c_ij|C_max, is such a problem. Nevertheless, for time-critical systems or for the evaluation of heuristics it is crucial to obtain optimal solutions. In this presentation two approaches to optimally scheduling P|prec,c_ij|C_max are studied. The first is based on an Integer Linear Programming (ILP) approach. To achieve a good ILP formulation it is crucial to have an efficient conversion of the bilinear constraints that arise from the consideration of the communication delays. The second approach is based on A*, a best first search algorithm. The focus of the A* scheduling algorithm discuss will be on novel pruning techniques.