Class IlcDiscreteResource

An instance of the class IlcDiscreteResource represents a resource of discrete capacity. Capacity can vary over time: at any given time, the capacity represents the number of copies or instances of the resource that are available, for example, the number of milling machines available in a manufacturing shop or the number of bricklayers at work on a construction site. By discrete, we mean that capacity is defined to be a non-negative integer.

Each activity may require some amount of the resource capacity, for example, one milling machine or three bricklayers. This requirement is represented by resource constraints, and propagating these constraints entails an update of the earliest and latest start and end times of activities.

Theoretical and Maximal Capacity

The theoreticalcapacity of a discrete resource is a bound (that is, a limit) on the amount of capacity that can be used at any point in time. This idea can be contrasted with the maximal capacity that can be used "in practice" at a particular point in time or over a particular interval of time. The maximal capacity typically varies over time, while the theoretical capacity is an intrinsic property of the resource. The theoretical capacity can be infinite. Also, at any point in time, the maximal capacity cannot exceed the theoretical capacity.

Minimal Capacity

It is also possible to constrain the capacity used so that it exceeds some minimal capacity over some interval of time. An inconsistency will be detected if at any point in time the minimal capacity exceeds the maximal capacity.

Constraints on Discrete Resources

For discrete resources, there are several methods to take into account the constraints concerning a resource.

• The first method allows capacity to vary over time: at any given time, a maximal and a minimal capacity can be defined representing the number of instances of the resource that are available at that time. This method depends on posting a timetable constraint. This method is sound, which means that it ensures that any schedule on the resource satisfy the maximal and minimal capacity constraints.
• A second method deals only with requiring activities. It consists of posting a balance constraint to insure that the theoretical capacity is satisfied. This constraint analyzes the precedence relations between activities requiring the resource, and discovers new precedences as well as new time bounds. Provided that the maximal capacity of the resource is constant over time, this method is sound, which means that it ensures that any schedule on the resource satisfies the maximal capacity constraints. This method does not handle the minimal capacity of the resource.
• A third method consists of posting a global disjunctive constraint. This constraint ensures that each pair of activities that require a combined capacity that exceeds the capacity of the resource are not scheduled at the same time. In general, using this constraint alone is not enough to ensure that any schedule on the resource satisfy the maximal capacity constraints so that this method must be used in conjunction with either the timetable or the balance constraint.

Note that when you use this third method, you can increase the level of propagation even further: rather than considering only pairs of activities (A1 A2) to prove that A1 must precede A2 or vice-versa, the constraint propagation process can consider arbitrary tuples {A1 ... An} of activities to prove that some activity Ai must execute first (or must execute last) among the activities in the tuple, {A1 ... An}. This algorithm is known as edge-finding.

Printing or Displaying Discrete Resources

The printed representation of an instance of the class IlcDiscreteResource consists of its name, followed by information about its capacity enclosed in brackets. For example:

[10] represents a discrete resource with a capacity equal to 10.

If the Solver trace is active and the resource is not named, the string "IlcDiscreteResource" is followed by the address of the implementation object. The address will be enclosed in parentheses.

For more information, see Balance Constraint, Disjunctive Constraint, Edge Finder, Timetable, and Transition Time in Scheduler Engine.

This constructor creates a new instance of IlcDiscreteResource and adds it to the set of resources managed by schedule. The capacity of the resource is limited to capacity.

The argument timetable indicates whether the standard timetable constraint should be posted. The standard timetable constraint manages the capacity of the resource from the time origin to the time horizon of the given schedule and allows the capacity to change at any point in time; that is, it defines a time step of 1 (one).

This constructor creates a new instance of IlcDiscreteResource and adds it to the set of resources managed by schedule. The capacity of the resource is limited to capacity.

The argument ttobj indicates which transition time function will be used for the invoking resource. The argument ttobj must have been built with an instance of IlcTransitionTable. An instance of IloSolver::SolverErrorException is thrown if this is not the case.

Transition times are taken into account when the disjunctive constraint or the type timetable constraint is posted. Transition times are only propagated between two activities that are incompatible. As the disjunctive constraint defines incompatibility based on the resource demand of the activities and the type timetable constraint defines incompatibility based on the transition types of the activities, they do not propagate in the same manner. Please see Transition Time in Scheduler Engine and Type Timetable Constraint for more information. Note that when the precedence graph constraint is posted, transition times are also propagated between successor resource constraints.

