带周期性维护时间的平行机排序问题研究

论文摘要

本文研究了带有维护时间（单个或周期性）的平行机排序问题。该问题可以描述为：给顶一个相互独立的工件序列J={J1，J2，…，Jn}，每个工件的加工时间（长度）是pi，i=1，…，n，且需要把它们分配到一台（或多台）平行机上进行不可中断地加工。在加工过程中，需要对机器进行维护，而工件在维护时段内不能加工。工件和机器在零时刻都处于就绪状态。全文共分为三章。第一章是绪论部分，主要介绍排序问题相关的一些概念和预备知识。第二章介绍了带单个维护时段的单机排序问题，分两种情况：维护时段固定、维护时段可选择。第三章讨论了带周期性维护时间的平行机排序问题。本章证明了LS算法是P1|periodic-mainten ance|Cmax在线情况的最优算法，算法竞争比为2。证明了两台机P2|periodic-maintenance|Cmax情况下，不存在常数界多项式时间算法。此外，给出了一个离线算法的参数界。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 平行机排序问题
• 1.2 离线、在线、半在线问题和算法性能分析
• 1.3 论文概述
• 第二章 带单个维护时段的单机排序问题研究
• 2.1 引言
• 2.2 维护时段固定的情况
• 2.2.1 维护时段前后机器加工速率不改变
• 2.2.2 维护时段前后机器加工速率改变
• 2.3 维护时段可选择的情况
• 第三章 带周期性维护时间的平行机排序问题研究
• 3.1 引言
• 3.2 单台机的最优在线算法
• 3.2.1 复杂性证明
• 3.2.2 LS算法的竞争比
• 3.2.3 在线情形问题下界
• 3.3 两台机问题讨论
• 3.3.1 复杂性证明
• 3.3.2 一般情况下不存在常数界多项式时间算法
• 3.3.3 离线算法及其参数界
• 参考文献
• 致谢