Bitte verwenden Sie diesen Link, um diese Publikation zu zitieren, oder auf sie als Internetquelle zu verweisen: https://hdl.handle.net/10419/149840 
Autor:innen: 
Erscheinungsjahr: 
1996
Schriftenreihe/Nr.: 
Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel No. 391
Verlag: 
Universität Kiel, Institut für Betriebswirtschaftslehre, Kiel
Zusammenfassung: 
NP-completeness and other complexity proofs often merely State that the problem at hand is a generalization of some other intractable problem. This proof technique relies on the widely accepted assumption that complexity results hold regardless of the model formulation used to represent the problem and the encoding used to represent its instances. However, recent results indicate that these assumptions are not always justified. Brüggemann and Jahnke (1996) show that for at least one model formulation of the feasibility variant of the discrete lotsizing and scheduling problem (DLSP) the Standard technique of proving NP-completeness fails even though the problem itself is NP-complete. With respect to the field of resource-constrained project scheduling, the question arises whether this or similar situations may occur as well. We extend the findings on the DLSP to two multi-mode project scheduling problems where the most striking result is that the well-known binary programming model of one of these is exponential - regardless of the encoding used. We also show under what circum-stances better-than-exponential results can still be achieved, showing the models to be strongly NP-equivalent.
Schlagwörter: 
Resource-Constrained Project Scheduling
Computational Complexity
Dokumentart: 
Working Paper
Dokumentversion: 
Digitized Version

Datei(en):
Datei
Größe





Publikationen in EconStor sind urheberrechtlich geschützt.