Scheduling and packing malleable and parallel tasks with precedence constraints of bounded width
We study the problems of non-preemptively scheduling and packing malleable and parallel tasks with precedence constraints to minimize the makespan. In the scheduling variant, we allow the free choice of processors; in packing, each task must be assigned to a contiguous subset. Malleable tasks can be processed on different numbers of processors with varying processing times, while parallel tasks require a fixed number of processors.
scheduling malleable parallel precedence constraints makespan approximation