排序论又称为时间表理论，它是为满足一个或者多个优化目标，安排稀缺资 源，执行任务的决策过程。一般认为，1954年,Johnson的论文[52]是经典排序的第一 篇文章，从此排序论迅速发展起来。随着社会的发展，新的问题及模型层出不穷，同 时伴随着问题的规模越来越大，因此从解决实际需要出发，从归结得到的排序模 型具有实际应用意义的角度来看，对于大量NP-难的排序问题，设计精确算法是目 前排序论研究中一个值得深入研究的课题。 对于大规模的NP-难的组合优化问题，已有的精确算法有分支定界算 法，动态规划算法，以及列生成算法[62，76，85，95，99]等。最初，列生成方法 是Ford与Fulkerson [34]在1958年求解最短路问题时提出，后来它在求解整数规 划方面得到很好的应用。但是很少的文献应用列生成方法来求解NP-难的排序问 题，van den Akker et a1.[87]结合D-W分解和分支定界方法，对于所有GJ的正则目 标函数，给出了经典单机排序问题的列生成算法。1999年，陈志龙和Powell[25]讨论 了经典排序问题α||∑ Fj(Cj)的列生成算法，这里α∈{P，Q，R}，他们在[26]中给出 了JIT(just-in-time)平行机排序问题的列生成算法。 本文主要研究结果包括以下几个方面：一是研究NP-难的成组加工排序问题 的列生成算法；二是建立一种新型排序—柔性同时加工排序模型，讨论它的复杂 性并设计精确算法。三是对现代排序问题，资源受限的确定性排序问题进行了研 究。 在第—章，首先介绍了排序问题的基本知识和分类方法，然后介绍了列生成方 法在整数规划方面的应用，以及关于求解大规模排序问题的列生成算法。 经典的排序中更换工件所需要的安装时间是假设与机器无关的，并且与工 件的排法也无关。然而在实际问题中，工件在机器上加工前所需要的安装时间往 往是与排法有关的，在第二章，我们考虑了成组加工排序问题。分别讨论一台机器 和m台机器环境下，大规模的NP-难问题的列生成算法，并通过试验，验证了我们 的算法的有效性。 在第三章考虑了一种新型的排序模型—柔性同时加工排序问题，系统地讨 论了它在不同的工件约束条件，以及不同的目标函数下，柔性同时加工排序问题的 计算复杂性。给出机器容量和时间满足一致性，目标是工件完工时间和的柔性同 时加工平行机排序问题的列生成算法。 最后考虑到企业的市场竞争，生产成本和资源的限制，例如机器加工能力的限 制，较少的生产线，库存限制等等，在第四章，主要研究机器加工和仓储的综合准时 排序问题，讨论了仓库容量有限，一台机器，目标函数分别是最小误工工件和，最 小工件投送时间和，最小最大工件误工和最小最大工件延误的排序问题的复杂性。 关键词：排序，多台机器，成组分批，柔性同时加工，复杂性，精确算法，伪多项 式算法，列生成算法