The product–mold–machine manufacturing problem: Complexity, MILP models and constructive heuristics

This study addresses the product–mold–machine manufacturing problem, a problem intrinsic to the fabrication processes in industries such as tires, plastics, ceramics, and glass. Each product possesses distinct shape and mechanical attributes, resulting from processing its corresponding mold on a specific machine. Uniquely, machines in this problem can handle multiple molds concurrently, implying that their processing time is dictated by the longest mold processing time within the set being used. The goal is to devise a production strategy that reduces the overall periods required to satisfy each product's demand. This has to be achieved under constraints like limited availability of machines and molds, changeover times, and incompatibility constraints. We establish the problem's NP-complete nature in the strong sense. Further, we introduce two mixed-integer linear programming (MILP) models and two polynomial-time constructive heuristics. These heuristics offer upper bounds for the optimal makespan and present easily implementable feasible solutions. Our numerical tests, conducted on real-world data, evaluate the efficacy of different solution strategies, specifically those using the preliminary insights from our heuristics to guide the mathematical formulations. The outcomes strongly advocate for leveraging these feasible solutions as starting points when solving the MILP models. Additionally, the notable efficiency and solution quality of our heuristics spotlight them as potent alternatives, especially in settings where traditional optimization tools might be absent.