排序问题是一类重要的组合优化问题，近几十年来，基于对经典问题的深入研究，具有实际背景的新问题正不断得到大家的重视。本文主要研究机器具有维护时段的带运输排序问题，该问题中的机器环境在单台机的基础上考虑到实际应用的情况增加了维护时段。研究的核心是近似算法设计与最坏情况界分析。全文共分五章。　　第一章简要介绍了排序问题的一些相关知识和概念，并对国内外带运输排序问题和带维护时段排序问题的研究进展进行了简要的概述。　　第二章研究机器具有维护时段的带运输排序问题。在该问题中工件需要在一台机器上加工完成后通过一辆运输工具分批运输到顾客处，其中机器环境为单台机，机器上有一个维护时段，在该时段内机器不能加工任何工件；每个工件具有不同的加工时间和尺寸大小，工件加工不可恢复；工件加工完成后只能被一辆车辆运输到顾客处。目标是极小化最大完工时间，即车辆运输完所有工件并返回到机器的时间。针对该问题，本章设计了两个近似算法，并分别证明了两个算法的最坏情况界均为2，且界均为紧的。　　第三章首先给出了物品分两批装箱的DFFD装箱算法，该算法在供应链管理中具有广泛的应用背景，且该算法在第四章的改进算法中起着重要的作用。在该装箱算法中，物品先被分成任意两个不相交的物品集，再分别对两个物品集中的物品采用FFD装箱算法装箱，以保证两个物品集中的物品不会被装到同一个箱子中。本章对该装箱算法的最坏情况界进行了分析和证明。　　第四章给出第二章问题的一个改进算法。该算法是一个复合算法，在该算法中用到了两种分批策略(NF算法分批策略和DFFD算法分批策略)，本章证明了该改进算法的最坏情况界不大于9/5。　　第五章总结全文并提出了对于该问题未来可以继续研究的几个方向。