Generation of low-dimensional capacity constraints for parallel machines
提出一种为不相关并行机生成低维线性容量约束的方法，通过Minkowski加法和凸多面体面枚举实现，并用半导体制造数据验证有效性，还设计了基于图划分的启发式算法平衡精度与计算时间。
A crucial input to production planning is a capacity model that accurately describes the amount of work that parallel machines can complete per planning period. This article proposes a procedure that generates the irredundant set of low-dimensional, linear capacity constraints for unrelated parallel machines. Low-dimensional means that the constraints contain one decision variable per product type, modeling the total production quantity across all machines. The constraint generation procedure includes the Minkowski addition and the facet enumeration of convex polytopes. We discuss state-of-the-art algorithms and demonstrate their effectiveness in experiments with data from semiconductor manufacturing. Since the computational complexity of the procedure is critical, we show how uniformity among machines and products can be used to reduce the problem size. Further, we propose a heuristic based on graph partitioning that trades constraint accuracy against computation time. A full-factorial experiment with randomly generated problem instances shows that the heuristic provides more accurate capacity constraints than alternative low-dimensional capacity models.