resource-constrained project-planning

Jan Beldman

unread,

May 15, 2001, 5:52:55 AM5/15/01

to

Hi,
Suppose you have n tasks, each requiring a certain amount of a resource,
while there isn't enough resource available to do all the tasks
simultaneously.

Par example:
Task Requirement
A 2
B 1
C 3
and there is 2 available.

Now, I want to know all most small sets of tasks of which the sum of the
requirements exceed the availability. In the example that are the sets {A,B}
and {C}, because all other sets don't exceed the availability or are not the
most small sets (for instance: the set {B,C} does exceed the availability
but a subset of this set, namely {C}, also does and thus the set {B,C} is
not the most small set).

In such a little example the solution is clear, but I want to make a
computerprogramme to get the answer quickly when there are a lot of tasks.
Does somebody know how I could program this in Turbo Pascal?

Thanks in advance,
Jan

Jan Beldman

unread,

May 15, 2001, 6:38:52 AM5/15/01

to

Hi,
I'm sorry but I make a stupid error in my example because the project can
never be performed when a tsks require more resource than that is avialable.
But I think the problem is clear.
Jan

Jan Beldman <j_be...@yahoo.com> wrote in message
news:9dqulh$ivh$1...@nereid.worldonline.nl...

Lutz Tautenhahn

unread,

May 16, 2001, 6:31:19 AM5/16/01

to

Hi Jan,
copy the following code in a blank textfile and save it as *.html.Open the
file with IE or NN.
Hope that helps.
Lutz Tautenhahn
lutz.ta...@wirtschaft.tu-chemnitz.de
www.tu-chemnitz.de/~luta/

<HTML>
<HEAD>
</HEAD>
<BODY>
<SCRIPT LANGUAGE="javascript">
var i, i2, j, dj, r, available_time, num_of_tasks;
var num_of_distinct_sets, set_string, set_time;
var num_of_iterations=0;

//***************** type in your data here *********************

available_time=10;
num_of_tasks=6;
task_name = new Array("C","D","A","B","E","F");
task_time = new Array( 6, 5, 7, 6, 3, 1);

//***************** end of data ********************************

//Note that the algorithm is fast only if available_time<sum(task_time)/2
//Otherwise you should use an algorithm, which solves the complementary
problem

task_rank = new Array(num_of_tasks); //we need the tasks sorted
for (i=0; i<num_of_tasks; i++) task_rank[i]=i;
for (i=0; i<num_of_tasks-1; i++)
{ for (j=i; j<num_of_tasks; j++)
{ if (task_time[task_rank[i]]>task_time[task_rank[j]])
{ r=task_rank[i];
task_rank[i]=task_rank[j];
task_rank[j]=r;
}
}
}

function pow2(ii)
{ var jj, pp=1;
for (jj=0; jj<ii; jj++) pp*=2;
return(pp);
}

num_of_distinct_sets=pow2(num_of_tasks);

Kent Paul Dolan

unread,

Jun 1, 2001, 4:29:56 AM6/1/01

to

"Lutz Tautenhahn" <lutz.ta...@wirtschaft.tu-chemnitz.de> wrote:

[...]

>copy the following code in a blank textfile and save it as *.html.Open the
>file with IE or NN.
>Hope that helps.
>Lutz Tautenhahn
>lutz.ta...@wirtschaft.tu-chemnitz.de
>www.tu-chemnitz.de/~luta/

Well, as the file arrived at my newsreader, three lines damaged by word-wrap
needed to be repaired before it would execute:

//Otherwise you should use an algorithm, which solves the complementary
problem

