Article ID Journal Published Year Pages File Type
4652756 Electronic Notes in Discrete Mathematics 2010 8 Pages PDF
Abstract

We study an extension of the precedence constrained knapsack problem where the knapsack can be filled in multiple periods. This problem is known in the mining industry as the open-pit mine production scheduling problem. We present a new algorithm for solving the LP relaxation of this problem and an LP-based heuristic to obtain feasible solutions. Computational experiments show that we can solve real mining instances with millions of items in minutes, obtaining solutions within 6% of optimality.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics