**

自动排料即使用计算机软件实现裁片（服装衣片，钣金零件）在规定材料（面料，金属板材）上的自动布局，并以材料利用率为主要追求目标。

目前市面上能看到的知名排料软件绝大部分是国外软件。 还有一类是使用国外排料引擎的国内排料软件，所谓排料引擎即核心算法库/模块。比较知名的有Autonester(德国),Gemini(罗马尼亚),Lectra(法国力克)，ShapeShifter(新西兰,简称SS)，Nestfab(英国), Sigmanest(美国?), … ，国内的比较有名的有smartnest, 和鹰和青鹤（均不确定两家是否使用自研发引擎， 主要用于皮料行业）：

从功能上看，国产引擎能够提供较多甚至完备的功能，主要差距还是体现在利用率上。 对比国外顶级排料软件，国产引擎与国外引擎利用率差距通常在平均2%以上。

比较不同的排料引擎，需要测试很多的例子，各种类型的例子，并统计平均利用率。 单独拿一个例子比较意义不大， 比如 A测试100个例子平均利用率85%， B对应的是84%。 但是随机抽取其中一个，B还是有比A利用率高的可能的。

国外对自动排料软件的研究从上世纪70年代就开始了。大概经历

从运行过程中的状态来看，又可以分为可行解法和不可行解法。

左底算法通常都是可行解法， 即设定一组零件排放顺序，依次把裁片放入材料（面料/板材）中， 通过调节和优化顺序改进利用率。

不可行解法通常利用启发式方法或者可行解法初始化一个初解， 然后缩短面料/板材长度或者增加裁片个数，这样这个布局就会有裁片相互重叠，通过移动或交换裁片来移除重叠，得到一个没有重叠的可行解。

通常不可行解的解空间接近问题的解空间࿰