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.

Download full text files

Export metadata

Metadaten
Author:Corinna Heßler, Kaouthar Deghdak
URN:urn:nbn:de:hbz:386-kluedo-41297
Series (Serial Number):Report in Wirtschaftsmathematik (WIMA Report) (157)
Document Type:Preprint
Language of publication:English
Date of Publication (online):2015/07/27
Year of first Publication:2015
Publishing Institution:Technische Universität Kaiserslautern
Date of the Publication (Server):2015/07/28
Page Number:24
Faculties / Organisational entities:Kaiserslautern - Fachbereich Mathematik
DDC-Cassification:5 Naturwissenschaften und Mathematik / 510 Mathematik
Licence (German):Standard gemäß KLUEDO-Leitlinien vom 13.02.2015