Originally posted by: SystemAdmin

Hi everybody,

I'm trying to model a preemptive priority-driven scheduling scenario, i.e. a scheduling problem in which activities are given a fixed priority and can be preempted (because of lack of resources) at any time by other activities which have higher priority and are ready to be executed. There are two key features for this problem:

1) Activities can be preempted at any time, so intensity functions are of no use since they can't be declared as variables.
2) The concept of "priority" has to be implemented through some set of constraints stating that an activity with higher priority (say +a1+) interrupts an activity with lower priority (say +a0+) when no resources are available, thus making the a0 free the shared resource so that a1 can execute.

Regarding feature 1), ideas found on the Reference Manual and the forum have proven to work well. Indeed an activity which can be preempted can be modeled as a chain of optional intervals with some additional constraints. An alternative (don't know if more efficient) is that some of these constraints can be replaced by defining the chain (formally speaking, an array) as a sequence with a "noOverlap" constraint.

Regarding feature 2), I am a bit struck (mostly because I didn't find any reference anywhere). I could imagine writing a constraint which quantifies over the whole time window in which activities can take place, stating "for every time point, if an activity a0 could run if more resources were available but is not running, and an activity a1 is running, then a1 has higher priority than a0". I'm not even sure if I could write such complicated constraint, but I think the quantification over every possible time point would destroy the efficiency of intervals, whose approach is "keeping track" just of the start and end times of an interval, rather than each single time point between them.

Has someone ever bothered with defining priorities over activities?

Regards,
Stefano
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: GGR

Hi

As you have noticed, temporal model of CPO for scheduling required to have all the possible interval of a solution declared in the model. That means for full interruptibility, you need to declare logico-temporal chain of (Horizon - Origin) intervals for each interruptible activities.

About static chronological scheduling priority, there is no such search phase declaration available for the automatic search of CPO. Then you have too possibilities to implement the priority rules.

First, you can declare your own search tree traversal in C++, that is you implement a Jakson-preemptive like selector using min start min selection + max priority tie break, instead of min start min selection + max start max tie break.

Second, you approximate the priority rule as objective function and use the automatic search. That is, for each interval variables itv, you associate an objective term alpha*(startOf(itv) - Origin + constant(itv)), alpha decreasing with priority, constant(itv) being a strictly positive constant decreasing with the position in the logical chain of the interval itv and triggering on the temporal relaxation parameter.

Hope that helps.
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

Thank you very much for your answers, but since I'm a beginner with CP Optimization, I have some questions about the two solutions you provided to implement activities priority in a scheduling scenario.

1) I'm sorry, but I just have a vague idea of what are you talking about. I think you mean that I'd have to write my own heuristic for exploring the solution tree, but I don't know what do you mean by "using min start min selection + max priority tie break, instead of min start min selection + max start max tie break". But that's my fault because of my lack of terminology knowledge and experience in writing tree traversals for constraint optimization problems. Does the CP Reference Guide cover such arguments? If so, where?

2) I didn't think at all about modelling the priority of activities in an objective function, but this could not be a solution. The problem is that my problem features a "classical" scheduling objective like minimizing the makespan, minimizing resources usage or things like that. Then I'd need to perform a multi-objective search (one of them being the "priority objective" you suggested, and the other one being my "business" objective), which does not seem to be supported by OPL, as you stated in another recent thread. You suggested there to solve a multiple objective CP by "iterating model solving by upgrading the models and objective for each term as well as reusing previous solution as starting point", but I'm not sure on what you mean here. You mean doing it programmatically, writing a program with the C++/Java/.NET API? Are there any references (or examples) on the guide? I also found the Multi-criteria objectives page in the Reference Guide. Reading the page, it seems to be possible then to define multiple objectives in a CP, so I'm a bit confused about your previous statement.

Thank you so much again for your patience and efforts.

Regards,
Stefano
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: GGR

Hi

1) The Jackson-preemptive schedule is an algorithm that allows to build optimal solution for full preemptive schedule under some conditions. This algorithm can be adapted to tour actual situation in some way. There is a wide literature on this field I invite you to consult.
Sorry for the too fast description, when I said min start min (or min earlier start time). Basically the start of a task/activity/interval is a range start min, start max. I wanted to say that in a Jackson-preemptive schedule the main selection algorithm consist by choosing the task/activity/interval which has a minimum start min ans and set its start time to this value. Eventually, among all activity that you can select, you take the one that has the best tie break: usual tie break are min start max, in your case max priority can also be considered.

2) Actually you're right. You need to build a cost function capturing both the operational objective and your preferences. That is you need to have coefficient that scale the different terms. If you really want to build a multi-objective search, you will search from some points on the Pareto frontier. To achieve it a good way it to successively solve several problem by changing the objective term and reusing knowledge from the last model. For example the best known solution and the value of the last objective.

Hope that helps
#DecisionOptimization
#OPLusingCPOptimizer