The optimality region for a single-machine scheduling problem with bounded durations of the jobs and the total completion time оbjective

Abstract

We study a single-machine scheduling problem to minimize the total completion time of the given set of jobs. The lower and upper bounds on the job duration is the only information that is available before scheduling. We use the optimality region for the job permutation as an optimality measure of the optimal schedule. We develop an efficient algorithm for finding a job permutation having the largest quasi-perimeter of the optimality set. The computational results on constructing such permutations show that they are close to the optimal ones, which can be constructed for the factual durations of all given jobs.