  In malleable job scheduling, jobs can be executed simultaneously on multiple
machines with the processing time depending on the number of allocated
machines. In this setting, jobs are required to be executed non-preemptively
and in unison, in the sense that they occupy, during their execution, the same
time interval over all the machines of the allocated set. In this work, we
study generalizations of malleable job scheduling inspired by standard
scheduling on unrelated machines. Specifically, we introduce a general model of
malleable job scheduling, where each machine has a (possibly different) speed
for each job, and the processing time of a job $j$ on a set of allocated
machines $S$ depends on the total speed of $S$ with respect to $j$. For
machines with unrelated speeds, we show that the optimal makespan cannot be
approximated within a factor less than $\frac{e}{e-1}$, unless $P = NP$. On the
positive side, we present polynomial-time algorithms with approximation ratios
$\frac{2e}{e-1}$ for machines with unrelated speeds, $3$ for machines with
uniform speeds, and $7/3$ for restricted assignments on identical machines. Our
algorithms are based on deterministic LP rounding. They result in sparse
schedules, in the sense that each machine shares at most one job with other
machines. We also prove lower bounds on the integrality gap of $1+\varphi$ for
unrelated speeds ($\varphi$ is the golden ratio) and $2$ for uniform speeds and
restricted assignments. To indicate the generality of our approach, we show
that it also yields constant factor approximation algorithms for a variant
where we determine the effective speed of a set of allocated machines based on
the $L_p$ norm of their speeds.
