Single machine scheduling problem with interval processing times and total completion time objective

Abstract

We consider a single machine scheduling problem with uncertain durations of the given jobs. The objective function is minimization of the sum of job completion times. We apply astability approach to this uncertain scheduling problem. The stability approach combines a stability analysis of schedules (job permutations) and constructing a job permutationwith the largest stability (optimality) box. We consider a relative perimeter of the optimality box of the job permutation as a stability measure for this permutation. We investigated properties of the optimality box and developed algorithms for finding permutations with the largest relative perimeters of their optimality boxes.