排序若干新問題的算法設計與分析

《排序若干新問題的算法設計與分析》是依託浙江大學，由談之奕擔任項目負責人的面上項目。

基本介紹

• 中文名：排序若干新問題的算法設計與分析
• 依託單位：浙江大學
• 項目負責人：談之奕
• 項目類別：面上項目
• 批准號：10671177
• 申請代碼：A0406
• 負責人職稱：教授
• 研究期限：2007-01-01 至 2009-12-31
• 支持經費：24（萬元）

項目摘要

排序理論是運籌學組合最最佳化領域中研究最為活躍的分支之一。本項目將深入研究來源於生產計畫調度，物流和供應鏈管理等實踐中的幾類排序新問題，例如，帶不精確信息的半線上排序，有一個或多個參數的半線上排序，多階段集成排序問題，複雜機器環境下的排序問題等等，每一類問題都包含了豐富的排序模型。對其中的離線情形，本項目將探討它們的計算複雜性、（完全）多項式時間近似方案的存在性或難近似性，以及快速近似算法的設計；對其中的線上、半線上情形，本項目將探討如何設計具有最好可能競爭比的算法，這些都是組合最最佳化問題的核心研究內容。對上述幾類排序新問題，國際上的研究剛剛起步或起步不久，有較大難度。本項目將對它們進行前瞻性研究，獲得創新性成果。