A resource precedence graph is a directed graph that can be associated with a resource and whose nodes are the resource constraints posted on the resource.

On a resource precedence graph, an edge between two resource constraints (rct1, rct2) means that the activity of rct1 is constrained to execute before the activity of rct2, provided that both resource constraints rct1 and rct2 definitely affect the availability of the resource (processing time and required capacity strictly greater than zero).

A resource precedence graph constraint is a constraint that creates a precedence graph structure for the resource with which it is associated and allows propagation of the precedence information contained in this graph on the variables of the resource constraints (start and end time, processing time, required capacity).

A resource precedence graph constraint can be created on a resource with the member function IlcResource::makePrecedenceGraphConstraint.

A resource precedence graph constraint is automatically created for each unary resource with a sequence constraint.

When a resource is associated with a precedence graph constraint, new precedence relations between resource constraints are automatically discovered and added to the graph by the disjunctive constraint, the edge finder, and the sequence constraint. New edges on the resource precedence graph are also discovered when the following precedence constraints are posted on the solver between two activities that require the resource:

• IlcPrecedenceConstraintType::IlcStartsAfterEnd with positive or null delay
• IlcPrecedenceConstraintType::IlcStartsAtEnd with positive or null delay
• IlcPrecedenceConstraintType::IlcEndsAtStart with negative or null delay

Some member functions of the class IlcResourceConstraint allow direct addition of new relations on the graph (IlcResourceConstraint::setNext, IlcResourceConstraint::setSetup, IlcResourceConstraint::setSuccessor, IlcResourceConstraint::setTeardown). Before entering the search, it is also possible to remove relations already added on the graph (IlcResourceConstraint::unsetNext, IlcResourceConstraint::unsetSetup, IlcResourceConstraint::unsetSuccessor, IlcResourceConstraint::unsetTeardown).

Transitive closure of the graph is automatically computed and maintained during the search.

The information stored in the precedence graph can be accessed with member functions of the class IlcResourceConstraint --such as IlcResourceConstraint::hasAsNext, IlcResourceConstraint::isDirectlySucceededBy, IlcResourceConstraint::isSucceededBy --and with the resource constraint iterator IlcResourceConstraintIterator. The availability of these accessors and iterators is restricted before entering the search, as the transitive closure of the graph has not been computed.

Status of Resource Constraints in a Precedence Graph

In a resource precedence graph, a resource constraint rct is said to surely contribute if and only if:

• rct has been posted, and
• the time extent of rct is not IlcNever, and
• the minimal processing time of the activity of rct is strictly greater than zero if the time extent of rct is IlcTimeExtent::IlcFromStartToEnd, and
• the minimal capacity required by rct is strictly greater than zero if rct is a capacity resource constraint.

In a resource precedence graph, a resource constraint rct is said to not possibly contribute if and only if it is sure that rct will not affect the availability of the resource. That is:

• the opposite of rct is posted, or
• the time extent of rct is IlcNever, or
• the processing time of the activity is equal to zero and the time extent of rct is IlcTimeExtent::IlcFromStartToEnd, or
• rct is a capacity resource constraint and the capacity required by rct is equal to zero.

Relative Positions of Resource Constraints in a Precedence Graph

Let rct1 and rct2 be two resource constraints on the same resource precedence graph.

• rct2 is said to be a successor of rct1 on the graph if the fact that both rct1 and rct2 definitely affect the availability of the resource implies that the activity of rct2 is constrained to execute after the activity of rct1 (that is, the start time of the activity of rct2 is greater than or equal to the end time of the activity of rct1).
• The pair (rct1,rct2) is said to be unranked on the graph if and only if neither rct1 is a successor of rct2 nor rct2 is a successor of rct1.
• rct1 is said to be ranked on the graph if and only if there is no resource constraint rct such that the pair (rct1,rct) is unranked.
• rct2 is said to be a direct successor of rct1 on the graph if and only if rct2 is a successor of rct1 and there is no resource constraint rct that definitely affects the availability of the resource such that rct is a successor of rct1 and rct2 is a successor of rct on the current state of the resource precedence graph.
• rct2 is said to be possibly next to rct1 on the graph if and only if either the pair (rct1,rct2) is unranked or rct2 is a direct successor of rct1.
• If the resource is closed, rct2 is said to be next to rct1 on the graph if and only if both rct1 and rct2 are ranked and rct2 is a direct successor of rct1. If rct2 is next to rct1, no other resource constraint can be scheduled between rct1 and rct2. In a resource precedence graph, a resource constraint can have several direct successors whereas it has at most one next resource constraint.
• If the resource is not closed, no next relation can be deduced because other resource constraints could still be added.
• rct1 is said to be a setup resource constraint if and only if no resource constraint rct exists such that rct1 is next to rct.
• rct1 is said to be a teardown resource constraint if and only if no resource constraint rct can be next to it.

