x
Solved

# Scheduling program..

Posted on 2008-10-05
Medium Priority
532 Views
I'm trying to implement a Job schedule algorithm shown on this website: http://ww3.algorithmdesign.net/sample/ch05-patterns.pdf
on pg. 261.

My source file is attached.

Basically, I get a set of task with start times and finish times and allot them to three machines. The machines are represented by an integer array M in the schedule function. Therefore, the machines used should be an index of 0, 1 or 2.

If I initialise M as follows, I get an index of 0, 1, 2 and 3 in my output... but that's not right is it? Again, I should only be seeing an index of 0, 1, or 2 How do I fix that?
int M[3] = {0, 0, 0};

They only way that I can get the program to work , as I would like, with just three machines (index: 0, 1, 2) is if I initialise M as follows..
int M[2] = {0, 0};
schedule.txt
0
Question by:kgpretty
• 13
• 8
• 5
• +1

LVL 6

Expert Comment

ID: 22646238
Why are you comparing "if(M[index] < T[0][k])", but then setting M[index] to T[1][k]?
0

LVL 6

Expert Comment

ID: 22646248
You have no boundary conditions for M

Eventually in the inner While loop, M's index will go out of bounds
0

Author Comment

ID: 22646251
I'm comparing the start time (T[0][k) on the current job to whatever M[index] is stored. Then, I'm assigning the finish time (T[1][k) to the machine. The finish time is a better indication of whether or not the machine is free.
0

Author Comment

ID: 22646253
How do I solve that?
0

LVL 6

Expert Comment

ID: 22646261
Are you sure you want this statement?

"index = 0;"?
0

LVL 6

Expert Comment

ID: 22646269
(After the while loop you set index back to 0)
0

LVL 6

Expert Comment

ID: 22646273
For your while loop, you could do something lik this if you need the index = 0 to be set...

"while(assigned == false && index <= M_LENGTH)"

and you define M_LENGTH = 2;
0

LVL 6

Expert Comment

ID: 22646274
I really am not 100 percent sure what you are trying to do, so this is just a guess
0

LVL 53

Expert Comment

ID: 22646279
You need 3 elements in the M array, since they represent your 3 machines. What I don't understand, is what you mean by :

>> If I initialise M as follows, I get an index of 0, 1, 2 and 3 in my output...

Can you show the code you used where you observed this behavior ?
0

Author Comment

ID: 22646280
I need to have
index = 0;
after the while loop, otherwise, when it gets to index = 2, all the rest of the jobs will be assigned 2.
0

LVL 6

Expert Comment

ID: 22646285
At his print statement infinity, the index goes out of bounds
0

LVL 6

Expert Comment

ID: 22646286
oops typo:

this "while(assigned == false && index <= M_LENGTH)"

should be while(assigned == false && index < M_LENGTH)"
0

Author Comment

ID: 22646293
Infinity08, I'm talking about the output that I see on the screen from the cout statement.
Here's the cout line:
cout << "Machine " << index << " is assigned Task " << k << endl;
The values for index are 0,1,2 or 3 when I initialise M with 3 elements.
0

LVL 53

Expert Comment

ID: 22646298
>> The values for index are 0,1,2 or 3 when I initialise M with 3 elements.

Can you show your code you used to get that result, please. Did you also fix the problem that RishadanPort pointed out ?
0

Author Comment

ID: 22646302
I tried both :
while(assigned == false && index <= M_LENGTH)    (4 loops)
& while(assigned == false && index < M_LENGTH)   (7 loops)
Each time, the loop doesn't run enough times. It's supposed to run 10 times because 10 tasks need to be assigned.
0

LVL 6

Expert Comment

ID: 22646310
But the output is correct right ? ;-) (when you do while(assigned == false && index < M_LENGTH) )
0

Author Comment

ID: 22646315
The output is correct for those first 7 loops.

Infinity, my code is in the attachments list.
0

LVL 6

Expert Comment

ID: 22646316
change M back to the length of 3, and see what happens

so initialize M[3] = {0, 0, 0} (and do my change as well)...
0

LVL 6

Expert Comment

ID: 22646331
Also change this line:

M[index] < T[0][k]

to

M[index] <= T[0][k]
0

LVL 53

Expert Comment

ID: 22646332
>> Infinity, my code is in the attachments list.

No it's not ;) That code has an array of size 2, not 3. And you claim to have a problem when the size is 3, not 2 ...
0

Author Comment

ID: 22646334
The length of M was set to 3 when I did the tests.

Should I give up trying to find a clear solution and just keep the length of M to 2 ?
0

LVL 6

Accepted Solution

ID: 22646345
Doing all the following changes will make it work
``````bool assigned = false;
const int M_LENGTH = 3;

int M[M_LENGTH] = {0, 0, 0};

int index = 0;

for(int k = 0; k < COL_MAX; k++)
{
//index < M_LENGTH just to make sure it doesn't go out of
//bounds
while(assigned == false && index < M_LENGTH)
{

if(M[index] <= T[0][k]) //if machine has same time,ok
{
M[index] = T[1][k];
assigned = true;
cout << "Machine " << index << " is assigned Task " << k << endl;
}
else
index++;

}//while the task has not yet been assigned

assigned = false;
index = 0;
}
``````
0

Author Comment

ID: 22646372
const int M_LENGTH = 3;

I changed M's implementation to this:
int M[M_LENGTH] = {0, 0, 0};

I changed the while loop header to this:
while(assigned == false && index < M_LENGTH)

I made those 3 changes and jobs 4,6 and 8 are not assigned to a machine.
0

LVL 6

Expert Comment

ID: 22646373
did you do this line too?
if(M[index] <= T[0][k])
0

LVL 53

Expert Comment

ID: 22647937
Maybe it's best to show the current code you are working with ...
0

LVL 31

Expert Comment

ID: 22648619
The algorithm you posted in 'schedule.txt' doesn't really implement the algorithm shown in the PDF.

It can't work with a fixed number of machines. In the PDF there's a code with the comment 'add new machine'. This IMO is essential. In your code this would be the case 'if ( assigned == false )' after the 'while'-loop.

You can easily see that your code with fixed number of 3 machines can't assign the 4'th task since it has a start-time = 3, the three tasks before have end-times = 3, 4, 6. So, there's no free machine where the current task can be scheduled to.

ZOPPO
0

LVL 53

Expert Comment

ID: 22648656
>> This IMO is essential.

The alternative of course is for the algorithm to either :

(a) report its failure to the user
(b) perform a best effort, and allocate as many of the tasks as possible
0

## Featured Post

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.