Move-optimal schedules for parallel machines to minimize total weighted completion time

T. Brueggemann, Johann L. Hurink, Walter Kern

Research output: Book/ReportReportProfessional

14 Downloads (Pure)

Abstract

We study the minimum total weighted completion time problem on identical machines, which is known to be strongly $\mathcal{NP}$-hard. We analyze a simple local search heuristic, moving jobs from one machine to another. The local optima can be shown to be approximately optimal with approximation ratio $1.5$. In case all jobs have equal Smith ratios, the approximation ratio is at most $1.092$.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Number of pages13
ISBN (Print)0169-2690
Publication statusPublished - 2005

Publication series

NameMemorandum Afdeling TW
PublisherDepartment of Applied Mathematics, University of Twente
No.1748
ISSN (Print)0169-2690

Keywords

  • MSC-90B35
  • METIS-225250
  • IR-65932
  • EWI-3568

Cite this

Brueggemann, T., Hurink, J. L., & Kern, W. (2005). Move-optimal schedules for parallel machines to minimize total weighted completion time. (Memorandum Afdeling TW; No. 1748). Enschede: University of Twente, Department of Applied Mathematics.
Brueggemann, T. ; Hurink, Johann L. ; Kern, Walter. / Move-optimal schedules for parallel machines to minimize total weighted completion time. Enschede : University of Twente, Department of Applied Mathematics, 2005. 13 p. (Memorandum Afdeling TW; 1748).
@book{12b28bd4493f4144a42e95ca71545549,
title = "Move-optimal schedules for parallel machines to minimize total weighted completion time",
abstract = "We study the minimum total weighted completion time problem on identical machines, which is known to be strongly $\mathcal{NP}$-hard. We analyze a simple local search heuristic, moving jobs from one machine to another. The local optima can be shown to be approximately optimal with approximation ratio $1.5$. In case all jobs have equal Smith ratios, the approximation ratio is at most $1.092$.",
keywords = "MSC-90B35, METIS-225250, IR-65932, EWI-3568",
author = "T. Brueggemann and Hurink, {Johann L.} and Walter Kern",
note = "Imported from MEMORANDA",
year = "2005",
language = "Undefined",
isbn = "0169-2690",
series = "Memorandum Afdeling TW",
publisher = "University of Twente, Department of Applied Mathematics",
number = "1748",

}

Brueggemann, T, Hurink, JL & Kern, W 2005, Move-optimal schedules for parallel machines to minimize total weighted completion time. Memorandum Afdeling TW, no. 1748, University of Twente, Department of Applied Mathematics, Enschede.

Move-optimal schedules for parallel machines to minimize total weighted completion time. / Brueggemann, T.; Hurink, Johann L.; Kern, Walter.

Enschede : University of Twente, Department of Applied Mathematics, 2005. 13 p. (Memorandum Afdeling TW; No. 1748).

Research output: Book/ReportReportProfessional

TY - BOOK

T1 - Move-optimal schedules for parallel machines to minimize total weighted completion time

AU - Brueggemann, T.

AU - Hurink, Johann L.

AU - Kern, Walter

N1 - Imported from MEMORANDA

PY - 2005

Y1 - 2005

N2 - We study the minimum total weighted completion time problem on identical machines, which is known to be strongly $\mathcal{NP}$-hard. We analyze a simple local search heuristic, moving jobs from one machine to another. The local optima can be shown to be approximately optimal with approximation ratio $1.5$. In case all jobs have equal Smith ratios, the approximation ratio is at most $1.092$.

AB - We study the minimum total weighted completion time problem on identical machines, which is known to be strongly $\mathcal{NP}$-hard. We analyze a simple local search heuristic, moving jobs from one machine to another. The local optima can be shown to be approximately optimal with approximation ratio $1.5$. In case all jobs have equal Smith ratios, the approximation ratio is at most $1.092$.

KW - MSC-90B35

KW - METIS-225250

KW - IR-65932

KW - EWI-3568

M3 - Report

SN - 0169-2690

T3 - Memorandum Afdeling TW

BT - Move-optimal schedules for parallel machines to minimize total weighted completion time

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -

Brueggemann T, Hurink JL, Kern W. Move-optimal schedules for parallel machines to minimize total weighted completion time. Enschede: University of Twente, Department of Applied Mathematics, 2005. 13 p. (Memorandum Afdeling TW; 1748).