On-line scheduling mesh jobs with dependencies

AbstractWe study an on-line problem of scheduling parallel jobs on two-dimensional meshes. Parallel jobs arrive dynamically according to the dependencies between them, which are unknown before the jobs appear. Each job may need more than one processor simultaneously and is required to be scheduled on a submesh of the processors which are located on a two-dimensional mesh, i.e., a job must be scheduled on a rectangle of given dimensions. The objective is to minimize the maximum completion time (makespan). We deal with a UET job system, in which all job processing times are equal. We show a lower bound of 3.859 and present a 5.25-competitive algorithm. It significantly improves a previous lower bound of 3.25 and a previous upper bound of 46/7. We consider also the rotated two-dimensional mesh, in which the parallel jobs can be rotated and the rotation of all the jobs is feasible. A lower bound of 3.535 is proven and an on-line algorithm with competitive ratio of at most 4.25 is derived