Single Machine Scheduling: Objectives and Complexity

1. From "Easy" to "Hard": A Conceptual Introduction

The idea that small changes to a problem can dramatically alter its difficulty is a central theme in algorithm design and complexity theory. The following video from MIT OpenCourseWare provides an excellent introduction to this concept and formally defines the key complexity classes.

To summarize and formalize the concepts from the video:

• Class P (Polynomial Time): This class contains "easy" or "tractable" decision problems. An algorithm is polynomial-time if its running time on an input of size $n$ is bounded by $O(n^k)$ for some constant $k$. Problems like sorting a list or finding the shortest path in a graph are in P. The SPT and EDD rules we learned are polynomial-time algorithms.
• Class NP (Nondeterministic Polynomial Time): This class contains decision problems for which a proposed solution (a "certificate") can be verified in polynomial time. For example, for the question "Does this graph have a path that visits every city exactly once?", if someone gives you a path, you can easily check if it's a valid solution in polynomial time. The challenge is finding that path in the first place.
• P versus NP: A major open question in computer science is whether P = NP. It is widely believed that P ≠ NP, meaning there are problems in NP that cannot be solved in polynomial time.
• Class NP-complete: These are the "hardest" problems in NP. If a polynomial-time algorithm were found for any single NP-complete problem, it would mean that all problems in NP could be solved in polynomial time (implying P = NP).
• Class NP-hard: A problem is NP-hard if it is at least as hard as any NP-complete problem. This class includes optimization problems (like minimizing makespan) whose decision versions are NP-complete. When we say a scheduling problem is "hard," we typically mean it is NP-hard.

These definitions are fundamental to a rigorous study of optimization. The following reading provides a concise, text-based summary of these ideas, which will be useful for your thesis.

2. A Concrete Example of Shifting Complexity

Let's return to the MIT video to see these concepts in action. The lecturer demonstrates how a simple problem becomes progressively harder.

This example clearly illustrates the core principle: adding features like job weights or additional resource constraints can fundamentally change a problem's computational nature, moving it from tractable (P) to intractable (NP-hard).

3. The Complexity Landscape of Single Machine Scheduling

Now, let's apply this framework to the single-machine scheduling problems we are studying. The complexity of a problem, defined in the standard $\alpha |\beta |\gamma$ notation, often depends on the choices for the $\beta$ (job characteristics) and $\gamma$ (objective function) fields.

The table below summarizes the complexity of several key single-machine problems. This directly addresses our learning outcome and explains the different solution methods we've seen.

| Problem ($1|\beta |\gamma$) | Complexity | Typical Optimal Algorithm |
| :--- | :--- | :--- |
| Simple Objectives | | |
| 1||ΣC_j | P | SPT Rule ($O(n\log n)$) |
| 1||L_max | P | EDD Rule ($O(n\log n)$) |
| 1||Σw_jC_j | P | WSPT Rule ($O(n\log n)$) |
| Adding Release Dates | | |
| 1|r_j|ΣC_j | Strongly NP-hard | Branch and Bound, MILP |
| 1|r_j|L_max | Strongly NP-hard | Branch and Bound, MILP |
| Minimizing Late Jobs | | |
| 1||ΣU_j | P | Moore-Hodgson Algorithm ($O(n\log n)$) |
| 1||Σw_jU_j | NP-hard | Dynamic Programming (Pseudo-polynomial) |
| Minimizing Tardiness | | |
| 1||ΣT_j | NP-hard | Dynamic Programming (Pseudo-polynomial) |
| 1||Σw_jT_j | Strongly NP-hard | Branch and Bound, MILP |

This table is synthesized from results in the survey papers by Pinedo, and by Gafarov et al., which you can refer to as "An Overview of Some Single Machine Scheduling Problems" (resource LINK).

Key Observations from the Table:

1. Changing the Objective: Simply changing the objective from L_max (in P) to ΣT_j (NP-hard) moves the problem into a different complexity class. This explains why we could use a simple EDD rule for one but needed a full MILP model for the other.
2. Adding Constraints: The 1||L_max problem is easy. However, adding release dates to get 1|r_j|L_max makes it strongly NP-hard. This again shows how a seemingly small modification can have a huge impact.
3. Pseudo-Polynomial vs. Strong NP-hardness: Notice the distinction for the tardiness and late jobs objectives. Problems like 1||ΣT_j and 1||Σw_jU_j are NP-hard, but they can be solved by dynamic programming algorithms whose runtimes depend polynomially on the sum of processing times (e.g., $O(n\sum p_j)$). These are pseudo-polynomial and are only "hard" when the processing times are very large numbers. In contrast, strongly NP-hard problems like 1||Σw_jT_j are considered harder, as they don't have such algorithms.

Conclusion

This lesson provided a formal basis for a practical reality in optimization: some problems are vastly harder than others. Understanding where a problem lies on the complexity spectrum is the first step in selecting an appropriate solution method.

Key Takeaways:

• Scheduling problems can be classified by their computational complexity into classes like P (tractable) and NP-hard (intractable).
• Slight changes to a problem's definition—such as adding release dates, weights, or changing the objective function—can move it from P to NP-hard.
• Problems like 1||ΣC_j and 1||L_max are in P, which is why simple, optimal rules exist.
• Problems like 1||ΣT_j and 1|r_j|L_max are NP-hard, justifying the use of more powerful but less scalable methods like MILP or heuristics.
• The distinction between NP-hard and strongly NP-hard is important, as it relates to whether a pseudo-polynomial time algorithm (like dynamic programming) exists.

Preview of the Next Lesson:
We have now established a strong foundation in the single-machine environment. In the next lesson, we will increase the complexity of the machine environment itself and begin our study of the flow shop. We will start by defining the permutation flow shop problem, understanding its core assumptions, and learning how to visualize its schedules using Gantt charts. This is the first major step toward the more complex job shop and flexible job shop environments central to your research.