New approaches for multiprocessor scheduling problem with incomplete information
Prof. Vladimir Kotov, Belarusian State University, Belarus

To the main page
 
Combinatorial optimization problems come with various paradigms on how an instance is revealed to a solving algorithm. The very common offline paradigm assumes that the entire instance is known in advance. On the opposite end, one can deal with the pure online scheme, where the instance is revealed part by part, unpredictable to the algorithm, and no further knowledge on these parts is assumed. In between these two extremes, and also highly relevant for many practical applications, are semi-online paradigms, where at least some characteristics of the instance in general are assumed to be known, for example, the total instance size or distributions of some internal values. The well-known classical multiprocessor scheduling problem is a fundamental and well-investigated scheduling problem both in the offline and the online setting. A set of n independent jobs is to be processed on m parallel machines in order to minimize the makespan. We present some approaches such as bunch techniques, a dynamic discrete lower bound and other priority rules. These approaches allow to design online and semi online algorithms with the best known worst-case performances.