Thread: Scheduling Algo

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.

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.

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 >

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?

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.

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).

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.