《若干新型排序算法與計算複雜性研究》是依託瀋陽航空航天大學，由王吉波擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：若干新型排序算法與計算複雜性研究
- 項目類別：青年科學基金項目
- 項目負責人：王吉波
- 依託單位：瀋陽航空航天大學
項目摘要,結題摘要,
項目摘要
在經典排序中，通常假設工件的加工時間為常數，但在許多實際問題中,工件的加工時間可能與其開工時間和（或）所排位置有著某種聯繫，由此產生一些新型排序問題。這些問題在鋼鐵工業及醫療等方面有著廣泛的套用，是當今國際研究的熱點問題之一。本課題將深入研究工件加工時間可變的新型排序，主要有：(1)工件加工時間與開工時間有關的排序，研究其中的若干未解決問題和更複雜實用的目標函式；(2)工件加工時間與所排位置有關的問題，研究其中的若干未解決問題和更複雜實用的目標函式；(3)建立更符合實際的新模型，分析模型的計算複雜性和算法。(4)將研究成果套用到實際問題中，來檢驗算法的可行性。這些新型排序比經典排序更為實用，也更為複雜，絕大多數都是NP-難的，將通過探討可行排序或最優排序的局部及整體性質和數量關係，建立系統有效的計算方法和基本理論。本研究預計將在計算複雜性分析、算法設計及模型建立等方面做出創新性的研究成果
結題摘要
工件加工時間可變的排序問題在鋼鐵工業及醫療等方面有著廣泛的套用，是當今國際研究的熱點問題之一。本項目研究成果主要包括三方面內容：（1）工件的加工時間與開工時間有關的排序（惡化工件）；(2)工件加工時間與所排位置有關的問題（學習效應）；(3) 工件加工時間同時具有學習效應、惡化效應和（或）資源分配的排序問題。 在第一方面，對多台機器的流水作業排序問題，目標函式為最大完工時間、總完工時間與加權總完工時間分別提出了分支定界算法和啟發式算法；對單機情況，工件具有共同鬆弛工期問題給出了一個多項式時間最優算法。 在第二方面，研究多台機器的流水作業排序問題，對幾個正則目標函式分別提出了近似算法和啟發式算法；提出了工件加工時間具有一般學校效應的排序模型，即工件加工時間即與所排位置有關，又與之前完成的工件有關，對一些正則目標函式分別給出了多項式時間最優算法。 在第三方面，提出了工件加工時間與開工時間、所排位置和所用資源都有關係的排序模型，對一些正則目標函式分別給出了多項式時間最優算法。研究了工件加工時間同時具有學習效應和惡化效應的排序問題，取得了一系列成果。
