Coping with Incomplete Information in Scheduling — Stochastic and Online Models

Vorschau

Inhaltsverzeichnis, Datei (34 KB)
Leseprobe, Datei (110 KB)

Incomplete information is an omnipresent issue when dealing with real-world optimization problems. Typically, such limitations concern the uncertainty of given data or the complete lack of knowledge about future parts of a problem instance. This thesis is devoted to investigations on how to cope with incomplete information when solving scheduling problems. These problems involve the temporal allocation of limited resources for executing activities so as to optimize some objective. Scheduling problems are apparent in many applications including, for example, manufacturing and service industries but also compiler optimization and parallel computing.

There are two major frameworks for modeling limited information in the theory of optimization. One deals with “stochastic information”, the other with “online information”. We design algorithms for NP-hard scheduling problems in both, the online and the stochastic scheduling models. Thereby, we provide first constant performance guarantees orimprove previously best known results.

Both frameworks have their legitimacy depending on the actual application. Nevertheless, problem settings are conceivable that comprise both, uncertain information about the data set and the complete lack of knowledge about the future. This rouses the need for a generalized model that integrates both traditional information environments. Such a general model is designed as a natural extension that combines stochastic and online information. But the challenging question is whether there exists any algorithm that can perform well in such a restricted information environment. More precisely, is there an algorithm that yields a constant performance guarantee? We successfully treat this intriguing question and give a positive answer by providing such algorithms for machine scheduling problems. In fact, our results are competitive with the performance guarantees best known in the traditional settings of stochastic and online scheduling. Thus, they do not only justify the generalized model but also imply – at least in the considered problem settings – that optimization in the general model with incomplete information does not necessarily mean to give up performance.