Das Open-Shop Schedulingproblem liegt in der Komplexitatsklasse NP-complete. Ein moglicher Weg zur Entwicklung von neuen Heuristiken zur Losung von Open-Shop Problemen ist die Einschrankung des Suchraums auf effiziente Losungen. Aus diesem Ansatz entwickelte sich die Theorie der Reduzierbarkeit von Open-Shop Planen. Ein Plan heisst irreduzibel, wenn es keinen anderen Plan gibt, der bei beliebiger Wahl der Bearbeitungszeiten einen besseren Zielfunktionswert liefert. In dieser Arbeit wird die Komplexitat des Reduzierbarkeitsproblems (REDUCIBILITY) untersucht. Bekannt ist die Zugehorigkeit von REDUCIBILITY zu NP. Untersucht werden die Bedingungen, unter denen das komplementare Problem IRREDUCIBILITY in NP, und damit in NP ? co-NP = ZPP*, oder sogar in P liegt. Es wird ein Algorithmus vorgestellt, der reduzierbare Plane nichtdeterministisch reduziert, und irreduzible Plane nur unter sehr engen Voraussetzungen nicht als irreduzibel erkennen kann. Die Hinweise auf die Zugehorigkeit von IRREDUCIBILITY zu P oder zu NP- incomplete = NP ? (P + NP-complete) werden diskutiert.

Данное издание не является оригинальным. Книга печатается по технологии принт-он-деманд после получения заказа.