The Buffer Minimization Problem for Multiprocessor Scheduling with Conflicts

Abstract

We consider the problem of scheduling a sequence of tasks in a multi-processor system with conflicts. Conflicting processors cannot process tasks at the same time. At certain times new tasks arrive in the system, where each task specifies the amount of work (processing time) added to each processor’s workload. Each processor stores this workload in its input buffer. Our objective is to schedule task execution, obeying the conflict constraints, and minimizing the maximum buffer size of all processors. In the off-line case, we prove that, unless P = NP, the problem does not have a polynomial-time algorithm with a polynomial approximation ratio. In the on-line case, we provide the following results: (i) a competitive algorithm for general graphs, (ii) tight bounds on the competitive ratios for cliques and complete k-partite graphs, and (iii) a (Δ/2 + 1)-competitive algorithm for trees, where Δ is the diameter. We also provide some results for small graphs with up to 4 vertices.