The argument timetable indicates whether the standard timetable constraint should be posted. The standard timetable constraint manages the capacity of the resource from the time origin to the time horizon of the given schedule and allows the capacity to change at any point in time; that is, it defines a time step of 1 (one).

This member function returns the theoretical capacity of the invoking resource, that is, the capacity that was passed to the resource constructor.

This member function returns the maximal capacity that can be used at the given time. An instance of IloSolver::SolverErrorException is thrown if the timetables of the invoking resource do not cover the given time.

This member function returns the maximal value of the maximal resource capacity over the interval [timeMin, timeMax). An instance of IloSolver::SolverErrorException is thrown if the timetables of the invoking resource do not cover the complete interval indicated by [timeMin, timeMax).

This member function returns the maximal value of the minimal resource capacity over the interval [timeMin, timeMax). An instance of IloSolver::SolverErrorException is thrown if the timetables of the invoking resource do not cover the complete interval indicated by [timeMin, timeMax).

This member function returns the minimal capacity that must be used or is actually used at the given time. An instance of IloSolver::SolverErrorException is thrown if the timetables of the invoking resource do not cover the given time.

This member function returns the minimal value of the maximal resource capacity over the interval [timeMin, timeMax). An instance of IloSolver::SolverErrorException is thrown if the timetables of the invoking resource do not cover the complete interval indicated by [timeMin, timeMax).

This member function returns the minimal value of the minimal resource capacity over the interval [timeMin, timeMax). An instance of IloSolver::SolverErrorException is thrown if the timetables of the invoking resource do not cover the complete interval indicated by [timeMin, timeMax).

This member function measures the overall capacity still available of the invoking resource. To do so, it looks at all the resource constraints that surely use the invoking resource and for which the activities have not yet been assigned a start time and calculates their overall minimal start time, smin, and their overall maximal end time, emax. It then computes the sum of all minimal energies of the activities that should be processed between smin and emax. It returns the maximal available energy between smin and emax minus this calculated sum of minimal energies; that is,

The minimal energy of an activity is defined as the minimum of the product of the duration of the activity and the required capacity of the activity on the resource.

Note that the global slack does not take into account the maximal capacity profile or the break list eventually defined on the invoking resource.

This member function returns the minimal slack over all intervals [t1, t2) where t1 corresponds to the earliest start time of an activity and t2 corresponds to the latest end time of an activity and for which it holds that [t1, t2) is included in the interval [smin, emax) where smin is the overall minimal start time and emax the overall maximal end time of the set of activities that surely use the invoking resource and that have not yet been assigned a start time.

The slack in an interval [t1, t2) is defined as (t2 - t1)*getCapacity - sumEnergy(t1, t2), where sumEnergy(t1, t2) is the sum of the minimal energy of activities that have to be scheduled between t1 and t2. The minimal energy of an activity is defined as the minimum of the product of the duration of the activity and the required capacity of the activity on the resource.

If all activities that surely use the resource have been assigned a start time, this member function returns the product of the capacity of the resource and the difference between the scheduling horizon and the scheduling origin ((schedule.getTimeMax() - schedule.getTimeMin())*getCapacity(), where schedule is the schedule of the invoking resource).

Note that the local slack does not take into account the maximal capacity profile or the break list eventually defined on the invoking resource.

Example

Let's consider an example. Let's say we're scheduling three activities, A, B, and C, of which we know that activity A has a duration of only two days and can take place anytime in the next twenty days; activity B lasts 5 days, cannot start before day 1, and must be finished by day 12; and finally activity C will last 4 days, can start on day 2, and must be finished by day 13. All 3 activities require a capacity of 1 from a resource with a capacity of 2

If we consider the problem globally, we look at all the earliest start times, and among those values, we take the minimal. That is, we take the smallest of the earliest start times (that's day 0 for activity A) and the last of the latest end times (that's day 20 for activity A), so there are 40 capacity-days (20 days * 2 capacity) available to us; and the activities take only 11 days (2+5+4) total; so we have 29 capacity days (40-11) slack globally.

However, if we refine our idea of slack by considering the earliest start time of any activity and the latest end time of any other activity, we get much tighter slack times. By considering the earliest start time of activity B and the latest end time of activity C, we'll get an overall span of 12 days. The total duration of the activities that must absolutely execute during this period is 9 days (5 days for B and 4 days for C), so we now have only 15 capacity days ((12*2)-9) of slack.

This member function returns the type timetable constraint of the invoking resource.

This member function returns IlcTrue if the invoking resource has a type timetable constraint. Otherwise, it returns IlcFalse.

