平行机排序及相关问题研究

本项目讨论了一系列平行机排序问题。对经典平行排序问题，解决了一些著名近似算法的紧界估计；利用对偶的思想设计出一些复合型近似算法，它们用来求解相应排序问题，既有很低的时间复杂性，又有很好的的似性能比。对带机器准备时间的平行机排序问题，首次发现了非积极机器的存在性；给出了几个经典贪婪算法在不同目标下的紧界估计。研究了在线半在线排序问题，对一些新提出的半在线排序模型，给出了各自的最好在线近似算法。探讨了工件可拒绝加工的平行机排序问题，对两台同类机在线模型，给出了一个近似优算法。此外，对随机算法，排序相关问题如分划问题、约束最短网络问题等进行了一些研究。发表论文有9篇被SCI检索。