基于调度管理与客户利益之间平衡的排序问题

项目名称： 基于调度管理与客户利益之间平衡的排序问题

项目编号： No.11171313

项目类型： 面上项目

立项/批准年度： 2012

项目学科： 数理科学和化学

项目作者： 李文华

作者单位： 郑州大学

项目金额： 42万元

中文摘要： 排序模型通常是从调度管理的角度考虑某个指标的最优，如最小化时间表长（即占用机器的最大时间）。实际中常需考虑顾客的利益，如顾客在排序系统的时间或总等待时间要求最小化等等。本项目首次提出并将深入研究来源于现代实践中的考虑调度管理与客户利益之间平衡的一系列排序新模型，主要解决三方面问题：一是考虑调度管理和顾客利益双方平衡的分层多目标排序问题，对离线情形进行复杂性分析，并给出最优算法或近似算法。二是考虑双方平衡的同级多目标排序问题，对离线情形研究Pareto最优解或近似解。三是对只考虑顾客利益的在线和半在线模型，给出竞争比分析。这三类问题包含了丰富的排序模型。不考虑双方平衡的多目标排序问题已有文献研究过若干模型，而顾客利益在线排序问题从未见过并有相当的难度。申请者的博士论文研究了分层多目标排序的若干模型，近期又对上述第三个问题有较系统的研究。本项目对上述模型进行深入研究，并将获得一系列创新成果。

中文关键词： 排序；复杂性分析；Pareto 最优性；近似算法；在线算法

英文摘要：

英文关键词： scheduling；complexity analysis；Pareto optimization；approximation algorithm；online algorithm