S
Sagar Bonthu
Guest
Imagine you are building a two-week staff schedule. The requirements look simple enough:
None of these rules is hard to understand by itself. Then you look at weekend coverage.
Across the four weekend days, the staffing targets ask for 35 employee shifts. But there are 14 employees, and each can work only one weekend, which means at most two weekend days each. Fourteen times two is 28.
Before I assign a single person to a single shift, at least seven weekend slots are already impossible to fill.
This is the part of scheduling that interests me when large language models are involved. A model can understand every requirement correctly and still hand back a schedule that breaks once those requirements start affecting each other. In this article I will show that with a public example, explain why it happens, and lay out how I would split the work between a language model and ordinary software.
To keep it reproducible, I used Instance2 from the University of Nottingham nurse rostering benchmark and rebuilt it as an optimization model. [1] The examples use public benchmark data and general engineering patterns. They do not describe any employer's internal implementation.
Instance2 covers 14 days with 14 employees and two shift types, Early and Late, each eight hours long.
Its rules fall into two groups, and the difference between them turns out to be the whole story.
Hard rules can never be broken:
Soft rules can be broken, at a price:
If staffing coverage were a hard rule too, the weekend numbers alone would make this schedule impossible. No valid answer would exist.
Because coverage is soft, the question changes. It is no longer "can I satisfy everything?" It becomes "what is the best valid schedule when not every goal can be met?"
Fourteen employees, one weekend each, two days in that weekend: 28 possible shifts against 35 requested. The minimum shortage is seven, and that is before I consider days off, who is allowed to work which shift, working-time limits, or the Late-to-Early rule.
The arithmetic is easy. Finding the best schedule once all of those rules start interacting is the hard part.
For this experiment, I rebuilt Instance2 as a mathematical optimization model and solved it with HiGHS, an open-source solver, through the SciPy library in Python. I will skip the equations and describe the idea, because the idea is what matters.
Think of every possible assignment as a yes-or-no switch. "Employee A works the Late shift on day 5" is one switch. With 14 employees, 14 days, and 2 shifts, there are 392 of them. A schedule is simply a choice of which switches are on.
Each hard rule then becomes a restriction on which switches may be on together:
The weekend rule needs one extra step, and it is worth spelling out because it drives the opening example. I add a second kind of switch that says "this employee works this weekend." Turning on any Saturday or Sunday shift forces that weekend switch on. Then the rule is simple: each employee may have at most one weekend switch on.
With that in place, the 35 versus 28 conflict stops being an observation in my introduction. It lives inside the model, where the solver has to respect it.
Coverage is soft, so it gets counters, not locks. For every shift, I track how many people are missing and how many are extra. The number assigned, plus the number missing, minus the number extra, must equal the number required.
Then each kind of miss gets a price. In Instance2:
The solver's job is to find the valid schedule with the lowest total penalty.
This gives the system three things a paragraph of instructions never does: an exact definition of what makes a schedule invalid, a list of what may be traded away, and a price for each trade.
The solver finished with a proven best score of 828.
The public benchmark lists Instance2 with a best-known lower bound of 828 and a best-known solution of 828. When a real schedule reaches the lower bound, nothing better can exist, so 828 is optimal. [1] My rebuilt model landed on the same number, which told me I had reconstructed the problem correctly.
The score breaks down like this: 8 missing staffing assignments at 100 points each makes 800, and employee preference penalties add 28, for a total of 828.
The weekend arithmetic had already proved that at least seven assignments would be missing. Once every other rule was included, the best possible schedule needed eight.
One detail is worth noting. A score of 828 does not point to one unique schedule. Different schedules can spread those eight gaps differently and still score the same. The useful result is that the schedule is valid and the score is proven, not any particular arrangement of names.
Take five of these requirements: Employee D cannot work Late. Employee A must have day 3 off. Late cannot be followed by Early. Each employee can work at most one weekend. Saturday needs ten people.
A language model may understand every one of those statements perfectly. The trouble starts when assignments begin to affect each other:
Every assignment changes the choices that remain. Keeping track of all of that at once is a different skill from reading a rule.
A recent benchmark called SCHEDBench shows the same thing at larger scale. It evaluates 13 language models across 1,132 scheduling problems whose correct answers are backed by a solver. [2] On its nurse rostering problems, the share of model-produced schedules that were valid averaged 97.0% on easy problems, 62.4% on medium ones, and 1.7% on hard ones.
The study also found that models were sensitive to the order in which the rules were presented. The underlying problem stayed exactly the same, yet shuffling the rules changed how often the models broke them.
Another benchmark, R-ConstraintBench, reports a related pattern: validity drops as resource limits, downtime, time windows, and either-or constraints begin to interact. [3]
So the boundary that matters is not whether a model can read a rule. It is whether it can hold the entire valid state in mind while many rules push against each other.
Real scheduling requirements rarely arrive as equations. A manager writes things like:
"Alice would prefer Saturday off."
"Bob can work one weekend, but not both."
"Anyone finishing Late should not open the next morning."
This is where a language model earns its place. It can turn Bob's sentence into a structured rule: the employee is Bob, the rule type is a maximum number of weekends, the value is one, and the window is 14 days.
I would use the model for:
I would keep these out of the model's hands:
Suppose the original requirement says "Alice must have Saturday off," and the interpretation step records it as a preference instead of a requirement.
The solver will return a mathematically perfect answer to the wrong problem, and Alice will be on the Saturday rota.
For any rule that matters, I would keep three things side by side:
A solver can only guarantee what it was given. The translation into rules still needs a human or a separate check to sign it off.
I would also check the finished schedule outside the solver. Useful checks include:
By independent checking, I do not mean running the same model twice. Where practical, the checks should be written separately from the model, so a mistake made while building the model is less likely to appear in both places.
I would use this approach when:
I would keep things simpler when:
A solver, an interpretation layer, and an independent checker all add complexity. They should earn it.
If you are putting a language model anywhere near scheduling, rostering, or planning, here is what I would do:
The first useful result appeared before the solver ever ran: 35 weekend shifts requested, 28 possible under the weekend rule, at least 7 gaps unavoidable. The full model needed 8 gaps and produced a proven best score of 828.
Every individual requirement was easy to read. The difficult part was making them all hold at once.
That is the boundary I would protect in any LLM-assisted scheduling system. Let the language model help interpret messy requirements. Once those requirements become precise rules, let deterministic software search for the schedule and verify it.
A schedule can look reasonable and still break a rule somewhere you were not looking. In any system with this many interacting rules, validity has to be checked, never assumed.
[1] University of Nottingham, Nurse Rostering Benchmark Instances, including the raw data for Instance2 and its published optimal score of 828.
[2] Shrenil Shaun Sharma and Avi Sharma, “SCHEDBench: A Benchmark for Evaluating LLM Constraint Faithfulness in Natural-Language Combinatorial Scheduling,” arXiv:2608.00991 (2026).
[3] Raj Jain and Marc Wetter, “R-ConstraintBench: Evaluating LLMs on NP-Complete Scheduling,” arXiv:2508.15204 (2025).
- 14 employees
- An Early shift and a Late shift every day
- Specific days off for each employee
- Limits on working hours and on how many days in a row someone can work
- Restrictions on which shifts can follow each other
- Each employee can work at most one weekend
None of these rules is hard to understand by itself. Then you look at weekend coverage.
Across the four weekend days, the staffing targets ask for 35 employee shifts. But there are 14 employees, and each can work only one weekend, which means at most two weekend days each. Fourteen times two is 28.
Before I assign a single person to a single shift, at least seven weekend slots are already impossible to fill.
This is the part of scheduling that interests me when large language models are involved. A model can understand every requirement correctly and still hand back a schedule that breaks once those requirements start affecting each other. In this article I will show that with a public example, explain why it happens, and lay out how I would split the work between a language model and ordinary software.
To keep it reproducible, I used Instance2 from the University of Nottingham nurse rostering benchmark and rebuilt it as an optimization model. [1] The examples use public benchmark data and general engineering patterns. They do not describe any employer's internal implementation.
The Rules are in Conflict
Instance2 covers 14 days with 14 employees and two shift types, Early and Late, each eight hours long.
Its rules fall into two groups, and the difference between them turns out to be the whole story.
Hard rules can never be broken:
- One shift per employee per day
- Required days off
- Which shifts each employee is allowed to work
- A Late shift cannot be followed by an Early shift the next morning
- Minimum and maximum total working time
- Limits on consecutive working days, and minimum rest
- At most one working weekend per employee
Soft rules can be broken, at a price:
- Too few people on a shift
- Too many people on a shift
- Employee shift preferences
If staffing coverage were a hard rule too, the weekend numbers alone would make this schedule impossible. No valid answer would exist.
Because coverage is soft, the question changes. It is no longer "can I satisfy everything?" It becomes "what is the best valid schedule when not every goal can be met?"
Fourteen employees, one weekend each, two days in that weekend: 28 possible shifts against 35 requested. The minimum shortage is seven, and that is before I consider days off, who is allowed to work which shift, working-time limits, or the Late-to-Early rule.
The arithmetic is easy. Finding the best schedule once all of those rules start interacting is the hard part.
Turning the Rules Into Something a Solver Can Check
For this experiment, I rebuilt Instance2 as a mathematical optimization model and solved it with HiGHS, an open-source solver, through the SciPy library in Python. I will skip the equations and describe the idea, because the idea is what matters.
Think of every possible assignment as a yes-or-no switch. "Employee A works the Late shift on day 5" is one switch. With 14 employees, 14 days, and 2 shifts, there are 392 of them. A schedule is simply a choice of which switches are on.
Each hard rule then becomes a restriction on which switches may be on together:
- One shift per day: for any employee on any day, the Early switch and the Late switch cannot both be on.
- No Late then Early: if someone's Late switch is on today, their Early switch for tomorrow must be off.
- Working time: the total hours behind an employee's switches must land between their minimum and maximum.
- Days off and eligibility: the switches for forbidden assignments are locked in the off position.
The weekend rule needs one extra step, and it is worth spelling out because it drives the opening example. I add a second kind of switch that says "this employee works this weekend." Turning on any Saturday or Sunday shift forces that weekend switch on. Then the rule is simple: each employee may have at most one weekend switch on.
With that in place, the 35 versus 28 conflict stops being an observation in my introduction. It lives inside the model, where the solver has to respect it.
Coverage Has to Be Modeled Differently
Coverage is soft, so it gets counters, not locks. For every shift, I track how many people are missing and how many are extra. The number assigned, plus the number missing, minus the number extra, must equal the number required.
Then each kind of miss gets a price. In Instance2:
- Each missing employee costs 100 penalty points.
- Each extra employee costs 1 point.
- Each ignored shift preference costs the weight published in the benchmark.
The solver's job is to find the valid schedule with the lowest total penalty.
This gives the system three things a paragraph of instructions never does: an exact definition of what makes a schedule invalid, a list of what may be traded away, and a price for each trade.
The Solver Returned 828
The solver finished with a proven best score of 828.
The public benchmark lists Instance2 with a best-known lower bound of 828 and a best-known solution of 828. When a real schedule reaches the lower bound, nothing better can exist, so 828 is optimal. [1] My rebuilt model landed on the same number, which told me I had reconstructed the problem correctly.
The score breaks down like this: 8 missing staffing assignments at 100 points each makes 800, and employee preference penalties add 28, for a total of 828.
The weekend arithmetic had already proved that at least seven assignments would be missing. Once every other rule was included, the best possible schedule needed eight.
One detail is worth noting. A score of 828 does not point to one unique schedule. Different schedules can spread those eight gaps differently and still score the same. The useful result is that the schedule is valid and the score is proven, not any particular arrangement of names.
Why an LLM Can Still Get This Wrong
Take five of these requirements: Employee D cannot work Late. Employee A must have day 3 off. Late cannot be followed by Early. Each employee can work at most one weekend. Saturday needs ten people.
A language model may understand every one of those statements perfectly. The trouble starts when assignments begin to affect each other:
- Put someone on Late today, and that person may be unavailable tomorrow morning.
- Use someone on the first weekend, and they vanish from the second.
- Move someone else in to cover that gap, and a consecutive-days limit may kick in.
- Fix that, and a new coverage gap may open somewhere else.
Every assignment changes the choices that remain. Keeping track of all of that at once is a different skill from reading a rule.
A recent benchmark called SCHEDBench shows the same thing at larger scale. It evaluates 13 language models across 1,132 scheduling problems whose correct answers are backed by a solver. [2] On its nurse rostering problems, the share of model-produced schedules that were valid averaged 97.0% on easy problems, 62.4% on medium ones, and 1.7% on hard ones.
The study also found that models were sensitive to the order in which the rules were presented. The underlying problem stayed exactly the same, yet shuffling the rules changed how often the models broke them.
Another benchmark, R-ConstraintBench, reports a related pattern: validity drops as resource limits, downtime, time windows, and either-or constraints begin to interact. [3]
So the boundary that matters is not whether a model can read a rule. It is whether it can hold the entire valid state in mind while many rules push against each other.
Give the LLM a Narrow Job
Real scheduling requirements rarely arrive as equations. A manager writes things like:
"Alice would prefer Saturday off."
"Bob can work one weekend, but not both."
"Anyone finishing Late should not open the next morning."
This is where a language model earns its place. It can turn Bob's sentence into a structured rule: the employee is Bob, the rule type is a maximum number of weekends, the value is one, and the window is 14 days.
I would use the model for:
- Pulling out employees, dates, and shifts
- Recognizing which type of scheduling rule a sentence describes
- Treating different wordings of the same rule as the same rule
- Keeping a pointer to the original sentence as evidence
- Explaining conflicts back to the planner in plain language
I would keep these out of the model's hands:
- The final decision on which rules are hard and which are soft
- Checking whether a schedule is valid
- Searching for the best schedule
- Calculating the score
- The final check of the finished schedule
The Solver Can Still Solve the Wrong Problem
Suppose the original requirement says "Alice must have Saturday off," and the interpretation step records it as a preference instead of a requirement.
The solver will return a mathematically perfect answer to the wrong problem, and Alice will be on the Saturday rota.
For any rule that matters, I would keep three things side by side:
- The source requirement: what was actually written.
- The structured interpretation: what the model extracted from it.
- The approved rule: what actually goes into the solver.
A solver can only guarantee what it was given. The translation into rules still needs a human or a separate check to sign it off.
Check the Result Separately
I would also check the finished schedule outside the solver. Useful checks include:
- Nobody is assigned twice on the same day
- No forbidden shift sequences
- Required days off are respected
- Weekend limits hold
- Working-time limits hold
- Staffing totals per shift are what the report says they are
- Coverage and preference penalties are calculated correctly
- The final score matches
By independent checking, I do not mean running the same model twice. Where practical, the checks should be written separately from the model, so a mistake made while building the model is less likely to appear in both places.
When This Design Is Worth It
I would use this approach when:
- Many rules interact
- Fixing one violation can create another
- Hard and soft requirements mean different things
- The system needs the best compromise, not just any plausible schedule
- Being right matters enough to justify a separate check
I would keep things simpler when:
- There are only a few independent rules
- Violations are cheap to spot
- There is nothing real to optimize
- Fixing one condition does not disturb the rest of the plan
A solver, an interpretation layer, and an independent checker all add complexity. They should earn it.
Before You Let an LLM Build a Schedule
If you are putting a language model anywhere near scheduling, rostering, or planning, here is what I would do:
- Do the back-of-the-envelope arithmetic first. Multiply out your tightest rule, as I did with 14 times 2 against 35. You may find the plan is impossible before any tool runs.
- Sort every requirement into hard or soft, and have a person make that call.
- Put a price on every soft rule, so trade-offs are decided by numbers and not by whatever reads well.
- Let the model translate plain language into structured rules, and keep the original sentence attached to each one.
- Have someone approve the important rules before they reach the solver.
- Let a solver do the searching and scoring.
- Check the finished schedule with separately written checks.
- Ask the model to explain the outcome to the planner, including which targets could not be met and why.
Conclusion
The first useful result appeared before the solver ever ran: 35 weekend shifts requested, 28 possible under the weekend rule, at least 7 gaps unavoidable. The full model needed 8 gaps and produced a proven best score of 828.
Every individual requirement was easy to read. The difficult part was making them all hold at once.
That is the boundary I would protect in any LLM-assisted scheduling system. Let the language model help interpret messy requirements. Once those requirements become precise rules, let deterministic software search for the schedule and verify it.
A schedule can look reasonable and still break a rule somewhere you were not looking. In any system with this many interacting rules, validity has to be checked, never assumed.
References and Further Reading
[1] University of Nottingham, Nurse Rostering Benchmark Instances, including the raw data for Instance2 and its published optimal score of 828.
[2] Shrenil Shaun Sharma and Avi Sharma, “SCHEDBench: A Benchmark for Evaluating LLM Constraint Faithfulness in Natural-Language Combinatorial Scheduling,” arXiv:2608.00991 (2026).
[3] Raj Jain and Marc Wetter, “R-ConstraintBench: Evaluating LLMs on NP-Complete Scheduling,” arXiv:2508.15204 (2025).