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

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

排序论是运筹学和组合最优化领域极为活跃的研究分支。多目标排序则包含了丰富的经典及新兴排序模型，例如：在线排序、分批排序、具有前瞻区间的排序、多代理排序等等。本项目“基于调度管理与客户利益之间平衡的排序问题”实际上是研究若干具有经济背景的多目标排序问题。这里我们研究了若干多目标排序的在线算法及离线情形的计算复杂性与近似算法。研究成果分类如下：在线算法研究发表论文13篇、多目标排序研究发表论文11篇、算法的复杂性分析发表论文9篇、具有前瞻区间的半在线排序研究发表论文5篇。 受本项目资助共发表学术论文38篇，其中33篇论文发表在国际SCI期刊上。本项目的代表性成果如下：（1）研究了带有前瞻区间、不相容工件组、批容量无界的平行批在线排序问题。当工件组个数 f 已知时，给出了最好可能的在线算法；（2）研究了具有前瞻区间的单位工件在 m 台批处理机器上的在线排序问题, 给出了若干情形的最好可能的在线算法；（3）研究了单机有界分批列表在线排序问题，给出了较好的在线算法；（4）研究了两台恒同机上具有链组约束的在线排序问题，给出了竞争比是1.3028的最好可能的在线算法；（5）研究了单机上两代理最小化最大延迟排序问题，给出了Pareto最优解；（6）研究了带有不相容工件组两代理无界分批Pareto最优排序问题，目标是最小化最大时间和最大延迟，给出了当工件组的个数已知时的多项式时间算法。