多代理排序和在线排序研究

本书研究多代理排序问题。排序问题在工作和生活中经常遇到，因此本书的研究内容非常实用，排序就是分配一定的资源到给定时间区间去完成某些任务,使得一个指标或多个指标达到很优。多代理排序和在线排序是排序论的两个重要研究领域。本书主要研究了平行批处理机上两个代理的机器排序问题；工件可拒绝的两个代理的单机排序问题；机器具有维修区间的两个代理的排序问题；目标函数为加权和的两个代理的排序问题；具有非交叉维修时间的平行机在线排序问题。对上述问题分别研究了它们的计算复杂性和（拟）多项式算法或近似算法；对于在线排序问题，给出问题的下界和在线算法的上界。

本书主要研究了单机多代理排序问题和带有禁用区间的在线排序问题，主要研究内容如下： 在第2章中，给出了多代理排序的概念、特征，并介绍了常见单机多代理排序问题的模型以及求解多代理排序问题的方法。 在第3章中，给出了多个代理的批处理机上的机器排序问题。 在第4章中，考虑了带有禁用区间的两个代理单机排序问题。 在第5章中，研究了k个代理的单机排序问题。每个代理的工件有一个加工时间和一个工期。 在第6章中，研究了m台平行机上带有禁用区间的列表在线排序问题。

冯琪，副教授，博士，主要从事排序论的研究工作。主持完成国家自然科学基金项目1项，主持完成河南省自然科学基金项目1项，参与国家自然科学基金项目5项，参与完成省级科研项目5项， 参与河南省教育厅项目2项。已在等SCI刊物上发表论文12篇。河南省高校青年骨干教师，中原工学院青年拔尖人才，中原工学院青年骨干教师。

1 引言
1.1 问题提出的背景
1.2 相关研究综述
1.3 排序问题的三参数表示法
1.4 概念与术语
2 多代理排序问题的常见模型和算法
2.1 问题描述
2.1.1 工件特征
2.1.2 求Pareto解集
2.1.3 目标函数的线性组合
2.1.4 ε-约束方法
2.1.5 字典序
2.1.6 问题的分类
2.2 问题的模型和算法
2.2.1 函数fmax，fmax
2.2.2 函数Cmax，ΣCj
2.2.3 函数fmax，ΣCj
2.2.4 函数ΣwjCj，Cmax
2.2.5 函数ΣwjCj，Lmax
2.2.6 函数ΣwjCj，fmax
2.2.7 函数ΣUj，fmax
2.2.8 函数ΣTj，fmax
2.2.9 函数ΣCj，ΣCj
2.2.10 函数ΣwjCj，ΣwjCj
2.2.11 函数ΣUj，ΣCj
2.2.12 函数ΣUj，ΣUj
2.2.13 函数ΣwjUj，ΣwjUj
2.2.14 函数ΣCj，maxwjCj
2.2.15 函数ΣwjCj，max wjCj
3 批处理机上的多代理排序问题
3.1 继列分批的多代理排序问题
3.1.1 函数fmax，ΣwjUj
3.1.2 函数Cmax，ΣCj
3.1.3 函数ΣCj，ΣCj
3.2 行分批的多代理排序问题
3.2.1 函数Cmax，Lmax
3.2.2 函数fmax，Σfj
4 具有禁用区间的多代理排序问题
4.1 问题描述
4.2 问题1r-a，FI CA max+αγB
4.3 问题1r-a，FI δA +αLB max
4.4 问题1r-a，FI ΣCAj +αΣCBj
4.5 问题1r-a，FI ΣTAj +αΣCBj
5 具有提前费用的多代理排序问题
5.1 问题描述
5.2 问题1p1i，d1i=d2i=d Σn1i=1w1iE1i ∶E2max ≤Q
5.3 问题1dki=d Σnki=1Eki∶E1max ≤Q1，…，Ekm-ax1 ≤Qk-1
5.4 问题[fA max(EAj )，fBmax(EBj )]
6 带有禁用区间的在线排序问题
6.1 问题描述
6.2 问题P2on -line-list，nr-a，D Cmax
6.2.1 竞争比的下界
6.2.2 在线算法
6.3 问题Pm on-line-list，nr-a，D Cmax
6.3.1 竞争比的下界
6.3.2 一个在线算法
参考文献