若干在线排序问题高性能算法及其应用研究

本项目主要研究如下两类排序问题: 一是lp范数下在线（可中断）排序问题算法研究，将首先针对3台同型机和恒速机可中断在线排序设计最优或具有较好竞争比的在线算法，然后将其推广到一般情形即m台同型机和恒速机情形,其次考虑推广到并行工件，对Pm/sizej,online/lp问题设计最优或具有较好竞争比的在线算法.另一是研究来源于炼钢－连铸生产中的动态调度问题。动态调度方法是钢铁企业的关键核心技术之一，本项目将根据钢铁生产的复杂性，动态性及生产的连续性建立能全面反映其生产过程中的各种动态因素的数学模型，并在此基础上形成新的排序模型，利用组合优化、约束规划等技巧给出高性能的实用算法。这使得本项目不仅具有重要的理论意义（涉及算法和排序理论核心），丰富排序理论，同时又具有很强的实际应用性，为实际生产调度提供算法支持。

本项目主要研究排序问题的高性能算法，主要对lp范数下的若干排序问题和来源于流程工业的调度问题进行研究，同时也对对光纤通信、无线通信网络和光子晶体结构等中的优化设计问题进行了研究。首先，对排序问题，针对lp范数下的在线排序问题，我们对2、3台平行机(可中断，在线，半在线等情形)排序问题设计了相应的在线算法并分析了其性能比。针对lp范数下的并行工件排序，我们对LS算法进行了分析，对2台机器的若干半在线模型得到了LS算法的竞争比和问题的算法竞争比下界，并对m台平行机情形设计了改进算法，分析了算法的竞争比，同时对已知工件最大加工时间的m台半在线排序问题设计了半在线算法并分析了竞争比。针对一类炼钢连铸调度问题建立了相应的数学模型并给出了一个启发式算法，对一类混合流水作业调度问题设计了基于模拟退火的启发式方法，仿真结果表明了算法的有效性。其次，研究了光网络中的组播路由与波长分配问题，无线传感器网络中的虚拟骨干网构造问题，设计了相应的近似算法，分析了算法的近似比。最后，对光子晶体优化设计进行了研究，得到了若干有趣的结果。这些结果将为进一步展开相关研究提供基础，丰富相应领域的模型和成果。