传统任务分配问题是以最小化计算代价和处理器间通信代价之和为研究目标的。然而,随着计算机硬件获得巨大的性能提升,多核处理器成为主流,传统任务分配理论面临前所未有的巨大挑战。在由多核处理器构建的集群环境中,不仅需要考虑计算节点间通信,还需要考虑计算节点内通信(处理器间通信和核间通信)。研究表明,NAS基准测试平台中超过50%的消息是通过计算节点内通信完成的。在此背景下,本文提出了多核环境任务分配问题,目标是最小化计算代价,计算节点间通信代价和计算节点内通信代价(包括处理器间通信代价和核间通信代价)。多核环境任务分配问题的研究面临两方面的重大挑战。挑战之一,传统任务分配问题是NP-hard问题,多核任务分配问题与之相比更为复杂,但是该新问题一定也是NP-hard问题吗?在多核集群环境下,随着核数越来越多,节点内通信代价也越来越大,通信代价的量变会不会导致质变?也就是说通信代价的变化会不会导致问题复杂性发生本质的变化,即使得NP-hard问题变为P问题?这些问题是算法复杂性研究的难点,具有重要的理论意义和实际意义。挑战之二,在传统任务分配问题的精确求解模型研究中,最好的结果是通过数学规划方法得到的。在多核任务分配问题研究中,如何使用数学规划方法建立高效的精确求解模型?本文研究正是围绕这两个挑战性问题展开的,在以下三个方面做出了重要贡献。首先,本文研究了多核环境任务分配问题的复杂性。首次证明了多核环境下新的任务分配问题是NP-hard问题,即使在任务通信图是二部图并且是平面图时,该结论依然成立。其次,本文使用最小费用流理论定量分析了通信代价的变化对问题复杂性的影响。得出的结论是,多核环境任务分配问题的复杂性是由通信代价决定的,并且随着节点内通信代价持续增大到一定程度,会使原来的NP-hard问题变为P问题。最后,本文建立了多核环境任务分配问题的0-1整数二次规划模型,并提出了两种线性松弛策略,为进一步设计高效的模型求解算法打下了坚实的基础。