Solved

Scheduling program..

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

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

by:kgpretty
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
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

Author Comment

by:kgpretty
ID: 22646253
How do I solve that?
0
 
LVL 6

Expert Comment

by:RishadanPort
ID: 22646261
Are you sure you want this statement?

"index = 0;"?
0
 
LVL 6

Expert Comment

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

Expert Comment

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

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

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

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

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

Expert Comment

by:RishadanPort
ID: 22646286
oops typo:

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

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

Author Comment

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

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

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

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

Author Comment

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

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

Expert Comment

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

by:RishadanPort
ID: 22646331
Also change this line:

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

to

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

Expert Comment

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

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

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

Open in new window

0
 

Author Comment

by:kgpretty
ID: 22646372
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
ID: 22646373
did you do this line too?
if(M[index] <= T[0][k])
0
 
LVL 53

Expert Comment

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

Expert Comment

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

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

Secure Your Active Directory - April 20, 2017

Active Directory plays a critical role in your company’s IT infrastructure and keeping it secure in today’s hacker-infested world is a must.
Microsoft published 300+ pages of guidance, but who has the time, money, and resources to implement? Register now to find an easier way.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Errors will happen. It is a fact of life for the programmer. How and when errors are detected have a great impact on quality and cost of a product. It is better to detect errors at compile time, when possible and practical. Errors that make their wa…
Article by: SunnyDark
This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

685 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