Quality of move-optimal schedules for minimizing total weighted completion time |
| |
| Authors: | Tobias Brueggemann Johann L Hurink |
| |
| Institution: | Department of Applied Mathematics, University of Twente, P.O. Box 217, 7500 AE Enschede, The Netherlands |
| |
| 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  . In a special case, the approximation ratio is  . |
| |
| Keywords: | 90B35 |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
