可中断排序相关问题研究及前沿应用

随着可中断排序问题的深入研究，与可中断排序密切相关的新问题也不断的涌现。本项目主要研究可中断排序的相关问题以及前沿问题的可中断算法设计，包括利用最优可中断在线算法研究不可中断排序，机器带特殊性质时机器空闲对可中断算法设计的影响，可中断算法与随机下界、随机算法的关系，可中断次数受限和带中断惩罚费用的排序问题以及可中断算法在CPU能耗管理中的应用。对离线问题，研究其计算复杂性，设计最坏情况界尽可能小的近似算法或近似方案。对（半）在线问题，用竞争比分析给出问题的下界和设计在线算法。通过本项目对可中断排序更为深入的理论研究和相关问题的算法设计与应用研究，在理论上进一步丰富和完善了排序问题的研究内容和算法设计与分析的技巧，在实际中进一步拓展排序理论的应用领域，具有一定的理论意义和应用价值。

可中断算法的设计与分析是排序理论研究中一个重要的研究方向，不仅在理论研究中有着重要的研究价值，在很多实际问题中也有着很强的应用背景。本项目主要研究可中断排序相关的一些基础问题，若干新型排序问题的可中断算法设计与分析以及可中断算法的应用。通过研究带服务等级平行机排序问题和带机器费用问题的不可中断与可中断情形来探讨可中断与不可中断在算法设计上的联系与区别。对一些新型的排序问题，如带装载服务器的平行机排序问题，在不可能中断情况下为NP问题，我们讨论了该问题的可中断情形，给出了一个4/3的近似算法，该算法在两种特殊情形能给出最优解，该问题在可中断情况下是否为NP难仍未知。对于中断次数受限的平行机排序问题，主要研究在有限次中断情况下最优解值与无限制情况下最优解值的最坏情况比。我们给出了一套新的处理方法，该方法比原有的结果更加简单有效且易于推广，同时能给出该问题一般情况下的近似算法，该算法能保证所得的最坏情况界。对于该问题，我们分别考虑了同型机与同类机上极小化最大完工时间和极大化最小完工时间两个目标函数。此外，我们还通过可中断算法的思想和技巧研究了若干不可中断情形的平行机排序和混合流水作业问题。分别对上述问题给出了算法复杂性证明，性能比更好的改进算法和最优参数界算法。以上大部分成果在本领域重要期刊和国际会议上发表，其中SCI检索论文6篇，EI检索论文4篇。通过上述问题的研究，在解决具体问题的同时为排序理论的研究提供新问题、新思路和新方法，同时也对一些实际问题提供了理论和技术支持。