Quality of move-optimal schedules for minimizing total weighted completion time. Brueggemann, T., Hurink, J. L., & Kern, W. Operations Research Letters, 34(5):583--590, September, 2006.
Quality of move-optimal schedules for minimizing total weighted completion time [link]Paper  doi  abstract   bibtex   
We study the minimum total weighted completion time problem on identical machines. 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 3 2 . In a special case, the approximation ratio is 3 2 - 1 / 6 ≈ 1.092 .
@article{brueggemann_quality_2006,
	title = {Quality of move-optimal schedules for minimizing total weighted completion time},
	volume = {34},
	issn = {0167-6377},
	url = {http://www.sciencedirect.com/science/article/pii/S0167637705001021},
	doi = {10.1016/j.orl.2005.08.003},
	abstract = {We study the minimum total weighted completion time problem on identical machines. 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 3 2 . In a special case, the approximation ratio is 3 2 - 1 / 6 ≈ 1.092 .},
	number = {5},
	urldate = {2014-01-20TZ},
	journal = {Operations Research Letters},
	author = {Brueggemann, Tobias and Hurink, Johann L. and Kern, Walter},
	month = sep,
	year = {2006},
	keywords = {Approximation, Total weighted completion time, parallel machines},
	pages = {583--590}
}

Downloads: 0