Iterated local search for the label printing problem
研究了标签印刷问题，即用n个模板印刷多种标签，需决定标签分组、每个模板上的印版数量及印刷次数，以最小化浪费。提出迭代局部搜索启发式算法，在测试实例中改进了许多已知最优解。
In the label printing problem (LPP), a set of labels must be printed in specified quantities, using n templates to be defined. Each template can accommodate a fixed number of printing plates. The LPP consists of determining: (1) an n-partition of the labels, where each block defines the labels that share a template, (2) for each label the number of identical printing plates to place in one of the n templates, and (3) the number of imprints to make with each template. The objective is to satisfy the labels’ demand while minimising total waste. Since the LPP is NP-Hard, to solve it, we propose here an Iterated Local Search heuristic that, once tested on all the instances available to us, it improved many of the best known results or find the optimum, when it is known.