Thread: Scheduling Algo

  1. #1
    Registered User
    Join Date
    Apr 2002
    Posts
    80

    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

  2. #2
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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?

  3. #3
    Registered User
    Join Date
    Nov 2001
    Posts
    1,348
    One solution could be SJF. Schedule the shortest job first.

    Kuphryn

  4. #4
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    No, that won't work. Imagine 3 jobs and one computer.

    Job 1: 3pm-6pm
    Job 2: 7pm-10pm
    Job 3: 5:30pm-7:30pm

    Putting in the shortest only does one job - Job 3, while the optimal solution is Job 1 and Job 2.

  5. #5
    Registered User
    Join Date
    Nov 2001
    Posts
    1,348
    Okay. I see the problem. There is a time requirement.

    Kuphryn

  6. #6
    Registered User
    Join Date
    Apr 2002
    Posts
    80
    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...

  7. #7
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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.

  8. #8
    Registered User
    Join Date
    Apr 2002
    Posts
    80
    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).

  9. #9
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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.

  10. #10
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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.

  11. #11
    Registered User
    Join Date
    Apr 2002
    Posts
    80
    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.

  12. #12
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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.

  13. #13
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,401
    Can you give us an explanation of your solution using recursion? It sounds like an interesting problem.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  14. #14
    Registered User
    Join Date
    Apr 2002
    Posts
    80
    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?

  15. #15
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,401
    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.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. flow control algo
    By Mr.Bit in forum C Programming
    Replies: 4
    Last Post: 04-28-2008, 10:32 AM
  2. scheduling in linux
    By anjana in forum Linux Programming
    Replies: 2
    Last Post: 05-24-2007, 03:48 PM
  3. Maze generation algo
    By VirtualAce in forum Game Programming
    Replies: 7
    Last Post: 03-01-2006, 05:03 AM
  4. Flight scheduling algorithm?
    By ChadJohnson in forum A Brief History of Cprogramming.com
    Replies: 14
    Last Post: 01-26-2006, 02:23 AM
  5. Round Robin Scheduling using c.
    By eclipt in forum C Programming
    Replies: 8
    Last Post: 12-28-2005, 04:58 PM