Cryogenic air separation is an efficient technology for supplying large quantities of nitrogen, argon, and oxygen to chemical, petroleum and manufacturing customers. However, numerous uncertainties make effective operation of these complex processes difficult. This work addresses the problem of determining an optimal operating strategy to maximize the total profit of a cryogenic air separation process while considering demand uncertainty and contractual obligations. A rigorous process model is included as constraints in a nonlinear programming formulation. Uncertain demands are assumed to be normally distributed with known mean and standard deviation, and expected profit in the objective function is evaluated using the standard loss function. A probabilistic fill-rate expression, also based on the loss function, is used to model the contractual obligations by providing a lower bound on the expected product sales. In the single period case with one customer satisfaction constraint, the nonlinear programming formulation can be solved efficiently using the general purpose nonlinear optimization package, IPOPT. This formulation is then extended to include multiple time periods, the potential for product storage, and customer satisfaction constraints on multiple products. To solve the large-scale nonlinear programming formulation that considers a seven-day operating horizon, a tailored parallel nonlinear programming algorithm is used. This approach makes use of a Schur complement decomposition strategy to exploit the block structure of the problem and allow efficient solution in parallel. Using these tools, we solve for a set of optimal operating strategies over the complete space of different fill rates. This produces planning figures that identify key trade-offs between profitability and contractual obligations. (C) 2010 Elsevier Ltd. All rights reserved.