当代工业中的若干排序问题研究

论文摘要

排序问题是一个经典的组合优化问题，受到众多学者的关注，随着社会生产的发展，又不断地产生一些新模型，本文就针对这些新模型，主要研究当代工业中的若干排序问题。全文共分为七章，第一章主要介绍与排序问题相关的一些概念和预备知识。接着我们分别研究了六个排序模型。 第二章研究机器带准备时间的两台同型机排序问题。对于极小化机器最大完工时间的目标函数，我们给出了一个最坏情况界为10／9的线性时间近似算法。 第三章研究机器需周期性维护的单台机排序问题。目标函数为极小化工件最大完工时间，我们考虑工件加工不可恢复情形。我们首先证明LPT算法的最坏情况界为2，然后证明在P≠NP的假设下不存在最坏情况界比2小的多项式时间近似算法，从而证明LPT算法已经是最优的近似算法。 第四章研究了机器在固定时刻提速的单台机排序问题，目标是极小化工件最大完工时间。我们分别对在线和离线情形进行了相应的分析，证明该问题是NP-hard问题，给出了最优在线算法，并设计了一个最坏情况界为5／4的离线算法。 第五章讨论机器可以进行速率调整的单台机排序问题。对于极小化工件最大完工时间和极小化工件总完工时间两个目标，我们都进行了计算复杂性分析，并对大部分情形设计了多项式时间近似算法或者伪多项式时间动态规划算法。特别地，对于极小化工件最大完工时间，我们还设计了完全多项式时间近似方案；对于极小化工件总完工时间，我们还对一个常见子情形给出了一个伪多项式时间最优算法。 第六章研究一种加工时间依赖开工时间，并且机器带一个维护时间段的单台机排序问题。我们考虑工件加工不可恢复情形，目标是极小化工件最大完工时间和极小化工件总完工时间。我们分别进行了计算复杂性分析。进一步地，对于前一个目标，我们给了一个最优的在线算法和一个离线情形下的完全多项式时间近似方案；对于后一个目标，我们给了一个启发式算法并通过数据试验验证其性能。 第七章主要研究带运送费用的单台机分批运送排序问题。目标为极小化赋权工件总运送时间和运送费用之和，其中运送费用和运送的次数有关。我们进行了计算复杂性分析，证明原始问题是强NP-hard问题，进一步对于以下几

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 组合优化简介
• 1.2 排序问题
• 1.3 算法和计算复杂性
• 1.4 论文概述
• 第二章 机器带准备时间的两台同型机线性时间算法
• 2.1 引言
• 2.2 算法描述
• 2.3 主要结论
• 第三章 机器需周期性维护的单台机排序问题
• 3.1 引言
• 3.2 LPT算法和其最坏情况界
• 3.3 不可近似性
• 第四章 机器在固定时刻提速的单台机排序问题
• 4.1 引言
• 4.2 计算复杂性
• 4.3 一个最优在线算法
• 4.4 一个线性时间离线算法
• 第五章 机器可以进行速率调整的单台机排序问题
• 5.1 引言
• 5.2 极小化工件最大完工时间
• 5.2.1 计算复杂性
• 5.2.2 伪多项式时间动态规划算法
• 5.2.3 完全多项式时间近似方案
• 5.3 极小化工件总完工时间
• 5.3.1 计算复杂性
• 5.3.2 一个伪多项式时间可解情形
• 第六章 加工时间依赖开工时间的带维护时间段的单台机排序问题
• 6.1 引言
• 6.2 极小化工件最大完工时间
• 6.2.1 计算复杂性
• 6.2.2 在线算法
• 6.2.3 离线算法
• 6.3 极小化工件总完工时间
• 6.3.1 计算复杂性
• 6.3.2 伪多项式时间动态规划算法
• 6.3.3 启发式算法
• 第七章 带运送费用的单台机分批运送排序问题
• 7.1 引言
• 7.2 计算复杂性
• 7.3 几个多项式时间可解情形
• 第八章 后记
• 参考文献
• 致谢
• 在学期间完成的论文