排序问题是一类经典的组合优化问题,受到了许多行业的从业人员与理论研究者的密切关注.它已成为当今世界上发展研究最为活跃、应用最为广泛的学科领域之一.排序问题的实质是在一定的约束条件下,如工件的到达时间,工件的工期（或截止期限）等等,利用一些机器（处理机或资源）最优的完成所给定的任务.第一章主要介绍排序问题的相关知识,并简要概括了本文的研究成果.第二章主要研究的内容是工件可转包加工的单台机排序问题.有n个工件需要被加工者自有的单台机加工或者转包给转包商加工.如果一个工件转包给其他机器加工,那么它的加工费用与在自有机器上加工费用是不同的,且它的完工时间是关于转包加工工件的总加工时间的阶梯函数.我们研究的两个目标函数分别是：·最小化工件最大完工时间与总加工费用的加权和；·最小化误工个数与总加工费用的加权和.对于第一个问题我们证明它是NP-难的,并给出了伪多项式时间算法.对于第二个问题我们也证明它是NP-难的,并对它的一种特殊情况给出伪多项式时间算法.对于这两个问题我们各给出一个启发式算法,并对其进行了数值模拟.