TL;DR
This paper proves that scheduling jobs on a single machine with release times, deadlines, and two different non-unit job lengths is NP-complete. This is a significant result because it establishes a sharp boundary: while scheduling with identical job lengths or unit job lengths is efficient, introducing just one additional non-unit job length makes the problem computationally intractable.
What Problem Does This Paper Address?
The paper tackles a fundamental problem in scheduling theory: how to optimally schedule a set of jobs on a single machine, given that each job has a specific time it can start (release time) and a time by which it must finish (deadline). This is known as the $1|r_i|L_{max}$ problem, where the goal is to minimize the maximum lateness (how much any job misses its deadline).
While the general problem is NP-hard, researchers have found efficient (polynomial-time) solutions for specific cases. For instance, if all jobs have the same processing time (length), or if all jobs have a unit length (length 1), efficient algorithms exist. The question that remained open was: what happens if we allow jobs to have two different non-unit lengths? Can we still solve this efficiently? This paper answers that question by showing that even with just two distinct non-unit job lengths, the problem becomes NP-complete.
Methods
The authors prove their main result, Theorem 1, by establishing two key lemmas:
- Reduction from an Auxiliary Problem (AUX(p,q)): They show that a newly defined auxiliary scheduling problem, AUX(p,q), can be efficiently transformed into the original scheduling problem with two non-unit job lengths ($p$ and $q$, where $p > q > 1$). This auxiliary problem involves "pending jobs" with both early and late deadlines, creating complex dependencies.
- NP-Completeness of AUX(p,q): They prove that the AUX(p,q) problem itself is NP-complete by reducing it from the Boolean Satisfiability (SAT) problem. This reduction involves constructing specific "blocks" of jobs (literal blocks and clause blocks) that encode the logical structure of a SAT formula. The scheduling of these blocks and their dependencies then mirrors the satisfiability of the formula.
The core of the NP-completeness proof for AUX(p,q) lies in a clever encoding of SAT clauses. Each literal in a SAT formula is represented by a "section" of jobs, and each clause is represented by "clause blocks" within these sections. The timing and deadline constraints of these blocks are designed such that a feasible schedule exists if and only if the SAT formula is satisfiable. Specifically, the "pending jobs" in these blocks are crucial: their ability to meet early deadlines is linked to whether a literal is true or false, and the overall feasibility hinges on satisfying all clauses.
Datasets
Not discussed in the paper. The paper focuses on theoretical complexity and uses reductions from abstract problems (like SAT) rather than empirical datasets.
Key Insights and Ideas
- Sharp Complexity Boundary: The paper demonstrates a very precise boundary for efficient solvability. Allowing identical job lengths or unit job lengths is efficient, but introducing any two distinct non-unit job lengths immediately pushes the problem into NP-completeness. This highlights how sensitive scheduling complexity can be to the structure of job properties.
- Sophisticated Reduction for AUX(p,q): The construction of the AUX(p,q) problem and its reduction from SAT is a key technical contribution. The use of "pending jobs" with dual deadlines and the careful design of "literal" and "clause" blocks to encode logical constraints are novel and intricate.
- Dependencies as the Source of Hardness: The proof relies heavily on creating complex dependencies between jobs. These dependencies are not just simple release times and deadlines but also involve pairs of jobs that must satisfy one of two deadlines, and these pairs are linked across different parts of the schedule. This intricate web of constraints is what makes the problem hard.
- Implications for Practical Solvability: Since the problem is proven to be NP-complete even for fixed, small non-unit job lengths (like $p=4, q=2$), it implies that for general instances with two non-unit job lengths, we cannot expect to find a polynomial-time algorithm. This suggests that for practical applications, approximation algorithms or heuristics will be necessary.
Key Results
- Theorem 1: The scheduling problem with release times, deadlines, and two non-unit job lengths ($p > q > 1$) is NP-complete. This is a strong result, implying it's also strongly NP-complete.
- Lemma 1: The auxiliary problem AUX(p,q) is polynomial-time reducible to the original scheduling problem with two non-unit job lengths.
- Lemma 2: The auxiliary problem AUX(p,q) is NP-complete.
- The paper provides a formal reduction from Boolean Satisfiability (SAT) to AUX(p,q).
Limitations and Future Work
- Specific Job Lengths: The proof of NP-completeness is for any fixed pair of non-unit job lengths $p > q > 1$. The paper doesn't explore the complexity for cases where $q=1$ and $p>1$ (which is known to be solvable) or the case where $p$ and $q$ are related in specific ways (e.g., $p$ is a multiple of $q$).
- Pseudo-polynomial Algorithms: The paper's result contradicts a claim of a pseudo-polynomial time algorithm for the $\{q, 2q\}$ case by Vakhania (2004). This suggests that such algorithms might not exist or the claim was based on a misunderstanding.
- Generalization: The paper focuses on a single machine. Extending these results to multiple machines or other scheduling environments with two non-unit job lengths would be a natural next step.
- Preemption: The current result is for non-preemptive scheduling. The impact of allowing preemption with two non-unit job lengths is not explored.
- Open Problems: The paper implicitly opens up research into understanding the exact complexity landscape for different combinations of job lengths and scheduling environments. The discussion mentions that the $\{1, p\}$ problem is "maximally theoretically solvable," suggesting a broader research direction on characterizing solvable scheduling problems.
Summary updated