document.writeln("<TD>set index</TD><TD>set string</TD><TD>set
time</TD></TR>");

document.writeln("<TD>"+j+"</TD><TD>"+set_string+"</TD><TD>"+set_time+"</TD>
</TR>");

each need to be joined to be single lines instead, the first two with an
intervening space, and the last without one.

Since I'd never mucked with Javascript before, I fixed about 20 other things
in the course of finding those three, but those three may be all the real
problems involved in the copy I received, the rest of my changes may just be
matters of taste.

Once those are fixed, the output is very pretty, Lutz, thanks for the chance
to pretend I can program in another language I don't know.

Cheers!

xanthian.
--
Kent Paul Dolan <xant...@well.com>

Lutz Tautenhahn

unread,

Jun 5, 2001, 7:40:07 PM6/5/01

to

I post this to the group, because I think this could be interesting for
other readers, too. Experts should skip this stuff.

> Dear Lutz Tautenhahn,
>
> Recently you sent me a javascript-code which leads to
> the smallest sets of tasks that exceed the
> availability of a certain resource.
> Thanks for that, but unfortunately I cannot read
> javascript, so I don't understand the algorithm. I
> would like to ask you if you can please send me the
> algorithm in words or the program in Pascal.
>
> Thanks in advance,
> best wishes,
> Jan Beldman

Hello Jan,
first let's analyze the problem:
You have n tasks, each item is characterized by a attribute 'requirement',
and you want all 'most small sets' of the tasks, whereby the sum of the
requirements exceeds a given 'availability'.
There are all in all 2^n distinct sets.
Example: with the items A, B, C you get 2^3=8 distinct sets:
{A, B, C}, {A, B}, {A, C}, {A}, {B, C}, {B}, {C}, {}.
Assume you have 2*m tasks, and all the tasks have the same requiremet of 2
units and yor availability is 2*m-1. Then your solution would be all sets
wich consist of exactly m tasks. So you would have
(2m*(2m-1)*...*(m+1))/(m*(m-1)*...*1)=(2m)!/(m!*m!)
distinct sets in your solution. You would need at least (2m)!/(m!*m!) steps
to select this sets.
(2m)!/(m!*m!)=(2m/m)*((2m-1)/(m-1))*...*(m+2)/2*(m+1)/1 > 2 * ... * 2 =2^m
There is not a polynomial upper bound for this, such a problem is also
called NP-hard or NP-complete. You must be aware of, that you could obtain a
large number of sets in your solution (I guess maximum is (2m)!/(m!*m!)).
Now let's get binary: You can identify every set by a unique index.
For example {A, B, C, D} would be binary 1111 wich yields to the index
1+2+4+8=15, then {B, D} would be binary 1010 (not 0101) wich yields to the
index 2+8=10.
Assume the tasks A, B, C, D are sorted, so that A has the smallest
requirement and D the largest. Now you can go through the index and
calculate the sum of requirement for the set, which belongs to that index,
let's look at the code:
j=0;
You could also start from 1 because the empty set with index 0 is never in
your solution
while (j<num_of_distinct_sets)
{ ...
We don't use "for (j=0; j<j<num_of_distinct_sets; j++)"
because we want to do this in less than "num_of_distinct_sets" steps

set_time=0;
for (i=num_of_tasks-1; i>=0; i--)

We go through all tasks, but you could also do

"for (i=0; i<num_of_tasks; i++)"

{ i2=pow2(i);
i2=2^i is a binary number like 0001, 0010, 0100, ... exactly one bit is 1

if ((j & i2) == i2)

In english: if (task i is a member of the set with index j)
The operator "&" is a "bitwise and" operator, for example
"if ((1010 & 0010) == 0010)" asks "Is task B a member of the set {B, D}"
{ ...
set_time+=task_time[task_rank[i]];
then we have to add the task requirement to the set requirement
}
}
After that we can check, if the set requirement exceeds the availability
if (set_time<=available_time) j++;
If not, we take the next set index.
else
{
We have found a "most small set", write this set to the output.
Now we must skip all sets which consist of the tasks which are in the
current set and additional tasks which are smaller than the smallest task
which is in the current set.
For example: current set is 0110 = {B,C}, we must skip 0111 = {A,B,C},
the next set which should be tested is 1000 = {D}
In general: we have to find the lowest bit of the current set index which is
1 and add this to the index of the current set. The lowest bit of 0110 is
0010.
0110+0010=1000
This is what the following code does:

i=1;
dj=0;
while (dj==0)
{ dj = (j & i);

We do a "bitwise and" until the lowest bit which is 1 is found
i*=2;
}
j+=dj;
and add this to the current set index.
}
}
And so we continue until the end. Note that the algorithm requires the tasks
to be sorted. To prevent trouble with word wrapping again, I dont post the
Turbo Pascal code. The file is uploaded to
www.tu-chemnitz.de/~luta/plt/rcpp.pas
Regards, Lutz Tautenhahn