11 a.m.
Hi,
I am new to Drools and Drools Planner, so apologies if I am asking anything
obvious.
My objective is to implement a simple (for now) planner which schedules
tasks according to 2 main criteria:
- Their duration (in seconds)
- Their dependencies on other tasks (e.g. Hard Constraint that Task B has
to start between 180 and 200 seconds after Task A finishes).
Since there are gaps between dependent tasks as part of the hard
constraints other tasks can be fitted in between dependent tasks.
So the Solver needs to find the optimal start time for each task that
satisfies the hard constraints, and in the shortest total timeline possible
to complete all tasks (soft constraint).
The main problem I am finding is that this start time, which is essentially
the planning variable is a continuous variable.
Chapter 4 of the Drools documentation mentions very briefly (Section
4.3.4.1) that planning variables can be continuous, but there does not
seem to be any more details about how to achieve this.
Even if the planning variable was discrete (say bins of 5 second
intervals), there is no upper bound as such.
How is it best to handle such planning variables in Drools Planner?
thanks,
josef
1:05 p.m.
Presuming that you don't want to leave space between tasks, you can
design your model differently by using the "chained" functionality:
it will be far more efficient and the planning variable won't be continuous.
Let's presume you're scheduling Tasks to Persons.
@PlanningEntity
class Task implements TaskOrPerson {
...
@PlanningVariable(chained = true)
@ValueRanges({
@ValueRange(type = ValueRangeType.FROM_SOLUTION_PROPERTY,
solutionProperty = "taskList"),
@ValueRange(type = ValueRangeType.FROM_SOLUTION_PROPERTY,
solutionProperty = "personList",
excludeUninitializedPlanningEntity = true)})
public TaskOrPerson getPreviousTaskOrPerson() {
return previousTaskOrPerson;
}
public int getDuration() {
return duration;
}
public int getStartingTime() {
int startingTime = 0;
TaskOrPerson taskOrPerson = getPreviousTaskOrPerson();
while (taskOrPerson instanceof Task) { // Every chain is
guarantee to end up with an anchor (= Person)
startingTime += ((Task) taskOrPerson).getDuration();
taskOrPerson = ((Task)
taskOrPerson).getPreviousTaskOrPerson()
}
return startingTime;
}
}
class Person implements TaskOrPerson {
}
For a good example, take a look at the VehicleRouting example.
For more info about chaining, in the manual see section 4.3.4.2.6. Chained
http://docs.jboss.org/drools/release/5.4.0.Final/drools-planner-docs/html...
Op 22-07-12 18:00, Josef Bajada schreef:
Hi,
I am new to Drools and Drools Planner, so apologies if I am asking
anything obvious.
My objective is to implement a simple (for now) planner which
schedules tasks according to 2 main criteria:
- Their duration (in seconds)
- Their dependencies on other tasks (e.g. Hard Constraint that Task B
has to start between 180 and 200 seconds after Task A finishes).
Since there are gaps between dependent tasks as part of the hard
constraints other tasks can be fitted in between dependent tasks.
So the Solver needs to find the optimal start time for each task that
satisfies the hard constraints, and in the shortest total timeline
possible to complete all tasks (soft constraint).
The main problem I am finding is that this start time, which is
essentially the planning variable is a continuous variable.
Chapter 4 of the Drools documentation mentions very briefly (Section
4.3.4.1) that planning variables can be continuous, but there does
not seem to be any more details about how to achieve this.
Even if the planning variable was discrete (say bins of 5 second
intervals), there is no upper bound as such.
How is it best to handle such planning variables in Drools Planner?
thanks,
josef
_______________________________________________
rules-users mailing list
rules-users(a)lists.jboss.org
https://lists.jboss.org/mailman/listinfo/rules-users
--
With kind regards,
Geoffrey De Smet
9:26 a.m.
Hi Geoffrey,
Well I want to leave 'space' between tasks in the situations where there
are hard constraints that require me to put this space.
As a simple example:
Task A: Put pasta in boiling water (duration 40 seconds)
Task B: Take pasta out of boiling water (duration 50 seconds, cannot start
before 7 mins after Task A finishes, cannot start after 8 mins after Task A
finishes)
Task C: Chop vegetables (duration 2 minutes).
This will evidently leave some gaps. The ideal result from the solver
should be:
Task A: at time 0 (ends at 40s)
Task C: at time 41s (ends at 2:41)
Task B: at time 7:40
There is a gap between C and B which is OK.
If another Task is added to the story:
Task D: Prepare sauce (duration 7 minutes)
I would want the following result:
Task A: at time 0 (ends at 40s)
Task D: at time 41s (ends 7:41s)
Task B: at time 8:42s (ends 9:32s)
Task C: at time 9:33s (ends 11:33s)
Task C can actually take place before Task A too.
I still need to read and understand the chaining functionality properly. Do
you think it would allow me to achieve the above?
thanks,
Josef
On 22 July 2012 20:05, Geoffrey De Smet <ge0ffrey.spam(a)gmail.com> wrote:
Presuming that you don't want to leave space between tasks, you
can
design your model differently by using the "chained" functionality:
it will be far more efficient and the planning variable won't be
continuous.
Let's presume you're scheduling Tasks to Persons.
@PlanningEntity
class Task implements TaskOrPerson {
...
@PlanningVariable(chained = true)
@ValueRanges({
@ValueRange(type = ValueRangeType.FROM_SOLUTION_PROPERTY,
solutionProperty = "taskList"),
@ValueRange(type = ValueRangeType.FROM_SOLUTION_PROPERTY,
solutionProperty = "personList",
excludeUninitializedPlanningEntity = true)})
public TaskOrPerson getPreviousTaskOrPerson() {
return previousTaskOrPerson;
}
public int getDuration() {
return duration;
}
public int getStartingTime() {
int startingTime = 0;
TaskOrPerson taskOrPerson = getPreviousTaskOrPerson();
while (taskOrPerson instanceof Task) { // Every chain is
guarantee to end up with an anchor (= Person)
startingTime += ((Task) taskOrPerson).getDuration();
taskOrPerson = ((Task)
taskOrPerson).getPreviousTaskOrPerson()
}
return startingTime;
}
}
class Person implements TaskOrPerson {
}
For a good example, take a look at the VehicleRouting example.
For more info about chaining, in the manual see section 4.3.4.2.6. Chained
http://docs.jboss.org/drools/release/5.4.0.Final/drools-planner-docs/html...
Op 22-07-12 18:00, Josef Bajada schreef:
Hi,
I am new to Drools and Drools Planner, so apologies if I am asking
anything obvious.
My objective is to implement a simple (for now) planner which schedules
tasks according to 2 main criteria:
- Their duration (in seconds)
- Their dependencies on other tasks (e.g. Hard Constraint that Task B has
to start between 180 and 200 seconds after Task A finishes).
Since there are gaps between dependent tasks as part of the hard
constraints other tasks can be fitted in between dependent tasks.
So the Solver needs to find the optimal start time for each task that
satisfies the hard constraints, and in the shortest total timeline possible
to complete all tasks (soft constraint).
The main problem I am finding is that this start time, which is
essentially the planning variable is a continuous variable.
Chapter 4 of the Drools documentation mentions very briefly (Section
4.3.4.1) that planning variables can be continuous, but there does not
seem to be any more details about how to achieve this.
Even if the planning variable was discrete (say bins of 5 second
intervals), there is no upper bound as such.
How is it best to handle such planning variables in Drools Planner?
thanks,
josef
_______________________________________________
rules-users mailing
listrules-users@lists.jboss.orghttps://lists.jboss.org/mailman/listinfo/rules-users
--
With kind regards,
Geoffrey De Smet
_______________________________________________
rules-users mailing list
rules-users(a)lists.jboss.org
https://lists.jboss.org/mailman/listinfo/rules-users
1:46 p.m.
Op 23-07-12 16:26, Josef Bajada schreef:
Hi Geoffrey,
Well I want to leave 'space' between tasks in the situations where
there are hard constraints that require me to put this space.
This makes the
chaining technique harder to model, but I wouldn't write
it off yet.
As a simple example:
Task A: Put pasta in boiling water (duration 40 seconds)
Task B: Take pasta out of boiling water (duration 50 seconds, cannot
start before 7 mins after Task A finishes, cannot start after 8 mins
after Task A finishes)
Does it make sense to wait longer than 7 mins after task A
(presuming no
other task forces occupies the user at that time)?
Put differently: Can we say that the starting time of B =
Math.max((endTime of task before B), (endTime of task A + 7 minutes))?
If we can say that, it's pointless to investigate the solutions where
task B starts 8 minutes after task A and the user doing no task that
last minute.
If we can say that, then chaining can calculate the the starting time of
a task on the fly differently.
Task C: Chop vegetables (duration 2 minutes).
This will evidently leave some gaps. The ideal result from the solver
should be:
Task A: at time 0 (ends at 40s)
Task C: at time 41s (ends at 2:41)
Task B: at time 7:40
There is a gap between C and B which is OK.
If another Task is added to the story:
Task D: Prepare sauce (duration 7 minutes)
I would want the following result:
Task A: at time 0 (ends at 40s)
Task D: at time 41s (ends 7:41s)
Task B: at time 8:42s (ends 9:32s)
Task C: at time 9:33s (ends 11:33s)
Task C can actually take place before Task A too.
I still need to read and understand the chaining functionality
properly. Do you think it would allow me to achieve the above?
I don't know.
But using continuous variables in a search problem such as this that
smells discrete with discrete constraints (A must start before B, ...),
could blow up the search space unnecessarily.
If you want to look into using continuous variables: the support for it
is limited currently.
you can reuse the Drools Planner metaheuristic algorithms (including
termination, score, ...), but there's no decent generic move factory
support for continuous variables yet.
So you 'll have to write a custom MoveFactory that creates a limited
subset of moves.
Also, construction heuristics can't handle continuous variables yet, so
you 'll have to write a custom SolutionIntializer.
There are examples with a custom MoveFactory and a custom
SolutionIntializer where you can copy paste from, but none with
continuous variables at the moment.
thanks,
Josef
On 22 July 2012 20:05, Geoffrey De Smet <ge0ffrey.spam(a)gmail.com
<mailto:ge0ffrey.spam@gmail.com>> wrote:
Presuming that you don't want to leave space between tasks, you
can design your model differently by using the "chained"
functionality:
it will be far more efficient and the planning variable won't be
continuous.
Let's presume you're scheduling Tasks to Persons.
@PlanningEntity
class Task implements TaskOrPerson {
...
@PlanningVariable(chained = true)
@ValueRanges({
@ValueRange(type =
ValueRangeType.FROM_SOLUTION_PROPERTY, solutionProperty = "taskList"),
@ValueRange(type =
ValueRangeType.FROM_SOLUTION_PROPERTY, solutionProperty =
"personList",
excludeUninitializedPlanningEntity = true)})
public TaskOrPerson getPreviousTaskOrPerson() {
return previousTaskOrPerson;
}
public int getDuration() {
return duration;
}
public int getStartingTime() {
int startingTime = 0;
TaskOrPerson taskOrPerson = getPreviousTaskOrPerson();
while (taskOrPerson instanceof Task) { // Every chain is
guarantee to end up with an anchor (= Person)
startingTime += ((Task) taskOrPerson).getDuration();
taskOrPerson = ((Task)
taskOrPerson).getPreviousTaskOrPerson()
}
return startingTime;
}
}
class Person implements TaskOrPerson {
}
For a good example, take a look at the VehicleRouting example.
For more info about chaining, in the manual see section 4.3.4.2.6.
Chained
http://docs.jboss.org/drools/release/5.4.0.Final/drools-planner-docs/html...
Op 22-07-12 18 <tel:22-07-12%2018>:00, Josef Bajada schreef:
> Hi,
>
> I am new to Drools and Drools Planner, so apologies if I am
> asking anything obvious.
>
> My objective is to implement a simple (for now) planner which
> schedules tasks according to 2 main criteria:
> - Their duration (in seconds)
> - Their dependencies on other tasks (e.g. Hard Constraint that
> Task B has to start between 180 and 200 seconds after Task A
> finishes).
>
> Since there are gaps between dependent tasks as part of the hard
> constraints other tasks can be fitted in between dependent tasks.
> So the Solver needs to find the optimal start time for each task
> that satisfies the hard constraints, and in the shortest total
> timeline possible to complete all tasks (soft constraint).
>
> The main problem I am finding is that this start time, which is
> essentially the planning variable is a continuous variable.
> Chapter 4 of the Drools documentation mentions very briefly
> (Section 4.3.4.1) that planning variables can be continuous, but
> there does not seem to be any more details about how to achieve this.
>
> Even if the planning variable was discrete (say bins of 5 second
> intervals), there is no upper bound as such.
>
> How is it best to handle such planning variables in Drools Planner?
>
> thanks,
> josef
>
>
>
>
> _______________________________________________
> rules-users mailing list
> rules-users(a)lists.jboss.org <mailto:rules-users@lists.jboss.org>
> https://lists.jboss.org/mailman/listinfo/rules-users
--
With kind regards,
Geoffrey De Smet
_______________________________________________
rules-users mailing list
rules-users(a)lists.jboss.org <mailto:rules-users@lists.jboss.org>
https://lists.jboss.org/mailman/listinfo/rules-users
_______________________________________________
rules-users mailing list
rules-users(a)lists.jboss.org
https://lists.jboss.org/mailman/listinfo/rules-users
--
With kind regards,
Geoffrey De Smet
4:14 p.m.
Hi Geoffrey,
Thanks for your reply.
Does it make sense to wait longer than 7 mins after task A (presuming
no
other task forces occupies the user at that time)?
Put differently: Can we say that the starting time of B =
Math.max((endTime of task before B), (endTime of task A + 7 minutes))?
If we can say that, it's pointless to investigate the solutions
where
task B starts 8 minutes after task A and the user doing no task that last
minute.
Yes, the starting time of B = Math.max((endTime of task before B), (endTime
of task A + 7mins)) as long as it is smaller than (endTime of task A +
8mins).
Yes, it is pointless to investigate the solutions where task B starts 8
minutes after task A and the user doing no task that last minute.
The 8 minute is just a constraint that the task in between tasks A and B
cannot take longer than 7:59s.
I am thinking that maybe instead of using time itself as the planning
variable, we would use time just to determine the Hard and Soft scores.
So if Task B is scheduled after Task A + 8mins by the solver, then it
inflicts on the hard score. Similarly if Task B is scheduled before Task A
+ 7 mins.
Does my reasoning make sense in any way?
thanks,
Josef
On 24 July 2012 20:46, Geoffrey De Smet <ge0ffrey.spam(a)gmail.com> wrote:
>
> Op 23-07-12 16:26, Josef Bajada schreef:
>
> Hi Geoffrey,
>
> Well I want to leave 'space' between tasks in the situations where there
> are hard constraints that require me to put this space.
>
> This makes the chaining technique harder to model, but I wouldn't write it
> off yet.
>
>
> As a simple example:
>
> Task A: Put pasta in boiling water (duration 40 seconds)
> Task B: Take pasta out of boiling water (duration 50 seconds, cannot start
> before 7 mins after Task A finishes, cannot start after 8 mins after Task A
> finishes)
>
Does it make sense to wait longer than 7 mins after task A (presuming
no
> other task forces occupies the user at that time)?
Put differently: Can we say that the starting time of B =
>
Math.max((endTime of task before B), (endTime of task A + 7 minutes))?
> If we can say that, it's pointless to investigate the solutions where task
> B starts 8 minutes after task A and the user doing no task that last minute.
> If we can say that, then chaining can calculate the the starting time of a
> task on the fly differently.
>
> Task C: Chop vegetables (duration 2 minutes).
>
> This will evidently leave some gaps. The ideal result from the solver
> should be:
>
> Task A: at time 0 (ends at 40s)
> Task C: at time 41s (ends at 2:41)
> Task B: at time 7:40
>
> There is a gap between C and B which is OK.
>
> If another Task is added to the story:
> Task D: Prepare sauce (duration 7 minutes)
>
> I would want the following result:
>
> Task A: at time 0 (ends at 40s)
> Task D: at time 41s (ends 7:41s)
> Task B: at time 8:42s (ends 9:32s)
> Task C: at time 9:33s (ends 11:33s)
>
> Task C can actually take place before Task A too.
>
> I still need to read and understand the chaining functionality properly.
> Do you think it would allow me to achieve the above?
>
> I don't know.
> But using continuous variables in a search problem such as this that
> smells discrete with discrete constraints (A must start before B, ...),
> could blow up the search space unnecessarily.
>
> If you want to look into using continuous variables: the support for it is
> limited currently.
> you can reuse the Drools Planner metaheuristic algorithms (including
> termination, score, ...), but there's no decent generic move factory
> support for continuous variables yet.
> So you 'll have to write a custom MoveFactory that creates a limited
> subset of moves.
> Also, construction heuristics can't handle continuous variables yet, so
> you 'll have to write a custom SolutionIntializer.
> There are examples with a custom MoveFactory and a custom
> SolutionIntializer where you can copy paste from, but none with continuous
> variables at the moment.
>
> thanks,
>
> Josef
>
>
>
> On 22 July 2012 20:05, Geoffrey De Smet <ge0ffrey.spam(a)gmail.com> wrote:
>
>> Presuming that you don't want to leave space between tasks, you can
>> design your model differently by using the "chained" functionality:
>> it will be far more efficient and the planning variable won't be
>> continuous.
>>
>> Let's presume you're scheduling Tasks to Persons.
>>
>> @PlanningEntity
>> class Task implements TaskOrPerson {
>>
>> ...
>>
>> @PlanningVariable(chained = true)
>> @ValueRanges({
>> @ValueRange(type = ValueRangeType.FROM_SOLUTION_PROPERTY,
>> solutionProperty = "taskList"),
>> @ValueRange(type = ValueRangeType.FROM_SOLUTION_PROPERTY,
>> solutionProperty = "personList",
>> excludeUninitializedPlanningEntity = true)})
>> public TaskOrPerson getPreviousTaskOrPerson() {
>> return previousTaskOrPerson;
>> }
>>
>> public int getDuration() {
>> return duration;
>> }
>>
>> public int getStartingTime() {
>> int startingTime = 0;
>> TaskOrPerson taskOrPerson = getPreviousTaskOrPerson();
>> while (taskOrPerson instanceof Task) { // Every chain is
>> guarantee to end up with an anchor (= Person)
>> startingTime += ((Task) taskOrPerson).getDuration();
>> taskOrPerson = ((Task)
>> taskOrPerson).getPreviousTaskOrPerson()
>> }
>> return startingTime;
>> }
>>
>> }
>>
>> class Person implements TaskOrPerson {
>>
>> }
>>
>> For a good example, take a look at the VehicleRouting example.
>> For more info about chaining, in the manual see section 4.3.4.2.6. Chained
>>
>>
http://docs.jboss.org/drools/release/5.4.0.Final/drools-planner-docs/html...
>>
>> Op 22-07-12 18:00, Josef Bajada schreef:
>>
>> Hi,
>>
>> I am new to Drools and Drools Planner, so apologies if I am asking
>> anything obvious.
>>
>> My objective is to implement a simple (for now) planner which schedules
>> tasks according to 2 main criteria:
>> - Their duration (in seconds)
>> - Their dependencies on other tasks (e.g. Hard Constraint that Task B has
>> to start between 180 and 200 seconds after Task A finishes).
>>
>> Since there are gaps between dependent tasks as part of the hard
>> constraints other tasks can be fitted in between dependent tasks.
>> So the Solver needs to find the optimal start time for each task that
>> satisfies the hard constraints, and in the shortest total timeline possible
>> to complete all tasks (soft constraint).
>>
>> The main problem I am finding is that this start time, which is
>> essentially the planning variable is a continuous variable.
>> Chapter 4 of the Drools documentation mentions very briefly (Section
>> 4.3.4.1) that planning variables can be continuous, but there does not
>> seem to be any more details about how to achieve this.
>>
>> Even if the planning variable was discrete (say bins of 5 second
>> intervals), there is no upper bound as such.
>>
>> How is it best to handle such planning variables in Drools Planner?
>>
>> thanks,
>> josef
>>
>>
>>
>>
>> _______________________________________________
>> rules-users mailing
listrules-users@lists.jboss.orghttps://lists.jboss.org/mailman/listinfo/rules-users
>>
>>
>> --
>> With kind regards,
>> Geoffrey De Smet
>>
>>
>> _______________________________________________
>> rules-users mailing list
>> rules-users(a)lists.jboss.org
>> https://lists.jboss.org/mailman/listinfo/rules-users
>>
>>
>
>
> _______________________________________________
> rules-users mailing
listrules-users@lists.jboss.orghttps://lists.jboss.org/mailman/listinfo/rules-users
>
>
> --
> With kind regards,
> Geoffrey De Smet
>
>
> _______________________________________________
> rules-users mailing list
> rules-users(a)lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/rules-users
>
>
1:30 a.m.
Op 24-07-12 23:14, Josef Bajada schreef:
Hi Geoffrey,
Thanks for your reply.
> Does it make sense to wait longer than 7 mins after task A
(presuming no other task forces occupies the user at that time)?
> Put differently: Can we say that the starting time of B =
Math.max((endTime of task before B), (endTime of task A + 7 minutes))?
> If we can say that, it's pointless to investigate the solutions
where task B starts 8 minutes after task A and the user doing no task
that last minute.
Yes, the starting time of B = Math.max((endTime of task before B),
(endTime of task A + 7mins)) as long as it is smaller than (endTime of
task A + 8mins).
Yes, it is pointless to investigate the solutions where task B starts
8 minutes after task A and the user doing no task that last minute.
The 8 minute is just a constraint that the task in between tasks A and
B cannot take longer than 7:59s.
I am thinking that maybe instead of using time itself as the planning
variable, we would use time just to determine the Hard and Soft scores.
So if Task B is scheduled after Task A + 8mins by the solver, then it
inflicts on the hard score. Similarly if Task B is scheduled before
Task A + 7 mins.
Does my reasoning make sense in any way?
Yes, but personally, I 'd design it
differently (although I have no
proof that my way would be better), like this:
"Task B is scheduled after Task A + 8mins by the solver" => make this a
hard constraint
"Task B is scheduled before Task A + 7 mins" => make this a build-in
hard constraint (= not a constraint in the scoreDRL or ScoreCalculator,
but by design, see manual).
Each Task is assigned to a previousTaskOrPerson (and this variable is
chained). It does not know it's startingTime directly.
The scoreDRL or ScoreCalculator calculates the startingTime of a Task
dynamically, by applying this logic:
starting time of B = Math.max((endTime of previousTaskOrPerson of B),
(endTime of task A + 7mins))
Note: "Chained=true" guarantees that there are no cycles of Tasks and
that no Tasks exists with a previousTaskOrPerson == null.
Note: "(endTime of task A + 7mins)" is not hard coded in the score
function: you won't find "7" or "A" in there.
thanks,
Josef
On 24 July 2012 20:46, Geoffrey De Smet <ge0ffrey.spam(a)gmail.com
<mailto:ge0ffrey.spam@gmail.com>> wrote:
Op 23-07-12 16 <tel:23-07-12%2016>:26, Josef Bajada schreef:
> Hi Geoffrey,
>
> Well I want to leave 'space' between tasks in the situations
> where there are hard constraints that require me to put this space.
This makes the chaining technique harder to model, but I wouldn't
write it off yet.
>
> As a simple example:
>
> Task A: Put pasta in boiling water (duration 40 seconds)
> Task B: Take pasta out of boiling water (duration 50 seconds,
> cannot start before 7 mins after Task A finishes, cannot start
> after 8 mins after Task A finishes)
Does it make sense to wait longer than 7 mins after task A
(presuming no other task forces occupies the user at that time)?
Put differently: Can we say that the starting time of B =
Math.max((endTime of task before B), (endTime of task A + 7 minutes))?
If we can say that, it's pointless to investigate the solutions
where task B starts 8 minutes after task A and the user doing no
task that last minute.
If we can say that, then chaining can calculate the the starting
time of a task on the fly differently.
> Task C: Chop vegetables (duration 2 minutes).
>
> This will evidently leave some gaps. The ideal result from the
> solver should be:
>
> Task A: at time 0 (ends at 40s)
> Task C: at time 41s (ends at 2:41)
> Task B: at time 7:40
>
> There is a gap between C and B which is OK.
>
> If another Task is added to the story:
> Task D: Prepare sauce (duration 7 minutes)
>
> I would want the following result:
>
> Task A: at time 0 (ends at 40s)
> Task D: at time 41s (ends 7:41s)
> Task B: at time 8:42s (ends 9:32s)
> Task C: at time 9:33s (ends 11:33s)
>
> Task C can actually take place before Task A too.
>
> I still need to read and understand the chaining functionality
> properly. Do you think it would allow me to achieve the above?
>
I don't know.
But using continuous variables in a search problem such as this
that smells discrete with discrete constraints (A must start
before B, ...), could blow up the search space unnecessarily.
If you want to look into using continuous variables: the support
for it is limited currently.
you can reuse the Drools Planner metaheuristic algorithms
(including termination, score, ...), but there's no decent generic
move factory support for continuous variables yet.
So you 'll have to write a custom MoveFactory that creates a
limited subset of moves.
Also, construction heuristics can't handle continuous variables
yet, so you 'll have to write a custom SolutionIntializer.
There are examples with a custom MoveFactory and a custom
SolutionIntializer where you can copy paste from, but none with
continuous variables at the moment.
> thanks,
>
> Josef
>
>
>
> On 22 July 2012 20:05, Geoffrey De Smet <ge0ffrey.spam(a)gmail.com
> <mailto:ge0ffrey.spam@gmail.com>> wrote:
>
> Presuming that you don't want to leave space between tasks,
> you can design your model differently by using the "chained"
> functionality:
> it will be far more efficient and the planning variable won't
> be continuous.
>
> Let's presume you're scheduling Tasks to Persons.
>
> @PlanningEntity
> class Task implements TaskOrPerson {
>
> ...
>
> @PlanningVariable(chained = true)
> @ValueRanges({
> @ValueRange(type =
> ValueRangeType.FROM_SOLUTION_PROPERTY, solutionProperty =
> "taskList"),
> @ValueRange(type =
> ValueRangeType.FROM_SOLUTION_PROPERTY, solutionProperty =
> "personList",
> excludeUninitializedPlanningEntity = true)})
> public TaskOrPerson getPreviousTaskOrPerson() {
> return previousTaskOrPerson;
> }
>
> public int getDuration() {
> return duration;
> }
>
> public int getStartingTime() {
> int startingTime = 0;
> TaskOrPerson taskOrPerson = getPreviousTaskOrPerson();
> while (taskOrPerson instanceof Task) { // Every
> chain is guarantee to end up with an anchor (= Person)
> startingTime += ((Task)
> taskOrPerson).getDuration();
> taskOrPerson = ((Task)
> taskOrPerson).getPreviousTaskOrPerson()
> }
> return startingTime;
> }
>
> }
>
> class Person implements TaskOrPerson {
>
> }
>
> For a good example, take a look at the VehicleRouting example.
> For more info about chaining, in the manual see section
> 4.3.4.2.6. Chained
>
http://docs.jboss.org/drools/release/5.4.0.Final/drools-planner-docs/html...
>
> Op 22-07-12 18 <tel:22-07-12%2018>:00, Josef Bajada schreef:
>> Hi,
>>
>> I am new to Drools and Drools Planner, so apologies if I am
>> asking anything obvious.
>>
>> My objective is to implement a simple (for now) planner
>> which schedules tasks according to 2 main criteria:
>> - Their duration (in seconds)
>> - Their dependencies on other tasks (e.g. Hard Constraint
>> that Task B has to start between 180 and 200 seconds after
>> Task A finishes).
>>
>> Since there are gaps between dependent tasks as part of the
>> hard constraints other tasks can be fitted in between
>> dependent tasks.
>> So the Solver needs to find the optimal start time for each
>> task that satisfies the hard constraints, and in the
>> shortest total timeline possible to complete all tasks (soft
>> constraint).
>>
>> The main problem I am finding is that this start time, which
>> is essentially the planning variable is a continuous variable.
>> Chapter 4 of the Drools documentation mentions very briefly
>> (Section 4.3.4.1) that planning variables can be
>> continuous, but there does not seem to be any more details
>> about how to achieve this.
>>
>> Even if the planning variable was discrete (say bins of 5
>> second intervals), there is no upper bound as such.
>>
>> How is it best to handle such planning variables in Drools
>> Planner?
>>
>> thanks,
>> josef
>>
>>
>>
>>
>> _______________________________________________
>> rules-users mailing list
>> rules-users(a)lists.jboss.org <mailto:rules-users@lists.jboss.org>
>> https://lists.jboss.org/mailman/listinfo/rules-users
>
> --
> With kind regards,
> Geoffrey De Smet
>
>
> _______________________________________________
> rules-users mailing list
> rules-users(a)lists.jboss.org <mailto:rules-users@lists.jboss.org>
> https://lists.jboss.org/mailman/listinfo/rules-users
>
>
>
>
> _______________________________________________
> rules-users mailing list
> rules-users(a)lists.jboss.org <mailto:rules-users@lists.jboss.org>
> https://lists.jboss.org/mailman/listinfo/rules-users
--
With kind regards,
Geoffrey De Smet
_______________________________________________
rules-users mailing list
rules-users(a)lists.jboss.org <mailto:rules-users@lists.jboss.org>
https://lists.jboss.org/mailman/listinfo/rules-users
_______________________________________________
rules-users mailing list
rules-users(a)lists.jboss.org
https://lists.jboss.org/mailman/listinfo/rules-users
--
With kind regards,
Geoffrey De Smet
6:53 p.m.
Hi Geoffrey,
Following your advice and after gaining some more understanding of planner,
I think approaching the problem as a chain of tasks one of the other makes
sense. It would have some 'wait' time between tasks where the end time of
the previous task is smaller than the minimum time the task has to wait
after its dependency (which could be different from the previous task).
I've noticed that in most examples (TSP and VRP), there is some separation
between the model and the planning entity that is being moved around in the
chain, which also makes sense. (For instance in TSP, Visit is the planning
entity while City is the data entity). When the planning entity gets
cloned, the data entity gets assigned to the clone.
I am concerned however, that with my dependency between tasks and their end
times (which are as such a property of the planning entity not the data
entity) I won't be able to model them in this way. (For a task to know
whether it has violated its hard constraint it needs to get access to the
end time of its dependency, which is in the planning entity). My concern is
that I might end up with a whole mess when it comes to the cloning of
tasks. I am also concerned about the performance of computing the end time
of each node recursively based on its previous task and dependent tasks.
What is the best approach in this case?
thanks,
Josef
On 25 July 2012 08:30, Geoffrey De Smet <ge0ffrey.spam(a)gmail.com> wrote:
Op 24-07-12 23:14, Josef Bajada schreef:
Hi Geoffrey,
Thanks for your reply.
> Does it make sense to wait longer than 7 mins after task A (presuming
no other task forces occupies the user at that time)?
> Put differently: Can we say that the starting time of B =
Math.max((endTime of task before B), (endTime of task A + 7 minutes))?
> If we can say that, it's pointless to investigate the solutions where
task B starts 8 minutes after task A and the user doing no task that last
minute.
Yes, the starting time of B = Math.max((endTime of task before B),
(endTime of task A + 7mins)) as long as it is smaller than (endTime of task
A + 8mins).
Yes, it is pointless to investigate the solutions where task B starts 8
minutes after task A and the user doing no task that last minute.
The 8 minute is just a constraint that the task in between tasks A and B
cannot take longer than 7:59s.
I am thinking that maybe instead of using time itself as the planning
variable, we would use time just to determine the Hard and Soft scores.
So if Task B is scheduled after Task A + 8mins by the solver, then it
inflicts on the hard score. Similarly if Task B is scheduled before Task A
+ 7 mins.
Does my reasoning make sense in any way?
Yes, but personally, I 'd design it differently (although I have no proof
that my way would be better), like this:
"Task B is scheduled after Task A + 8mins by the solver" => make this a
hard constraint
"Task B is scheduled before Task A + 7 mins" => make this a build-in hard
constraint (= not a constraint in the scoreDRL or ScoreCalculator, but by
design, see manual).
Each Task is assigned to a previousTaskOrPerson (and this variable is
chained). It does not know it's startingTime directly.
The scoreDRL or ScoreCalculator calculates the startingTime of a Task
dynamically, by applying this logic:
starting time of B = Math.max((endTime of previousTaskOrPerson of B),
(endTime of task A + 7mins))
Note: "Chained=true" guarantees that there are no cycles of Tasks and that
no Tasks exists with a previousTaskOrPerson == null.
Note: "(endTime of task A + 7mins)" is not hard coded in the score
function: you won't find "7" or "A" in there.
thanks,
Josef
On 24 July 2012 20:46, Geoffrey De Smet <ge0ffrey.spam(a)gmail.com> wrote:
>
> Op 23-07-12 16:26, Josef Bajada schreef:
>
> Hi Geoffrey,
>
> Well I want to leave 'space' between tasks in the situations where
> there are hard constraints that require me to put this space.
>
> This makes the chaining technique harder to model, but I wouldn't write
> it off yet.
>
>
> As a simple example:
>
> Task A: Put pasta in boiling water (duration 40 seconds)
> Task B: Take pasta out of boiling water (duration 50 seconds, cannot
> start before 7 mins after Task A finishes, cannot start after 8 mins after
> Task A finishes)
>
> Does it make sense to wait longer than 7 mins after task A (presuming no
> other task forces occupies the user at that time)?
> Put differently: Can we say that the starting time of B =
> Math.max((endTime of task before B), (endTime of task A + 7 minutes))?
> If we can say that, it's pointless to investigate the solutions where
> task B starts 8 minutes after task A and the user doing no task that last
> minute.
> If we can say that, then chaining can calculate the the starting time of
> a task on the fly differently.
>
> Task C: Chop vegetables (duration 2 minutes).
>
> This will evidently leave some gaps. The ideal result from the solver
> should be:
>
> Task A: at time 0 (ends at 40s)
> Task C: at time 41s (ends at 2:41)
> Task B: at time 7:40
>
> There is a gap between C and B which is OK.
>
> If another Task is added to the story:
> Task D: Prepare sauce (duration 7 minutes)
>
> I would want the following result:
>
> Task A: at time 0 (ends at 40s)
> Task D: at time 41s (ends 7:41s)
> Task B: at time 8:42s (ends 9:32s)
> Task C: at time 9:33s (ends 11:33s)
>
> Task C can actually take place before Task A too.
>
> I still need to read and understand the chaining functionality
> properly. Do you think it would allow me to achieve the above?
>
> I don't know.
> But using continuous variables in a search problem such as this that
> smells discrete with discrete constraints (A must start before B, ...),
> could blow up the search space unnecessarily.
>
> If you want to look into using continuous variables: the support for it
> is limited currently.
> you can reuse the Drools Planner metaheuristic algorithms (including
> termination, score, ...), but there's no decent generic move factory
> support for continuous variables yet.
> So you 'll have to write a custom MoveFactory that creates a limited
> subset of moves.
> Also, construction heuristics can't handle continuous variables yet, so
> you 'll have to write a custom SolutionIntializer.
> There are examples with a custom MoveFactory and a custom
> SolutionIntializer where you can copy paste from, but none with continuous
> variables at the moment.
>
> thanks,
>
> Josef
>
>
>
> On 22 July 2012 20:05, Geoffrey De Smet <ge0ffrey.spam(a)gmail.com> wrote:
>
>> Presuming that you don't want to leave space between tasks, you can
>> design your model differently by using the "chained" functionality:
>> it will be far more efficient and the planning variable won't be
>> continuous.
>>
>> Let's presume you're scheduling Tasks to Persons.
>>
>> @PlanningEntity
>> class Task implements TaskOrPerson {
>>
>> ...
>>
>> @PlanningVariable(chained = true)
>> @ValueRanges({
>> @ValueRange(type = ValueRangeType.FROM_SOLUTION_PROPERTY,
>> solutionProperty = "taskList"),
>> @ValueRange(type = ValueRangeType.FROM_SOLUTION_PROPERTY,
>> solutionProperty = "personList",
>> excludeUninitializedPlanningEntity = true)})
>> public TaskOrPerson getPreviousTaskOrPerson() {
>> return previousTaskOrPerson;
>> }
>>
>> public int getDuration() {
>> return duration;
>> }
>>
>> public int getStartingTime() {
>> int startingTime = 0;
>> TaskOrPerson taskOrPerson = getPreviousTaskOrPerson();
>> while (taskOrPerson instanceof Task) { // Every chain is
>> guarantee to end up with an anchor (= Person)
>> startingTime += ((Task) taskOrPerson).getDuration();
>> taskOrPerson = ((Task)
>> taskOrPerson).getPreviousTaskOrPerson()
>> }
>> return startingTime;
>> }
>>
>> }
>>
>> class Person implements TaskOrPerson {
>>
>> }
>>
>> For a good example, take a look at the VehicleRouting example.
>> For more info about chaining, in the manual see section 4.3.4.2.6.
>> Chained
>>
>>
http://docs.jboss.org/drools/release/5.4.0.Final/drools-planner-docs/html...
>>
>> Op 22-07-12 18 <22-07-12%2018>:00, Josef Bajada schreef:
>>
>> Hi,
>>
>> I am new to Drools and Drools Planner, so apologies if I am asking
>> anything obvious.
>>
>> My objective is to implement a simple (for now) planner which
>> schedules tasks according to 2 main criteria:
>> - Their duration (in seconds)
>> - Their dependencies on other tasks (e.g. Hard Constraint that Task B
>> has to start between 180 and 200 seconds after Task A finishes).
>>
>> Since there are gaps between dependent tasks as part of the hard
>> constraints other tasks can be fitted in between dependent tasks.
>> So the Solver needs to find the optimal start time for each task that
>> satisfies the hard constraints, and in the shortest total timeline possible
>> to complete all tasks (soft constraint).
>>
>> The main problem I am finding is that this start time, which is
>> essentially the planning variable is a continuous variable.
>> Chapter 4 of the Drools documentation mentions very briefly (Section
>> 4.3.4.1) that planning variables can be continuous, but there does not
>> seem to be any more details about how to achieve this.
>>
>> Even if the planning variable was discrete (say bins of 5 second
>> intervals), there is no upper bound as such.
>>
>> How is it best to handle such planning variables in Drools Planner?
>>
>> thanks,
>> josef
>>
>>
>>
>>
>> _______________________________________________
>> rules-users mailing
listrules-users@lists.jboss.orghttps://lists.jboss.org/mailman/listinfo/rules-users
>>
>>
>> --
>> With kind regards,
>> Geoffrey De Smet
>>
>>
>> _______________________________________________
>> rules-users mailing list
>> rules-users(a)lists.jboss.org
>> https://lists.jboss.org/mailman/listinfo/rules-users
>>
>>
>
>
> _______________________________________________
> rules-users mailing
listrules-users@lists.jboss.orghttps://lists.jboss.org/mailman/listinfo/rules-users
>
>
> --
> With kind regards,
> Geoffrey De Smet
>
>
> _______________________________________________
> rules-users mailing list
> rules-users(a)lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/rules-users
>
>
_______________________________________________
rules-users mailing
listrules-users@lists.jboss.orghttps://lists.jboss.org/mailman/listinfo/rules-users
--
With kind regards,
Geoffrey De Smet
_______________________________________________
rules-users mailing list
rules-users(a)lists.jboss.org
https://lists.jboss.org/mailman/listinfo/rules-users
2:46 a.m.
You 'll want incremental score calculation (with delta's) for your "end
times".
http://docs.jboss.org/drools/release/5.4.0.Final/drools-planner-docs/html...
So that naturally puts the calculation of those end times in the
scoreDRL (or IncrementalJavaCalculator if you're not using drools).
Whether or not that endTime should be a property on the model (at least
the model that Planner works with), is an open design question.
If it isn't, you can use insertLogicals in DRL, like I did in
nurserostering to calculate the number of sequential weekends being
worked etc.
If it is a property on your model, either the DRL must first "correct
it" (with higher salience rules for example),
or custom moves must "correct it" as they are being done (which is very
hard as it entails constraints functionality).
As for the cloning: it's quite simple:
Either the model's entity contains the endTime property, then clone it.
If it doesn't, then there's nothing to clone.
I don't see any problems related to the cloning.
Op 18-08-12 01:53, Josef Bajada schreef:
Hi Geoffrey,
Following your advice and after gaining some more understanding of
planner, I think approaching the problem as a chain of tasks one of
the other makes sense. It would have some 'wait' time between tasks
where the end time of the previous task is smaller than the minimum
time the task has to wait after its dependency (which could be
different from the previous task).
I've noticed that in most examples (TSP and VRP), there is some
separation between the model and the planning entity that is being
moved around in the chain, which also makes sense. (For instance in
TSP, Visit is the planning entity while City is the data entity). When
the planning entity gets cloned, the data entity gets assigned to the
clone.
I am concerned however, that with my dependency between tasks and
their end times (which are as such a property of the planning entity
not the data entity) I won't be able to model them in this way. (For a
task to know whether it has violated its hard constraint it needs to
get access to the end time of its dependency, which is in the planning
entity). My concern is that I might end up with a whole mess when it
comes to the cloning of tasks. I am also concerned about the
performance of computing the end time of each node recursively based
on its previous task and dependent tasks.
What is the best approach in this case?
thanks,
Josef
On 25 July 2012 08:30, Geoffrey De Smet <ge0ffrey.spam(a)gmail.com
<mailto:ge0ffrey.spam@gmail.com>> wrote:
Op 24-07-12 23:14, Josef Bajada schreef:
> Hi Geoffrey,
>
> Thanks for your reply.
>
> > Does it make sense to wait longer than 7 mins after task A
> (presuming no other task forces occupies the user at that time)?
> > Put differently: Can we say that the starting time of B =
> Math.max((endTime of task before B), (endTime of task A + 7
> minutes))?
> > If we can say that, it's pointless to investigate the solutions
> where task B starts 8 minutes after task A and the user doing no
> task that last minute.
>
> Yes, the starting time of B = Math.max((endTime of task before
> B), (endTime of task A + 7mins)) as long as it is smaller than
> (endTime of task A + 8mins).
> Yes, it is pointless to investigate the solutions where task B
> starts 8 minutes after task A and the user doing no task that
> last minute.
> The 8 minute is just a constraint that the task in between tasks
> A and B cannot take longer than 7:59s.
>
> I am thinking that maybe instead of using time itself as the
> planning variable, we would use time just to determine the Hard
> and Soft scores.
> So if Task B is scheduled after Task A + 8mins by the solver,
> then it inflicts on the hard score. Similarly if Task B is
> scheduled before Task A + 7 mins.
> Does my reasoning make sense in any way?
Yes, but personally, I 'd design it differently (although I have
no proof that my way would be better), like this:
"Task B is scheduled after Task A + 8mins by the solver" => make
this a hard constraint
"Task B is scheduled before Task A + 7 mins" => make this a
build-in hard constraint (= not a constraint in the scoreDRL or
ScoreCalculator, but by design, see manual).
Each Task is assigned to a previousTaskOrPerson (and this variable
is chained). It does not know it's startingTime directly.
The scoreDRL or ScoreCalculator calculates the startingTime of a
Task dynamically, by applying this logic:
starting time of B = Math.max((endTime of previousTaskOrPerson
of B), (endTime of task A + 7mins))
Note: "Chained=true" guarantees that there are no cycles of Tasks
and that no Tasks exists with a previousTaskOrPerson == null.
Note: "(endTime of task A + 7mins)" is not hard coded in the score
function: you won't find "7" or "A" in there.
>
> thanks,
> Josef
>
>
>
> On 24 July 2012 20:46, Geoffrey De Smet <ge0ffrey.spam(a)gmail.com
> <mailto:ge0ffrey.spam@gmail.com>> wrote:
>
>
> Op 23-07-12 16 <tel:23-07-12%2016>:26, Josef Bajada schreef:
>> Hi Geoffrey,
>>
>> Well I want to leave 'space' between tasks in the situations
>> where there are hard constraints that require me to put this
>> space.
> This makes the chaining technique harder to model, but I
> wouldn't write it off yet.
>
>>
>> As a simple example:
>>
>> Task A: Put pasta in boiling water (duration 40 seconds)
>> Task B: Take pasta out of boiling water (duration 50
>> seconds, cannot start before 7 mins after Task A finishes,
>> cannot start after 8 mins after Task A finishes)
> Does it make sense to wait longer than 7 mins after task A
> (presuming no other task forces occupies the user at that time)?
> Put differently: Can we say that the starting time of B =
> Math.max((endTime of task before B), (endTime of task A + 7
> minutes))?
> If we can say that, it's pointless to investigate the
> solutions where task B starts 8 minutes after task A and the
> user doing no task that last minute.
> If we can say that, then chaining can calculate the the
> starting time of a task on the fly differently.
>
>> Task C: Chop vegetables (duration 2 minutes).
>>
>> This will evidently leave some gaps. The ideal result from
>> the solver should be:
>>
>> Task A: at time 0 (ends at 40s)
>> Task C: at time 41s (ends at 2:41)
>> Task B: at time 7:40
>>
>> There is a gap between C and B which is OK.
>>
>> If another Task is added to the story:
>> Task D: Prepare sauce (duration 7 minutes)
>>
>> I would want the following result:
>>
>> Task A: at time 0 (ends at 40s)
>> Task D: at time 41s (ends 7:41s)
>> Task B: at time 8:42s (ends 9:32s)
>> Task C: at time 9:33s (ends 11:33s)
>>
>> Task C can actually take place before Task A too.
>>
>> I still need to read and understand the chaining
>> functionality properly. Do you think it would allow me to
>> achieve the above?
>>
> I don't know.
> But using continuous variables in a search problem such as
> this that smells discrete with discrete constraints (A must
> start before B, ...), could blow up the search space
> unnecessarily.
>
> If you want to look into using continuous variables: the
> support for it is limited currently.
> you can reuse the Drools Planner metaheuristic algorithms
> (including termination, score, ...), but there's no decent
> generic move factory support for continuous variables yet.
> So you 'll have to write a custom MoveFactory that creates a
> limited subset of moves.
> Also, construction heuristics can't handle continuous
> variables yet, so you 'll have to write a custom
> SolutionIntializer.
> There are examples with a custom MoveFactory and a custom
> SolutionIntializer where you can copy paste from, but none
> with continuous variables at the moment.
>
>> thanks,
>>
>> Josef
>>
>>
>>
>> On 22 July 2012 20:05, Geoffrey De Smet
>> <ge0ffrey.spam(a)gmail.com <mailto:ge0ffrey.spam@gmail.com>>
>> wrote:
>>
>> Presuming that you don't want to leave space between
>> tasks, you can design your model differently by using
>> the "chained" functionality:
>> it will be far more efficient and the planning variable
>> won't be continuous.
>>
>> Let's presume you're scheduling Tasks to Persons.
>>
>> @PlanningEntity
>> class Task implements TaskOrPerson {
>>
>> ...
>>
>> @PlanningVariable(chained = true)
>> @ValueRanges({
>> @ValueRange(type =
>> ValueRangeType.FROM_SOLUTION_PROPERTY, solutionProperty
>> = "taskList"),
>> @ValueRange(type =
>> ValueRangeType.FROM_SOLUTION_PROPERTY, solutionProperty
>> = "personList",
>> excludeUninitializedPlanningEntity = true)})
>> public TaskOrPerson getPreviousTaskOrPerson() {
>> return previousTaskOrPerson;
>> }
>>
>> public int getDuration() {
>> return duration;
>> }
>>
>> public int getStartingTime() {
>> int startingTime = 0;
>> TaskOrPerson taskOrPerson =
>> getPreviousTaskOrPerson();
>> while (taskOrPerson instanceof Task) { //
>> Every chain is guarantee to end up with an anchor (= Person)
>> startingTime += ((Task)
>> taskOrPerson).getDuration();
>> taskOrPerson = ((Task)
>> taskOrPerson).getPreviousTaskOrPerson()
>> }
>> return startingTime;
>> }
>>
>> }
>>
>> class Person implements TaskOrPerson {
>>
>> }
>>
>> For a good example, take a look at the VehicleRouting
>> example.
>> For more info about chaining, in the manual see section
>> 4.3.4.2.6. Chained
>>
http://docs.jboss.org/drools/release/5.4.0.Final/drools-planner-docs/html...
>>
>> Op 22-07-12 18 <tel:22-07-12%2018>:00, Josef Bajada schreef:
>>> Hi,
>>>
>>> I am new to Drools and Drools Planner, so apologies if
>>> I am asking anything obvious.
>>>
>>> My objective is to implement a simple (for now) planner
>>> which schedules tasks according to 2 main criteria:
>>> - Their duration (in seconds)
>>> - Their dependencies on other tasks (e.g. Hard
>>> Constraint that Task B has to start between 180 and 200
>>> seconds after Task A finishes).
>>>
>>> Since there are gaps between dependent tasks as part of
>>> the hard constraints other tasks can be fitted in
>>> between dependent tasks.
>>> So the Solver needs to find the optimal start time for
>>> each task that satisfies the hard constraints, and in
>>> the shortest total timeline possible to complete all
>>> tasks (soft constraint).
>>>
>>> The main problem I am finding is that this start time,
>>> which is essentially the planning variable is a
>>> continuous variable.
>>> Chapter 4 of the Drools documentation mentions very
>>> briefly (Section 4.3.4.1) that planning variables can
>>> be continuous, but there does not seem to be any more
>>> details about how to achieve this.
>>>
>>> Even if the planning variable was discrete (say bins of
>>> 5 second intervals), there is no upper bound as such.
>>>
>>> How is it best to handle such planning variables in
>>> Drools Planner?
>>>
>>> thanks,
>>> josef
>>>
>>>
>>>
>>>
>>> _______________________________________________
>>> rules-users mailing list
>>> rules-users(a)lists.jboss.org
<mailto:rules-users@lists.jboss.org>
>>> https://lists.jboss.org/mailman/listinfo/rules-users
>>
>> --
>> With kind regards,
>> Geoffrey De Smet
>>
>>
>> _______________________________________________
>> rules-users mailing list
>> rules-users(a)lists.jboss.org
>> <mailto:rules-users@lists.jboss.org>
>> https://lists.jboss.org/mailman/listinfo/rules-users
>>
>>
>>
>>
>> _______________________________________________
>> rules-users mailing list
>> rules-users(a)lists.jboss.org <mailto:rules-users@lists.jboss.org>
>> https://lists.jboss.org/mailman/listinfo/rules-users
>
> --
> With kind regards,
> Geoffrey De Smet
>
>
> _______________________________________________
> rules-users mailing list
> rules-users(a)lists.jboss.org <mailto:rules-users@lists.jboss.org>
> https://lists.jboss.org/mailman/listinfo/rules-users
>
>
>
>
> _______________________________________________
> rules-users mailing list
> rules-users(a)lists.jboss.org <mailto:rules-users@lists.jboss.org>
> https://lists.jboss.org/mailman/listinfo/rules-users
--
With kind regards,
Geoffrey De Smet
_______________________________________________
rules-users mailing list
rules-users(a)lists.jboss.org <mailto:rules-users@lists.jboss.org>
https://lists.jboss.org/mailman/listinfo/rules-users
_______________________________________________
rules-users mailing list
rules-users(a)lists.jboss.org
https://lists.jboss.org/mailman/listinfo/rules-users
--
With kind regards,
Geoffrey De Smet
9:02 p.m.
Hi Geoffrey,
I managed to implement the solution with the relative end Times. (I haven't
yet used the incremental score calculation because I haven't quite
understood how I implement it)
However I am facing one problem with our approach:
Lets say we have 3 tasks A, B, and C, each of duration 1 just for
simplicity, with these constraints:
a) B can only start between A.endTime + 10 and A.endTime + 100
b) C can only start between A.endTime + 50 and A.endTime + 100
c) C can only start between B.endTime + 10 and B.endTime + 20
With our approach of B.startTime = max(prev.endTime, A.endTime + 10) B
will always be scheduled to start at time 11 (and end at time 12) given the
hard constraints above.
On the other hand C cannot start before time 51, thus violating constaint
C.
The only solution to this would be to move B forward to start at time 30.
Is there any technique to detect these situations and make such adjustments?
thanks again,
Josef
On 20 August 2012 09:46, Geoffrey De Smet <ge0ffrey.spam(a)gmail.com> wrote:
You 'll want incremental score calculation (with delta's)
for your "end
times".
http://docs.jboss.org/drools/release/5.4.0.Final/drools-planner-docs/html...
So that naturally puts the calculation of those end times in the scoreDRL
(or IncrementalJavaCalculator if you're not using drools).
Whether or not that endTime should be a property on the model (at least
the model that Planner works with), is an open design question.
If it isn't, you can use insertLogicals in DRL, like I did in
nurserostering to calculate the number of sequential weekends being worked
etc.
If it is a property on your model, either the DRL must first "correct it"
(with higher salience rules for example),
or custom moves must "correct it" as they are being done (which is very
hard as it entails constraints functionality).
As for the cloning: it's quite simple:
Either the model's entity contains the endTime property, then clone it.
If it doesn't, then there's nothing to clone.
I don't see any problems related to the cloning.
Op 18-08-12 01:53, Josef Bajada schreef:
Hi Geoffrey,
Following your advice and after gaining some more understanding of
planner, I think approaching the problem as a chain of tasks one of the
other makes sense. It would have some 'wait' time between tasks where the
end time of the previous task is smaller than the minimum time the task has
to wait after its dependency (which could be different from the previous
task).
I've noticed that in most examples (TSP and VRP), there is some
separation between the model and the planning entity that is being moved
around in the chain, which also makes sense. (For instance in TSP, Visit is
the planning entity while City is the data entity). When the planning
entity gets cloned, the data entity gets assigned to the clone.
I am concerned however, that with my dependency between tasks and their
end times (which are as such a property of the planning entity not the data
entity) I won't be able to model them in this way. (For a task to know
whether it has violated its hard constraint it needs to get access to the
end time of its dependency, which is in the planning entity). My concern is
that I might end up with a whole mess when it comes to the cloning of
tasks. I am also concerned about the performance of computing the end time
of each node recursively based on its previous task and dependent tasks.
What is the best approach in this case?
thanks,
Josef
On 25 July 2012 08:30, Geoffrey De Smet <ge0ffrey.spam(a)gmail.com> wrote:
>
> Op 24-07-12 23:14, Josef Bajada schreef:
>
> Hi Geoffrey,
>
> Thanks for your reply.
>
> > Does it make sense to wait longer than 7 mins after task A (presuming
> no other task forces occupies the user at that time)?
> > Put differently: Can we say that the starting time of B =
> Math.max((endTime of task before B), (endTime of task A + 7 minutes))?
> > If we can say that, it's pointless to investigate the solutions where
> task B starts 8 minutes after task A and the user doing no task that last
> minute.
>
> Yes, the starting time of B = Math.max((endTime of task before B),
> (endTime of task A + 7mins)) as long as it is smaller than (endTime of task
> A + 8mins).
> Yes, it is pointless to investigate the solutions where task B starts 8
> minutes after task A and the user doing no task that last minute.
> The 8 minute is just a constraint that the task in between tasks A and B
> cannot take longer than 7:59s.
>
> I am thinking that maybe instead of using time itself as the planning
> variable, we would use time just to determine the Hard and Soft scores.
> So if Task B is scheduled after Task A + 8mins by the solver, then it
> inflicts on the hard score. Similarly if Task B is scheduled before Task A
> + 7 mins.
> Does my reasoning make sense in any way?
>
> Yes, but personally, I 'd design it differently (although I have no proof
> that my way would be better), like this:
> "Task B is scheduled after Task A + 8mins by the solver" => make this a
> hard constraint
> "Task B is scheduled before Task A + 7 mins" => make this a build-in
hard
> constraint (= not a constraint in the scoreDRL or ScoreCalculator, but by
> design, see manual).
> Each Task is assigned to a previousTaskOrPerson (and this variable is
> chained). It does not know it's startingTime directly.
> The scoreDRL or ScoreCalculator calculates the startingTime of a Task
> dynamically, by applying this logic:
> starting time of B = Math.max((endTime of previousTaskOrPerson of B),
> (endTime of task A + 7mins))
> Note: "Chained=true" guarantees that there are no cycles of Tasks and
> that no Tasks exists with a previousTaskOrPerson == null.
> Note: "(endTime of task A + 7mins)" is not hard coded in the score
> function: you won't find "7" or "A" in there.
>
>
>
> thanks,
> Josef
>
>
>
> On 24 July 2012 20:46, Geoffrey De Smet <ge0ffrey.spam(a)gmail.com> wrote:
>
>>
>> Op 23-07-12 16 <23-07-12%2016>:26, Josef Bajada schreef:
>>
>> Hi Geoffrey,
>>
>> Well I want to leave 'space' between tasks in the situations where
>> there are hard constraints that require me to put this space.
>>
>> This makes the chaining technique harder to model, but I wouldn't write
>> it off yet.
>>
>>
>> As a simple example:
>>
>> Task A: Put pasta in boiling water (duration 40 seconds)
>> Task B: Take pasta out of boiling water (duration 50 seconds, cannot
>> start before 7 mins after Task A finishes, cannot start after 8 mins after
>> Task A finishes)
>>
>> Does it make sense to wait longer than 7 mins after task A (presuming
>> no other task forces occupies the user at that time)?
>> Put differently: Can we say that the starting time of B =
>> Math.max((endTime of task before B), (endTime of task A + 7 minutes))?
>> If we can say that, it's pointless to investigate the solutions where
>> task B starts 8 minutes after task A and the user doing no task that last
>> minute.
>> If we can say that, then chaining can calculate the the starting time of
>> a task on the fly differently.
>>
>> Task C: Chop vegetables (duration 2 minutes).
>>
>> This will evidently leave some gaps. The ideal result from the solver
>> should be:
>>
>> Task A: at time 0 (ends at 40s)
>> Task C: at time 41s (ends at 2:41)
>> Task B: at time 7:40
>>
>> There is a gap between C and B which is OK.
>>
>> If another Task is added to the story:
>> Task D: Prepare sauce (duration 7 minutes)
>>
>> I would want the following result:
>>
>> Task A: at time 0 (ends at 40s)
>> Task D: at time 41s (ends 7:41s)
>> Task B: at time 8:42s (ends 9:32s)
>> Task C: at time 9:33s (ends 11:33s)
>>
>> Task C can actually take place before Task A too.
>>
>> I still need to read and understand the chaining functionality
>> properly. Do you think it would allow me to achieve the above?
>>
>> I don't know.
>> But using continuous variables in a search problem such as this that
>> smells discrete with discrete constraints (A must start before B, ...),
>> could blow up the search space unnecessarily.
>>
>> If you want to look into using continuous variables: the support for it
>> is limited currently.
>> you can reuse the Drools Planner metaheuristic algorithms (including
>> termination, score, ...), but there's no decent generic move factory
>> support for continuous variables yet.
>> So you 'll have to write a custom MoveFactory that creates a limited
>> subset of moves.
>> Also, construction heuristics can't handle continuous variables yet, so
>> you 'll have to write a custom SolutionIntializer.
>> There are examples with a custom MoveFactory and a custom
>> SolutionIntializer where you can copy paste from, but none with continuous
>> variables at the moment.
>>
>> thanks,
>>
>> Josef
>>
>>
>>
>> On 22 July 2012 20:05, Geoffrey De Smet <ge0ffrey.spam(a)gmail.com> wrote:
>>
>>> Presuming that you don't want to leave space between tasks, you can
>>> design your model differently by using the "chained"
functionality:
>>> it will be far more efficient and the planning variable won't be
>>> continuous.
>>>
>>> Let's presume you're scheduling Tasks to Persons.
>>>
>>> @PlanningEntity
>>> class Task implements TaskOrPerson {
>>>
>>> ...
>>>
>>> @PlanningVariable(chained = true)
>>> @ValueRanges({
>>> @ValueRange(type = ValueRangeType.FROM_SOLUTION_PROPERTY,
>>> solutionProperty = "taskList"),
>>> @ValueRange(type = ValueRangeType.FROM_SOLUTION_PROPERTY,
>>> solutionProperty = "personList",
>>> excludeUninitializedPlanningEntity = true)})
>>> public TaskOrPerson getPreviousTaskOrPerson() {
>>> return previousTaskOrPerson;
>>> }
>>>
>>> public int getDuration() {
>>> return duration;
>>> }
>>>
>>> public int getStartingTime() {
>>> int startingTime = 0;
>>> TaskOrPerson taskOrPerson = getPreviousTaskOrPerson();
>>> while (taskOrPerson instanceof Task) { // Every chain is
>>> guarantee to end up with an anchor (= Person)
>>> startingTime += ((Task) taskOrPerson).getDuration();
>>> taskOrPerson = ((Task)
>>> taskOrPerson).getPreviousTaskOrPerson()
>>> }
>>> return startingTime;
>>> }
>>>
>>> }
>>>
>>> class Person implements TaskOrPerson {
>>>
>>> }
>>>
>>> For a good example, take a look at the VehicleRouting example.
>>> For more info about chaining, in the manual see section 4.3.4.2.6.
>>> Chained
>>>
>>>
http://docs.jboss.org/drools/release/5.4.0.Final/drools-planner-docs/html...
>>>
>>> Op 22-07-12 18 <22-07-12%2018>:00, Josef Bajada schreef:
>>>
>>> Hi,
>>>
>>> I am new to Drools and Drools Planner, so apologies if I am asking
>>> anything obvious.
>>>
>>> My objective is to implement a simple (for now) planner which
>>> schedules tasks according to 2 main criteria:
>>> - Their duration (in seconds)
>>> - Their dependencies on other tasks (e.g. Hard Constraint that Task B
>>> has to start between 180 and 200 seconds after Task A finishes).
>>>
>>> Since there are gaps between dependent tasks as part of the hard
>>> constraints other tasks can be fitted in between dependent tasks.
>>> So the Solver needs to find the optimal start time for each task that
>>> satisfies the hard constraints, and in the shortest total timeline possible
>>> to complete all tasks (soft constraint).
>>>
>>> The main problem I am finding is that this start time, which is
>>> essentially the planning variable is a continuous variable.
>>> Chapter 4 of the Drools documentation mentions very briefly (Section
>>> 4.3.4.1) that planning variables can be continuous, but there does not
>>> seem to be any more details about how to achieve this.
>>>
>>> Even if the planning variable was discrete (say bins of 5 second
>>> intervals), there is no upper bound as such.
>>>
>>> How is it best to handle such planning variables in Drools Planner?
>>>
>>> thanks,
>>> josef
>>>
>>>
>>>
>>>
>>> _______________________________________________
>>> rules-users mailing
listrules-users@lists.jboss.orghttps://lists.jboss.org/mailman/listinfo/rules-users
>>>
>>>
>>> --
>>> With kind regards,
>>> Geoffrey De Smet
>>>
>>>
>>> _______________________________________________
>>> rules-users mailing list
>>> rules-users(a)lists.jboss.org
>>> https://lists.jboss.org/mailman/listinfo/rules-users
>>>
>>>
>>
>>
>> _______________________________________________
>> rules-users mailing
listrules-users@lists.jboss.orghttps://lists.jboss.org/mailman/listinfo/rules-users
>>
>>
>> --
>> With kind regards,
>> Geoffrey De Smet
>>
>>
>> _______________________________________________
>> rules-users mailing list
>> rules-users(a)lists.jboss.org
>> https://lists.jboss.org/mailman/listinfo/rules-users
>>
>>
>
>
> _______________________________________________
> rules-users mailing
listrules-users@lists.jboss.orghttps://lists.jboss.org/mailman/listinfo/rules-users
>
>
> --
> With kind regards,
> Geoffrey De Smet
>
>
> _______________________________________________
> rules-users mailing list
> rules-users(a)lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/rules-users
>
>
_______________________________________________
rules-users mailing
listrules-users@lists.jboss.orghttps://lists.jboss.org/mailman/listinfo/rules-users
--
With kind regards,
Geoffrey De Smet
_______________________________________________
rules-users mailing list
rules-users(a)lists.jboss.org
https://lists.jboss.org/mailman/listinfo/rules-users
11:17 a.m.
Hi Geoffrey,
Thanks for your reply.
Well, my current design is just:
@PlanningEntity class Task
{
@PlanningVariable Task previousTask;
The startTime and endTime then are just derived from the previousTask and
the constraints that come from the facts (i.e. other dependency tasks which
cannot change).
The startTime is computed by taking the max(prevTask.endTime,
max{dependency.endTime + dependency.minoffset}) for each dependency when
calculating the Score, since continuous variables were not that
'recommended' so far.
One thing I wanted to do is 'cache' the startTime of each task once
computed for that Score iteration. This way if A depends on B and B already
had its startTime calculated I don't calculate it again.
On the other hand, to make sure that they don't get carried over from one
iteration to another the first thing the score calculator does is set the
startTime of all planning entities to null.
Not sure if this is the right approach after all, but it was another reason
why I stayed away from the IncrementalScoreCalculator. If I find a more
elegant solution for the startTime calculation (maybe as you are suggesting
with design option 1) it would fit more easily into a Drools drl file...
once I get my head around it.
I like this approach:
@PlanningEntity class Task {
@PlanningVariable Task previousTask;
@PlanningVariable int gap;
}
However, didn't the 'gap' now become a Continuous variable? How do I use
it?
Is it possible to prune the search space in any way so that it only looks
for values between the minOffset and maxOffset of its dependencies?
Re the custom move factory, I'll have a look.
thanks,
Josef
On 11 September 2012 13:33, Geoffrey De Smet <ge0ffrey.spam(a)gmail.com>wrote:
Op 11-09-12 04:02, Josef Bajada schreef:
Hi Geoffrey,
I managed to implement the solution with the relative end Times. (I
haven't yet used the incremental score calculation because I haven't quite
understood how I implement it)
If you use DRL, the incremental score calculation comes automatically.
Basically, the average calculation score count should be above 1000/s,
even for cases with 1000+ entities. Without incremental score calcluation,
the average calculation score count won't be anywhere near that when the
entityList size scales out.
However I am facing one problem with our approach:
Lets say we have 3 tasks A, B, and C, each of duration 1 just for
simplicity, with these constraints:
a) B can only start between A.endTime + 10 and A.endTime + 100
b) C can only start between A.endTime + 50 and A.endTime + 100
c) C can only start between B.endTime + 10 and B.endTime + 20
With our approach of B.startTime = max(prev.endTime, A.endTime + 10) B
will always be scheduled to start at time 11 (and end at time 12) given the
hard constraints above.
On the other hand C cannot start before time 51, thus violating constaint
C.
Good point. The question is whether you need to go for an implementation
1) for which B can have any gap with A between 10 and 100
or 2) for which B can only chose from a specific set of gap lengths
between 10 and 100: 11, 99, 51, (51 - B length), ...
I think 2) is probably not realistic, if you start adding many other tasks
it becomes unmanageable (unless we are overlooking a clever way to filter
potential gaps).
Ok, so the question is if we want this design:
1) @PlanningEntity class Task {
@PlanningVariable Task previousTask;
@PlanningVariable int gap;
}
Or your original design:
0) @PlanningEntity class Task {
@PlanningVariable int startTime;
}
(there might be other designs too)
It kinda depends on your planning window length what might works best:
Presume you have a planning window length of 100000 and 200 tasks and an
average maximum gap of 100.
In case 0), each of 200 tasks will have 1 variable with 100000 values. =>
that's a search space of 100000^200 = 10^1000.
In case 1), each of 200 tasks will have 2 variables, one var with 200
values and one var with on average 100 values. => that's a search space of
(100 * 200)^200 = 10^860.
Note that those kind of search space sizes are ok, don't let the numbers
scare you.
The only solution to this would be to move B forward to start at time
30. Is there any technique to detect these situations and make such
adjustments?
In a custom MoveFactory you could detect these situations and generate
moves for them.
The advantage of design 1) is that you 'd be effectively pushing all the
tasks dependent on the task that get moved too.
If those dependent task don't get pushed back, they 'll cause a hard
constraint to trigger and the move will be very unlikely to win the local
search step.
This is known as a "score trap" (see manual).
You might also want to take a long hard look at as complex as
BedDesignationPillarPartSwapMoveFactory in the hospital bed planning
example.
The idea is to swap 2 chains of tasks, instead of just 2 tasks.
thanks again,
Josef
On 20 August 2012 09:46, Geoffrey De Smet <ge0ffrey.spam(a)gmail.com> wrote:
> You 'll want incremental score calculation (with delta's) for your
"end
> times".
>
>
http://docs.jboss.org/drools/release/5.4.0.Final/drools-planner-docs/html...
>
> So that naturally puts the calculation of those end times in the scoreDRL
> (or IncrementalJavaCalculator if you're not using drools).
> Whether or not that endTime should be a property on the model (at least
> the model that Planner works with), is an open design question.
> If it isn't, you can use insertLogicals in DRL, like I did in
> nurserostering to calculate the number of sequential weekends being worked
> etc.
> If it is a property on your model, either the DRL must first "correct it"
> (with higher salience rules for example),
> or custom moves must "correct it" as they are being done (which is very
> hard as it entails constraints functionality).
>
> As for the cloning: it's quite simple:
> Either the model's entity contains the endTime property, then clone it.
> If it doesn't, then there's nothing to clone.
> I don't see any problems related to the cloning.
>
> Op 18-08-12 01:53, Josef Bajada schreef:
>
> Hi Geoffrey,
>
> Following your advice and after gaining some more understanding of
> planner, I think approaching the problem as a chain of tasks one of the
> other makes sense. It would have some 'wait' time between tasks where the
> end time of the previous task is smaller than the minimum time the task has
> to wait after its dependency (which could be different from the previous
> task).
>
> I've noticed that in most examples (TSP and VRP), there is some
> separation between the model and the planning entity that is being moved
> around in the chain, which also makes sense. (For instance in TSP, Visit is
> the planning entity while City is the data entity). When the planning
> entity gets cloned, the data entity gets assigned to the clone.
>
> I am concerned however, that with my dependency between tasks and their
> end times (which are as such a property of the planning entity not the data
> entity) I won't be able to model them in this way. (For a task to know
> whether it has violated its hard constraint it needs to get access to the
> end time of its dependency, which is in the planning entity). My concern is
> that I might end up with a whole mess when it comes to the cloning of
> tasks. I am also concerned about the performance of computing the end time
> of each node recursively based on its previous task and dependent tasks.
>
> What is the best approach in this case?
>
> thanks,
>
> Josef
>
>
>
> On 25 July 2012 08:30, Geoffrey De Smet <ge0ffrey.spam(a)gmail.com> wrote:
>
>>
>> Op 24-07-12 23:14, Josef Bajada schreef:
>>
>> Hi Geoffrey,
>>
>> Thanks for your reply.
>>
>> > Does it make sense to wait longer than 7 mins after task A
>> (presuming no other task forces occupies the user at that time)?
>> > Put differently: Can we say that the starting time of B =
>> Math.max((endTime of task before B), (endTime of task A + 7 minutes))?
>> > If we can say that, it's pointless to investigate the solutions where
>> task B starts 8 minutes after task A and the user doing no task that last
>> minute.
>>
>> Yes, the starting time of B = Math.max((endTime of task before B),
>> (endTime of task A + 7mins)) as long as it is smaller than (endTime of task
>> A + 8mins).
>> Yes, it is pointless to investigate the solutions where task B starts 8
>> minutes after task A and the user doing no task that last minute.
>> The 8 minute is just a constraint that the task in between tasks A and B
>> cannot take longer than 7:59s.
>>
>> I am thinking that maybe instead of using time itself as the planning
>> variable, we would use time just to determine the Hard and Soft scores.
>> So if Task B is scheduled after Task A + 8mins by the solver, then it
>> inflicts on the hard score. Similarly if Task B is scheduled before Task A
>> + 7 mins.
>> Does my reasoning make sense in any way?
>>
>> Yes, but personally, I 'd design it differently (although I have no
>> proof that my way would be better), like this:
>> "Task B is scheduled after Task A + 8mins by the solver" => make
this a
>> hard constraint
>> "Task B is scheduled before Task A + 7 mins" => make this a
build-in
>> hard constraint (= not a constraint in the scoreDRL or ScoreCalculator, but
>> by design, see manual).
>> Each Task is assigned to a previousTaskOrPerson (and this variable is
>> chained). It does not know it's startingTime directly.
>> The scoreDRL or ScoreCalculator calculates the startingTime of a Task
>> dynamically, by applying this logic:
>> starting time of B = Math.max((endTime of previousTaskOrPerson of B),
>> (endTime of task A + 7mins))
>> Note: "Chained=true" guarantees that there are no cycles of Tasks and
>> that no Tasks exists with a previousTaskOrPerson == null.
>> Note: "(endTime of task A + 7mins)" is not hard coded in the score
>> function: you won't find "7" or "A" in there.
>>
>>
>>
>> thanks,
>> Josef
>>
>>
>>
>> On 24 July 2012 20:46, Geoffrey De Smet <ge0ffrey.spam(a)gmail.com> wrote:
>>
>>>
>>> Op 23-07-12 16 <23-07-12%2016>:26, Josef Bajada schreef:
>>>
>>> Hi Geoffrey,
>>>
>>> Well I want to leave 'space' between tasks in the situations where
>>> there are hard constraints that require me to put this space.
>>>
>>> This makes the chaining technique harder to model, but I wouldn't
>>> write it off yet.
>>>
>>>
>>> As a simple example:
>>>
>>> Task A: Put pasta in boiling water (duration 40 seconds)
>>> Task B: Take pasta out of boiling water (duration 50 seconds, cannot
>>> start before 7 mins after Task A finishes, cannot start after 8 mins after
>>> Task A finishes)
>>>
>>> Does it make sense to wait longer than 7 mins after task A (presuming
>>> no other task forces occupies the user at that time)?
>>> Put differently: Can we say that the starting time of B =
>>> Math.max((endTime of task before B), (endTime of task A + 7 minutes))?
>>> If we can say that, it's pointless to investigate the solutions where
>>> task B starts 8 minutes after task A and the user doing no task that last
>>> minute.
>>> If we can say that, then chaining can calculate the the starting time
>>> of a task on the fly differently.
>>>
>>> Task C: Chop vegetables (duration 2 minutes).
>>>
>>> This will evidently leave some gaps. The ideal result from the solver
>>> should be:
>>>
>>> Task A: at time 0 (ends at 40s)
>>> Task C: at time 41s (ends at 2:41)
>>> Task B: at time 7:40
>>>
>>> There is a gap between C and B which is OK.
>>>
>>> If another Task is added to the story:
>>> Task D: Prepare sauce (duration 7 minutes)
>>>
>>> I would want the following result:
>>>
>>> Task A: at time 0 (ends at 40s)
>>> Task D: at time 41s (ends 7:41s)
>>> Task B: at time 8:42s (ends 9:32s)
>>> Task C: at time 9:33s (ends 11:33s)
>>>
>>> Task C can actually take place before Task A too.
>>>
>>> I still need to read and understand the chaining functionality
>>> properly. Do you think it would allow me to achieve the above?
>>>
>>> I don't know.
>>> But using continuous variables in a search problem such as this that
>>> smells discrete with discrete constraints (A must start before B, ...),
>>> could blow up the search space unnecessarily.
>>>
>>> If you want to look into using continuous variables: the support for it
>>> is limited currently.
>>> you can reuse the Drools Planner metaheuristic algorithms (including
>>> termination, score, ...), but there's no decent generic move factory
>>> support for continuous variables yet.
>>> So you 'll have to write a custom MoveFactory that creates a limited
>>> subset of moves.
>>> Also, construction heuristics can't handle continuous variables yet, so
>>> you 'll have to write a custom SolutionIntializer.
>>> There are examples with a custom MoveFactory and a custom
>>> SolutionIntializer where you can copy paste from, but none with continuous
>>> variables at the moment.
>>>
>>> thanks,
>>>
>>> Josef
>>>
>>>
>>>
>>> On 22 July 2012 20:05, Geoffrey De Smet
<ge0ffrey.spam(a)gmail.com>wrote:
>>>
>>>> Presuming that you don't want to leave space between tasks, you can
>>>> design your model differently by using the "chained"
functionality:
>>>> it will be far more efficient and the planning variable won't be
>>>> continuous.
>>>>
>>>> Let's presume you're scheduling Tasks to Persons.
>>>>
>>>> @PlanningEntity
>>>> class Task implements TaskOrPerson {
>>>>
>>>> ...
>>>>
>>>> @PlanningVariable(chained = true)
>>>> @ValueRanges({
>>>> @ValueRange(type = ValueRangeType.FROM_SOLUTION_PROPERTY,
>>>> solutionProperty = "taskList"),
>>>> @ValueRange(type = ValueRangeType.FROM_SOLUTION_PROPERTY,
>>>> solutionProperty = "personList",
>>>> excludeUninitializedPlanningEntity = true)})
>>>> public TaskOrPerson getPreviousTaskOrPerson() {
>>>> return previousTaskOrPerson;
>>>> }
>>>>
>>>> public int getDuration() {
>>>> return duration;
>>>> }
>>>>
>>>> public int getStartingTime() {
>>>> int startingTime = 0;
>>>> TaskOrPerson taskOrPerson = getPreviousTaskOrPerson();
>>>> while (taskOrPerson instanceof Task) { // Every chain is
>>>> guarantee to end up with an anchor (= Person)
>>>> startingTime += ((Task) taskOrPerson).getDuration();
>>>> taskOrPerson = ((Task)
>>>> taskOrPerson).getPreviousTaskOrPerson()
>>>> }
>>>> return startingTime;
>>>> }
>>>>
>>>> }
>>>>
>>>> class Person implements TaskOrPerson {
>>>>
>>>> }
>>>>
>>>> For a good example, take a look at the VehicleRouting example.
>>>> For more info about chaining, in the manual see section 4.3.4.2.6.
>>>> Chained
>>>>
>>>>
http://docs.jboss.org/drools/release/5.4.0.Final/drools-planner-docs/html...
>>>>
>>>> Op 22-07-12 18 <22-07-12%2018>:00, Josef Bajada schreef:
>>>>
>>>> Hi,
>>>>
>>>> I am new to Drools and Drools Planner, so apologies if I am asking
>>>> anything obvious.
>>>>
>>>> My objective is to implement a simple (for now) planner which
>>>> schedules tasks according to 2 main criteria:
>>>> - Their duration (in seconds)
>>>> - Their dependencies on other tasks (e.g. Hard Constraint that Task B
>>>> has to start between 180 and 200 seconds after Task A finishes).
>>>>
>>>> Since there are gaps between dependent tasks as part of the hard
>>>> constraints other tasks can be fitted in between dependent tasks.
>>>> So the Solver needs to find the optimal start time for each task that
>>>> satisfies the hard constraints, and in the shortest total timeline
possible
>>>> to complete all tasks (soft constraint).
>>>>
>>>> The main problem I am finding is that this start time, which is
>>>> essentially the planning variable is a continuous variable.
>>>> Chapter 4 of the Drools documentation mentions very briefly (Section
>>>> 4.3.4.1) that planning variables can be continuous, but there does not
>>>> seem to be any more details about how to achieve this.
>>>>
>>>> Even if the planning variable was discrete (say bins of 5 second
>>>> intervals), there is no upper bound as such.
>>>>
>>>> How is it best to handle such planning variables in Drools Planner?
>>>>
>>>> thanks,
>>>> josef
>>>>
>>>>
>>>>
>>>>
>>>> _______________________________________________
>>>> rules-users mailing
listrules-users@lists.jboss.orghttps://lists.jboss.org/mailman/listinfo/rules-users
>>>>
>>>>
>>>> --
>>>> With kind regards,
>>>> Geoffrey De Smet
>>>>
>>>>
>>>> _______________________________________________
>>>> rules-users mailing list
>>>> rules-users(a)lists.jboss.org
>>>> https://lists.jboss.org/mailman/listinfo/rules-users
>>>>
>>>>
>>>
>>>
>>> _______________________________________________
>>> rules-users mailing
listrules-users@lists.jboss.orghttps://lists.jboss.org/mailman/listinfo/rules-users
>>>
>>>
>>> --
>>> With kind regards,
>>> Geoffrey De Smet
>>>
>>>
>>> _______________________________________________
>>> rules-users mailing list
>>> rules-users(a)lists.jboss.org
>>> https://lists.jboss.org/mailman/listinfo/rules-users
>>>
>>>
>>
>>
>> _______________________________________________
>> rules-users mailing
listrules-users@lists.jboss.orghttps://lists.jboss.org/mailman/listinfo/rules-users
>>
>>
>> --
>> With kind regards,
>> Geoffrey De Smet
>>
>>
>> _______________________________________________
>> rules-users mailing list
>> rules-users(a)lists.jboss.org
>> https://lists.jboss.org/mailman/listinfo/rules-users
>>
>>
>
>
> _______________________________________________
> rules-users mailing
listrules-users@lists.jboss.orghttps://lists.jboss.org/mailman/listinfo/rules-users
>
>
> --
> With kind regards,
> Geoffrey De Smet
>
>
> _______________________________________________
> rules-users mailing list
> rules-users(a)lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/rules-users
>
>
_______________________________________________
rules-users mailing
listrules-users@lists.jboss.orghttps://lists.jboss.org/mailman/listinfo/rules-users
_______________________________________________
rules-users mailing list
rules-users(a)lists.jboss.org
https://lists.jboss.org/mailman/listinfo/rules-users
4459
days inactive
4510
days old
10 comments
2 participants
participants (2)
-
Geoffrey De Smet -
Josef Bajada