A universal model for scheduling problems is proposed and as an alternative to solving such problems with the help of ILP-Solvers we found that SAT-Solvers can be a decent alternative in certain scenarios.
C#, .NET 6.0, Gurobi, CaDiCal
The main goal of this project is the development of a universal model for scheduling problems. We should provide a program that solves problems in our model and is accessible over a web interface. Another goal is the evaluation of the gurobi ILP-Solver and CaDiCal SAT-Solver, in the context of our model, which are used as solvers in our program.
Scheduling problems are a form of optimization problem where an optimal distribution of tasks to people and locations over a given time period needs to be found. Because of their complex nature models and solving programs for scheduling problems are highly specialized for one specific problem. We received multiple scheduling problems with solutions and documentation on which we based our model. One of them is a nurse scheduling problems, where hospital shifts need to be assigned to shifts while keeping the costs low and the shift distribution fair. Another one is a examinatino scheduling problem, where a school needs to schedule presentations of students and assign rooms and time slots. The amount of rooms and time slots needs to be minimized. A third one is a staff scheduling problem, where a company that provides further education courses needs to assign speakers to their planned courses. The speakers travel costs to each course location needs to be minimized.
All of the above mentioned problems can be fitted into our model model and the program and the web interface can be used to input new custom scheduling problems. The model is implemented as a c# class library that can be used as a standalone, with an c# interface for solvers and implementation for gurobi and a SAT-Library which includes CaDiCal and other solvers. The results also show that, while in most scenarios the ILP-Solvers outperform the SAT-Solvers they are nonetheless a decent alternative, especially when considering the steep cost that gurobi introduces.
This Bachelors Thesis was written in one Semester over 720 man hours distributed across two students
FHNW, Windisch, FHNW.CH
Joshua Schärer, Elias Mjø
Simon Felix, simon.felix@fhnw.ch
