Michael Andresen

Zur Komplexität der Reduzierbarkeit von Open-Shop-Plänen

Erkennung effizienter Pläne: Beschreibung mittels H-Comparabilitygraphen und Analyse der Zeitkomplexität

• Broschiertes Buch

Produktbeschreibung

Das Open-Shop Schedulingproblem liegt in der Komplexitätsklasse NP-complete. Ein möglicher Weg zur Entwicklung von neuen Heuristiken zur Lösung von Open-Shop Problemen ist die Einschränkung des Suchraums auf effiziente Lösungen. Aus diesem Ansatz entwickelte sich die Theorie der Reduzierbarkeit von Open-Shop Plänen. Ein Plan heißt irreduzibel, wenn es keinen anderen Plan gibt, der bei beliebiger Wahl der Bearbeitungszeiten einen besseren Zielfunktionswert liefert. In dieser Arbeit wird die Komplexität des Reduzierbarkeitsproblems (REDUCIBILITY) untersucht. Bekannt ist die Zugehörigkeit von REDUCIBILITY zu NP. Untersucht werden die Bedingungen, unter denen das komplementäre Problem IRREDUCIBILITY in NP, und damit in NP _ co-NP = ZPP , oder sogar in P liegt. Es wird ein Algorithmus vorgestellt, der reduzierbare Pläne nichtdeterministisch reduziert, und irreduzible Pläne nur unter sehr engen Voraussetzungen nicht als irreduzibel erkennen kann. Die Hinweise auf die Zugehörigkeit von IRREDUCIBILITY zu P oder zu NP- incomplete = NP _ (P + NP-complete) werden diskutiert.

---

Hinweis: Dieser Artikel kann nur an eine deutsche Lieferadresse ausgeliefert werden.

Produktdetails

• Verlag: Südwestdeutscher Verlag für Hochschulschriften
• Seitenzahl: 304
• Erscheinungstermin: 8. November 2015
• Deutsch
• Abmessung: 220mm x 150mm x 19mm
• Gewicht: 471g
• ISBN-13: 9783838117980
• ISBN-10: 3838117980
• Artikelnr.: 31625924

Autorenporträt

Studium und Promotion an der Otto-von-Guericke-Universität Magdeburg (Promotionsstipendium des Landes Sachsen-Anhalt). Anschließende Tätigkeit als wissenschaftlicher Mitarbeiter am Institut für Algebra und Geometrie.