平行机排序问题的新模型和新算法研究

本项目主要研究平行机排序问题中若干新模型与新算法。着重考虑半在线算法，在线问题的资源增广研究，机器有特殊性质的排序问题，实时在线问题等有重要应用价值和理论意义的问题以及研究随机算法在排序中的应用。对其中的在线和半在线问题，用竞争比分析法研究近似算法的竞争比和问题的下界，希望得到该问题的最好算法。对离线问题，设计该问题的多项式时间近似方案，或者给出具有较好近似性能的快速实用算法，或者证明其不可近似性。