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.s...@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_single/index.html#incrementalScoreCalculation > > 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.s...@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.s...@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.s...@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_single/index.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@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@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@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@lists.jboss.org > https://lists.jboss.org/mailman/listinfo/rules-users > >
_______________________________________________ rules-users mailing list rules-users@lists.jboss.org https://lists.jboss.org/mailman/listinfo/rules-users