Yuri Sotskov1, Natalja Egorova2, Frank Werner3
11:22 - 11:44 | Wed 28 Aug | 014 | WeAT5.2
A set of jobs has to be processed on a single machine without preemptions of a job. The exact value of the job processing time (duration) is unknown until the completion of the job. Lower and upper bounds on the job duration are known before scheduling. The problem is to minimize total completion time of the given jobs. We apply a stability approach to this scheduling problem and introduce an optimality region for a job permutation as an optimality measure of the schedule. We investigate properties of the optimality region and derive $O(n)$ algorithms for calculating the relative perimeter of the optimality region (the sum of the relative optimality sets of the $n$jobs) for a fixed job permutation. We present computational results for a comparison of the relative perimeters of the optimality regions for the mid-point permutations, the lower-bound permutations, the upper-bound permutations and the permutations having the largest optimality box.