SPT is optimally competitive for uniprocessor flow |
| |
| Authors: | David P. Bunde |
| |
| Affiliation: | University of Illinois at Urbana-Champaign, Department of Computer Science, 201 N. Goodwin Ave., Urbana, IL 61801, USA |
| |
| Abstract: | We show that the Shortest Processing Time (SPT) algorithm is (Δ+1)/2-competitive for nonpreemptive uniprocessor total flow time with release dates, where Δ is the ratio between the longest and shortest job lengths. This is best possible for a deterministic algorithm and improves on the (Δ+1)-competitive ratio shown by Epstein and van Stee using different methods. |
| |
| Keywords: | Algorithms On-line algorithms Scheduling |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
