Solved

Scheduling program..

Posted on 2008-10-05
27
520 Views
Last Modified: 2012-05-05
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
Comment
Question by:kgpretty
  • 13
  • 8
  • 5
  • +1
27 Comments
 
LVL 6

Expert Comment

by:RishadanPort
Comment Utility
Why are you comparing "if(M[index] < T[0][k])", but then setting M[index] to T[1][k]?
0
 
LVL 6

Expert Comment

by:RishadanPort
Comment Utility
You have no boundary conditions for M

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

Author Comment

by:kgpretty
Comment Utility
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

by:kgpretty
Comment Utility
How do I solve that?
0
 
LVL 6

Expert Comment

by:RishadanPort
Comment Utility
Are you sure you want this statement?

"index = 0;"?
0
 
LVL 6

Expert Comment

by:RishadanPort
Comment Utility
(After the while loop you set index back to 0)
0
 
LVL 6

Expert Comment

by:RishadanPort
Comment Utility
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

by:RishadanPort
Comment Utility
I really am not 100 percent sure what you are trying to do, so this is just a guess
0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
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

by:kgpretty
Comment Utility
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

by:RishadanPort
Comment Utility
At his print statement infinity, the index goes out of bounds
0
 
LVL 6

Expert Comment

by:RishadanPort
Comment Utility
oops typo:

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

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

Author Comment

by:kgpretty
Comment Utility
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
Highfive Gives IT Their Time Back

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
>> 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

by:kgpretty
Comment Utility
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

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

Author Comment

by:kgpretty
Comment Utility
The output is correct for those first 7 loops.

Infinity, my code is in the attachments list.
0
 
LVL 6

Expert Comment

by:RishadanPort
Comment Utility
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

by:RishadanPort
Comment Utility
Also change this line:

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

to

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

Expert Comment

by:Infinity08
Comment Utility
>> 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

by:kgpretty
Comment Utility
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

by:
RishadanPort earned 60 total points
Comment Utility
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;

}

Open in new window

0
 

Author Comment

by:kgpretty
Comment Utility
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.
0
 
LVL 6

Expert Comment

by:RishadanPort
Comment Utility
did you do this line too?
if(M[index] <= T[0][k])
0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
Maybe it's best to show the current code you are working with ...
0
 
LVL 30

Expert Comment

by:Zoppo
Comment Utility
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

by:Infinity08
Comment Utility
>> 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

Do You Know the 4 Main Threat Actor Types?

Do you know the main threat actor types? Most attackers fall into one of four categories, each with their own favored tactics, techniques, and procedures.

Join & Write a Comment

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.

744 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

18 Experts available now in Live!

Get 1:1 Help Now