
Scheduling Algo
Hi guys,
A few weeks ago I was working on a recursive scheduling algorithm for assigning jobs to computers. At that time, PJYelton and I discussed what we thought would work as an iterative solution. I'm now investigating this, but my current solution is not doing the trick.
The general problem: I have a list of jobs, each of which may be scheduled on several different computers. Each job has a start and end time associated with it. The goal is to schedule as many of the jobs as possible. No job may be scheduled on the same computer at the same time...if this occurs, then perhaps one of the jobs may be scheduled on another machine.
I have succesfully solved this problem using recursion, but I now desire for a fast and correct iterative solution. I attempted to solve it using a greddy algo which simply starts with the first computer, assigns all possible jobs to it, then moves to the next computer, assigns all possible remaining jobs, etc. This solution solves almost all cases, but unfortunatly, doesn't get the job done in general.
Does anyone care to point me in the right direction? If there are questions about the problem, please ask.
Thanks

Did you try the other greedy possibility where you sort the list first by end times, then iterate through the list putting each item in the first available computer, and if no computer is available move onto the next item?

One solution could be SJF. Schedule the shortest job first.
Kuphryn

No, that won't work. Imagine 3 jobs and one computer.
Job 1: 3pm6pm
Job 2: 7pm10pm
Job 3: 5:30pm7:30pm
Putting in the shortest only does one job  Job 3, while the optimal solution is Job 1 and Job 2.

Okay. I see the problem. There is a time requirement.
Kuphryn

I didn't try the other greedy algo...but I'm almost 100% positive that no greedy algo will work for this scenario...
I will try that, but I'm after something that I can prove will work, rather than implement a buch of solutions and go trial and error...

This greedy algorithm works with a single computer and isn't too hard to prove, I just don't know if it works with multiple computers even though I think it should. If it doesn't could you give me a small example where it fails? I'm really curious.

1 1 a b
2 2 b a
1 2 a b
This might need some explaining. Each line represents a job. The ints represent the times that the job must be scheduled for (inclusive). The letters represent the computers on which that job may be scheduled.
To use your greedy algo, job 0 would be scheduled on a. Job 1 would be scheduled on b. Job 2 could then not be scheduled on either computer.
The optimal solution in this small example would be to schedule job 0 on a, job 1 on a, and job 2 on b. ( or 0 on b, 1 on b, and 2 on a).

I'm a little confused, are you saying that each task has it's own list of computers that it can be on in order of preference? A big part of the algorithm is that the tasks MUST be sorted first in order of ending times, and if ending times are equal, then sort those times by beginning times. I would also sort the list of computers that task must use, although I'm unsure of how much of a difference that will make. So your new sorted list would like this:
1 1 a b
1 2 a b
2 2 a b
So job 0 gets put on a, job 1 gets put on b, job 2 gets put on a, which is ideal.

Ok, I did some thinking. If not all tasks can be scheduled on all computers (which I didn't realize unfortunately) then the greedy algo will not work. Easiest example:
1 1 a b
1 2 a
If this is the case, then I'm not sure how to solve this problem easily. I only know the variation of the problem that tries to solves what is the least number of computers you can use with a set up scheduled tasks.

Sorry if things were confusing...
Each job DOES have it's own list of computers, which may only be a small portion of the total number of computers.
The computers are not ordered by preference, and can be changed around, so long as the same computers are associated with each job.

Then I'm not sure how this would be solved. Try asking at the Topcoder.com round tables, lot of very bright people there who specialize in algorithms.

Can you give us an explanation of your solution using recursion? It sounds like an interesting problem.

My recursive solution simply explores the entire space, saving the best solution. I do some bounding of branches, to cut a bunch of time if possible.
To put it basically, I try every feasible combination. By feasible, I mean that no job conflicts exist. ( Two jobs scheduled at same time on same computer.)
I have a new idea for my iterative solution, but I fear it may not work and may be difficult to code. My current iterative solution (doesn't work) is to start with a computer, put all possible jobs on it, move to next computer, put all possible remaining jobs on it, etc. It does this for all sequential orders of computers. ( {a,b,c,d,e}, {b,c,d,e,a}, {c,d,e,a,b}, etc )
Assume the number of computers is M. My new idea is to do the greedy algorithm in the above paragraph over all M! orderings of computers. I think this *might* work, but have my doubts, and am also not confident I can code it.
Any more thoughts anyone?

I'm not sure, but it feels like you could solve this with some convolted type of tableau. I'll have to pull out my notes and see if I can dig anything up.