  We present a scheduler that improves cluster utilization and job completion
times by packing tasks having multi-resource requirements and
inter-dependencies. While the problem is algorithmically very hard, we achieve
near-optimality on the job DAGs that appear in production clusters at a large
enterprise and in benchmarks such as TPC-DS. A key insight is that carefully
handling the long-running tasks and those with tough-to-pack resource needs
will produce good-enough schedules. However, which subset of tasks to treat
carefully is not clear (and intractable to discover). Hence, we offer a search
procedure that evaluates various possibilities and outputs a preferred schedule
order over tasks. An online component enforces the schedule orders desired by
the various jobs running on the cluster. In addition, it packs tasks, overbooks
the fungible resources and guarantees bounded unfairness for a variety of
desirable fairness schemes. Relative to the state-of-the art schedulers, we
speed up 50% of the jobs by over 30% each.
