Solved

Scheduling program..

Posted on 2008-10-05
27
527 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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
Industry Leaders: 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

Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

Many modern programming languages support the concept of a property -- a class member that combines characteristics of both a data member and a method.  These are sometimes called "smart fields" because you can add logic that is applied automaticall…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

696 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