Bitte verwenden Sie diesen Link, um diese Publikation zu zitieren, oder auf sie als Internetquelle zu verweisen: https://hdl.handle.net/10419/147680 
Erscheinungsjahr: 
2007
Schriftenreihe/Nr.: 
Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel No. 627
Verlag: 
Universität Kiel, Institut für Betriebswirtschaftslehre, Kiel
Zusammenfassung: 
The generalized assignment problem (GAP) examines the maximum profit assignment of jobs to processors such that each job is assigned to precisely one processor subject to capacity restrictions on the processors. Due to the fact that the GAP is an NP-hard integer program dual prices are not readily available. In this paper we propose a family of linear programming models the optimal solution of which is integral "almost always". We provide a computational proof of this conjecture by an in-depth experimental study of 1500 instances generated according to the standard procedure adopted in literature. Summarizing this analysis we have linear prices for all but 17 of the whole bunch of instances and, hence, there exists a linear price function that supports the optimal assignment of jobs to processors.
Schlagwörter: 
Generalized assignment problem
integer programming
duality
linear programming
pricing
Dokumentart: 
Working Paper
Dokumentversion: 
Digitized Version

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





Publikationen in EconStor sind urheberrechtlich geschützt.