kgpretty
asked on
Scheduling program..
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
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
Why are you comparing "if(M[index] < T[0][k])", but then setting M[index] to T[1][k]?
You have no boundary conditions for M
Eventually in the inner While loop, M's index will go out of bounds
Eventually in the inner While loop, M's index will go out of bounds
ASKER
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.
ASKER
How do I solve that?
Are you sure you want this statement?
"index = 0;"?
"index = 0;"?
(After the while loop you set index back to 0)
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;
"while(assigned == false && index <= M_LENGTH)"
and you define M_LENGTH = 2;
I really am not 100 percent sure what you are trying to do, so this is just a guess
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 ?
>> 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 ?
ASKER
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.
index = 0;
after the while loop, otherwise, when it gets to index = 2, all the rest of the jobs will be assigned 2.
At his print statement infinity, the index goes out of bounds
oops typo:
this "while(assigned == false && index <= M_LENGTH)"
should be while(assigned == false && index < M_LENGTH)"
this "while(assigned == false && index <= M_LENGTH)"
should be while(assigned == false && index < M_LENGTH)"
ASKER
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.
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.
>> 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 ?
Can you show your code you used to get that result, please. Did you also fix the problem that RishadanPort pointed out ?
ASKER
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.
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.
But the output is correct right ? ;-) (when you do while(assigned == false && index < M_LENGTH) )
ASKER
The output is correct for those first 7 loops.
Infinity, my code is in the attachments list.
Infinity, my code is in the attachments list.
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)...
so initialize M[3] = {0, 0, 0} (and do my change as well)...
Also change this line:
M[index] < T[0][k]
to
M[index] <= T[0][k]
M[index] < T[0][k]
to
M[index] <= T[0][k]
>> 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 ...
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 ...
ASKER
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 ?
Should I give up trying to find a clear solution and just keep the length of M to 2 ?
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
I added this line:
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.
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.
did you do this line too?
if(M[index] <= T[0][k])
if(M[index] <= T[0][k])
Maybe it's best to show the current code you are working with ...
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
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
>> 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
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