A methodology for the large-scale multi-period precedence-constrained knapsack problem: an application in the mining industry

Mehran Samavati, Daryl Essam, Micah Nehring and Ruhul Sarker

International Journal of Production Economics, 2017, vol. 193, issue C, 12-20

Abstract: This paper considers a generalization of the precedence-constrained knapsack problem known as multi-period precedence-constrained knapsack, in which the decision maker faces a horizon of several periods. Associated with each period is a capacity limit that cannot be exceeded by items chosen in that specific period. The motivation for studying this problem comes from a recognized problem in the mining industry, known as open pit mine production scheduling. An old, yet fast sequencing heuristic has been used in the literature to tackle similar combinatorial problems with precedence constraints. In this study, we first strengthen the LP relaxation formulation of the problem by adding inequalities derived from both precedence and knapsack constraints, and then use the LP solutions to generate efficient weights for the sequencing heuristic. Generating the heuristic's weights in this way significantly improves its output. Using this methodology, extremely large instances can be solved to near-optimum levels in minutes. The performance of this methodology is tested on a set of benchmark instances in the mining industry, where this problem is a major application.

Keywords: Integer programming; Multi-period precedence-constrained knapsack; Open pit mine scheduling; Topological ordering (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0925527317301986
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:proeco:v:193:y:2017:i:c:p:12-20

DOI: 10.1016/j.ijpe.2017.06.025

Access Statistics for this article

International Journal of Production Economics is currently edited by Stefan Minner

More articles in International Journal of Production Economics from Elsevier
Bibliographic data for series maintained by Catherine Liu ().