Bitte verwenden Sie diesen Link, um diese Publikation zu zitieren, oder auf sie als Internetquelle zu verweisen: https://hdl.handle.net/10419/149839 
Autor:innen: 
Erscheinungsjahr: 
1996
Schriftenreihe/Nr.: 
Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel No. 390
Verlag: 
Universität Kiel, Institut für Betriebswirtschaftslehre, Kiel
Zusammenfassung: 
Complexity proofs often restrict themselves to stating that the problem at hand is a generalization of some other intractable problem, This proof technique relies on the widely accepted assumptions 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 (1995) showed that for at least one model formulation of the discrete lotsizing and scheduling problem (DLSP) and certain, pathological instances the corresponding decision problem cannot be a member of NP; therefore that DLSP-model is exponential.With respect to the field of resource-constrained project scheduling, the question arises whether here this or a similar Situation may occur as well. We extend the findings of Brüggemann to the Single mode project scheduling problem (SMPSP) where we prove the well-known binary programming model of the SMPSP to be exponential as well - regardless of the particular encoding used. In addition, we demonstrate that this result can be improved to a strongly NP-equivalence result by adding one moderate restriction on the problem parameters.
Schlagwörter: 
Resource-Constrained Project Scheduling
Computational Complexity
Dokumentart: 
Working Paper
Dokumentversion: 
Digitized Version

Datei(en):
Datei
Größe
707.06 kB





Publikationen in EconStor sind urheberrechtlich geschützt.