二维不规则带排样问题(two-dimensional irregular strip packing problem),又称为下料问题(nesting problem),它在工业生产中有着广泛的应用,其典型应用如服装制造、钢铁切割、家具制造、制鞋工业等制造工业中的零件下料问题。该问题的研究目标在于如何充分利用原材料,即尽量减少原材料消耗,提高经济效益。因此研究二维不规则带排样问题有着非常重要的实际应用价值。　　 本文提出了求解二维不规则带排样问题的扩展局部搜索(ELS)算法。该算法首先采用简单的启发策略来获得待排样多边形的一个合法放置。然后利用局部搜索算法来得到更好的解。局部搜索中所采用的邻域为:交换两个多边形的位置和将一个多边形放置到一个新的位置。在移动多边形的过程中可能会产生重叠区域,无约束非线性规划模型被用于最小化这一重叠区域,以此来获得一个合法的放置。在搜索过程中引入了禁忌搜索以避免陷入局部最优。最后,本文还提出了一个压缩算法用于进一步优化已得到的合法解。本文采用二维不规则带排样问题的标准测试实例对ELS算法进行了测试。实验结果表明,ELS算法与其他现有算法相比不但具有很强的竞争力,而且更新了不少实例的最优解,是当前求解效果最好的算法之一。此外,本文还展示了ELS算法应用于圆形带排样问题和大规模带排样问题的排样效果。