[Model] StaffScheduling

[isPANN]

Motivation

STAFF SCHEDULING (P204) from Garey & Johnson, A5 SS20. A classical NP-complete problem in workforce scheduling: given a collection of binary schedule patterns (m-tuples with k ones), a requirement vector specifying minimum staffing per period, and a workforce budget n, can workers be assigned to schedules to meet all requirements? Shown NP-complete by Garey and Johnson (unpublished) via reduction from X3C. Solvable in polynomial time when schedules have the cyclic ones property (consecutive shifts), a result of Bartholdi, Orlin, and Ratliff (1977).

Associated rules:

• R149: X3C -> Staff Scheduling (incoming, [Garey and Johnson, unpublished])

Definition

Name: StaffScheduling

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

Mathematical definition:

INSTANCE: Positive integers m and k, a collection C of m-tuples, each having k 1's and m - k 0's (representing possible worker schedules), a "requirement" m-tuple R̄ of non-negative integers, and a number n of workers.
QUESTION: Is there a schedule f: C→Z0+ such that ∑_{c̄ ∈ C} f(c̄) ≤ n and such that ∑_{c̄ ∈ C} f(c̄)·c̄ ≥ R̄?

Variables

• Count: |C| (one integer variable per schedule pattern)
• Per-variable domain: {0, 1, ..., n} — how many workers are assigned to each schedule pattern
• Meaning: f(c̄) is the number of workers following schedule pattern c̄. The total number of workers across all patterns must not exceed n, and the sum of scheduled workers in each period must meet or exceed the requirement for that period.

Schema (data type)

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

Field	Type	Description
num_periods	usize	Number of time periods m
shifts_per_schedule	usize	Number of active shifts k per schedule pattern
schedules	Vec<Vec<bool>>	Collection C of m-tuples (binary schedule patterns)
requirements	Vec<u64>	Requirement vector R̄ (minimum staffing per period)
num_workers	u64	Maximum number of workers n available

Complexity

• Best known exact algorithm: The problem is NP-complete in general (Garey and Johnson, 1979). It can be formulated as an integer linear program and solved with ILP solvers, but no polynomial-time exact algorithm exists unless P = NP. For the special case where all schedule patterns have the cyclic ones property (all 1's are consecutive, with wraparound), the problem is solvable in polynomial time via network flow techniques (Bartholdi, Orlin, and Ratliff, 1980). In the general case, brute-force enumeration of all possible assignments f: C -> {0,...,n} requires O((n+1)^|C|) time. The nurse scheduling problem, a practical generalization, is typically solved with ILP or metaheuristics (genetic algorithms, tabu search, simulated annealing).

Extra Remark

Full book text:

INSTANCE: Positive integers m and k, a collection C of m-tuples, each having k 1's and m - k 0's (representing possible worker schedules), a "requirement" m-tuple R̄ of non-negative integers, and a number n of workers.
QUESTION: Is there a schedule f: C→Z0+ such that ∑_{c̄ ∈ C} f(c̄) ≤ n and such that ∑_{c̄ ∈ C} f(c̄)·c̄ ≥ R̄?

Reference: [Garey and Johnson, ——] Transformation from X3C.

Comment: Solvable in polynomial time if every c̄ ∈ C has the cyclic one's property, i.e., has all its 1's occuring in consecutive positions with position 1 regarded as following position m [Bartholdi, Orlin, and Ratliff, 1977]. (This corresponds to workers who are available only for consecutive hours of the day, or days of the week.)

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all assignments f: C -> {0,...,n} with sum f(c̄) <= n; check if sum f(c̄)*c̄ >= R̄ component-wise.)
• It can be solved by reducing to integer programming. (ILP: minimize sum f(c̄) subject to f(c̄) >= 0 integer, sum f(c̄) <= n, and for each period j: sum_{c̄} f(c̄)*c̄_j >= R̄_j.)
• Other: For cyclic ones property schedules, solvable via network flow / circular ones ILP.

Example Instance

Input:
m = 7 periods (days of the week), k = 5 shifts per schedule (5-day work week)
n = 4 workers

Schedules (C):

Schedule	Mon	Tue	Wed	Thu	Fri	Sat	Sun
c_1	1	1	1	1	1	0	0
c_2	0	1	1	1	1	1	0
c_3	0	0	1	1	1	1	1
c_4	1	0	0	1	1	1	1
c_5	1	1	0	0	1	1	1

Requirements R̄ = (2, 2, 2, 3, 3, 2, 1)

Feasible schedule:
f(c_1) = 1, f(c_2) = 1, f(c_3) = 1, f(c_4) = 1, f(c_5) = 0.
Total workers: 1 + 1 + 1 + 1 + 0 = 4 <= n = 4 ✓

