訂單排序模型及其最優性研究

《訂單排序模型及其最優性研究》是依託湖南師範大學，由李榮珩擔任項目負責人的面上項目。

基本介紹

• 中文名：訂單排序模型及其最優性研究
• 項目類別：面上項目
• 項目負責人：李榮珩
• 依託單位：湖南師範大學

項目摘要

訂單排序問題是工件客戶向機器代理以訂單方式提出加工請求，機器代理方根據訂單參數確定加工策略。本課題將深入研究訂單排序模型的建立、組合結構特性分析、算法設計及算法性能的理論分析和模擬驗證。 (1) 模型方面，考慮機器方依據訂單模式建立回應時間策略，引入影響工件參數費用函式(如人力、資金等費用)及機器費用，建立訂單的接受或拒絕決策機制，考慮訂單系統內各方代理的協作或競爭方式,研究多方代理的博弈模式。(2) 以代數結構理論方法分析一些特殊訂單排序的組合結構特性，基於這種代數組合特性來探討複雜性理論。(3) 設計高性能算法並進行理論分析和模擬驗證，分析效益函式性質對排序決策的靈敏性。本課題的目的是為解決實際問題提供理論依據和技術上的指導性方案。

結題摘要

本項目研究的問題具有廣泛的實際套用背景並且在組合最佳化領域具有重要的理論價值。根據項目計畫，我們主要研究有：1. 對於在ｍ台平行機上工件有單調非減的到達時間和單調非增的加工時間的半線上排序問題，目標函式是最小化最大完工時間時，證明 了3/2-1/2m為LS算法的最壞性能比,並猜想緊界為4/3-1/3m，也研究了LPT算法在工件具有相似加工時間的最壞性能比，得到部分緊界結果。2. 研究了m台相同平行機上工件有預約到達時間，目標函式為最小化最大完工時間的ordinal半線上排序問題，給出了近似算法，並證明了近似算法的最壞性能比的上界。3. 研究了一致平行機上訂單排序的問題，分別給出了最壞性能比為12和7.461的近似算法。4. 對機器和工件多方代理都有自私性的博弈排序問題，我們考慮了雙向納什均衡的POA(Price of Anarchy)，給出並證明了兩台機上當工件有相似加工長度時的緊界，此緊界是關於相似度的一個很複雜的分段線性函式。當機器台數m大於2 且小於10時的緊界是4/3. 當機器台數大或等於10時，我們給出了比現有界更緊的界。5. 通過對組合結構性質的研究，對布爾可滿足性問題(SAT)引入了一類可分離 SAT 問題,即 3-正則可分離可滿足性問題(3-RSSAT),證明了 3-RSSAT 是 NP 完全問題,給出了一般 SAT 問題 3-正則可分離性的 O(1.890^n)判定算法. 然後,利用矩陣相乘算法的研究成果,給出了 3-RSSAT 問題的 O(1.890^n)精確算法,該算法與子句長度無關. 6. 研究了進化算法收斂性問題，我們假定適應值函式為非單射的，藉助於 Markov 鏈，通過對狀態空間的合理劃分和狀態的適當排序，獲得了多基因系統中變異運算元的良好性質．基於所建立的一般性 Markov 模型和轉移矩陣的結構特徵，分別在兩種衡量方式下證明了算法呈現指數級收斂速度，其估計式無需對變異率額外施加條件．