[hotproject-devel] proposal: resource and constraint functions

[Jamey S. <ja...@sh...>]

I've been unhappy with our representations of resource capacity,
resource utilization, and task constraints. This proposal is intended to
inspire some thought on the subject, not to suggest a complete design.

I'd like to re-write some of the definitions given in Crawford [1]. I'll
reproduce the relevant section with my changes here.

Let t be time, B = { true, false }, and N be the set of natural numbers
including 0.

Given: A set of tasks T, a set of resources R, a capacity function
C : R x t -> N, a duration limit function L : T x N -> B, a utilization
function U : T x R x t -> N, a time constraint function W : T x t -> B,
a partial order P on T, and a deadline d.

Find: An assignment of start times S : T -> N and durations D : T -> N
satisfying the following:

1. Precedence constraints: If t1 precedes t2 in the partial order P,
then S(t1) + D(t1) <= S(t2). (Note that this is only end-start
precedence.)

2. Resource constraints: For any time x, let
 running(x) = { t | S(t) <= x <= S(t) + D(t) }
Then for all times x, and all r in R,
 (sum for all t in running(x) over U(t, r, x)) <= C(r, x)

3. Deadline: For all t in T,
 S(t) + D(t) <= d

4. Time constraints: For all times x and all t in T,
 t in running(x) implies (W(t, x) = true)

5. Duration constraints: For all t in T,
 L(t, D(t)) = true

Note that, as far as I know, the only reason for the deadline constraint
is to turn this into a decision problem: "Is there a satisfying schedule
with a makespan of 20 days? Yes? How about 19 days?" I think it's
important for the formulation of the problem, but not important to the
implementation. So I'm not suggesting we need to store a project
deadline.

So the model is that all these hard pieces are just functions, either
boolean- or natural-valued. I propose this model because I know more
about functions than I do about project management, and so finding UIs
and data structures for functions seems easier to me than doing so for,
say, resource capacities.

This also precisely defines the semantics of the various kinds of
constraints.

So. Any comments? Ideas on how to represent functions to the user? Did I
miss any important constraints? Bart, do my changes make scheduling way
harder?

[1]. Crawford, James. "An Approach to Resource Constrained Project
Scheduling." http://www.cirl.uoregon.edu/crawford/papers/albur.ps
-- 
Jamey Sharp <ja...@sh...> - http://jamey.is.dreaming.org/