排序（也称调度）问题是组合优化中一类有着重要理论意义和广泛背景的问题。本文主要研究生产管理中的两个排序问题：带机器故障的两台机求解带权误工数最小的排序问题和考虑工件加工时间和运输时间的单机在线排序问题。全文共分为四章，第一章首先介绍了与排序问题相关的一些概念以及预备知识，并概括了本文研究的背景和意义。　　 第二章研究机器带故障中断的两台平行机排序问题，工件加工时间均为单位时间，目标是极小化带权误工工件数。当转移时间t=0时，对问题P2|D=∞, t=0, Pij=1|∑wijUij给出了最优的算法。当工件转移时间t>0时，对问题P2|D=∞，t≠0, pij=1|∑ wijUij，本文给出了一个多项式时间的近似算法，并证明算法解与最优解至多相差一个带权误工数。　　 第三章研究将加工时间和运输时间一起考虑的单机在线排序问题，目标是极小化最大的工件加工时间和运输时间之和。每个工件Jj都有一个到达时间r，一个加工时间pj和一个运输时间qj，工件加工过程中不允许被打断，工件到达之前我们不知道工件的任何信息。本章考虑工件的加工时间和运输时间满足一致性关系的模型，即工件Ji和Jj的加工时间满足Pi≥pj，则它们的运输时间有qi≥qj，用三参数法将问题表示为1|on- line, rj, agreeable( pj，qj)|Lmax。本文给出了竞争比为(?)的最优在线算法。第四章总结全文并给出了今后进一步的研究方向和研究内容。