Texture Measurements

From a general perspective, a texture measurement is a measurement of some aspect of a search state. The actual measured values can then be used for any purpose. A typical use is to guide search by helping to identify characteristics of a search state that can be exploited to aid heuristic search. It is important to distinguish between the texture measurements themselves, and the uses to which they may be put; a single texture measurement may be used in multiple ways for multiple purposes.

For example, the first-fail heuristic in constraint programing chooses the variable with the smallest domain size to be assigned a value in the current search state. The domain size can be seen as a texture measurement: it is an aspect of the search state that can be efficiently evaluated and then used for some purpose (in this case, as a basis for a heuristic decision). Note that nothing limits the uses to which the domain sizes can be put. While assigning the variable with the smallest domain is a useful heuristic, there may be other uses, perhaps unrelated to heuristic search, for which the domain size information can be used.

Scheduler Engine implements a specific type of texture, IlcResourceTexture, which is a measure of the criticality of a resource over the scheduling horizon. Criticality is a floating point value with minimal predefined semantics. All that is required is that higher levels of criticality are represented by larger floating point values.

The criticality curve can be used to drive heuristic search. For example, in a resource allocation application, it may be useful to assign an activity to the resource with the lowest criticality over the activity's execution time window. In an application more directed towards scheduling, identifying the set of activities that demand the most critical time point across all resources may help heuristic search. In this latter case, a heuristic might sequence a pair of activities from the set.

To define a resource texture measurement it is necessary to define the impact of a resource constraint on a resource and to define how the criticality is computed given the aggregated demand and variance for all the resource constraints on a resource.

This impact that a resource constraint has on a resource is represented by an IlcRCTexture object which represents two curves: the demand curve of a resource constraint for a resource and the variance of this demand. Representation of the variance curve is optional. Users can define the demand and variance curves by subclassing the implementation class IlcRCTextureI and by subclassing the RC Texture factory class IlcRCTextureFactoryI. The factory class simply returns an instance of the user-defined IlcRCTextureI subclass. The factory is used internally to create a new RC texture object whenever a new resource constraint is added to a resource. A number of RC texture and RC texture factory classes are predefined in the Scheduler Engine (such as IlcRCTextureProbabilisticI, and IlcRCTextureProbabilisticFactoryI).

The criticality calculation is similarly defined by subclassing IlcTextureCriticalityCalculatorI. This class has two pure virtual functions that are used to calculate the criticality for a maximum and minimum resource capacity constraint given the aggregate demand and variance of all possible resource constraints of a resource. A number of criticality calculators are predefined in the Scheduler Engine (such as IlcRelativeDemandCriticalityCalculatorI and IlcProbabilisticCriticalityCalculatorI).

Internally, the texture maintenance algorithm uses an RC factory to create an instance of a subclass of IlcRCTextureI for each resource constraint on a resource. The demand and variance curve corresponding to each resource constraint are aggregated across the scheduling horizon and, then, for each relevant time point, the IlcTextureCriticalityCalculatorI subclass is called to compute the criticality given the aggregate demand and variance.

At the modeling level, there are a number of predefined classes corresponding to the predefined Scheduler Engine classes (such as IloTextureCriticalityCalculatorI and IloRCTextureFactory). These classes allow the specification of the texture measurements in an instance of IloTextureParam. We also provide a number of utilities (such as the macros ILOTEXTURECRITICALITYCALCULATOR0 and ILORCTEXTUREFACTORY0) that create user-defined modeling objects that correspond to user-defined Scheduler Engine objects. For example, with the former macro you can create a model object MyIloTextureCalculator that corresponds to and is extracted as your Scheduler Engine object MyIlcTextureCalculator.

PREVIOUS NEXT