This member function creates and returns the global disjunctive constraint associated with the invoking resource. That constraint has to be posted in order to be taken into account. For more information, see Disjunctive Constraint.

This member function attaches a type timetable constraint to the resource and returns it.

The type timetable constraint uses the transition time object that was passed to the constructor of the invoking resource to propagate the transition times. This transition time object needs to have been built with an instance of IlcTransitionTable. An instance of IloSolver::SolverErrorException is thrown if no transition time object was passed to the constructor of the resource or if the transition time object was not built with an instance of IlcTransitionTable.

The useBatch parameter allows you to batch overlapping activities together that use the same resource and that are of the same transition type. Basically, if the execution time of the activities overlaps on the resource, then the activities will be constrained to start and end at the same time. If the execution time of the activities does not intersect on the resource, then the useBatch parameter has no effect on the activities. Although the activities must be of the same transition type, the transition time has no effect on the action of useBatch.

This member function states that at most capacityMax can be used throughout the interval [timeMin, timeMax). An instance of IloSolver::SolverErrorException is thrown if the timetables of the invoking resource do not cover the complete interval indicated by [timeMin, timeMax).

This member function states that at least capacityMin must be used throughout the interval [timeMin, timeMax). Only if the resource is closed will this result in propagation. If the resource is not closed, any number of resource constraints can still be added, and thus no deductions can be made. An instance of IloSolver::SolverErrorException is thrown if the timetables of the invoking resource do not cover the complete interval indicated by [timeMin, timeMax).

If the parameter edgeFinder is 1 (one), then this member function switches on the extra propagation for Disjunctive Constraint. If edgeFinder is strictly greater than 1 and the resource is an instance of the class IlcUnaryResource, an extra level of propagation is switched on also. If edgeFinder is 0 (zero), all extra propagation is switched off. Note that if the invoking resource is not an instance of IlcUnaryResource, then the disjunctive constraints must have been created on the resource.

Extra propagation should not be used when a very large capacity is defined for the resource. That extra propagation requires the calculation of the available “energy” of the resource; that energy is defined as the theoretical capacity multiplied by the available time. Having such a large capacity might lead to overflow problems.

This member function should be used only if a precedence graph constraint has been created on the resource. It switches on an extra propagation for the precedence graph constraint.

If level is 1, the extra propagation computes new bounds for the start time and completion time of the resource constraints in the graph by analyzing their direct predecessors and successors.

If level is 2, this extra propagation computes new bounds for the start time and completion time of the resource constraints in the graph by analyzing all their predecessors and successors.

For example, consider a schedule with 4 activities: a1 (earliest start time = 0, duration = 20), a2 (earliest start time = 0, duration = 30), a3 (earliest start time = 0, duration = 40) and b that require the same discrete resource res (capacity = 2). Suppose that a2 requires 2 units of res whereas all other activities require 1 unit of res. If, on the precedence graph of resource res, activity a2 is constrained to be successor of a1 and activity b is constrained to be successor of both activities a2 and a3, the extra-propagation at level 1 will deduce that b cannot start before 50 while the extra-propagation at level 2 will deduce that b cannot start before 60.

When the argument level is equal to 1, this member function switches on extra propagation for the maximal duration and maximal capacity of resource constraints on the resource. This extra propagation globally analyzes the timetable of the resource to identify two things:

1. Temporal intervals where the maximal duration of the activity can be supported should the resource constraint require its minimal capacity
2. Temporal intervals where the maximal capacity of the resource constraint can be supported should the duration of the activity equal its minimal duration.

The constraint finds new upper bounds on duration and capacity that are supported by such time intervals.

For example, consider a schedule with two activities: a0 (fixed start time 20, fixed end time 70) and a1 (earliest start time = 0, latest end time 100, variable duration in [10..100]). These two activities require the same discrete resource res (capacity = 2). Suppose that a0 requires 1 unit of res whereas a1 requires 2 units of res. The extra propagation at level 1 will deduce that the maximal duration of a1 is 30. This is because the two time intervals where a1 could be executed, given its minimal requirement of 2 units of res, are [0,20] and [70,100]. The maximal duration of 30 corresponds to this last interval.

When the level is equal to 0, the extra propagation above is not performed. The propagation level can be changed in a reversible way during the search.

This member function stores in the solution a set of direct successors that are sufficient to ensure that the theoretical capacity of the resource is not exceeded. It can be called even if no precedence graph has been created. Only resource constraints that surely contribute and that have their start and end variables bound are taken into account. When the optional parameter rand is used, a non-deterministic heuristic is used to select the set of direct successors.