单机双目标串行分批排序问题

摘要

排序论又称时间表理论,是一类重要的组合最优化问题,也是运筹学研究的—个非常活跃的分支,具有极强的应用背景.近年来,分批排序和多目标排序作为两类新兴的现代排序模型,引起越来越多的关注.本文将以上两种现代排序模型结合起来,讨论了两类特殊的单机双目标串行分批排序问题.论文主要结构安排如下:
　　 第一章(绪论)首先介绍了排序问题的应用背景及问题描述,给出了必要的预备知识,然后概述了本文的主要研究结果.
　　 第二章主要研究了一类批容量无限的单机双目标平行分批排序问题模型,约束模型.目标函数主要涉及一些常见目标函数,如Cmax,Lmax,∑Cj等的组合,通过动态规划就相应问题分别给出了多项式时间算法,并作了时间复杂性分析.最后我们证明了在本文研究的约束模型比以前的主次指标模型更具一般性.
　　 第三章主要讨论了一类特殊的串行分批排序问题(s-batch)(目标函数分别为Cmax和∑Cj)的Pareto最优解的问题.我们找到这个问题的Pareto最优排序,并在此基础上找到所有的Pareto最优点.最后分析算法的计算复杂性为O(n3).

目录

文摘

英文文摘

第一章 绪论

§1.1排序问题简述

§1.2计算复杂性

§1.2.1计算复杂性的定义

§1.2.2 NP-理论

§1.3近似算法

§1.4本文主要结果及创新点

第二章 一类单机双目标串行分批排序问题

§2.1问题背景及研究现况

§2.2有关引理

§2.3约束模型的求解

§2.3.1f1=Gmax,f2=∑Cj的情形

§2.3.2f1=Lmax,f2=∑Cj的情形

§2.4关于双目标排序的几种模型之间的关系

§2.5本章小结

第三章 一类特殊的双目标串行分批问题的Pareto最优解

§3.1问题的描述

§3.2 Pareto最优解的定义

§3.3问题1,s|s-batch,b≥n|F(∑Cj,Cmax)的Pareto最优解

§3.4本章小结

参考文献

附录一 在校期间的研究成果及发表的学术论文

附录二 致谢