IlcSetTimesBackward

This function creates and returns a goal that assigns an end time to all activities managed by schedule. If the argument criterion is given, then the assignments are made to maximize criterion. The activity selector aSel selects the next activity. By default, that is, if no activity selector is given as an argument, the activity selector used is defined as follows:

 IloSelector<IlcActivity,IlcSchedule> aSel = IlcActivityInScheduleSelector(s);
 sel.setPredicate(!IlcActivityEndVarBoundPredicate(s) &&
		    !IlcActivityPostponedBackwardPredicate(s));
 sel.setComparator(IlcLexicalComposition(IlcCompareMax(IlcActivityEndMaxEvaluator(s)),
					   IlcCompareMax(IlcActivityStartMinEvaluator(s))));

The function is designed to efficiently schedule activities in an anti-chronological order. It considers only solutions that can be produced as follows: in each step, choose an unscheduled activity A of maximal latest end time and schedule it as late as possible, as allowed by the previously scheduled activities (which have greater end times than A).

Internally, the function uses the schedule-or-postpone-backward method that works as follows.

A selected activity is assigned to its latest end time.
If that end time leads to a failure, the activity is postponed backward until its latest end time has been removed. This removal can occur as a result of a combination of decisions and propagation.

Before assigning the latest end time to an activity, with this candidate end time et, it is determined whether a backward postponed activity actP exists that can be or should be scheduled after et, that is, whether actP.getStartMax() >= et or actP.getEndMin() >= et. If this is the case, a fail is generated based on the reasoning that if we have “normal” precedence and resource constraints, the latest end time of actP will never be removed and thus actP will remain postponed backward and no solution will be found in this branch of the search tree.

As implied by the above description, IlcSetTimesBackward can be thought of as a “mirror image” of IlcSetTimes: rather than scheduling chronologically according to earliest start times and postponement, it schedules anti-chronologically according to latest end times and “backward” postponement. Consequently, there are also mirror image situations where IlcSetTimesBackward performs an incomplete search. To examine this, let's adapt the first example presented in IlcSetTimes. Assume we have an activity B that can start a maximal 50 units after the start of an activity A which can be expressed by a precedence constraint with negative delay.

A.startsAfterStart(B, -50)

Given a scheduling horizon of 1000, suppose that A cannot be scheduled at a later time than 900 since it requires a resource that has a maximal capacity of 0 in the interval [900,1000). Then B cannot be scheduled after time 950 even if there are no later activities. IlcSetTimesBackward will not find a solution here, because it will attempt to assign B to an end time of 1000. When this fails, it will postpone-backward B but then realize that there are no other activities that can be schedule after B and therefore it concludes that there are no solutions. Note that in this very simple case, it is likely that constraint propagation will discover that 950 is the actual latest end time of B and so IlcSetTimesBackward will successfully find a solution. However, if this situation is part of a larger, more complex constraint interaction, it cannot be guaranteed that constraint propagation will discover the globally consistent latest end time. In such a situation, then, a solution will be missed.

Similarly, the code presented in IlcSetTimes can be easily adapted to produce an example where IlcSetTimesBackward concludes that no solutions exist, even when there is one.

In general, IlcSetTimesBackward can miss solutions if there are precedence constraints with negative delay, if the processing time of an activity depends on its start or end time, or if reservoirs are used.

Note

WARNING In order to ensure a purely chronological scheduling, the supplied activity selector should always choose an unscheduled activity of minimal earliest start time. Furthermore, scheduling an activity at time t should not have an impact on the earliest start times of activities that have been scheduled earlier.

In particular, care should be taken in using precedence constraints with a negative delay, activities where the processing time depends on the start or end time of the activity, and reservoirs.

See IloSelector in the IBM ILOG Solver Reference Manual for more information.