A stochastic batching and scheduling problem

We consider a batch scheduling problem in which the processing time of a ba tch of jobs equals the maximum of the processing times of all jobs in the b atch. This is the case, for example, for burn-in operations in semiconducto r manufacturing and other testing operations. Processing times are assumed to be random, and we consider minimizing the makespan and the flow time. Th e problem is much more difficult than the corresponding deterministic probl em, and the optimal policy may have many counterintuitive properties. We pr ove various structural properties of the optimal policy and use these to de velop a polynomial-time algorithm to compute the optimal policy.