You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
The objective of this post is to bootstrap the integration of scheduling modeling constructs in the UP, while keeping the gap with planning models minimal.
My feeling is that the only fundamental change we need to make is provide the ability of define temporal variables in the problem.
In essence, a planning problem has a set of action templates, where each template may lead to a number of instances (each instance defining a start and an end timepoint).
On the other in scheduling problems, one would instead have a set of activities. Each activity must be present exactly once in the solution. This radically changes the way of modeling, because from the problem alone you know all possible timepoints.
For this reason the most common representation for scheduling problems is an unstructured CSP with integer variables representing both timepoints and "object variables".
In the UP, we already have many facilities to model the state evolution at given timepoints. The missing part is thus to define your own timepoints outside of actions. Unlike most scheduling models, I would keep a clear separation between temporal variables and regular variables similar to what is already done in the UP.
Short term proposal
The proposition would thus be to have a scheduling problem class that:
shares with the Problem class the definition of the state variables, initial values, ...
support defining temporal variables and object variables
support constraining the state evolution (timed conditions)
support affecting the state evolution (timed effects)
This remains very basic but defines the key building blocks.
A textual view of a scheduling problem would be something like so (note that modeling resources is beyond the scope of this discussion):
// == activity A1 ==
// variables
timepoint a1_start; // activity start
timepoint a1_end; // activity end
Resource r; // parameter of activity a1: which resource it will consume
// constraints
a1_end = a1_start + 4; // fix duration (note that the second timepoint is not necessary)
support_process_1(r); // restrict possible resource used
// borrow 1 from resource r over [a1_start, a2_end]
// essentially just regular effects
at a1_start: level(r) -= 1;
at a1_end: level(r) += 1;
// global conditions on state evolution (essentially timed conditions)
[10,50] level(R4) >= 2;
Longer term view
The model above captures the core elements to model scheduling problems but is not particularly ergonomic. In the future, we could provide some modeling features that would essentially be syntactic sugar around the flat model above.
This should typically include:
activity as an always-present-once alternative to actions
possibly more advanced features (common global constraints, optional activities)
With these facilities, a scheduling problem could be defined as something like this:
activity A1(Resource r) {
duration = 4
support_process_1(r) // constraint on selected resource e.g. r in {R1, R2, R3}
[start, end] borrow(r);
}
activity A2 {
duration := 10;
[all] borrow(R4);
}
// support temporal constraints on interval/timepoints among activities
A1 < A2;
start(A1) == start(A3);
// any pair of timepoints can be used as an interval
// here setting a resource consumption to span over two activities.
[start(A1), end(A2)] borrow(R5)
reacted with thumbs up emoji reacted with thumbs down emoji reacted with laugh emoji reacted with hooray emoji reacted with confused emoji reacted with heart emoji reacted with rocket emoji reacted with eyes emoji
-
The objective of this post is to bootstrap the integration of scheduling modeling constructs in the UP, while keeping the gap with planning models minimal.
My feeling is that the only fundamental change we need to make is provide the ability of define temporal variables in the problem.
In essence, a planning problem has a set of action templates, where each template may lead to a number of instances (each instance defining a start and an end timepoint).
On the other in scheduling problems, one would instead have a set of activities. Each activity must be present exactly once in the solution. This radically changes the way of modeling, because from the problem alone you know all possible timepoints.
For this reason the most common representation for scheduling problems is an unstructured CSP with integer variables representing both timepoints and "object variables".
In the UP, we already have many facilities to model the state evolution at given timepoints. The missing part is thus to define your own timepoints outside of actions. Unlike most scheduling models, I would keep a clear separation between temporal variables and regular variables similar to what is already done in the UP.
Short term proposal
The proposition would thus be to have a scheduling problem class that:
Problem
class the definition of the state variables, initial values, ...This remains very basic but defines the key building blocks.
A textual view of a scheduling problem would be something like so (note that modeling resources is beyond the scope of this discussion):
Longer term view
The model above captures the core elements to model scheduling problems but is not particularly ergonomic. In the future, we could provide some modeling features that would essentially be syntactic sugar around the flat model above.
This should typically include:
With these facilities, a scheduling problem could be defined as something like this:
Beta Was this translation helpful? Give feedback.
All reactions