Scheduling tall and small unit length jobs or P|rj;pj=1;sizej∈{1,m};Dj|-

We are given n jobs. Each job has an integer release time before which it is not available, a strict integer deadline by which it has to complete, and each job has the same unit processing time p. Some of the jobs (small) need to be scheduled in a single machine, some of the jobs (tall) need to be scheduled on all machines at the same time. We wish to find a feasible schedule on m machines.


Number of machines
Release times/deadlines for small jobs
.. and for tall jobs