Solved

# Scheduling program..

Posted on 2008-10-05
520 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

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

LVL 6

Expert Comment

You have no boundary conditions for M

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

Author Comment

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

How do I solve that?
0

LVL 6

Expert Comment

Are you sure you want this statement?

"index = 0;"?
0

LVL 6

Expert Comment

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

LVL 6

Expert Comment

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

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

LVL 53

Expert Comment

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

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

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

LVL 6

Expert Comment

oops typo:

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

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

Author Comment

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

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

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

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

Author Comment

The output is correct for those first 7 loops.

Infinity, my code is in the attachments list.
0

LVL 6

Expert Comment

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

Also change this line:

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

to

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

LVL 53

Expert Comment

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

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

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

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

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

LVL 53

Expert Comment

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

LVL 30

Expert Comment

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

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

This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why tâ€¦
C++ Properties One feature missing from standard C++ that you will find in many other Object Oriented Programming languages is something called a Property (http://www.experts-exchange.com/Programming/Languages/CPP/A_3912-Object-Properties-in-C.htâ€¦
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.