  Due to the ubiquity of batch data processing in cloud computing, the related
problem of scheduling malleable batch tasks and its extensions have received
significant attention recently. In this paper, we consider a fundamental model
where a set of n tasks is to be processed on C identical machines and each task
is specified by a value, a workload, a deadline and a parallelism bound. Within
the parallelism bound, the number of machines assigned to a task can vary over
time without affecting its workload. For this model, we obtain two core
results: a sufficient and necessary condition such that a set of tasks can be
finished by their deadlines on C machines, and an algorithm to produce such a
schedule. These core results provide a conceptual tool and an optimal
scheduling algorithm that enable proposing new algorithmic analysis and design
and improving existing algorithms under various objectives.
