[Model] TimetableDesign

[isPANN]

Motivation

TIMETABLE DESIGN (P203) from Garey & Johnson, A5 SS19. A classical NP-complete problem modeling the assignment of craftsmen to tasks across work periods, subject to availability and requirement constraints. Shown NP-complete by Even, Itai, and Shamir (1976) even in a very restricted form (|H|=3, all R(c,t) in {0,1}). This is the foundational hardness result for all timetabling and scheduling problems in education and workforce management.

Associated rules:

• R148: 3SAT -> Timetable Design (incoming, [Even, Itai, and Shamir, 1976])

Definition

Name: TimetableDesign
Problem type: SatisfactionProblem (Metric = bool)

Reference: Garey & Johnson, Computers and Intractability, A5 SS19

Mathematical definition:

INSTANCE: Set H of "work periods," set C of "craftsmen," set T of "tasks," a subset A(c) ⊆ H of "available hours" for each craftsman c ∈ C, a subset A(t) ⊆ H of "available hours" for each task t ∈ T, and, for each pair (c,t) ∈ C×T, a number R(c,t) ∈ Z0+ of "required work periods."
QUESTION: Is there a timetable for completing all the tasks, i.e., a function f: C×T×H → {0,1} (where f(c,t,h) = 1 means that craftsman c works on task t during period h) such that (1) f(c,t,h) = 1 only if h ∈ A(c)∩A(t), (2) for each h ∈ H and c ∈ C there is at most one t ∈ T for which f(c,t,h) = 1, (3) for each h ∈ H and t ∈ T there is at most one c ∈ C for which f(c,t,h) = 1, and (4) for each pair (c,t) ∈ C×T there are exactly R(c,t) values of h for which f(c,t,h) = 1?

Variables

• Count: |C| * |T| * |H| (one binary variable per craftsman-task-period triple)
• Per-variable domain: {0, 1} — whether craftsman c works on task t during period h
• Meaning: f(c,t,h) = 1 if craftsman c is assigned to task t during work period h; 0 otherwise. The constraints ensure: (1) assignments respect availability windows, (2) each craftsman works on at most one task per period, (3) each task has at most one craftsman per period, and (4) total work on each (c,t) pair meets the requirement R(c,t).

Schema (data type)

Type name: TimetableDesign
Variants: none (no type parameters; all values are non-negative integers)

Field	Type	Description
num_periods	usize	Number of work periods
num_craftsmen	usize	Number of craftsmen
num_tasks	usize	Number of tasks
craftsman_avail	Vec<Vec<bool>>	A(c): for each craftsman, which periods are available
task_avail	Vec<Vec<bool>>	A(t): for each task, which periods are available
requirements	Vec<Vec<u64>>	R(c,t): required work periods for each (craftsman, task) pair

Complexity

• Best known exact algorithm: The problem is NP-complete (Even, Itai, and Shamir, 1976). It remains NP-complete even when |H| = 3, A(t) = H for all tasks, and all R(c,t) in {0,1}. In the general case, brute-force enumeration of all valid f functions requires O*(2^(|C||T||H|)) time. For the restricted case with |A(c)| <= 2 for all c, or when A(c) = A(t) = H for all c and t, the problem is solvable in polynomial time via bipartite matching. No known exact algorithm significantly improves upon O*(2^(|C||T||H|)) in the worst case.
• declare_variants! complexity string: "2^(num_craftsmen * num_tasks * num_periods)"

Extra Remark

Full book text:

INSTANCE: Set H of "work periods," set C of "craftsmen," set T of "tasks," a subset A(c) ⊆ H of "available hours" for each craftsman c ∈ C, a subset A(t) ⊆ H of "available hours" for each task t ∈ T, and, for each pair (c,t) ∈ C×T, a number R(c,t) ∈ Z0+ of "required work periods."
QUESTION: Is there a timetable for completing all the tasks, i.e., a function f: C×T×H → {0,1} (where f(c,t,h) = 1 means that craftsman c works on task t during period h) such that (1) f(c,t,h) = 1 only if h ∈ A(c)∩A(t), (2) for each h ∈ H and c ∈ C there is at most one t ∈ T for which f(c,t,h) = 1, (3) for each h ∈ H and t ∈ T there is at most one c ∈ C for which f(c,t,h) = 1, and (4) for each pair (c,t) ∈ C×T there are exactly R(c,t) values of h for which f(c,t,h) = 1?

Reference: [Even, Itai, and Shamir, 1976]. Transformation from 3SAT.

Comment: Remains NP-complete even if |H| = 3, A(t) = H for all t ∈ T, and each R(c,t) ∈ {0,1}. The general problem can be solved in polynomial time if |A(c)| ≤ 2 for all c ∈ C or if A(c) = A(t) = H for all c ∈ C and t ∈ T.

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all valid assignment functions f: C x T x H -> {0,1} satisfying constraints (1)-(4); check feasibility.)
• It can be solved by reducing to integer programming. (Binary ILP: f(c,t,h) in {0,1} with constraints for availability, one-task-per-craftsman-per-period, one-craftsman-per-task-per-period, and requirement satisfaction.)
• Other: For special cases (|A(c)| <= 2 or A(c)=A(t)=H), reduce to bipartite matching.

Example Instance

Input:
H = {h₁, h₂, h₃} (3 work periods)
C = {c₁, c₂, c₃, c₄, c₅} (5 craftsmen)
T = {t₁, t₂, t₃, t₄, t₅} (5 tasks)

Craftsman availability:

• A(c₁) = {h₁, h₂, h₃}, A(c₂) = {h₁, h₂}, A(c₃) = {h₂, h₃}, A(c₄) = {h₁, h₃}, A(c₅) = {h₁, h₂, h₃}

