Given a set of $m$ tasks with a precedence constraint $P$ and a communication requirement $C$, where each task has execution time and a subcube requirement, the Hypercube Task Scheduling Problem (HTSP) is to find an assignment of tasks which minimizes the total completion time. In this paper, we show that HTSP and its many restricted versions are NP-hard. This motivates the development of heuristic algorithms for HTSP. We have developed four efficient heuristics for scheduling hypercube task graphs onto the hypercubes. We have tested these new heuristics and shown that for many practical problems the heuristics produce optimal and near optimal schedules.