The difficulty of the automatic work schedule increases with scale

“Realistically, how large should the optimal solution be?

What is the nurse scheduling problem , we explained that the larger the scale of the problem, the more difficult it becomes to find an optimal solution within a realistic time frame.
Now, let’s look at the question, “How large can the optimal solution be obtained? Let’s take a look at the following table.

The following table shows the years of optimal solution discovery for each instance at the Scheduling Benchmark Site .

Since this benchmark collection was published in 2014, we can safely assume that the problem is easy for instances that were solved in 2014.

This group of instances increases as you go down.
For example, Instance1 is a 2-week problem with eight staff and one shift, while Instance24 is a 52-week (1-year) problem with 150 staff and 32 shifts.

The only unresolved problems are instances 23 and 24, but you can see that the lower you go, the more recent the year of discovery.
This benchmark has no limits on PC performance or test time. Nevertheless, the optimal solution is not known for huge problems with more than 100 staff members and a duration of one year.

The best modern group of solvers with the latest performance are challenging this benchmark. Even so, when the scale is large, finding the optimal solution in a realistic time frame is difficult, which is the nurse scheduling problem.

Although on a smaller scale, you are the ones who solve that nurse scheduling problem every month.

For example, instance 8 is close to the scale of the problem you usually solve (duration four weeks, number of staff 30, number of shifts 8).
Yet, the optimal solution is found in 2017.
It means that even at the scale of problems that you usually solve, it is possible to have problems that are difficult to find optimal solutions.
In short, even with the State-of-the-Art solvers, it is difficult to find an optimal solution to the nurse scheduling problem, even today.
On the other hand, some problems can be solved at the same time as the year of publication, even if the scale of the problem is more significant than that. It is not wrong to say that the larger the scale of the problem, the more difficult it becomes, but it does not mean that it should be easy to solve because the scale is small.

With ordinary shift work schedule software, it is impossible to know if their problem is difficult. Most of us have to trust that the answer is the best.