Semi on-line scheduling on three processors with known sum of the tasks

摘要

We consider a semi on-line version of the multiprocessor scheduling problem on three processors, where the total size of the tasks is known in advance. We prove a lower bound 1 + √129-9/6 > 1.3929 on the competitive ratio of any algorithm and propose a simple algorithm with competitive ratio equal to 1.5. The performance is improved to 1 + 8/19 < 1.4211 by a preprocessing strategy. The latter algorithm is only 2% away from the lower bound.