We present a new approach to fair-share, deadline-aware job scheduling for resource-limited cloud deployments that are managed by “big data” framework resource negotiators (e.g. YARN and Mesos), called Justice. Justice provides admission control that leverages historical traces and job deadline information to guide and adapt resource allocation decisions to changing workload conditions. We evaluate Justice using different deadline types and production analytics workloads. We find that it outperforms extant allocators in terms of fair allocation, deadline satisfaction, and useful work, among other metrics.