In the Grid Scheduling problem, there is a set of jobs each with a positive integral memory requirement. Processors arrive in an online manner and each is assigned a maximal subset of the remaining jobs such that the sum of the memory requirements of those jobs does not exceed the processor's memory capacity. The goal is to assign all the jobs to processors so as to minimize the sum of the memory capacities of the processors that are assigned at least one job. Previously, a lower bound of 5/4 on the competitive ratio of this problem was achieved using jobs of size S and 2S-1. For this case, we obtain matching upper and lower bounds, which vary depending on the ratio of the number of small jobs to the number of large jobs.
Last modified: Thu Aug 22 10:09:54 CEST 2013