Underground production scheduling has typically been a task completed manually or with heuristic-based commercial software. Applying traditional optimization methods for solving open pit mine scheduling problems to underground settings has had limited success due to their complex resource and precedence structure. The Bienstock-Zuckerberg algorithm is a method to determine linear programming relaxation solutions for precedence-constrained knapsack problems. We tailor this algorithm for underground mine scheduling, obtain integer solutions via heuristics guided by these linear relaxations, and demonstrate the effectiveness of our techniques on real-life data sets containing multiple underground mines, time fidelities, and levels of accuracy (strategic and tactical).