Scheduling with variable Resources

Question

Hello,

(First of all, sorry for my english, it's not my first language)

I have a list of tasks/jobs, each task must start after a specific start time, needs to run for a certain time and has to be finished after a certain end time.

I can dynamically add and remove workers, so it is possible to execute 2 or more tasks at the same time if I have to. My Goal is to find a scheduling plan that executes each job successfully and uses the minimal amount of workers possible.

I'm currently using an EDF (http://en.wikipedia.org/wiki/Earliest_deadline_first_scheduling) Algorithm and recursively call the function with a higher Worker Limit if it can't schedule all jobs correctly, but I think this doesn't work right because I don't have a real way to measure when I can lower the ressource limit again.

Are there any Algorithms that work for my problem, or any other clever ideas?

Thanks for your help.

Answer 1

A scheduling problem can often be solved very effectively by formulating it either as mixed-integer program (MIP)

http://en.wikipedia.org/wiki/Mixed_integer_programming#Integer_unknowns

or expressing it using constraint programming (CP)

http://en.wikipedia.org/wiki/Constraint_programming

For either MIP or CP, you will find both free and commercial solvers that can address your problem.

In both of these approaches, you put your effort into stating the properties that the solution must have, and the hard work of applying an appropriate algorithm is left to a specialized solver.