UNIVERSITÄTSBIBLIOTHEK

Discrete Parallel Machine Makespan ScheLoc Problem

  • Scheduling-Location (ScheLoc) Problems integrate the separate fields of scheduling and location problems. In ScheLoc Problems the objective is to find locations for the machines and a schedule for each machine subject to some production and location constraints such that some scheduling object- ive is minimized. In this paper we consider the Discrete Parallel Machine Makespan (DPMM) ScheLoc Problem where the set of possible machine loc- ations is discrete and a set of n jobs has to be taken to the machines and processed such that the makespan is minimized. Since the separate location and scheduling problem are both NP-hard, so is the corresponding ScheLoc Problem. Therefore, we propose an integer programming formulation and different versions of clustering heuristics, where jobs are split into clusters and each cluster is assigned to one of the possible machine locations. Since the IP formulation can only be solved for small scale instances we propose several lower bounds to measure the quality of the clustering heuristics. Ex- tensive computational tests show the efficiency of the heuristics.

Volltext Dateien herunterladen

Metadaten exportieren

Metadaten
Verfasserangaben:Corinna Heßler, Kaouthar Deghdak
URN (Permalink):urn:nbn:de:hbz:386-kluedo-41297
Schriftenreihe (Bandnummer):Report in Wirtschaftsmathematik (WIMA Report) (157)
Dokumentart:Preprint
Sprache der Veröffentlichung:Englisch
Veröffentlichungsdatum (online):27.07.2015
Jahr der Veröffentlichung:2015
Veröffentlichende Institution:Technische Universität Kaiserslautern
Datum der Publikation (Server):28.07.2015
Seitenzahl:24
Fachbereiche / Organisatorische Einheiten:Fachbereich Mathematik
DDC-Sachgruppen:5 Naturwissenschaften und Mathematik / 510 Mathematik
Lizenz (Deutsch):Standard gemäß KLUEDO-Leitlinien vom 13.02.2015