The Optimality Box and Region for Single-Machine Scheduling of a Set of Jobs with Uncertain Durations

Yuri Sotskov1, Natalja Egorova2, Frank Werner3

  • 1Academy of Sciences of Belarus
  • 2United Institute of Informatics Problems
  • 3Otto-von-Guericke-University Magdeburg

Details

11:22 - 11:44 | Wed 28 Aug | 014 | WeAT5.2

Session: Planning and Scheduling of Manufacturing Processes

Abstract

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.