单机双目标分批排序中的几个问题

摘要

排序论又称时间表理论，已经发展成为运筹学的一个重要分支，作为一门应用科学，它有深刻的实际背景和广阔的应用前景.分批排序问题、多目标排序问题是近年来新兴起的两类现代排序模型，因其显著的现实意义，更具研究价值.本文将以上两种现代排序模型相结合，讨论了几类特殊的单机双目标分批排序问题.论文主要结构安排如下： 第一章(绪论)首先介绍了排序问题的应用背景及问题描述，然后给出了必要的预备知识，最后概述了本文的主要研究结果. 第二章主要研究了两类批容量无限的单机双目标平行分批排序问题模型t约束模型与线性加权模型.目标函数主要涉及一些常见目标函数，如Cmax，Lmax，∑wjCj等的组合，通过动态规划就相应问题分别给出了多项式时间算法，并作了时间复杂性分析.最后我们证明在本文约束模型解决前提之下，问题对应的主次指标模型也可相应解决. 第三章主要研究了平行分批排序问题(p-batch)中一类主指标为∑wjCj,次指标为Cmax的主次指标排序问题.首先讨论了单机上批容量无限模型(6≥n)，通过动态规划给出了一个多项式时间算法，并分析了算法时间复杂性；然后对仇台同型机上批容量有限模型(6

目录

文摘

英文文摘

声明

第一章绪论

§1.1排序问题的介绍

§1.2计算复杂性

§1.3近似算法

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

第二章两类单机双目标分批排序问题

§2.1问题背景及研究现况

§2.2基本符号与引理

§2.3约束模型

§2.3.1f1=Cmax，f2=∑wjCj的情形

§2.3.2f1=Lmax，f2=∑wjCj的情形

§2.4线性加权模型

§2.5一点补充说明

§2.6小结

第三章一类特殊主次指标分批排序问题的算法分析

§3.1问题背景及描述

§3.2批容量无限的单机主次指标模型

§3.3批容量有限的平行机主次指标模型

§3.4小结

参考文献

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

附录二致谢