Existing Algorithm for Scheduling Problems?

Question

Let's say I want to build a function that would properly schedule three bus drivers to drive in a week with the following constraints:

• Each driver must not drive more than five times per week
• There must be two drivers driving everyday
• They will rest one day each week (will not clash with other drivers' rest day)

What kind of algorithm would be used to solve a problem like this?

I looked through several sites and I found these:

1) Backtracking algorithm (brute force)
2) Genetic algorithm
3) Constraint programming

Frankly, these are all "culture shock" for me as I have never learnt any kind of linear programming in the past. There are two things I want to know:

1) Which algorithm will best suit the case scenario above?

2) What would be the simplest algorithm to solve this problem?

3) Please suggest any other algorithms I can look into to solve the above problem.

Answer 1

1) I agree brute force is bad.

2) Your Problem is an Integer Problem. They can be solved with Linear Programming though.

3) You can distinquish 2 different approaches: heuristics and exact approaches. Heuristics provide good solutions in reasonable computation time. They are used when there are strict requirements on the computation time or if the problem is too hard to calculate an optimal solution. Genetic Algorithms is a heuristic.

As your Problem is comparably simple, you would probably go with an exact approach.

4) The standard way to solve this exacly, is to embed a Linear Program in a Branch & Bound search tree. There is lots of literature on it. The procedure can be outlined as follows:

1. Solve the Linear Program with the Simplex-Algorithm
2. Find a fractional variable for branching. I.e. x=1.5
3. Create two new nodes and add the constraints x<=1 and x>=2 respectively
4. Go into one node (selected by some strategy)
5. Go to point 1

Additionally, at every node in the tree, after point 1, the algorithms checks, if a node can be pruned. That means to stop searching 'deeper' from this node on, because

a) the problem has become infeasible,

b) a better solution already exists,

c) an integer solution is found. This objective value of this solution is used to determine point b.

The procedure finishes when all nodes are pruned.

Luckily, as Nicolas stated, there are free implementations that do just this. All you have to do is to create your model. Code its objective and constraints in some tool and let it solve.