Home About Upload Latest Additions Statistics Contact
UT Proceedings
UT Student Theses
Dutch Academic Output Dutch Dissertations EU Publications (OpenAIRE)
Printversion
Advanced search

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

Share/Save/Bookmark

Brueggemann, T. and Hurink, J.L. and Kern, W. (2005) Move-optimal schedules for parallel machines to minimize total weighted completion time. [Report]

[img]
Preview
PDF
181Kb
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$.
Item Type:Report
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/65932
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 225250