Optimal makespan scheduling with given bounds of processing times

This paper deals with the general shop scheduling problem with the objective of minimizing the makespan under uncertain scheduling environments. The processing time of an operation is usually assumed to take a known probability distribution function when dealing with uncertain scheduling environments. The scheduling environments that we consider in this paper are so uncertain that all information available about the processing time of an operation is an upper and lower bound. We present an approach to deal with such a situation based on an improved stability analysis of an optimal makespan schedule and demonstrate this approach on an illustrative example of the job shop scheduling problem.