Generation of low-dimensional capacity constraints for parallel machines

ABSTRACT

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.

KEYWORDS:

• Semiconductor manufacturing
• production planning
• capacity constraint generation
• unrelated parallel machines

Additional information

Notes on contributors

Phillip O. Kriett

Phillip O. Kriett is a Ph.D. candidate at the Technical University of Munich, Germany, and an operations research scientist at Amazon EU, Luxembourg. He holds a Diplom in business engineering from Karlsruhe Institute of Technology, a Master 2 Recherche in Informatics from Grenoble Institute of Technology, and a, Master of science in industrial engineering from Oregon State University. His research interests are in production and logistics with a focus on semiconductors and e-commerce.

Martin Grunow

Martin Grunow is a Professor of production and supply chain management at TUM School of Management at Technical University of Munich, Germany. He received his industrial engineering degree and his Ph.D. from Technical University Berlin before joining the R&D department of Evonik Degussa, a producer of special chemicals. Later, he became a professor and department head at the Technical University of Denmark. His research interests are in manufacturing and logistics with a focus on the electronics and automotive sector, as well as on the process industries, including chemicals, pharmaceuticals, and food.