Open pit design and production scheduling is an intricate process that defines the sequence of ore and waste extraction during the life-of-mine and up to an ultimate pit limit. This process deals with the management of cash flows in the order of hundreds of millions of dollars. Uncertainty in the metal/ore and waste forecasted to be produced from a pit has a major financial impact in both valuations and operation. To deal with this uncertainty, a new push re-label minimum cut algorithm is tested in an application at a gold mine. The push re-label algorithm is implemented on the so-called directed graph, formulated from the simultaneous use of a set of multiple stochastically simulated models of the orebody representing the related uncertainty. This leads to the definition of the optimal pit limits under uncertainty in ore/metal supply from the orebody; and for a given set of other engineering inputs. In addition, pushbacks can be similarly designed by parametrizing the space of the orebody. The application at an epithermal vein hosted gold deposit finds its optimal pit limits. This is then generated along with pushbacks, and results assessed for feasibility, risk, and NPV. The comparison to the conventionally derived design (commercial implementation of the Lerchs-Grossman algorithm) shows that the method presented here generates a larger pit and about 30% higher undiscounted economic value