Please keep in mind the following information:
Difficulty of optimization for nurse scheduling problem
Finding the optimal value for the nurse scheduling problem is challenging, even with Gorobi, currently considered the world’s best mathematical solver.
For instance, after submitting instance8 in the scheduling benchmarks., it took several years to determine the optimal solution. Note that it is a common-scale scheduling problem involving 30 staff over 4 weeks.
Optimized operations for Algorithms
Algorithm 1 provides a quasi-optimal solution. If it completes without reaching the software timeout, it implies that no better optimal value exists.
Even when the exact solution is found, the solver continues attempting to prove its optimality. Because the solver only knows that no better solution exists by proving its optimality.
However, the search loop stops if the Final Soft Timeout is reached.
It’s worth noting that the discovery of the optimal value is an ongoing process, and it may still be found even at the timeout stage.
Algorithm 2, in contrast, is designed to continue its search until the exact solution (optimal value) is found. However, it’s important to note that it may not terminate within a reasonable timeframe, especially for complex projects with more than 10 staff.
Algorithm 3/4 stops once the exact solution (optimal value) is reached. However, if the Abort button is pressed, it provides the best solution attained up to that point.