排序论是组合最优化领域的一个重要研究方向.它有着广泛的应用背景和深刻的理论意义,常常应用于军事、经济、运输、管理和计算机科学等诸多领域.工件的加工和配送协作排序问题起源于大型工业车床加工领域,在物流和供应链管理领域都有着重要的实际背景,研究成果也非常丰富.分批排序、工件加工时间具有学习效应、工件属于一些不相容的组（famly）及工件的配送过程外包的排序问题都是比较新型的模型,也吸引了众多国内外学者的关注.本文对这几类排序问题进行了讨论,做了如下工作.1.第一章介绍排序问题的一些基本概念、符号和相关知识.2.第二章讨论了工件的运输和继列分批加工协作排序问题.目标分别是极小化工件的总完工时间与批的费用之和及极小化工件的最大完工时间与批的加工费用之和.在工件的加工时间都相等的情况下,如果车辆运输工件的次序确定,分别给出了多项式时间的动态规划算法；如果车辆运输工件的次序不确定,证明了该问题是NP-困难的,分别给出了车辆返回时间t=0时最差性能比等于2-1/m的近似算法.3.第三章讨论了带有多个工件组的平行批处理机排序问题,其中,共有F个不相容的组,且每一组中的工件都具有相同的加工时间和相同的权.目标为极小化带权误工工件数.当组的个数F为固定常数时,给出了运行时间为O（bF1-2Fn2FW）的伪多项式时间算法,得到了运行时间为O（bF1-2Fn2F+2ε）的完全多项式时间近似方案（FPTAS）,其中,参数b为批的容量.如果每一组中工件的交货期也相同,给出了运行时间为O（n（log n+W min{P,dmax}））的伪多项式时间算法,其中,参数P,W分别表示工件的总完工时间和总权,dmax为工件的最大交货期.4.第四章讨论了工件具有学习效应的加工和配送协作排序问题.机器随着加工工件的增多,相应地具有一定的学习功能,机器上第r个位置上工件j的实际加工时间满足pj[r]=pj（1+Σ（r-1）（l=1）lnp[l]）α,其中,p[l]为排序中第l个位置上工件的正常加工时间,α≤0为学习因子.对目标分别为极小化工件的总配送时间与批的费用之和及极小化工件的最大延迟时间与批的费用之和的排序问题,给出了运行时间为O（n4）和O（n5）的动态规划算法.5.第五章讨论了配送外包的工件加工和批送货的排序问题,中间环节工件的配送由第三方物流公司负责,工件要在上一阶段加工完成T时间内分批送达下一阶段.工件的配送有正常、快递和即送三种模式,目标为极小化配送批的总费用.在制造商安排生产加工过程的情形中,如果只有正常或者快递一种配送模式,给出了运行时间为O（nL）的多项式时间算法,其中,参数L为正常或者快递配送模式车辆发车时间的个数.如果有正常和快递两种配送模式,当快递模式的车辆个数无限时,给出了运行时间为O（n3L1L2V1c2（L1V1+L2c2））的多项式时间算法；当快递模式的车辆个数有限时,给出了运行时间为O（n3L1L2V1V2c2（L1V1+ L2V2））的多项式时间算法.如果有三种配送模式,当即送模式的车辆个数无限时,给出了运行时间为O（n4L1L2V1V2c3（L1V1+L2V2+c3））的多项式时间算法；当即送模式的车辆个数有限时,给出了运行时间为O（n2V3+4L1V2V1V2c3（L1V1+ L2V2）+n2V3+6L1L2V1V2c23）的多项式时间算法,其中,参数L1、L2表示正常和快递模式下车辆发车时间的个数,Vi、ci（i=1,2,3）表示正常、快递和即送模式下可用的车辆数及相应的容量.在第三方物流公司安排生产加工过程的情形中,证明了该问题是强NP—困难的.