本文研究的排序问题属于一类新的组合优化问题。这类新问题具有明显的二层结构特征，约束部分是一个组合优化问题的约束，而目标部分则是另一个组合优化问题。例如，给定一个工件集合和一个图，工件和图的顶点一一对应。两个顶点之间有边代表对应的两个工件至少有一个需要被加工。优化问题是寻找一个满足顶点覆盖的工件子集在平行机上的排序，它的最晚完工时间最小。通过人为地为这类新问题的下层约束部分引入一个目标函数，并将该目标函数当做上层问题的决策变量，可以把原问题转化为一个二层组合优化问题。通常这类新的组合优化问题是NP难的，本文考虑的问题能充分利用这种二层结构的特点，从而设计出相应的自适应算法来得到原问题的近似解。关于组合优化问题的组合，王振波最近明确提出了这个概念，并和崔振华共同研究了带顶点覆盖约束的同速机排序问题。王振波接着抽象出一类包含众多常见组合优化问题的Covering问题，并研究了带Covering约束的同速机排序问题。本文的工作可分为两部分。第一部分是将王振波和洪文益关于带Covering约束的同速机排序结果平行推广到了同类机上，同时简单考虑了变速机的情况。第二部分考虑的问题与以往不同，是一类极大化最小完工时间的排序问题。针对该类问题，本文提出了一类Packing约束，并考虑了带Packing约束的同速机排序问题和同类机排序问题。针对不同的问题，本文设计了不同的算法框架，并给出了相应的算法复杂度分析和近似比结果。文章最后还给出了一些关于这类新问题的不可近似性猜想。