Partitioning with Deadline