RE: Fwd: Programming bounty

["Dan Heily" <dan22066 cox net>]

Maurice;

What is puzzling to me is lack of a project end date.  What is the origin of
the backward pass?

By modeling the network of tasks, the order is automatically determined.

Forward pass:  "start" all tasks that have no predecessor (assuming resource
availability).  When a task completes (i.e. time = start time + duration)
then you look at all successors to the completed task.  If the successor has
no uncompleted predecessors, then that successor may be started (again
within resource constraints).  When all tasks are complete, then the
earliest start/finish has been determined for all tasks.

Backward pass:  initially, "start" all tasks with no successor at project
end date minus duration.  When the task completes, then look at its
predecessors.  If all successors to that predecessor have been completed
then that successor may be "started".  When all tasks are complete, you have
determined latest start/finish.

When I say "start" above, I really mean that the start is added to an event
queue.  The event queue kept in time order (gets tricky when running the
clock in reverse during the reverse pass).  After initialization the
simulation is started and just executes until there are no more events.
Upon completion, if all tasks are not complete, then there must be a
resource deadlock (i.e. fewer of a given resource than there are demands for
that resource)

Additionally in both the forward and reverse simulations, whenever a
resource is returned then all tasks waiting on that resource are examined
and "started" if the returning resource is sufficient to unblock the task.

I was able to do linked lists in FORTRAN by determining how the compiler
computes the address of a subscripted variable.  For example, to compute the
location of X(I) i.e. &X(I), the compiler uses the following formula for a 4
byte variable:  &X+4*I-4.  The 4*I converts from words to bytes, and
subtracting 4 converts from base 1 to base 0 i.e. first element is X(1).

The epitome of my simulations was a machine shop simulation that would roll
back lower priority tasks that had allocated a resource that was later
needed by a higher priority task.  The process flows included forks/joins
whereby a process could split and later synchronize.

Let me relook at the people resources again.

Thank you for sharing your thoughts with me.

Dan
Virginia, USA



-----Original Message-----
From: planner-dev-list-bounces gnome org
[mailto:planner-dev-list-bounces gnome org] On Behalf Of Maurice van der Pot
Sent: Wednesday, July 23, 2008 6:59 AM
To: planner-dev-list gnome org
Subject: Re: Fwd: Programming bounty

On Wed, Jul 23, 2008 at 12:22:14AM -0400, Dan Heily wrote:
> This two step simulation needs to be invoked whenever a task or 
> resource is added, deleted or modified.

There is a part of planner doing forward and backward passes and each task
actually does have a latest_start and latest_finish property. 
I suspect this is just not presented to the user, but I have not yet looked
at the code in detail.

However, the above does assume a complete ordering of tasks and determining
that ordering is probably the most difficult problem. An algorithm to
determine this ordering is what I hope will be implemented (or integrated in
the case of libRCPS) in the coming period.

> I did the above work before C++ and object oriented programming (OOP) 
> and the wonderful graphics we now have.  In summary, I know the 
> algorithms, but am not facile with the C++ and OOP that the planner is
written in.

May I ask what languages you are familiar with? Planner is written in C, but
in a way that is sorta OO. It uses libraries such as glib to provide us with
all sorts of nice things such as lists.

> One additional functionality that I also request is the ability to 
> designate a resource as "returnable".  For example if a pool of trucks 
> is shared by various tasks, when a task completes the truck used by 
> the task would be returned to the pool.  i.e. the resource is not consumed
by the task.

Planner makes a distinction between material resources and work resources. I
have not yet noticed the difference though... probably because I only ever
use work resources.

But aren't the work resources (people) exactly the same as the returnable
resources you speak of?

> Please advise if this is a direction you would like to explore.

Your experience could certainly be very valuable for this project.
I regularly have questions about project management or scheduling that I as
a software engineer can't answer nor find the answer to. The answers to
these questions often directly influence the user-visible part of planner.

Regards,
Maurice.

--
Maurice van der Pot

Gentoo Linux Developer   griffon26 gentoo org    http://www.gentoo.org
Gnome Planner Developer  griffon26 kfk4ever com
http://live.gnome.org/Planner