Preemptive scheduling algorithms with nested processing set restriction

We consider the problem of preemptively scheduling n independent jobs {J₁, J₂, ..., J_n} on m parallel machines {M₁, M₂, ..., M_m}, where each job J_j can only be processed on a prespecified subset Mj of machines called its processing set. The machines are linearly ordered, and the processing set of J_j is specified by two machine indexes a_j and b _j; i.e., Mj = { Ma_j, Ma_j + 1, ... Mb _j}. The processing sets are nested; i.e., for i ≠ j, we have Mi⊆Mj, or Mj ⊆Mi, or Mj ∩ Mi = 0. Our goal is to minimize the makespan. We first give an O(n log n)-time algorithm to find an optimal schedule. We then give an O(mn + n log n)-time algorithm to find a maximal schedule, where a schedule is said to be maximal if it processes as much work as any other schedule in any time interval [0, t], t > 0.