《基於調度管理與客戶利益之間平衡的排序問題》是依託鄭州大學，由李文華擔任項目負責人的面上項目。
基本介紹
- 中文名：基於調度管理與客戶利益之間平衡的排序問題
- 項目類別：面上項目
- 項目負責人：李文華
- 依託單位：鄭州大學
項目摘要,結題摘要,
項目摘要
排序模型通常是從調度管理的角度考慮某個指標的最優，如最小化時間表長（即占用機器的最大時間）。實際中常需考慮顧客的利益，如顧客在排序系統的時間或總等待時間要求最小化等等。本項目首次提出並將深入研究來源於現代實踐中的考慮調度管理與客戶利益之間平衡的一系列排序新模型，主要解決三方面問題：一是考慮調度管理和顧客利益雙方平衡的分層多目標排序問題，對離線情形進行複雜性分析，並給出最優算法或近似算法。二是考慮雙方平衡的同級多目標排序問題，對離線情形研究Pareto最優解或近似解。三是對只考慮顧客利益的線上和半線上模型，給出競爭比分析。這三類問題包含了豐富的排序模型。不考慮雙方平衡的多目標排序問題已有文獻研究過若干模型，而顧客利益線上排序問題從未見過並有相當的難度。申請者的博士論文研究了分層多目標排序的若干模型，近期又對上述第三個問題有較系統的研究。本項目對上述模型進行深入研究，並將獲得一系列創新成果。
結題摘要
排序論是運籌學和組合最最佳化領域極為活躍的研究分支。多目標排序則包含了豐富的經典及新興排序模型，例如：線上排序、分批排序、具有前瞻區間的排序、多代理排序等等。本項目“基於調度管理與客戶利益之間平衡的排序問題”實際上是研究若干具有經濟背景的多目標排序問題。這裡我們研究了若干多目標排序的線上算法及離線情形的計算複雜性與近似算法。研究成果分類如下：線上算法研究發表論文13篇、多目標排序研究發表論文11篇、算法的複雜性分析發表論文9篇、具有前瞻區間的半線上排序研究發表論文5篇。 受本項目資助共發表學術論文38篇，其中33篇論文發表在國際SCI期刊上。本項目的代表性成果如下：（1）研究了帶有前瞻區間、不相容工件組、批容量無界的平行批線上排序問題。當工件組個數 f 已知時，給出了最好可能的線上算法；（2）研究了具有前瞻區間的單位工件在 m 台批處理機器上的線上排序問題, 給出了若干情形的最好可能的線上算法；（3）研究了單機有界分批列表線上排序問題，給出了較好的線上算法；（4）研究了兩台恆同機上具有鏈組約束的線上排序問題，給出了競爭比是1.3028的最好可能的線上算法；（5）研究了單機上兩代理最小化最大延遲排序問題，給出了Pareto最優解；（6）研究了帶有不相容工件組兩代理無界分批Pareto最優排序問題，目標是最小化最大時間和最大延遲，給出了當工件組的個數已知時的多項式時間算法。
