单机可拒绝分批排序中的若干问题

摘要

分批排序是兴起于20世纪90年代初应用背景极强的一类组合最优化问题，它主要产生于大规模的现代化生产流水作业线。工件加工可拒绝的排序问题是近年来出现的一类新型排序问题，该问题更符合实际情况，具有重要的现实意义。本文将分批排序与可拒绝排序相结合，讨论了一些可拒绝分批排序问题，论文主要结构安排如下：
　　第一章是本文的绪论部分，主要介绍了排序问题的背景、相关概念以及所需的基本知识，然后介绍了本文的主要结果和创新点。
　　第二章中首次研究了目标函数为极小化总加权完工时间加上被拒绝工件的拒绝费用之和的单机可拒绝分批排序问题。证明了该问题是NP-难的，然后给出了基于动态规划的伪多项式时间算法和FPTAS。
　　第三章中首次研究了两类特殊情况下的可拒绝分批排序问题。一个是极小化加权总完工时的有界批量可拒绝分批排序问题，考虑了该问题的一些特殊情况，如所有工件加工时间都相等、工件有两种到达时间；另一个是极小化最大延迟的无界批量可拒绝分批排序问题，考虑了所有工件的拒绝费用都相等的情况。分别给出了以上两类问题基于动态规划的多项式时间算法。

目录

曲阜师范大学研究生学位论文原创性说明

曲阜师范大学研究生学位论文使用授权书

第一章 绪论

§1.1排序问题的背景及描述

§1.1.1排序问题的背景

§1.1.2排序问题的定义

§1.1.3经典排序与现代排序

§1.1.4排序问题的三参数表示

§1.2算法复杂性和NP-理论

§1.2.1算法复杂性

§1.2.2NP-理论

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

第二章 极小化总加权完工时间及拒绝费用的批容量无界的分批排序问题

§2.1引言

§2.2问题的复杂性分析

§2.3伪多项式时间算法

§2.4问题1∣B≥n∣Σj∈SwjCj + Σj∈Sej的FPTAS

第三章 两类特殊情况下的可拒绝分批排序问题

§3.1问题的描述及预备知识

§3.2极小化加权总完工时的有界批量可拒绝分批排序问题

§3.3极小化最大延迟的无界批量可拒绝分批排序问题

参考文献

附录一 攻读硕士期间撰写的论文

附录二 致谢