Suppose you're managing a collection of processors and must schedule a sequence of job...

Suppose you're managing a collection of processors and must schedule a sequence of jobs over time.

The jobs have the following characteristics. Each job j has an arrival time aj when it is first available for processing, a length lj which indicates how much processing time it needs, and a deadline dj by which it must be finished. (We'll assume 0 lj

Moreover, the collection of processors is not entirely static either: You have an overall pool of k possible processors; but for each processor i, there is an interval of time [ti, ti'] during which it is available; it is unavailable at all other times.

Given all this data about job requirements and processor availability, you'd like to decide whether the jobs can all be completed or not. Give a polynomial-time algorithm that either produces a schedule completing all jobs by their deadlines or reports (correctly) that no such schedule exists. You may assume that all the parameters associated with the problem are integers.

Example. Suppose we have two jobs J1 and J2. J1 arrives at time 0, is due at time 4, and has length 3. J2 arrives at time 1, is due at time 3, and has length 2. We also have two processors P1 and P2. P1 is available between times 0 and 4; P2 is available between times 2 and 3. In this case, there is a schedule that gets both jobs done.

• At time 0, we start job J1 on processor P1

• At time 1, we preempt J1 to start J2 on P1.

• At time 2, we resume J1 on P2.(J2 continues processing on P1.)

• At time 3, J2 completes by its deadline. P2 ceases to be available, so we move J1 back to P1 to finish its remaining one unit of processing there.

• At time 4, J1 completes its processing on P1.

Notice that there is no solution that does not involve preemption and moving of jobs.