4.17.3 Scheduling

Definition

Given a set of n jobs with processing time t_i, release time r_i, and deadline d_i, is it possible to schedule all jobs on a single machine such that job i is processed with a contiguous slot of ti time units in the interval [r_i,d_i]?

Polynomial Certifier

• Input: Given a set of n jobs, each with processing time t_i, release time r_i, and deadline d_i.
• Certificate: A sequence of jobs with start time.
• Certifier: Check if all requirements are met.
• Time Complexity: O(n).

Reduction from Subset Sum from simple case to general case

Given an instance of SUBSET-SUM w₁,…,w_n and an target W. Create n jobs with processing time t_i = w_i, release time r_i = 0, and no deadline (d_i = 1 + ∑ _jw_j). Create job 0 with t₀ = 1, release time r₀ = W, and deadline d₀ = W + 1.

Subset Sum ⇒ Scheduling

Subset Sum ⇒ Scheduling