Randomized on-line scheduling on three processors |
| |
| Authors: | Tomá &scaron Tichý |
| |
| Affiliation: | Mathematical Institute, AS CR, ?itná 25, CZ-11567 Praha 1, Czech Republic |
| |
| Abstract: | We consider a randomized on-line scheduling problem where each job has to be scheduled on any of m identical processors. The objective is to minimize the expected makespan. We show that the competitive ratio of any randomized algorithm for m=3 processors must be strictly greater than  . |
| |
| Keywords: | Scheduling Makespan Competitive analysis On-line algorithm Lower bound |
| 本文献已被 ScienceDirect 等数据库收录！ |
