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