The complexity of scheduling problems is not easy to appreciate. Scheduling
involves taking discrete decisions, which means that solutions to such problems consist
of a number of discrete decisions. For example, in workforce scheduling, a shift needs to
be assigned to exactly one of a fixed number of staff members that can meet the requirements
for a given slot. Thus, a solution has to decide which staff member to assign to the slot.
The difficulty in solving such problem arises because in order to verify that a given solution
is the best possible solution, all possible alternatives must be examined. Thus, these problems
are often called combinatorial optimization problems.
The simplest approach to solving these problems consists of enumerating all solutions
and choosing the best. The problem with this approach is that the number of solutions to
examine grows exponentially with the size of the problem. For example, the solving of scheduling
problems with only 210 slots (10 staff members, 7 days, 3 shifts) already has as many solutions
as the universe has atoms. No wonder this effect is called combinatorial explosion! It
is not simply a question of efficiency of hardware, whether this approach works. Even if
computers become one million times faster, the approach of enumerating solutions will still
only be able to solve very small combinatorial search problems.
Due to combinatorial explosion, search techniques that rely on search space exploration
are not scalable. As the problem size grows, the computation time increases such that for
some problem size, days, weeks and years of computation time would be required. Therefore,
heuristic search techniques have been invented to find good solutions quickly. These solutions
then provide "bounds" for precise algorithms, which typically employ pruning
techniques such as "branch and bound" in order to avoid examining all solutions.
Combinatorial problems vary remarkably in how effective heuristics and pruning techniques
are. On the positive side lies the Traveling Salesman Problem, which asks for the most
efficient way to visit every city in a given geographical area. There are very efficient
heuristics and extremely effective pruning techniques available, which leads to an optimal
solution even of very large problems, such as visiting the 24,978 towns of Sweden. On the
other hand, the optimal scheduling of very small sports tournament problems (tournaments
with only 10 teams) is not possible with today’s computers and available algorithms,
due to combinatorial explosion. For workforce scheduling problems, there are no published
algorithms available as for the traveling salesman problem; efficient solvers need to be
carefully crafted and configured for this domain.
References:
|