Example

Consider a closed resource with five resource constraints rct1, rct2, rct3, rct4, and rct5 that definitely affect the availability of the resource. Suppose that the following relations have been added:

• rct1 is succeeded by rct2 and rct3,
• rct2 is succeeded by rct4 and rct5,
• rct3 is succeeded by rct4, and
• rct4 is succeeded by rct5.

After the transitive closure of the graph has been computed during search, we find that:

• rct1 is succeeded by rct5
• rct2 is not directly succeeded by rct5 because rct4 is necessarily between rct2 and rct5
• the pair (rct2, rct3) is not ranked
• the pair ( rct3, rct5) is ranked because rct3 is succeeded by rct5
• rct4 is ranked
• rct4 has rct5 as next resource constraint
• rct3 has no next resource constraint as there are still two possible candidates: rct2 and rct4
• rct4 is not a next resource constraint of rct3
• rct1 is a setup resource constraint
• rct5 is a teardown resource constraint

This list is not exhaustive and, of course, the initial relations are still valid in the transitive closure.

Precedence Graph Events and Delta Sets of Resource Constraints

Several events can be defined on a resource constraint with a precedence graph (IlcResource::whenDirectPredecessors, IlcResource::whenDirectSuccessors, IlcResource::whenPredecessors, IlcResource::whenSuccessors, IlcResource::whenNext, IlcResource::whenPrevious). These events are triggered as soon as the corresponding set of resource constraints is modified because the structure of the precedence graph has changed.

The modifications of these sets of resource constraints are stored in special sets called delta sets. These delta sets can be accessed during the execution of the goals associated with the event (see IlcResourceConstraintDeltaIterator). When all the graph events associated with a resource constraint have been processed, these delta sets are cleared.

For example, the following code displays the set of new direct successor links in the graph as soon as they are discovered.

class PrintCtI :public IlcConstraintI {    
      public:
      PrintCtI(IloSolver solver) :IlcConstraintI(solver) {}
      void printNewDirectSuccessors(IlcResourceConstraint rct) {
        getSolver().out() << "New direct successors of " << rct << ":" << endl;
        for (IlcResourceConstraintDeltaIterator ite(rct, IlcDirectSuccessors); ite.ok(); ++ite)
             getSolver().out() << "\t" << *ite << endl;
         }
      };

      ILCRESOURCEDEMON(PrintDirectSucc, PrintCtI, printNewDirectSuccessors);


      PrintCtI* printer = new PrintCtI(solver);
      IlcResource resource ...;

      resource.whenDirectSuccessors(PrintDirectSucc(printer));

The light precedence graph is a light version of the precedence graph constraint on unary resources. It is a global constraint that maintains the sequence of activities that have been ranked first, the sequence of activities that have been ranked last and a partition of the other (unranked) activities according to their status (Not)PossibleFirst/Last. The light precedence graph constraint is sufficient to enforce the unit capacity of the resource and the successor links between resource constraints. The main interest of the light precedence graph relies on the fact that its average complexity is linear with the number of activities.

The functionality consists of two member functions:

• IlcResource::makeLightPrecedenceGraphConstraint allows the creation and return of a light precedence graph constraint.
• IlcResource::hasLightPrecedenceGraphConstraint returns IlcTrue if and only if a light precedence graph constraint has been created on the resource.

When the light precedence graph is created and posted on a unary resource, the member function IlcResource::hasRankInfo returns IlcTrue, and it allows the use of the rank functionalities listed below:

• On the methods IlcResourceConstraint::rankFirst, IlcResourceConstraint::rankNotFirst, IlcResourceConstraint::rankLast, IlcResourceConstraint::rankNotLast, IlcResourceConstraint::setSuccessor, IlcResourceConstraint::isPossibleFirst, IlcResourceConstraint::isPossibleLast, IlcResourceConstraint::isRanked, IlcResourceConstraint::isRankedFirst, and IlcResourceConstraint::isRankedLast.
• Also on the methods IlcUnaryResource::isRanked, IlcResource::whenRankedFirstRC, IlcResource::whenRankedLastRC, IlcResource::getLastRankedFirstRC, IlcResource::getLastRankedLastRC, IlcResource::getOldLastRankedFirstRC, and IlcResource::getOldLastRankedLastRC.
• On the nested iterators IlcResource::ResourceConstraintIterator and IlcResource::ResourceConstraintDeltaIterator.
• And on the goals IlcRank and IlcRankBackward.

