A novel branch and bound algorithm for scheduling flowshop plants with uncertain processing times

We address the problem of scheduling a flowshop plant with uncertain processing times described by discrete probability distributions. The objective is to find a sequence of batches that minimizes the expected makespan. To circumvent the problem of combinatorially explosive state spaces, we propose a novel and rigorous branch and bound algorithm that provides the optimal solution and is based on the result that a lower bound to the expected makespan can be obtained by evaluating over an aggregated probability model. Numerical results for a number of example problems show that the solution times for the proposed method are several orders of magnitude smaller than those for a multiperiod model. In addition, an important extension of this method is proposed for the case of continuous probability distributions of certain forms, using discretization schemes that give excellent approximations. (C) 2002 Elsevier Science Ltd. All rights reserved.