“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.

Instance Name Weeks Number of Staff Number of Shifts Year of Discovery Remarks
Instance1 2 8 1 2014
Instance2 2 14 2 2014
Instance3 2 20 3 2014
Instance4 4 10 2 2014
Instance5 4 16 2 2014
Instance6 4 18 3 2014
Instance7 4 20 3 2014
Instance8 4 30 4 2017
Instance9 4 36 4 2017
Instance10 4 40 5 2014
Instance11 4 50 6 2014
Instance12 4 60 10 2014
Instance13 4 120 8 2017
Instance14 6 32 4 2017
Instance15 6 45 6 2022
Instance16 8 20 3 2017
Instance17 8 32 4 2017
Instance18 12 22 3 2017
Instance19 12 40 5 2020
Instance20 26 50 6 2020
Instance21 26 100 8 2021 Sugawara-systems(This article’s author)
Instance22 52 50 10 2022 Sugawara-systems(This article’s author)
Instance23 52 100 16
Instance24 52 150 32

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.