本论文主要研究了一些现代排序问题,包括带有拒绝的排序问题、带有不可用时间约束的排序问题以及烟草制造行业中产生的自动仓储系统一轨双车排序调度问题。我们研究了这些问题的性质,对这些问题分别设计了算法,分析了算法的性能比或竞争比,并对一些问题使用数值模拟验证了算法的有效性,全文共分六章。第一章介绍了组合优化问题和排序问题的研究背景,引入了本文涉及的基本概念和定义。对经典排序问题、在线排序问题、带有拒绝的排序问题和带有不可用时间约束的排序问题,分别介绍了目前的研究现状和研究结果。第二章研究了带有拒绝的单机和同型机排序问题。对于带有拒绝的单机排序问题,我们研究了惩罚费用是对应工件加工时间α倍的情形。当工件有不同的到达时间时,目标函数为时间表长与惩罚费用之和的问题是可解的；当所有工件在零时刻到达时,目标函数为总完工时间与惩罚费用之和的问题也是可解的。对于带有拒绝的同型机排序问题,我们研究了至多有两个到达时间的在线情形,对机器台数是2和m的情形,分别给出了竞争比为2和4—2/m的在线算法。第三章研究了带有拒绝的两机流水作业排序问题。每个工件有两个操作,每个操作可以被接受并安排到机器上加工,或者被拒绝并支付一定的惩罚费用。两台机器上操作的惩罚费用分别为对应加工时间的α1倍和α2倍。目标函数是最小化时间表长和惩罚费用之和。对于此问题min{α1,α2}<1且max{α1,α2}≥1的情形,我们给出了性能比为4/3的近似算法。对于α1和α2的一般情形,我们给出了两个时间复杂度不同的动态规划算法,并设计了完全多项式时间近似方案(FPTAS)。第四章研究了带有不可用时间约束的单机半在线排序问题。在此问题中,机器由于维修或故障等原因,有一个不可用时间段,工件无法在此时间段内进行加工。工件是在线实时到达的,目标函数是最小化时间表长。我们研究了这个问题的半在线形式,即工件的某些信息在初始时刻是已知的。对于已知最大工件的加工时间、所有工件的加工时间和、最后工件的到达时间、最优时间表长这四个半在线问题,我们分别研究了问题的下界,给出了半在线算法,并证明了这些算法的竞争比。第五章研究了由烟草制造行业提出的自动仓储系统一轨双车排序调度问题。在这个系统中有两台堆垛机运行于同一轨道上,两台堆垛机之间需要保持一定的安全距离。轨道两侧分别有高层货架,多个出／入货口位于高层货架的底部。运送货箱的请求由成型机与发射机在线实时产生,堆垛机在机器与高层货架之间运送货箱。问题的目标是保证系统安全运行,满足生产要求,最小化完成所有请求时所需要的时间。这个问题可以看成是一个在线排序与路线问题。在给定系统的物理布局下,我们证明了问题的复杂性。对于一轨单车模型与一轨双车模型两种情形,我们给出了四个在线控制策略,形成在线算法,并用实例与数值模拟验证了在线算法的有效性。算法已经投入实际使用并取得了良好的效果。第六章对本论文进行了总结,介绍了未来可以研究的方向及问题。