Uncertainty is a major factor in power system operations. In recent years, with the emergence of the smart grid, uncertainty level has been further elevated in both the generation and demand side of power systems. Increasing uncertainty exposes the electric grid to potential safety issues and economic loss, thus posing significant challenges to the grid operations. Traditionally, power system operations use certainty equivalent approach to deal with uncertainty, i.e., replacing random variables by their expected values. With this simplification, the original stochastic optimization is reduced to a deterministic problem. However, the certainty equivalent method is inadequate for the modern electric grid with deep penetration of distributed energy resources. Due to increasing uncertainty, operations and decision makings need to incorporate system dynamics over a broad range of temporal and spatial horizons. To this end, this thesis provides a new paradigm for operation under uncertainty and computationally efficient algorithms based on multiparametric programming theory. Under this new paradigm, uncertainty is characterized by conditional distributions and decisions are made by incorporating such probabilistic descriptions. To illustrate the new paradigm, we consider two specific problems. For characterization of system uncertainty, we develop a formal methodology for probabilistic forecasting of real-time operations and locational marginal prices. Conditioning on the current system state, we provide a full distribution of future operations and prices. For operational decision making, we propose an optimal stochastic approach to interchange scheduling in multi-area systems. By incorporating the conditional distribution of load and generation, the optimal interchange is obtained through an iterative process.