具有服務等級的平行機線上排序問題研究

《具有服務等級的平行機線上排序問題研究》是依託南京農業大學，由侯麗英擔任項目負責人的數學天元基金項目。

基本介紹

• 中文名：具有服務等級的平行機線上排序問題研究
• 項目負責人：侯麗英
• 依託單位：南京農業大學
• 項目類別：數學天元基金項目

項目摘要

本項目主要研究具有服務等級的平行機線上排序問題。首先，研究具有服務等級的同類機線上機器負載平衡問題；其次，考慮目標為最小化最大完工時間的具有服務等級的同類機線上排序問題；最後，討論具有服務等級的同型機按時線上排序問題。對這些問題，分別設計有效的線上算法，從而可以為管理者提供更有效的生產服務策略。

結題摘要

排序問題是運籌學與組合最佳化領域內的一類重要問題，對排序理論的研究具有重要的理論意義和廣闊的實際套用前景。本項目主要研究具有服務等級的線上排序及其相關問題。首先，我們考慮了具有服務等級的兩台同型機實時線上排序問題，給出了競爭比為7/4的線上算法。其次，我們研究了工件帶有拒絕費用的三台同類機線上排序問題，提出了具有參數競爭比的線上算法。最後，我們討論了工件帶有拒絕費用的m台同型機線上排序問題並設計了線上算法，該算法的競爭比也為參數競爭比。