Megow | Coping with Incomplete Information in Scheduling — Stochastic and Online Models | E-Book | sack.de
E-Book

E-Book, Englisch, 144 Seiten

Megow Coping with Incomplete Information in Scheduling — Stochastic and Online Models


1. Auflage 2007
ISBN: 978-3-7369-2238-9
Verlag: Cuvillier Verlag
Format: PDF
Kopierschutz: 0 - No protection

E-Book, Englisch, 144 Seiten

ISBN: 978-3-7369-2238-9
Verlag: Cuvillier Verlag
Format: PDF
Kopierschutz: 0 - No protection



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.

Megow Coping with Incomplete Information in Scheduling — Stochastic and Online Models jetzt bestellen!

Autoren/Hrsg.




Ihre Fragen, Wünsche oder Anmerkungen
Vorname*
Nachname*
Ihre E-Mail-Adresse*
Kundennr.
Ihre Nachricht*
Lediglich mit * gekennzeichnete Felder sind Pflichtfelder.
Wenn Sie die im Kontaktformular eingegebenen Daten durch Klick auf den nachfolgenden Button übersenden, erklären Sie sich damit einverstanden, dass wir Ihr Angaben für die Beantwortung Ihrer Anfrage verwenden. Selbstverständlich werden Ihre Daten vertraulich behandelt und nicht an Dritte weitergegeben. Sie können der Verwendung Ihrer Daten jederzeit widersprechen. Das Datenhandling bei Sack Fachmedien erklären wir Ihnen in unserer Datenschutzerklärung.