Optimization models and algorithms for batch process scheduling under uncertainty

This dissertation is concerned with the development of mathematical models and algorithms for the optimal scheduling of batch processes under uncertainty in either task processing times or product demands. Chapter 1 presents a review of scheduling of batch processing systems and approaches to modeling uncertainty and a brief discussion of the mathematical programming and heuristic search techniques employed in this work. Chapter 2 considers the problem of scheduling to minimize the expected makespan of flowshop plants with uncertainty in processing times. Mixed Integer Linear Programming (MILP) models are presented for the case where the uncertainty is described using discrete probability distributions. A novel branch and bound algorithm based on successive probability disaggregation is proposed to reduce the computational effort associated with solving the scheduling problem. An extension to the case where continuous probability distributions model the processing times is also discussed. Chapter 3 considers the scheduling of multistage flowshop plants and the New Product Development testing process in the agrochemical industry, when the task durations are represented by fuzzy numbers. The MILP models developed with this approach do not feature the exponential increase in variables and constraints typically seen in probabilistic approaches. Furthermore, since the time complexity of schedule evaluation is polynomial in problem size, a heuristic search algorithm called Reactive Tabu Search is adapted for the multistage flowshop plant problem to provide near-optimal solutions in reasonable time. Chapter 4 presents stochastic programming approaches for the optimal scheduling of a multiproduct batch plant under demand uncertainty. The batch plant is represented by a State Task Network and modeled using a discrete-time formulation. A stochastic multistage MILP model is formulated for the maximization of the expected profit, given different processing modes, inventory costs and product demand uncertainty. An approximation strategy consisting of the solution of two-stage models within a shrinking-horizon framework is proposed to overcome the computational expense of solving the multistage model. Several examples are presented to show that the approximation strategy yields expected profits within a few percent of the optimal value, with order of magnitude reduction in computation time. Finally, Chapter 5 summarizes the major contributions of this dissertation and indicates promising directions for future work.