Solution procedures for block selection and sequencing in flat-bedded potash underground mines

Phosphates, and especially potash, play an essential role in the increase in crop yields. Potash is mined in Germany in underground mines using a conventional drill-and-blast technique. The most commercially valuable mineral contained in potash is the potassium chloride that is separated from the potash in aboveground processing plants. The processing plants perform economically best if the amount of potassium contained in the output is equal to a specific value, the so-called optimal operating point. Therefore, quality-oriented extraction plays a decisive role in reducing processing costs. In this paper, we mathematically formulate a block selection and sequencing problem with a quality-oriented objective function that aims at an even extraction of potash regarding the potassium content. We, thereby, have to observe some precedence relations, maximum and minimum limits of the output, and a quality tolerance range within a given planning horizon. We model the problem as a mixed-integer nonlinear program which is then linearized. We show that our problem is $${\mathcal {NP}}$$ NP -hard in the strong sense with the result that a MILP-solver cannot find feasible solutions for the most challenging problem instances at hand. Accordingly, we develop a problem-specific constructive heuristic that finds feasible solutions for each of our test instances. A comprehensive experimental performance analysis shows that a sophisticated combination of the proposed heuristic with the mathematical program improves the feasible solutions achieved by the heuristic, on average, by $$92.5\%$$ 92.5 % .