若干線上排序問題高性能算法及其套用研究

《若干線上排序問題高性能算法及其套用研究》是依託北京郵電大學，由帥天平擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：若干線上排序問題高性能算法及其套用研究
• 項目類別：青年科學基金項目
• 項目負責人：帥天平
• 依託單位：北京郵電大學

項目摘要

本項目主要研究如下兩類排序問題: 一是lp範數下線上（可中斷）排序問題算法研究，將首先針對3台同型機和恆速機可中斷線上排序設計最優或具有較好競爭比的線上算法，然後將其推廣到一般情形即m台同型機和恆速機情形,其次考慮推廣到並行工件，對Pm/sizej,online/lp問題設計最優或具有較好競爭比的線上算法.另一是研究來源於煉鋼－連鑄生產中的動態調度問題。動態調度方法是鋼鐵企業的關鍵核心技術之一，本項目將根據鋼鐵生產的複雜性，動態性及生產的連續性建立能全面反映其生產過程中的各種動態因素的數學模型，並在此基礎上形成新的排序模型，利用組合最佳化、約束規劃等技巧給出高性能的實用算法。這使得本項目不僅具有重要的理論意義（涉及算法和排序理論核心），豐富排序理論，同時又具有很強的實際套用性，為實際生產調度提供算法支持。

結題摘要

本項目主要研究排序問題的高性能算法，主要對lp範數下的若干排序問題和來源於流程工業的調度問題進行研究，同時也對對光纖通信、無線通信網路和光子晶體結構等中的最佳化設計問題進行了研究。首先，對排序問題，針對lp範數下的線上排序問題，我們對2、3台平行機(可中斷，線上，半線上等情形)排序問題設計了相應的線上算法並分析了其性能比。針對lp範數下的並行工件排序，我們對LS算法進行了分析，對2台機器的若干半線上模型得到了LS算法的競爭比和問題的算法競爭比下界，並對m台平行機情形設計了改進算法，分析了算法的競爭比，同時對已知工件最大加工時間的m台半線上排序問題設計了半線上算法並分析了競爭比。針對一類煉鋼連鑄調度問題建立了相應的數學模型並給出了一個啟發式算法，對一類混合流水作業調度問題設計了基於模擬退火的啟發式方法，仿真結果表明了算法的有效性。其次，研究了光網路中的組播路由與波長分配問題，無線感測器網路中的虛擬骨幹網構造問題，設計了相應的近似算法，分析了算法的近似比。最後，對光子晶體最佳化設計進行了研究，得到了若干有趣的結果。這些結果將為進一步展開相關研究提供基礎，豐富相應領域的模型和成果。