Scheduling Algo

This is a discussion on Scheduling Algo within the C++ Programming forums, part of the General Programming Boards category; The recursive was homework (Which has been done for a while), but the iterative is for my own fun (Which ...

  1. #31
    Registered User
    Join Date
    Apr 2002
    Posts
    80
    The recursive was homework (Which has been done for a while), but the iterative is for my own fun (Which is what I'm trying to solve now).

    The jobs can be ordered, or seperated, or whatever if desired. I order them on end time, so I can check for collision in a constant amount of time (Look at last job, check that its end time is before the start time of the job we're attempting to schedule). I've batted around ideas of organizing jobs into "bins" based on who intersects with who, or what potential computers they can be on, etc.... But, I haven't been able to make anything out of this approaches.
    Last edited by BigDaddyDrew; 03-07-2003 at 12:06 PM.

  2. #32
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Since I'm at work I haven't been able to test this out throroughly or prove if it works 100%, but what about this idea: sort the items by end times (and if tied, then by beginning times), iterate them from beginning to end putting them into the first available computer. If there is no open computer, then PUSH the conflicted elements onto the next available computer that they can go onto. Continue pushing elements until nothing needs to be pushed anymore, or if it is impossible to push any of the conflicting elements, then revert everything back to the way it was and try the next computer. If all possible computers come up as NO PUSH, then skip this task and move onto the next one. You should be able to assume that this task is not in the optimal solution. In pseudocode:
    Code:
    for each task in list:
       for each computer in task availability list:
           place task in computer if possible.
       if task not placed yet
           for each computer in task availabilty list
              place conflicting tasks into a queue and place task in this computer;
              continue until queue is empty or no push possible
                   push top of queue into first available comp or if no available comp, then
                   repeat by pushing onto a new comp and adding conflictions to queue
              if queue is empty then successful, move onto next task
    I feel like this should work, although two problems that I see off the top of the bat that I can't work out off the top of my head (I have to get back to work!) One is that after each unsuccessful try in the pushing you must be able to revert everything back to how it was before you started the pushing. The second is that you don't want to exactly pop the queue on a succesful push, because later on you might need to come back to it and try a different computer (ie pushing onto comp A resulted in a failure a few pushed down the line, so lets try comp B). Back to work... sigh... If this is unclear send me a couple of examples and I'll demonstrate my algo on them.
    Last edited by PJYelton; 03-07-2003 at 12:33 PM.

  3. #33
    Registered User
    Join Date
    Apr 2002
    Posts
    80
    Heh, I'm having problems following this algorithm exactly. What is the final result of the outermost for loop? Is it attempting to find on which computer that job will eventually be scheduled?

    When you say "revert everything back to the way it was", to where do you suggest reverting? I think it's to the stage where we were considering scheduling the current job, right?

    Let's see here:
    Code:
    1:  for each task in list:
    2:     for each computer in task availability list:
    3:         place task in computer if possible.
    4:     if task not placed yet
    5:         for each computer in task availabilty list
    6:            place conflicting tasks into a queue and place task in this
    7:                     computer;
    8:            continue until queue is empty or no push possible
    9:                 push top of queue into first available comp or if no
    10:                    available comp, then
    11:                repeat by pushing onto a new comp and adding
    12:                    conflictions to queue
    13:           if queue is empty then successful, move onto next task
    Line 6) Does this put ALL conflicting tasks from the whole task list into a queue?
    Line 9) Does first available computer mean the first one in our "task availability list" that doesn't have a job scheduled at our desired times?
    Lind 10) What conflictions should we add to queue?

    Phew...sorry I'm not on the same page as you...

    Maybe we'll get there!

  4. #34
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,643
    Can you post your recursive solution? That may help me with coming up with an iterative one.
    I'm juggling a few solutions but can't think of a way of proving that they are optimal.

    gg

  5. #35
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Yeah, I kinda wrote that in haste, sorry for the confusion!

    When each loop is completed in the outermost loop, then the current task will have been scheduled in its current more optimal place, or it would have found out that it can't be placed. When the outer for loop is finished, then everything should be placed optimally.

    When I say revert everything back to how it was, I mean revert the changes you made back to where you are trying a different comp either with a main task or with a task on the queue. In other words change back to the last place where theres a fork in the road in terms of choices.

    Line 6 puts all conflictions in the queue since they all must be pushed in order to put the current task on this computer.

    Line 9 means put in first available computer on that tasks list that doesn't have any conflictions.
    <Keeps fingers crossed that this works in all situations >

    Think of line 10 as pretty much repeating the process of adding conflictions to the queue but with this task instead.

    Heres a couple of small examples:
    Task 1: Start 1:00 End 2:00 possible comps: A B
    Task 2: Start 1:00 End 3:00 possible comps: A

    -Task 1 gets put onto comp.
    -Task 2 goes through all comps and sees none are available.
    -Task 2 then PUSHES task 1 onto the queue and is placed onto comp A.
    -The top of the queue (task 1) then looks for available computers, finds comp B available, gets put on comp B. The queue is now empty, so these two tasks are now optimal.
    -Optimal solution is correct.

    Example 2:

    Task 1: 1:00 End 2:00 possible comps: A B
    Task 2: 1:00 End 2:00 possible comps: A B
    Task 3: 1:00 End 3:00 possible comps: A
    Task 4: 2:00 End 3:00 possible comps: A B
    Task 5: 2:00 End 3:00 possible comps: A B

    -Task 1 gets put on first available comp. Put on comp A.
    -Task 2 gets put on first available comp. Put on comp B.
    -Task 3 sees no available comp. Puts task 1 on queue and gets put on comp 1.
    -Top of queue (task 1) looks for first available comp, doesn't find one. Pushes task 2 out of comp B. (Make sure you don't ever push the same task twice). Task 2 gets added to queue.
    -Top of queue (task 2) looks for first available comp, doesn't find one. Can't push anything since both possibilities have already been pushed or done a push. Since no push possible, revert back to last fork in the road of possibilities. None found in this case, so Task 3 cannot be placed. Skip it.
    -Task 4 gets put on first available comp. Put on comp A.
    -Task 5 gets put on first available comp. Put on comp B.
    -Again optimal solution found and is correct.

    Hope this makes a little more sense! If not, like I said give me a harder problem set and I'll try and demonstrate again.

    <Keeps fingers crossed that this works in every situation >
    Last edited by PJYelton; 03-07-2003 at 04:32 PM.

  6. #36
    Registered User
    Join Date
    Apr 2002
    Posts
    80
    Recursive Solution:

    All data structures are global! (Bad style, more speed) Let me know if you have any questions on it.

    Code:
    void solveRecurse(int currentJob)
    {
        char currentJobSched = jobs[currentJob].getSchedule();
        int jobSize = jobs.size();
        char getComp;
    
        if (currentJobSched != '-' && currentJob >= 0)
        {
            numOfJobs++;        
            if (numOfJobs > currentBest)
            {
                currentBest = numOfJobs;
                best = jobs;
            }
            computers[currentJobSched - 97].addJob(jobs[currentJob].getEnd());        
        }
        if (currentJob + 1 < jobSize)
        {
            for (int i = 0; i < Job::getMachPerJob(); i++)
            {            
                getComp = jobs[currentJob + 1].getComp(i);
                if (computers[getComp - 97].isAvailable(jobs[currentJob + 1].getStart()))
                {
                    jobs[currentJob + 1].setSchedule(getComp);
                    solveRecurse(currentJob + 1);
                }
            }
            jobs[currentJob + 1].setSchedule('-');
            solveRecurse(currentJob + 1);
        }    
        if (currentJobSched != '-' && currentJob >= 0)
        {
            computers[currentJobSched - 97].removeJob();
            numOfJobs--;
        }    
    }

    Sample test cases: (short ones)

    Each line is a job. Int 1 is start time, int 2 is end time. The chars are the potential computers to be scheduled on.

    A '-' means that the job is not scheduled. All answers that schedule the same number of jobs are valid.

    Remember that all jobs have the same number of computers on which to be scheduled. In other words, in the input file, there are the same # of letters after each job.

    Code:
    Test case 1:
    
    1 4 a
    3 6 a
    6 7 a
    8 10 a
    
    Answer:
    
    1 4 a
    3 6 -
    6 7 a
    8 10 a
    
    Test case 2:
    
    0 1 a b
    0 2 a b
    3 6 b a
    3 4 b a
    2 3 a b
    20 21 a b
    19 20 b a
    5 6 a b
    
    Answer:
    
    0 1 a
    0 2 b
    3 6 -
    3 4 b
    2 3 a
    20 21 a
    19 20 b
    5 6 b
    
    Test case 3:
    
    0 4 a b
    0 2 a b
    3 6 b a
    3 4 b a
    2 3 a b
    20 21 a b
    19 20 b a
    5 6 a b
    
    Answer:
    
    0 4 -
    0 2 a
    3 6 a
    3 4 b
    2 3 -
    20 21 a
    19 20 b
    5 6 b
    
    Test case 4:
    
    0 1 a b c
    2 3 b c d
    2 3 a b c
    4 6 a d c
    4 5 a d c
    4 5 a d c
    6 7 a d c
    
    Answer:
    
    0 1 a
    2 3 d
    2 3 b
    4 6 a
    4 5 c
    4 5 d
    6 7 d
    These test cases are rather short. My greedy (wrong) iterative solution solves these no problem. I would be happy to post longer, more challanging samples, if people desire.


    In addition, I have been told that Belady's algorithm may be applied to a portion of this problem, both for the recursive and the iterative solutions. Any ideas?
    Last edited by BigDaddyDrew; 03-07-2003 at 07:11 PM.

  7. #37
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399
    Yes, please post some more challenging samples. I think I've almost got a semi-tabular solution (pretty similar to PJYelton's algorithim, actually), but I need to make sure I understand the format of the samples first. Reconsider test case 2:
    Code:
    0 1 a b
    0 2 a b  //second
    3 6 b a
    3 4 b a
    2 3 a b  //fifth
    20 21 a b
    19 20 b a
    5 6 a b
    Notice the second job and the fifth job. Even though it may not lead to an optimal solution, can they both be put on the same computer? I wasn't sure if the ending time 2 conflicted with the beginning time 2.

    Also, I'm no longer convinced that there is one optimal solution. For some of the test cases, I got different answers, but still scheduled the same number of jobs. Hopefully the tougher ones will help me figure this out.
    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

  8. #38
    Registered User
    Join Date
    Apr 2002
    Posts
    80
    Hard test cases are on the way...give me a second.

    In test case 2, the second and fifth jobs can NOT be scheduled on the same computer. The times are inclusive, so the time 2 is used by both computers.

    And you are right, in many cases, there may be more than one optimal solution. Optimal solutions will all schedule the same number of jobs, but not necessarily the exact same jobs.

    Code:
    Hard Test Case 1:
    
    1 1 a h
    1 1 b h
    2 2 a h
    2 2 b h
    3 3 c h
    3 3 d h
    4 4 c h
    4 4 d h
    5 5 e h
    5 5 f h
    6 6 e h
    6 6 e h
    7 7 a h
    7 7 c h
    8 8 b h
    8 8 f h
    9 9 a h
    9 9 e h
    10 10 e h
    10 10 b h
    11 11 g h
    11 11 g h
    1 14 a h
    1 14 b h
    1 14 c h
    1 14 d h
    1 14 e h
    1 14 f h
    14 14 g h
    14 14 g h
    14 14 g h
    
    Answer:
    
    1 1 h
    1 1 b
    2 2 h
    2 2 b
    3 3 c
    3 3 h
    4 4 c
    4 4 h
    5 5 e
    5 5 h
    6 6 h
    6 6 e
    7 7 h
    7 7 c
    8 8 b
    8 8 h
    9 9 h
    9 9 e
    10 10 e
    10 10 b
    11 11 g
    11 11 h
    1 14 a
    1 14 -
    1 14 -
    1 14 d
    1 14 -
    1 14 f
    14 14 -
    14 14 h
    14 14 g
    
    Hard Test Case 2:
    
    10 12 a h
    10 12 a h
    20 22 b h
    20 22 b h
    10 55 c h
    10 55 c h
    10 10 a d
    11 11 a d
    10 10 a d
    11 11 a d
    20 20 c d
    20 20 c d
    21 21 c d
    21 21 c d
    1 1 a h
    1 1 b h
    2 2 c h
    2 2 d h
    3 3 a h
    3 3 c h
    4 4 a h
    4 4 d h
    5 5 b h
    5 5 d h
    5 5 b h
    5 5 c h
    1 5 a h
    1 5 b h
    1 5 c h
    1 5 d h
    
    Answer:
    
    10 12 h
    10 12 -
    20 22 h
    20 22 b
    10 55 -
    10 55 -
    10 10 a
    11 11 a
    10 10 d
    11 11 d
    20 20 d
    20 20 c
    21 21 d
    21 21 c
    1 1 h
    1 1 b
    2 2 c
    2 2 d
    3 3 h
    3 3 c
    4 4 h
    4 4 d
    5 5 b
    5 5 d
    5 5 h
    5 5 c
    1 5 a
    1 5 -
    1 5 -
    1 5 -
    
    Hard Test Case 3:
    
    1 1 a h
    1 1 b h
    2 2 a h
    2 2 b h
    3 3 c h
    3 3 d h
    4 4 c h
    4 4 d h
    5 5 e h
    5 5 f h
    6 6 e h
    6 6 e h
    7 7 a h
    7 7 c h
    8 8 b h
    8 8 f h
    9 9 a h
    9 9 e h
    10 10 e h
    10 10 b h
    11 11 g h
    11 11 g h
    1 14 a h
    1 14 b h
    1 14 c h
    1 14 d h
    1 14 e h
    1 14 f h
    14 14 g h
    14 14 g h
    14 14 g h
    15 15 a b
    15 15 a b
    15 30 a h
    30 30 a h
    28 30 a h
    
    Answer:
    
    1 1 h
    1 1 b
    2 2 h
    2 2 b
    3 3 c
    3 3 h
    4 4 c
    4 4 h
    5 5 e
    5 5 h
    6 6 e
    6 6 h
    7 7 h
    7 7 c
    8 8 b
    8 8 h
    9 9 h
    9 9 e
    10 10 e
    10 10 b
    11 11 g
    11 11 h
    1 14 a
    1 14 -
    1 14 -
    1 14 d
    1 14 -
    1 14 f
    14 14 g
    14 14 h
    14 14 -
    15 15 a
    15 15 b
    15 30 -
    30 30 a
    28 30 h
    There are more where that came from!

    I'm currently working on a stack based scheme that mimmicks recursion, but I know it's going to be slow (plus I can't get it to work anyway).
    Last edited by BigDaddyDrew; 03-07-2003 at 11:28 PM.

  9. #39
    Registered User
    Join Date
    Apr 2002
    Posts
    80

    Something else that doesn't work

    I just wrote a function that goes through all permutations of computers. For each permutation, it schedules as many jobs as possible on the first computer, then as many of the remaining jobs as possible on the next computer, etc. At the end, it compares which permutation scheduled the most jobs, and goes with that schedule.

    Doesn't work.

    At least not with the data ordered by end time....

  10. #40
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399
    Code:
    1:  for each task in list:
    2:     for each computer in task availability list:
    3:         place task in computer if possible.
    4:     if task not placed yet
    5:         for each computer in task availabilty list
    6:            place conflicting tasks into a queue and place task in this
    7:                     computer;
    8:            continue until queue is empty or no push possible
    9:                 push top of queue into first available comp or if no
    10:                    available comp, then
    11:                repeat by pushing onto a new comp and adding
    12:                    conflictions to queue
    13:           if queue is empty then successful, move onto next task
    PJ, could you walk me through using your algorithim with, say, the first or the second simple test case? I'm not sure if I'm following you, especially after line 8.
    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

  11. #41
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,643
    If you can rewrite your recursive solution using tail recursion, then turning the recursive solution into an iterative solution shouldn't be too hard (and should be faster). I find it easier when you mimic the stack frame using a stack ADT - so you would put all your locals and recursive function parameters into a struct and push/pop that struct..
    Code:
    //prime the pump
    push initial locals
    
    WHILE stack not empty
       //this is our "recursive" entry point, peek the TOS to get locals
       ...
       //to mimic a recursive call, push and continue
       ...
       //to mimic a "return", pop and continue
    ENDWHILE
    But alas, you probabably knew this. Have you tried coming up with a tail recursive solution?

    gg

  12. #42
    Registered User
    Join Date
    Apr 2002
    Posts
    80
    Codeplug, you're on the exact same page as I am...I began that process last night, but it is something I hadn't done before. With the way my code was coming, it seemed like I was doing a breadth traversal of the tree, rather than a depth traversal. Depth is much more desireable, since we can utilize branching and bounding techniques to get rid of bad solutions.

    I don't believe the recursive fuction can be written with tail recursion, as it is called (# of computers + 1) times within each recursive call. Thus, there will be operations/code/whatever after the recursive calls.

    I have posted my recursive code up there somewhere ( I think I took out my bounding functions ). Would you be willing to get me started on the stack based implementation - either with some hints or pseudo code, or something? I understand the concept fully, in that I wish to imitate the recursive stack frame and the recursive function's activation records, but I'm not able to make the leap to a working solution. I've written up some code that is really messy....and it certainly doesn't work.

    Thanks!

Page 3 of 3 FirstFirst 123
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, 04:03 AM
  4. Flight scheduling algorithm?
    By ChadJohnson in forum A Brief History of Cprogramming.com
    Replies: 14
    Last Post: 01-26-2006, 01:23 AM
  5. Round Robin Scheduling using c.
    By eclipt in forum C Programming
    Replies: 8
    Last Post: 12-28-2005, 03:58 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21