Task availability:

• A(t₁) = {h₁, h₂}, A(t₂) = {h₂, h₃}, A(t₃) = {h₁, h₃}, A(t₄) = {h₁, h₂, h₃}, A(t₅) = {h₁, h₂, h₃}

Requirements (R(c,t)):

c \ t	t₁	t₂	t₃	t₄	t₅
c₁	1	0	1	0	0
c₂	0	1	0	0	1
c₃	0	0	0	1	0
c₄	0	0	0	0	1
c₅	0	1	0	0	0

Note: Tasks t₁, t₂, and t₃ have restricted availability windows, creating tight scheduling constraints. In particular, A(c₂) ∩ A(t₂) = {h₂} forces c₂ to work on t₂ during h₂, cascading into further forced assignments.

Feasible timetable:

• h₁: f(c₁, t₁, h₁) = 1, f(c₂, t₅, h₁) = 1
• h₂: f(c₂, t₂, h₂) = 1, f(c₃, t₄, h₂) = 1
• h₃: f(c₁, t₃, h₃) = 1, f(c₄, t₅, h₃) = 1, f(c₅, t₂, h₃) = 1

All constraints satisfied: (1) every assignment respects A(c) ∩ A(t), (2) no craftsman is double-booked in any period, (3) no task has two craftsmen in the same period, and (4) all requirements R(c,t) are exactly met. Answer: YES.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph; classic scheduling/timetabling problem
Non-trivial	✅ Pass	Distinct feasibility constraints from all existing problems
Correctness	✅ Pass	Reference verified; example schedule is correct
Well-written	⚠️ Warn	Minor issues: complexity bound uses wrong variable count; example could be more challenging

Overall: 3 passed, 0 failed, 1 warning

---

Usefulness

TimetableDesign does not exist in the codebase. It is a classic NP-complete problem from Garey & Johnson (A5 SS19) with strong practical relevance to education scheduling and workforce management. The issue mentions an associated rule (3SAT -> TimetableDesign) which would connect it to the reduction graph. Brute-force and ILP solvers are both identified. Pass.

Non-trivial

The problem has genuinely distinct feasibility constraints: three-dimensional binary assignment (craftsmen x tasks x periods) with availability windows, mutual exclusion in two dimensions (one task per craftsman per period, one craftsman per task per period), and exact requirement satisfaction. This is not a variant or relabeling of any existing problem in the codebase. Pass.

Correctness

References:

• Even, Itai, and Shamir (1976) — "On the Complexity of Timetable and Multicommodity Flow Problems," SIAM Journal on Computing, 5, 691–703. ✅ Verified. The paper establishes NP-completeness of the timetable problem via reduction from satisfiability. The claim that it remains NP-complete even when |H|=3 and R(c,t) in {0,1} is consistent with the paper's results.

• Garey & Johnson (1979) — Computers and Intractability, A5 SS19. ✅ Consistent with the standard reference.

Example verification: ✅ All four constraints verified manually:

1. Availability: all assignments respect A(c) ∩ A(t) windows.
2. One task per craftsman per period: no craftsman is double-booked.
3. One craftsman per task per period: no task has two craftsmen in the same period.
4. Requirements: all R(c,t) values are exactly met.

Complexity: The issue states "O*(2^(|C||T|))" as the brute-force bound, but the actual variable count is |C||T||H| (as correctly stated in the Variables section), so the brute-force bound should be O(2^(|C||T||H|)). This is a minor inconsistency but does not affect correctness of the problem definition itself. Pass (with note).

Well-written

4a: Information Completeness — All required template sections are present and substantive. ✅

4b: Definition Completeness — The formal definition is directly from Garey & Johnson, mathematically well-formed, with all constraints explicitly stated. This is a satisfaction problem (Metric = bool), consistent with the decision formulation. ✅

4c: Symbol and Notation Consistency:

• Symbols H, C, T, A(c), A(t), R(c,t), f(c,t,h) are consistent across all sections. ✅
• The Schema field names (num_periods, num_craftsmen, num_tasks, craftsman_avail, task_avail, requirements) are clear and map to the mathematical definition. ✅
• Minor issue: the Complexity section says "O*(2^(|C||T|))" but should be "O(2^(|C||T||H|))" to match the variable count. ⚠️

4d: Example Quality:

• The example has 5 craftsmen, 5 tasks, and 3 periods — reasonable size. ✅
• The schedule is fully worked out with all assignments listed. ✅
• However, all tasks have A(t) = H (full availability), and most R(c,t) = 0, making the example somewhat easy. A slightly more constrained example with task availability restrictions would be more illustrative of the problem's difficulty. ⚠️
• The known optimal answer is stated (YES). ✅

Recommendations

• Fix the complexity bound from "O*(2^(|C||T|))" to "O(2^(|C||T||H|))" to match the variable count
• Provide a concrete declare_variants!-compatible complexity string for implementation
• Consider adding task availability restrictions to the example to make it more illustrative
• Explicitly note that this is a SatisfactionProblem (Metric = bool) in the issue

[GiggleLiu]

Fix-issue changelog

• Fixed complexity bound from O*(2^(|C|*|T|)) to O*(2^(|C|*|T|*|H|)) to match the actual variable count
• Added declare_variants!-compatible complexity string: "2^(num_craftsmen * num_tasks * num_periods)"
• Added explicit SatisfactionProblem (Metric = bool) designation in the Definition section
• Replaced example: tasks t₁, t₂, t₃ now have restricted availability windows (not all A(t)=H), creating forced assignments and tighter scheduling constraints
• Example schedule verified feasible by constraint solver

Applied by /fix-issue.