Learn how to a build a cloud-first strategyRegister Now

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 531
  • Last Modified:

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
0
kgpretty
Asked:
kgpretty
  • 13
  • 8
  • 5
  • +1
1 Solution
 
RishadanPortCommented:
Why are you comparing "if(M[index] < T[0][k])", but then setting M[index] to T[1][k]?
0
 
RishadanPortCommented:
You have no boundary conditions for M

Eventually in the inner While loop, M's index will go out of bounds
0
 
kgprettyAuthor Commented:
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
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 
kgprettyAuthor Commented:
How do I solve that?
0
 
RishadanPortCommented:
Are you sure you want this statement?

"index = 0;"?
0
 
RishadanPortCommented:
(After the while loop you set index back to 0)
0
 
RishadanPortCommented:
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
 
RishadanPortCommented:
I really am not 100 percent sure what you are trying to do, so this is just a guess
0
 
Infinity08Commented:
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
 
kgprettyAuthor Commented:
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
 
RishadanPortCommented:
At his print statement infinity, the index goes out of bounds
0
 
RishadanPortCommented:
oops typo:

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

should be while(assigned == false && index < M_LENGTH)"
0
 
kgprettyAuthor Commented:
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
 
Infinity08Commented:
>> 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
 
kgprettyAuthor Commented:
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
 
RishadanPortCommented:
But the output is correct right ? ;-) (when you do while(assigned == false && index < M_LENGTH) )
0
 
kgprettyAuthor Commented:
The output is correct for those first 7 loops.

Infinity, my code is in the attachments list.
0
 
RishadanPortCommented:
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
 
RishadanPortCommented:
Also change this line:

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

to

M[index] <= T[0][k]
0
 
Infinity08Commented:
>> 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
 
kgprettyAuthor Commented:
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
 
RishadanPortCommented:
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
 
kgprettyAuthor Commented:
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
 
RishadanPortCommented:
did you do this line too?
if(M[index] <= T[0][k])
0
 
Infinity08Commented:
Maybe it's best to show the current code you are working with ...
0
 
ZoppoCommented:
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
 
Infinity08Commented:
>> 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

Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

  • 13
  • 8
  • 5
  • +1
Tackle projects and never again get stuck behind a technical roadblock.
Join Now