Existing algorithm for schedule tasks?

Question

Suppose I want to create a function that properly plans three bus drivers to drive through in a week with the following restrictions:

• Each driver should not drive more than five times a week.
• There must be two drivers who drive every day
• They will rest one day every week (will not interfere with the rest day of other drivers)

What algorithm will be used to solve such a problem?

I looked at several sites and I found them:

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

Honestly, this is all a “cultural shock” for me, as I have never studied linear programming in the past. I want to know two things:

1) Which algorithm is best suited for the scenario above?

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

3) Please suggest any other algorithms that I can learn to solve the above problem.

Answer 1

First of all, this is a discrete optimization problem, so linear programming is probably not a good idea (since it is designed for continuous optimization). You can still solve this with linear programming (it will become a whole or mixed whole program), but it is heard exponentially (if your input size is small, then it is fine).

Now back to the comparison:

• Brute force: worst.

• Genetics: cannot guarantee optimality. Perhaps this algorithm will not be able to solve the problem.

• Programming constraints: certainly the best in this case (and in many discrete optimization problems). There is a super-efficient implementation of it in the IBM ILOG CPLEX solver (but it is not free, it is free for academia or for testing).

Answer 2

1) I agree that brute force is bad.

2) Your problem is the integer problem. However, they can be solved using linear programming.

3) You can distinguish between two different approaches: heuristics and exact approaches. Heuristics provides good solutions in a reasonable calculation time. They are used when there are strict requirements for calculation time or if the problem is too complex to calculate the optimal solution. Genetic algorithms are heuristic.

Since your problem is relatively simple, you will probably come up with the exact approach.

4) The standard way to solve this problem is to embed a linear program in the search and related search tree. It has a lot of literature. The procedure can be described as follows:

• Solve a linear program using a simplex algorithm
• Find the fractional variable for branching. That is, x = 1.5
• Create two new nodes and add constraints x <= 1 and x> = 2 respectively
• Go to one node (selected by some strategy)
• Go to step 1

In addition, on each node in the tree, after point 1, the algorithms check whether it is possible to trim the node. This means stopping the search “deeper” for this node, because

a) the problem has become unattainable,

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 ends when all nodes are cut.

Fortunately, as Nicholas said, there are free implementations that do just that. All you have to do is create your own model. Encode its purpose and limitations in some tool and allow it to be solved.