Coverage per period:

• Mon: c_1 + c_4 = 2 >= 2 ✓
• Tue: c_1 + c_2 = 2 >= 2 ✓
• Wed: c_1 + c_2 + c_3 = 3 >= 2 ✓
• Thu: c_1 + c_2 + c_3 + c_4 = 4 >= 3 ✓
• Fri: c_1 + c_2 + c_3 + c_4 = 4 >= 3 ✓
• Sat: c_2 + c_3 + c_4 = 3 >= 2 ✓
• Sun: c_3 + c_4 = 2 >= 1 ✓

Answer: YES — a feasible staff schedule exists with 4 workers.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph; practical workforce scheduling problem
Non-trivial	✅ Pass	Distinct feasibility constraints (integer assignment to schedule patterns with coverage requirements)
Correctness	✅ Pass	References verified; example schedule is correct
Well-written	⚠️ Warn	Minor date inconsistency for Bartholdi et al.; missing concrete complexity string

Overall: 3 passed, 0 failed, 1 warning

---

Usefulness

StaffScheduling does not exist in the codebase. It is a classic NP-complete problem from Garey & Johnson (A5 SS20) with strong practical relevance to workforce scheduling, nurse rostering, and shift planning. The issue mentions an associated rule (X3C -> StaffScheduling) which would connect it to the reduction graph. Both brute-force and ILP solvers are identified. Pass.

Non-trivial

The problem has genuinely distinct feasibility constraints from all existing problems: integer-valued assignment of workers to binary schedule patterns, with a workforce budget constraint and per-period minimum staffing requirements. The variables are non-binary integers ({0,...,n}), which distinguishes it from binary decision problems. This is not a variant or relabeling of any existing problem. Pass.

Correctness

References:

• Garey and Johnson (1979) — Computers and Intractability, A5 SS20, NP-completeness via transformation from X3C (unpublished result by the authors). ✅ This is a standard reference from the book's appendix. The "unpublished" transformation from X3C is documented in the book itself.

• Bartholdi, Orlin, and Ratliff — "Cyclic Scheduling via Integer Programs with Circular Ones," Operations Research, 28(5), 1074–1085. ✅ Verified. The paper shows that the cyclic staffing problem with the circular ones property is solvable in polynomial time via network flow techniques. Note: the actual publication year is 1980, not 1977 as stated in the Extra Remark section (the book likely cited a 1977 working paper or technical report).

Example verification: ✅ All constraints verified manually:

1. All five schedule patterns have exactly k=5 ones in m=7 positions. ✅
2. Total workers: f(c_1)+f(c_2)+f(c_3)+f(c_4)+f(c_5) = 4 <= n=4. ✅
3. Per-period coverage meets or exceeds requirements R̄ = (2,2,2,3,3,2,1) on all 7 days. ✅

Definition correctness: The formal definition is well-formed. The function f: C -> Z0+ assigns non-negative integer counts of workers to schedule patterns, with sum constraint and component-wise coverage requirement. This is consistent with Garey & Johnson's formulation. ✅

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 precise, with all constraints clearly stated. This is a satisfaction problem (Metric = bool). ✅

4c: Symbol and Notation Consistency:

• Symbols m, k, C, R̄, n, f are consistent across all sections. ✅
• Schema field names (num_periods, shifts_per_schedule, schedules, requirements, num_workers) clearly map to the mathematical definition. ✅
• Minor inconsistency: the Extra Remark quotes the book as "[Bartholdi, Orlin, and Ratliff, 1977]" but the Complexity section says "1980". The published paper is from 1980; the book may reference a 1977 technical report. ⚠️

4d: Example Quality:

• The example is well-chosen: 7 periods (days of a week), 5 shifts (5-day work week), 5 schedule patterns, 4 workers. Realistic and illustrative. ✅
• The schedule is fully worked out with coverage verification for each period. ✅
• Known answer (YES) is stated. ✅
• All schedule patterns happen to have the cyclic ones property (consecutive shifts with wraparound), so this example falls in the polynomial-time solvable case. Adding one non-cyclic pattern would make the example more representative of the NP-hard general case. ⚠️

Recommendations

• Reconcile the date: use "1980" consistently for the published paper (Bartholdi, Orlin, and Ratliff, Operations Research, 1980), or note that the 1977 date is from the book's citation of a technical report
• Provide a concrete declare_variants!-compatible complexity string for implementation (e.g., based on brute-force bound)
• Explicitly note that this is a SatisfactionProblem (Metric = bool) in the issue
• Note that the variables are non-binary integers (domain size n+1 per pattern), which is important for dims() implementation
• Consider adding a non-cyclic schedule pattern to the example to exercise the NP-hard general case