本文的主要研究对象是二维不规则排样问题(2D Irregular Packing Problem)。该问题是一个更一般领域——排样问题(也称下料问题)的核心问题,是一个在工业生产中有着广泛应用的重要问题,最典型的应用如服装制造业、钢铁切割、家具制造、制鞋工业等制造工业中的零件下料问题。该问题的研究目标在于如何充分利用原材料,以充分减少原材料消耗,提高经济效益。因此可以说二维不规则排样问题有着非常重要的实际应用价值。本文最重要的贡献在于提出了离散临界多边形这个新概念。论文首先指出了Burke等人提出的新BL(Bottom-Left)算法存在的一个不足:算法对一些特殊实例会产生非法的解;然后引入了离散临界多边形这个新概念,给出并严格证明了离散临界多边形的分解定理;在此基础上给出了离散临界多边形的构造算法,实验测试表明该构造算法的实际执行效率是很高的。利用离散临界多边形,我们将原问题转化为一个只需要处理点和区间的简化问题,在大大降低原问题几何复杂性的同时,也使许多启发式策略可以更容易地运用到该问题中来。基于离散临界多边形,利用基本的爬山算法和遗传算法分别得到了两个求解不规则排样问题的算法,并测试了15组benchmark,这两个算法可以在很短时间内得到解,并且结果十分接近最优解,在一些数据上甚至超越了已知最好的解。这个计算结果表明,基于离散临界多边型的排样算法是有效的。