Single machine scheduling with uncertain processing times

This paper considers scheduling a given number of jobs on a single machine such that various completion times related objective functions are minimized in the existence of uncertainty. Processing times are assumed to be known only by their bounds, lower and upper, at the time of scheduling. The two bounds represent the most optimistic and the most pessimistic estimates of processing times. As such, schedules that minimize the maximum, minimum and range of total completion times are identified. Also, expected values of mean completion times are minimized under the two boundary values of processing times as well as when a third point, the most likely, is known. The optimal solution is analyzed and characterized with respect to the available information. Schedules that are robust and dominant are characterized.