Note that both the disjunctive constraint (makeDisjunctiveConstraint) and the (classical) precedence graph constraint (makePrecedenceGraphConstraint) automatically create a light precedence graph constraint. The light precedence graph constraint should be used on unary resources with a large number of activities when the quadratic complexity of the disjunctive constraint is too expensive.

Whereas the nodes of a resource precedence graph represent resource constraints (see above), we describe in this section the concept of schedule precedence graph whose nodes are the activities created on a schedule.

On a schedule precedence graph, an edge between two activities ( act1, act2) means that activity act1 is constrained to execute before activity act2.

A schedule precedence graph constraint is a constraint that creates a precedence graph structure for the schedule with which it is associated and allows propagation of the precedence information contained in this graph on the variables of the activities (start and end time).

Creating a Schedule Precedence Graph Constraint

A schedule precedence graph constraint can be created on a schedule with the member function IlcSchedule::makePrecedenceGraphConstraint.

Overview of Functions Related to Schedule Precedence Graphs

When a schedule is associated a precedence graph constraint, the coherence between this global graph and the resource precedence graphs is ensured: when new precedence relations are discovered on a resource with a precedence graph, these relations are also added on the schedule precedence graph and, reciprocally, when new precedence relations are added on the schedule precedence graph, the resource precedence graphs are updated accordingly.

New edges on the schedule precedence graph are automatically discovered when the following precedence constraints are posted on the solver:

• IlcPrecedenceConstraintType::IlcStartsAfterEnd with positive or null delay
• IlcPrecedenceConstraintType::IlcStartsAtEnd with positive or null delay
• IlcPrecedenceConstraintType::IlcEndsAtStart with negative or null delay

Some member functions of the class IlcActivity allow direct addition of new precedence relations on the graph (IlcActivity::setSuccessor). Before entering the search, it is also possible to remove relations already added on the graph (IlcActivity::unsetSuccessor).

Note that adding a new precedence relation on the graph leads exactly to the same propagation as posting a IlcPrecedenceConstraintType::IlcStartsAfterEnd constraint with null delay.

Transitive closure of the graph is automatically computed and maintained during the search.

The information stored in the precedence graph can be accessed with member functions of the class IlcActivity (such as IlcActivity::isDirectlySucceededBy, and IlcActivity::isSucceededBy), and with the activity iterator IlcActivityIterator. The availability of these accessors and iterators is limited before entering the search, as the transitive closure of the graph has not been computed.

Relative Positions of Activities in a Precedence Graph

Let act1 and act2 be two activities of a schedule with precedence graph.

• Activity act2 is said to be a successor of act1 on the graph if it is constrained to execute after act1.
• The pair (act1,act2) is said to be unranked on the graph if and only if neither act1 is a successor of act2 nor act2 is a successor of act1.
• Activity act1 is said to be ranked on the graph if and only if there is no activity act such that the pair (act1,act) is unranked.
• Activity act2 is said to be a direct successor of act1 on the graph if and only if act2 is a successor of act1 and there is no activity act of the schedule such that act is a successor of act1 and act2 is a successor of act on the current state of the schedule precedence graph.

Precedence Graph Events and Delta Sets of Activities

Several events can be defined on an activity with precedence graph (IlcSchedule::whenDirectPredecessors, IlcSchedule::whenDirectSuccessors, IlcSchedule::whenPredecessors, IlcSchedule::whenSuccessors.) These events are triggered as soon as the corresponding set of activities is modified because the structure of the precedence graph has changed.

The modifications of these sets of activities are stored in special sets called delta sets. These delta sets can be accessed during the execution of the goals associated with the event (see IlcActivityDeltaIterator). When all the graph events associated with an activity have been processed, then these delta sets are cleared.

Example

For example, the following code displays the set of new direct successors of the activity act as soon as new direct successors of act are discovered on the precedence graph.

class PrintCtI :public IlcConstraintI {   
  public:
     PrintCtI(IloSolver solver) :IlcConstraintI(solver) {}
     void printNewDirectSuccessors(IlcActivity act) {
          getSolver().out() << "New direct successors of " << act << ":" << 
  endl;
          for (IlcActivityDeltaIterator ite(act, IlcDirectSuccessors); 
  ite.ok(); ++ite)
          getSolver().out() << "\t" << *ite << endl;
     }
  };

ILCRESOURCEDEMON(PrintDirectSucc, PrintCtI, printNewDirectSuccessors);

PrintCtI* printer = new PrintCtI(solver);
IlcSchedule sched ...;

sched.whenDirectSuccessors(PrintDirectSucc(printer));

See Also

IlcActivity, IlcActivityIterator, IlcActivityIteratorFilter, IlcActivityDeltaIterator, IlcResource, IlcResourceConstraint, IlcResourceConstraintIterator, IlcResourceConstraintDeltaIterator, IlcResourceConstraintIteratorFilter