We study two related problems in non-preemptive scheduling and packing
of malleable tasks with precedence constraints to minimize the
makespan. We distinguish the scheduling variant, in which we allow the
free choice of processors, and the packing variant, in which a task
must be assigned to a contiguous subset of processors.
For precedence constraints of bounded width, we completely resolve
the complexity status for any particular problem setting concerning
width bound and number of processors, and give polynomial-time
algorithms with best possible performance. For both, scheduling and
packing malleable tasks, we present an FPTAS for the NP-hard
problem variants and exact algorithms for all remaining special
cases. To obtain the positive results, we do not require the common
monotonous penalty assumption on processing times, whereas our
hardness results hold even when assuming this restriction.
With the close relation between contiguous scheduling and strip
packing, our FPTAS is the first (and best possible) constant factor
approximation for (malleable) strip packing under special precedence
constraints.
