Cuvillier Verlag

Publications, Dissertations, Habilitations & Brochures.
International Specialist Publishing House for Science and Economy

Cuvillier Verlag

De En Es
Coping with Incomplete Information in Scheduling — Stochastic and Online Models

Hard Copy
EUR 16.00 EUR 15.20

EUR 11.20

Coping with Incomplete Information in Scheduling — Stochastic and Online Models (English shop)

Nicole Megow (Author)


Table of Contents, Datei (34 KB)
Extract, Datei (110 KB)

ISBN-13 (Printausgabe) 3867272387
ISBN-13 (Hard Copy) 9783867272384
ISBN-13 (eBook) 9783736922389
Language English
Page Number 144
Lamination of Cover matt
Edition 1
Volume 0
Publication Place Göttingen
Place of Dissertation Berlin
Publication Date 2007-05-23
General Categorization Dissertation
Departments Mathematics
Keywords combinatorial optimization, scheduling problems, approximation algorithms, stochastic scheduling, online algorithm.

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.