| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427654 | Information Processing Letters | 2010 | 6 Pages |
Abstract
The single machine semi-online scheduling problem is considered with the assumption that the ratio of the longest processing time to the shortest one is not greater than γ. The goal is to minimize the total weighted completion time. We design a semi-online algorithm and prove that it has a competitive ratio of , which is also shown to be the best performance achieved by any deterministic semi-online algorithm for the problem.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
