Existing Algorithm for Scheduling Problems?
algorithm, constraints, java, linear-programming
Solution
First of all this is a discrete optimization problem, so linear programming is probably not a good idea (since it is meant for continuous optimization). You can still solve this using linear programming (it will become an integer or mixed-integer program) but that is exponentially heard (if your input size is small then it is ok).
Now back to the comparison:
Brute force : worst.
Genetic: Can not guarantee optimality. The algorithm may not be able to solve the problem.
Constraint programming: definitely the best in this case (and in many discrete optimization problems). There is a super efficient implementation of it in IBM ILOG CPLEX solver (but is is not free, it is free for academia or for testing though).
Problem
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.