automatic allocate only one resource

[Jack01]

Hi,

I have a resource team of e.g. three people

resources team1 "Team1" {
resource ps1 "Person 1"
resource ps2 "Person 2"
resource ps3 "Person 3"
}

then I have some tasks where I want to use the resources without
choosing them manually

task1 {
...
effort 10d
allocate ps1 { alternative ps2,ps3 }
}

task2 {
...
effort 10d
allocate ps1 { alternative ps2,ps3 }
}

These tasks should be done by only Person for the whole task. e.g.
task1 = ps1 and task2 = ps2
TJ sorts to a task sometimes more then one resource, that's what I
want to avoid. On the other hand TJ longens the duration by using the
same resource for both tasks in parallel.
What is the easiest way to solve my problem?

kind regards
Jack01

[Tim Heil]

Hi Jack,

Jack01 schrieb:

> TJ sorts to a task sometimes more then one resource, that's what I
> want to avoid. On the other hand TJ longens the duration by using the
> same resource for both tasks in parallel.
> What is the easiest way to solve my problem?

task1 {

effort 10d
allocate ps1 {
alternative ps2, ps3

persistent
}
}

should do the trick.

Best regards,

Tim

[Jack01]

Hi Tim,

>
> task1 {
>   effort 10d
>   allocate ps1 {
>     alternative ps2, ps3
>     persistent
>  }
>
> }

thanks for the answer. I allready tried the persistent attribute. If I
use it the same resource (e.g. ps1) is used for both tasks. This
longens the duration of the tasks instead of doing both tasks by one
resource for each task in parallel!?

kind regards
Jack

[Chris Schlaeger]

Hi Jack,

> thanks for the answer. I allready tried the persistent attribute. If I
> use it the same resource (e.g. ps1) is used for both tasks. This
> longens the duration of the tasks instead of doing both tasks by one
> resource for each task in parallel!?

the only case where this can happen is when a higher priority task
pre-empts a lower priority task. Can you post an example, please.

Chris

[Jack01]

Hi Chris,

> the only case where this can happen is when a higher priority task
> pre-empts a lower priority task. Can you post an example, please.

I tried to reproduce the problem with a simple project plan but I
didn't work. My project consists of some files and macros. I will try
reproduce it hopefully it works. In my plan I don't use the priority
attribute - so it should be the default value. If I set different
priorities for the tasks the problem is solved, too. I want to make a
long term planning and so I don't want to use different priorities in
advance.
For me the automatic schedule isn't comprehensible to use the same
resource instead of using different ones.
I will still try to reproduce it with a simple example to give it to
you.

Jack

[Francis Provencher]

Hi guys,

On Thursday, October 22, 2009 4:51:38 AM UTC-4, Jack01 wrote:

> the only case where this can happen is when a higher priority task
> pre-empts a lower priority task. Can you post an example, please.

If I set different priorities for the tasks the problem is solved, too.

We got the same problem here with the version 3.3.0.

Attached is an example of the problem. I tried to simplify the case as much as possible. Like Jack01, if we set priority the problem disappear (see the project file, I put a comment in it), but with many tasks, it gets really complicated and manual to make sure all the resources are used to the fullest.

In this case, you can clearly see the bug by opening the produced Work by task.html: the mechanic 2 is never assigned to the task and the entire project takes longer due to that.

Cheers,

Francis

[Chris Schlaeger]

On Thu, Aug 2, 2012 at 11:25 PM, Francis Provencher <fran...@gmail.com> wrote:

In this case, you can clearly see the bug by opening the produced Work by task.html: the mechanic 2 is never assigned to the task and the entire project takes longer due to that.

The resource gets the 4h assigned as you can see by the 0.5d effort value. There is just no load bar since it is smaller than 1 pixel. Switching to 'day' scale will show the bar properly.

I've just made a fix that ensures that the bar is at least 1 pixel width.

Chris

[Ash]

Hi Chris,

I have the same problem than Francis here. His example show it pretty clearly if you look at the Work by Task page.

Mechanic01 get the Frame.Base task assigned but the scheduler, and as soon as the Frame.Motor task becomes

available it is assigned to Mechanic01. What i would expect is to see Mechanic01 finish with the current task and

get Frame.Motor assigned to Mechanic02. If you look at the Resource Graph page, Mechanic02 gets absolutely no

task assigned.

I got the same problem in a pretty large project. Everything seems to work like i expect when there is dependencies,

but as soon as some predecessor task for a particular task is finished, this task gets assigned by the scheduler right

away if a resource has already another task assigned and other resources are available.

Thanks !

Ash

[Ash]

Hello again,

Sorry i meant everything seems the work like i expect when there is no dependencies, but as soon as i start to put

some, then what is described below happens.

Thanks !

Ash

[Chris Schlaeger]

On Sun, Aug 5, 2012 at 5:32 PM, Ash <ashm...@gmail.com> wrote:

Hello again,

Sorry i meant everything seems the work like i expect when there is no dependencies, but as soon as i start to put

some, then what is described below happens.

Thanks !

Ash

On Sunday, August 5, 2012 8:26:55 AM UTC-7, Ash wrote:

Hi Chris,

I have the same problem than Francis here. His example show it pretty clearly if you look at the Work by Task page.

Mechanic01 get the Frame.Base task assigned but the scheduler, and as soon as the Frame.Motor task becomes

available it is assigned to Mechanic01. What i would expect is to see Mechanic01 finish with the current task and

get Frame.Motor assigned to Mechanic02. If you look at the Resource Graph page, Mechanic02 gets absolutely no

task assigned.

I got the same problem in a pretty large project. Everything seems to work like i expect when there is dependencies,

but as soon as some predecessor task for a particular task is finished, this task gets assigned by the scheduler right

away if a resource has already another task assigned and other resources are available.

Ok, I see the problem now. It's due to the heavy use of 'persistent' and the fact that  primary_task.car.g_frame.motor has a higher pathcriticalness. Let me see if I can add some special handling for this corner case.

Chris

[Ash]

Thanks !

Cheers,

Ash

[Ash]

Hi Chris,

I think i understand what you meant by "pathcriticalness" but i have to say i fail to see how

this represent a corner case. Intuitively i would expect that as soon as a resource is assigned

to a task, it will have to end it before being assigned to another one. I guess what you mean is

that it is true unless some other task has a bigger impact on the completion date for the

project ? Which might be true unless there is another resource available to work on this more

critical task.

I have a 1200 tasks project that i'd like to schedule using the alternative keyword for the

resources and be able to play with the size of the teams and see what the impact would be if

i add one more member or get rid of one. Without any priority there is a lot of cases where a

resource working on a task is re-assigned to some other task before coming back to the first one.

Resulting in a much later completion date than i would expect. Maybe you could walk me quickly

through the scheduler logic, i might have completely misunderstood something ?

Let me add one more quick question. Is there a way to assign a couple of task to the same

resource using the "alternative" keyword ? Like for example a task containing 2 sub-tasks would

be assigned to the same resource even when the "alternative" keyword is used ? I am not sure

that i actually want to do that, but i figured that i was worst the question.

Thanks a lot for you help !

Cheers,

Ash

[John C.]

Hi Chris,

I don't really see how the notion of pathcriticalness effects scheduling.  In fact, it seems to me that you can't determine the critical path until after the scheduler is done unless the scheduler does a pass at the project prior to resource allocation and only does allocation as a post scheduling process.  That second scheme seems a bit illogical to me, although I can see how it would be considerably faster.

As I understood the allocation and scheduling logic in TaskJuggler, allocation and scheduling should happen together, e.g., the scheduler should not schedule a task unless there are sufficient resources to allocate to it.  The "priority" keyword should help during resource allocation by defining which tasks are more important as far as the arbitration process is concerned.  The "persistent" keyword should have an effect on allocation.  Everything that has an effect on allocation can have an effect on scheduling and scheduling certainly has an effect on the way resources are allocated.

It occurs to me that the critical path should be calculated only after the project has been successfully scheduled and should have no effect on the scheduling or allocation processes.

Now, looking at the examples in this thread, it is obvious to me that I am misunderstanding something critical about the way allocation and scheduling work in TaskJuggler, something that isn't expressed in the documentation, at least not in a way I can understand it.

We are telling you that the tool doesn't work as we expect, which means that we will not be able to use it effectively.  I suggest that it would help if you could give us a brief idea of how the allocation and scheduling process work so we can use this amazing tool better.

All the best,

John

[Chris Schlaeger]

On Sun, Aug 12, 2012 at 8:54 PM, John C. <jo...@carey.org> wrote:

We are telling you that the tool doesn't work as we expect, which means that we will not be able to use it effectively.  I suggest that it would help if you could give us a brief idea of how the allocation and scheduling process work so we can use this amazing tool better.

I think this is pretty well described in the manual:

http://www.taskjuggler.org/tj3/manual/TaskJuggler_Internals.html#How_the_Scheduler_works

If not, there's always the source. ;)

Chris

[Chris Schlaeger]

On Sun, Aug 12, 2012 at 3:33 AM, Ash <ashm...@gmail.com> wrote:

Let me add one more quick question. Is there a way to assign a couple of task to the same

resource using the "alternative" keyword ? Like for example a task containing 2 sub-tasks would

be assigned to the same resource even when the "alternative" keyword is used ? I am not sure

that i actually want to do that, but i figured that i was worst the question.

No, there is no way to ensure that a resource that was selected for one task is also used for another task. That would be even more complicated to get right.

However, I've just committed a fix to improve the heuristic that selects the persistent resource from an alternative list. It will avoid picking a resource for a task that starts earlier than a higher priority (or more critical) task. Please check the latest version from the git repository or the daily built tomorrow.

Chris

[Francis Provencher]

Hi Chris,

On Sunday, August 5, 2012 3:16:27 PM UTC-4, Chris Schlaeger wrote:

Ok, I see the problem now. It's due to the heavy use of 'persistent'

 Quick question: what would have been to correct or better way to do that?

Also, is there a way to assign tasks to a team (without sharing the task between multiple people) without using macros?

Thanks

Francis

[Ash]

Hi Chris,

Thanks for the quick turnover !

It does seem to fix the case that was described in Francis example. Though it still have the same problem

with my current project. Let's say that i have 3 days task, then what happens is that a resource is assigned

to it for 0.5d and then re-assigned to a bunch of other tasks, and finally comeback to the original one 8 weeks

after. I guess there is still something that i don't understand, even after having read the scheduler documentation.

I guess i don't expect that the default behavior would to allow to re-assign a resource before the current task is

completed. Let me see if can send you an example.

Thanks !

Ash

[Ash]

Hello Chris,

Here is a project where this task re-assigment happens. Sorry for the gibberish but i had

to rename the tasks and teams. In any case if you look at the LLL Team in the Resource

Graph page, The resource LLL 01 starts to work on task called BC_050_055 LLL for 0.5d

and then is re-assigned to bunch of other task until 8 weeks later it is finally re-assigned

to this task for 1.5d to finish with it. It happens a lot along the whole project, sometimes it

is less obvious. Still on the Resource Page, LLL 01 is assigned to a task called HC_037_015 LLL,

that is supposed to last for days but is spread on 3 weeks : 0.5d + 1.0d + 0.5d.

Is there something wrong with the project structure ? Or do you think i am hitting another

corner case ?

Thanks a lot !

Cheers,

Ash

[John C.]

Hi Chris,

First of all, I think that it is great that you as the developer of the tool participates in this forum so actively and the documentation is very good, but even so, there are some things that I don't understand.

I have read the documentation and I just read it again to be sure I didn't miss something.  It is a good general explanation of how the scheduler works but it doesn't explain why the combination of the "persistent" keyword and the calculated path criticalness combine to create a behavior that you describe as a "corner case".

I suppose that there are some aspects of TaskJuggler concept of criticalness (path, resource and milestone) that are a bit counter intuitive to me.  For instance, how can a milestone every be on the critical path since it has by definition no resource allocation and no duration.  How can an event like that ever effect the duration of the project in any way other than through dependency relationships?

I am a long time TaskJuggler user and don't think that this is the way TaskJuggler 2.X worked, although I haven't tested that hypothesis.  The point is that I have been using the persistent keyword to insure that once a resource is assigned to a task, that the resource stays assigned to that task rather than having another resource assigned based on resource balancing efficiency.

It seems that in Francis' case above, that there is something wrong with the allocation and scheduling algorithm because it creates a schedule that doesn't effectively allocate the available resources in the most efficient way within the constraints of the task description, in this case using the persistent keyword for every task.  I suppose that it depends of course  on what you mean by efficient.  In the case of the way tj3 schedules the project, it is efficient in the sense that it uses the fewest possible resources but the project takes longer.

I am attaching a simple edit of Francis' project where I explicitly allocate the "Mechanic" resources in what I consider to be a more efficient way, using the word efficient to mean the shortest schedule and the best use of the available resources.

In short, in Francis' case, TaskJuggler doesn't seem to work as I would expect given my reading of the documentation.

I'll take a look at the code as you suggest.

Thanks,

John

[Chris Schlaeger]

On Tue, Aug 14, 2012 at 4:03 AM, Ash <ashm...@gmail.com> wrote:

Here is a project where this task re-assigment happens. Sorry for the gibberish but i had

to rename the tasks and teams. In any case if you look at the LLL Team in the Resource

Graph page, The resource LLL 01 starts to work on task called BC_050_055 LLL for 0.5d

and then is re-assigned to bunch of other task until 8 weeks later it is finally re-assigned

to this task for 1.5d to finish with it. It happens a lot along the whole project, sometimes it

is less obvious. Still on the Resource Page, LLL 01 is assigned to a task called HC_037_015 LLL,

that is supposed to last for days but is spread on 3 weeks : 0.5d + 1.0d + 0.5d.

Is there something wrong with the project structure ? Or do you think i am hitting another

corner case ?

Thanks a lot for this test case! It made it clear that my initial implementation for improved allocation of 'persistent' resources was way too performance heavy. I've now implemented a much more light weight version. It is probably not exactly as good as the previous version but about 50x faster.

Probably, the new version also does not address all the issues in your project. The scheduler tries to minimize the overall project duration. There is no guarantee that it actually succeeds, since we are not doing an exhaustive search of the solution space. The heuristic just tries to make smart decisions. The more constraint the project is, the more likely it will not find the optimal case. Using many 'persistent' allocations with small alternative lists is such a heavy constraint. If used heavily or exclusively like in your project, interrupted tasks are inevitable. The only workaround would be to delay task starts until resources become available again. This would result in even more idle resources.

Your project has a lot of very similar tasks groups that all compete for the same set of resources. Your resources are so heavily competed for that their availability largely drives the schedule. To mitigate the artifacts you are seeing, I would recommend to at least prioritize your top-level tasks somewhat. If you look at the pathcritical values of the tasks that use LLL or VVV resources, they are all the same. That removes any chance of the heuristic to make some educated guesses which tasks are more important than others.

Chris

 

[Chris Schlaeger]

On Tue, Aug 14, 2012 at 7:06 PM, John C. <jo...@carey.org> wrote:

I have read the documentation and I just read it again to be sure I didn't miss something.  It is a good general explanation of how the scheduler works but it doesn't explain why the combination of the "persistent" keyword and the calculated path criticalness combine to create a behavior that you describe as a "corner case".

The persistent keyword has the effect that once a resource is picked from a set of alternatives, the tasks will only make progress if that resource is available. That makes it a lot harder pick that resource. Before my last patch, only the resource criticalness was used to select the resource. That's a static value and is the same for all resources if the set of alternatives is used for all the same tasks. Now I first look for the resource that has the least allocated time slots to higher priority or more pathcritical tasks. That increases the chances that a lower priority task picks a resource that will be unavailable for some time during the duration of the task.
 

I suppose that there are some aspects of TaskJuggler concept of criticalness (path, resource and milestone) that are a bit counter intuitive to me.  For instance, how can a milestone every be on the critical path since it has by definition no resource allocation and no duration.  How can an event like that ever effect the duration of the project in any way other than through dependency relationships?

Milestones were added to the pathcriticalness after user complaints. In case some tasks chains had the same patchcriticalness. Some users felt that those with milestones should be ranked higher since milestones should add some importance to the tasks leading to them. That does make some sense, but the actual weight was arbitrarily picked.

I am a long time TaskJuggler user and don't think that this is the way TaskJuggler 2.X worked, although I haven't tested that hypothesis.  The point is that I have been using the persistent keyword to insure that once a resource is assigned to a task, that the resource stays assigned to that task rather than having another resource assigned based on resource balancing efficiency.

The scheduling algorithm hasn't actually changed much over the last 10 years. Some aspects were improved, but I don't think the handling of persistent resources was any better than the current solution as of this week.
 

It seems that in Francis' case above, that there is something wrong with the allocation and scheduling algorithm because it creates a schedule that doesn't effectively allocate the available resources in the most efficient way within the constraints of the task description, in this case using the persistent keyword for every task.  I suppose that it depends of course  on what you mean by efficient.  In the case of the way tj3 schedules the project, it is efficient in the sense that it uses the fewest possible resources but the project takes longer.

The scheduling algorithm is based on a heuristic. It's not even trying to scan the gigantic solution space for the best solution. It should work well for the most common projects. If not, we can look at it on a case by case base and try to tweak the heuristic somewhat. But it will never schedule all kind of weird projects (corner cases) in an optimal way. Such an algorithm would take orders of magnitude more time.
 

I am attaching a simple edit of Francis' project where I explicitly allocate the "Mechanic" resources in what I consider to be a more efficient way, using the word efficient to mean the shortest schedule and the best use of the available resources.

In short, in Francis' case, TaskJuggler doesn't seem to work as I would expect given my reading of the documentation.

Francis' problem was already fixed by the recent changes. It also improves Ash's project, but it also shows the limitations of the heuristic.

Chris

[John C.]

Hello Chris,

Thanks again for your patience and your very thorough answer.  I feel that I understand the scheduling process considerably better now and that I will be able to use TaskJuggler more effectively as a result of it.

For what it is worth, I recognize that the scheduling and allocation process is a combinatorial optimization problem, very similar to the minimum spanning tree and probably NP-complete.  I just wanted to know a little more about the mechanics of your heuristic and it seemed simpler to ask you than to try to infer that from the code.

I intend to look at the code anyway, but your explanation will definitely make my exploration considerably simpler and I suspect that it will help other users on the list as well, especially those with non-trivial projects whose scheduling dynamics results in one of those corner cases you have identified.

Thanks,

John

[Francis Provencher]

Hi Chris,

On Tuesday, August 14, 2012 3:05:35 PM UTC-4, Chris Schlaeger wrote:

Your project has a lot of very similar tasks groups that all compete for the same set of resources. Your resources are so heavily competed for that their availability largely drives the schedule. To mitigate the artifacts you are seeing, I would recommend to at least prioritize your top-level tasks somewhat. If you look at the pathcritical values of the tasks that use LLL or VVV resources, they are all the same. That removes any chance of the heuristic to make some educated guesses which tasks are more important than others.

Would it make sense to add a metric to a task that would be set during scheduling to the amount of work done on the task up to now? This way when we have multiple task with similar base priority the system could prioritize tasks that have the biggest amount of work done on them up to now.

What do you think?

Francis

[Ash]

Hi Chris,

Thanks a lot for you very thorough answer !

I am glad that you liked my little project. I can definitely gives you more of those if it is of any interest to you.

This one is a rather small one.

Though, i have the same experience as John with with regards to TaskJuggler 2.x I've been using it to do the

exact same thing on the same kind of project and that's definitely the first time that i have this split task issue.

Unfortunately i could not verify that, as i don't have TaskJuggler 2 installed anymore.

Cheers,

Ash

[Chris Schlaeger]

On Wed, Aug 15, 2012 at 2:04 PM, John C. <jo...@carey.org> wrote:

Thanks again for your patience and your very thorough answer.  I feel that I understand the scheduling process considerably better now and that I will be able to use TaskJuggler more effectively as a result of it.

Since there are a number of folks interested in the details of the TaskJuggler scheduler, I've updated the description in the manual with many more details:

http://www.taskjuggler.org/tj3/manual/TaskJuggler_Internals.html#How_the_Scheduler_works

Chris

[Ash]

Hi Chris,

I've just tried the last night build, after i saw that you added some warning about stolen tasks. My use case definitely

activate those warnings, though the text invoke some mix between ALAP and ASAP mode and my tasks are all using

the ASAP mode, so i guess there is more than one way to trigger those warnings.

In any case, i still trying to find the best solution for my problem. As i use other scripts to create Taskjuggler includes

files, i added some random priority number on the main tasks, as you suggested. It is not a very satisfying solution but

it helped plan for few projects. But as soon as several resources are competing for a task and several tasks are available

the problem arises again. Actually it does not really need to be that much, it seems that 2 tasks with the same priority are

enough to create this "allocation split". Putting priorities on every tasks would just mean to do the schedule by hand.

On top of that, it seems that in some cases, even priorities cannot influence the result. I've attached another example with

that message. It is a smaller project and the split happens on a couple of tasks (for example : ITEM_03 Task_12). In that

In that case the priority is 999 and higher than any other tasks, but it still is stolen by an another task and only finished weeks

after it has been started. It you have a look at the Work by Tasks page, you'll see a couple of tasks that are splitter, even so

their priority is bigger than any other task.

Cheers,

Ash

[Chris Schlaeger]

Hi Ash,

On Fri, Aug 24, 2012 at 10:24 PM, Ash <ashm...@gmail.com> wrote:
>
> Hi Chris,
>
> I've just tried the last night build, after i saw that you added some warning about stolen tasks. My use case definitely
> activate those warnings, though the text invoke some mix between ALAP and ASAP mode and my tasks are all using
> the ASAP mode, so i guess there is more than one way to trigger those warnings.

this is excellent feedback! And you are right, there are other ways to
trigger a priority inversion that I hadn't though of in that message.
I've fixed that now.

>
> In any case, i still trying to find the best solution for my problem. As i use other scripts to create Taskjuggler includes
> files, i added some random priority number on the main tasks, as you suggested. It is not a very satisfying solution but
> it helped plan for few projects. But as soon as several resources are competing for a task and several tasks are available
> the problem arises again. Actually it does not really need to be that much, it seems that 2 tasks with the same priority are
> enough to create this "allocation split". Putting priorities on every tasks would just mean to do the schedule by hand.
>
> On top of that, it seems that in some cases, even priorities cannot influence the result. I've attached another example with
> that message. It is a smaller project and the split happens on a couple of tasks (for example : ITEM_03 Task_12). In that
> In that case the priority is 999 and higher than any other tasks, but it still is stolen by an another task and only finished weeks
> after it has been started. It you have a look at the Work by Tasks page, you'll see a couple of tasks that are splitter, even so
> their priority is bigger than any other task.

The task with 999 priority depends on
project_01.item_03.task_01.task_01 with only priority 398. That seems
to be a logical error in the project description.

You have many extremely similar groups of tasks that compete for the
same small resource pools. Try using the 'competitors' columns to see
how bad the problem is. In some cases, there are more than 100 tasks
competing for the same resource. It's just a _very_ hard problem for
any scheduler to find a good scheduling solution for such a project.

Chris

[Ash]

Hi Chris,

Thanks for the quick turnover !

I do understand the difficulty of the scheduling problem, and obviously i do not expect that Taskjuggler

will come up with the most efficient solution, but a reasonable one. Reasonable is very vague term and i

guess anybody could argue that any solution for a given project is reasonable from a certain point of view

(and i did not even tried to quote Obi-Wan Kenobi here ...). If i had to do the scheduling work by hand, i

would probably come up with one of those reasonable solution, but most likely not the most efficient. What

makes Taskjuggler so close to be absolutely awesome, is that it is able to give me one of those solution in

a matter of seconds, so when i wrote my project file i can play with different staffing models and see what

would be the absolute minimum number of resource i need for project using the "maxloaded" parameter or

where to add a team member to have the biggest impact on the completion date.

I have not looked at the code closely but i think the only additional thing that i would expect is that as soon

as a task has been started or some work has been allocated, that it would weigh more than any other task

available for the next time slot. So, whatever the "pathcriticalness" value or the arbitrary priority it would still

be completed by the resource, before being assigned to any other task. I guess you could argue that priority

should supersede that weight, so to make it flexible it should probably be some parameter to add to a task to

make it uninterruptible. As, it seems that what creates the "split task" is several competing tasks asking for

a small pool of resources and that their priority and "pathcriticalness" is the same, it should not impact the

completion date for the project and we would still get a reasonable solution. In fact, when i got through the

tedious process of adding priority to tasks to avoid this split problem, the completion date for the project never

changed.

Cheers,

Ash

[John C.]

Hi Ash, Jack, Francis, and Chris,

I would suggest that one potential solution to this problem is to establish another keyword that would allow a single resource to be applied to a task just as persistent does now, but would also prevent the assigned resource from being allocated to any other task, regardless of priority or taskcriticalness until the task to which that resource is allocated is completed.

The "persistent" keyword allows for persistent, but not exclusive allocation.  Exclusive allocation is the behavior that a number of us are trying to model with TaskJuggler and we keep running afoul of the scheduling and allocation heuristic.  I would suggest that no matter what work around we try, given the way the heuristic works that we are very likely going to continue to keep encountering what you are calling "corner cases".  In addition, all of the suggested work arounds can be as much effort as scheduling the project manually.

Might I nominate "exclusive" as a new keyword?  Once a resource is allocated to a task with the new keyword, the resource will be persistently allocated and in addition, it is not available for any other resource arbitration until it is the task to which it is exclusively allocated is completed again.  I would think that removing resources from arbitration upon "exclusive" assignment in addition to allowing us to model this use case gracefully would have the added benefit of increasing the speed of the scheduling and allocation process.

For what it is worth, I don't consider this to be in any way an extraordinary case.  I think that this is a rather common project management resource allocation model and one that TaskJuggler should support explicitly.

All the best,

John

[Chris Schlaeger]

On Wed, Aug 29, 2012 at 1:58 PM, John C. <jo...@carey.org> wrote:
> Might I nominate "exclusive" as a new keyword? Once a resource is allocated
> to a task with the new keyword, the resource will be persistently allocated
> and in addition, it is not available for any other resource arbitration
> until it is the task to which it is exclusively allocated is completed
> again. I would think that removing resources from arbitration upon
> "exclusive" assignment in addition to allowing us to model this use case
> gracefully would have the added benefit of increasing the speed of the
> scheduling and allocation process.
>
> For what it is worth, I don't consider this to be in any way an
> extraordinary case. I think that this is a rather common project management
> resource allocation model and one that TaskJuggler should support
> explicitly.

I agree that it can be desirable to have a resource working on a task
without interrupts. I do not agree that a lower priority task should
steal resources from a higher priority task just because the lower
priority task started earlier and got the resource first. Instead, the
scheduler should try to find an interval that fits the task without a
higher priority task competing for the same resource. Naturally, this
can result in longer overall project durations.

Unfortunately, this isn't trivial to implement. The scheduler can
neither look forward to find such an interval, nor can it roll back
allocations it has already made. Fortunately, the amount of state that
would need to be rolled back in case the scheduler detects that it
cannot assign the resource atomically, is not that big. I'll see if I
can implement something.

Chris

[Francis Provencher]

Hi Chris,

If we look at the two following statements:

On Thursday, September 6, 2012 2:30:25 PM UTC-4, Chris Schlaeger wrote:

I agree that it can be desirable to have a resource working on a task
without interrupts. 

 

I do not agree that a lower priority task should
steal resources from a higher priority task just because the lower
priority task started earlier and got the resource first.

I think we all agree that it is not the desired default behavior.

But it would be the desired behavior for tasks with the "exclusive" keyword that John suggested.

Do  you think that would be a difficult thing to add?

Francis

[John C.]

Hello Chris,

Thanks again for your thoughtful response.

Unfortunately, this isn't trivial to implement. The scheduler can
neither look forward to find such an interval, nor can it roll back
allocations it has already made. Fortunately, the amount of state that
would need to be rolled back in case the scheduler detects that it
cannot assign the resource atomically, is not that big. I'll see if I
can implement something. 

 It occurs to me that this might be handled by not letting the scheduler "see" resources that are allocated using the "exclusive" attribute until the task to which they are assigned are completed.  This seems to me would provide exactly the behavior we are seeking and at the same time, wouldn't require any change to the scheduler, only the way resources are presented to it when the scheduler is trying to arbitrate between tasks and resources.

In looking briefly at the source, as you suggested I do, I can see that this would require some modification of Allocate.rb, Attributes.rb, TaskScenario.rb and  TjpSyntaxRules.rb, and while I am not suggesting that it would be trivial, it seems to me that the question at hand isn't about modifying the scheduler per se, but the allocation list and resource attributes which seems a bit simpler than actually trying to get the scheduler to look ahead or look back.

Of course, you are the expert.  This is just now it look to me after a very brief look at the code.

All the best,

John

[Chris Schlaeger]

On Sat, Sep 8, 2012 at 11:53 PM, John C. <jo...@carey.org> wrote:
> It occurs to me that this might be handled by not letting the scheduler
> "see" resources that are allocated using the "exclusive" attribute until the
> task to which they are assigned are completed. This seems to me would
> provide exactly the behavior we are seeking and at the same time, wouldn't
> require any change to the scheduler, only the way resources are presented to
> it when the scheduler is trying to arbitrate between tasks and resources.

But this would lead to the priority being ignored. I don't think this
is acceptable behavior as it would introduce a serious inconsistency.

> In looking briefly at the source, as you suggested I do, I can see that this
> would require some modification of Allocate.rb, Attributes.rb,
> TaskScenario.rb and TjpSyntaxRules.rb, and while I am not suggesting that
> it would be trivial, it seems to me that the question at hand isn't about
> modifying the scheduler per se, but the allocation list and resource
> attributes which seems a bit simpler than actually trying to get the
> scheduler to look ahead or look back.
>
> Of course, you are the expert. This is just now it look to me after a very
> brief look at the code.

I have made several attempts but they all have serious complexity
issues. I'm now working on a partial roll-back support so I can retry
tasks to start at a later date should the persistent resource be
assigned to another task already. But I'm still not sure if it's a
workable solution.

Chris

[John C.]

Hi Chris,

On Thursday, September 20, 2012 11:35:20 AM UTC-7, Chris Schlaeger wrote:

On Sat, Sep 8, 2012 at 11:53 PM, John C. <jo...@carey.org> wrote:
>  It occurs to me that this might be handled by not letting the scheduler
> "see" resources that are allocated using the "exclusive" attribute until the
> task to which they are assigned are completed.  This seems to me would
> provide exactly the behavior we are seeking and at the same time, wouldn't
> require any change to the scheduler, only the way resources are presented to
> it when the scheduler is trying to arbitrate between tasks and resources.

But this would lead to the priority being ignored. I don't think this
is acceptable behavior as it would introduce a serious inconsistency.

In the use case that some of us are hoping to be able to model with TaskJuggler, I think that what you are describing as a "serious inconsistency" may well be the desired behavior, more or less.  Just to clarify, we don't want to ignore priority with regard to the initial assignment, but once a resource is assigned to a task, we would like that resource to stay assigned to that task regardless of priority.  In other words, in some cases, we don't want either priority or "criticalness" to be able to preempt an existing assignment in those cases that we so designate.  We would like a resource that is assigned to a task with the new "exclusive" attribute to always win the priority and "criticalness" contention for that task or we would like a resource, once assigned exclusively to be removed from the resources list until such time as the task to which it is exclusively allocated has completed.

What is the inconsistency that would be introduced by that behavior?  I am curious because a number of us seem to think that the current behavior is inconsistent, at least with regard to our intent.

 

I have made several attempts but they all have serious complexity
issues. I'm now working on a partial roll-back support so I can retry
tasks to start at a later date should the persistent resource be
assigned to another task already. But I'm still not sure if it's a
workable solution.

Well, you are the expert of course, but it seems to me that the roll-back solution is all but guaranteed to have undesirable regression effects and will represent a serious loss in efficiency due to the complexity effects you note above and in addition, in my opinion, it will be considerably more difficult to implement.

Good luck in any case with this.  I am and I suspect that a lot of us are very grateful that you are so responsive to the needs/desires of the TaskJuggler user community.

All the best,

John

[Chris Schlaeger]

On Fri, Sep 21, 2012 at 5:53 PM, John C. <jo...@carey.org> wrote:

In the use case that some of us are hoping to be able to model with TaskJuggler, I think that what you are describing as a "serious inconsistency" may well be the desired behavior, more or less.  Just to clarify, we don't want to ignore priority with regard to the initial assignment, but once a resource is assigned to a task, we would like that resource to stay assigned to that task regardless of priority.  In other words, in some cases, we don't want either priority or "criticalness" to be able to preempt an existing assignment in those cases that we so designate.  We would like a resource that is assigned to a task with the new "exclusive" attribute to always win the priority and "criticalness" contention for that task or we would like a resource, once assigned exclusively to be removed from the resources list until such time as the task to which it is exclusively allocated has completed.

What is the inconsistency that would be introduced by that behavior?  I am curious because a number of us seem to think that the current behavior is inconsistent, at least with regard to our intent.

Task priorities are a very important mechanism to influence the resource assignments. 'priority' always overrules the heuristic. If a higher priority task does not get the resource because a lower priority task keeps hugging them than this would be inconsistent behavior.

BTW, resources are assigned to tasks from priority 1000 down to 1. So the higher priority task usually has the resources already assigned before the scheduler even notices that a lower priority task wants to keep their resource no matter what. The challenge comes when multiple alternative resources have been given. Finding the right one that will be available without interrupts is currently not possible.

Chris

[John C.]

Hi Chris,

Thanks for the explanation.  It is a little disappointing, but understandable.  That being said, I do have some notes on the idea of inconsistency.

On Sunday, November 11, 2012 12:01:52 PM UTC-8, Chris Schlaeger wrote:

Task priorities are a very important mechanism to influence the resource assignments. 'priority' always overrules the heuristic. If a higher priority task does not get the resource because a lower priority task keeps hugging them than this would be inconsistent behavior.

BTW, resources are assigned to tasks from priority 1000 down to 1. So the higher priority task usually has the resources already assigned before the scheduler even notices that a lower priority task wants to keep their resource no matter what. The challenge comes when multiple alternative resources have been given. Finding the right one that will be available without interrupts is currently not possible.

Chris

The application of resources to tasks is essentially a load balancing problem.  There are typically two modalities associated with load balancing, that is preemptive and non-preemptive, the use case defining which is the better approach.

Two common implementations of load balancing are found in the Linux kernel itself and in batch queuing systems like Sun Grid Engine, Condor, LSF, Moab, Portable Batch System, etc.  All load balancing implementations with which I am familiar have those two modalities, excluding TaskJuggler of course, which is always preemptive.

The Linux kernel is often called preemptive and in most cases it is, but it is non-preemptive when executing critical components, like kernel code and critical services.  Some of those services won't be interrupted and even higher priority tasks have to wait.  In the Linux kernel, this all happens automatically during execution but you can tune it during kernel builds for instance if you have a particular requirement or use case.

In the case of batch queuing systems, there are a number of modalities, FIFO, LIFO, Fair Share, etc. and each of them can be either preemptive or non-preemptive, in fact, in most systems, you can usually make preemption a task or "job" attribute.

Those aren't inconsistencies.  They are solutions to valid use cases.

So, I am content with you to say TaskJuggler is always preemptive by design and will remain so, but I am not quite so content with the characterization of a non-preemptive scheduler as inconsistent.

Today, TaskJuggler is always preemptive.  In theory, with TaskJuggler, the task with highest priority or "criticalness" always gets the resource, even if it has to preempt an existing task.  I presume that is what you mean by consistency and I understand your point of view with respect to a preemptive model.  Within that model, the behavior of TaskJuggler is more or less consistent.

On the other hand, if the use case you are trying to model is essentially non-preemptive, this consistently preemptive behavior is inconsistent.  In other words, it doesn't match the use case well and one has to manipulate priorities, dependencies or both in an artificial way to get the behavior that one is trying to model and it is both an unsatisfying, ineffective and labor intensive to solve the problem that way.

It may be that given the way the load balancing algorithm within the scheduler works that it cannot handle this use case without a significant amount of redesign.  You said as much above and I accept that and I still think that TaskJuggler is an extraordinary tool, just not one that is well suited for projects that contain tasks that once started, shouldn't be preempted, even by higher priority tasks.

That does not mean however that the  non-preemptive use case is invalid or inconsistent.  A number of us have expressed it as a need that we are trying to work around that with other means within TaskJuggler more or less successfully and within the corpus of load existing balancing applications, non-preemption is recognized as a valid use case and it is accommodated in their implementations.

Thanks again though for being so extraordinarily responsive to questions like this, for taking the time to explain the scheduler and your point of view and for writing and maintaining TaskJuggler.  I am sorry that it doesn't work for this use case, first of all because I need a tool that does this and secondly, because I sincerely believe that this need is considerably more common than you think, but I still consider TaskJuggler to be a really great tool for a wide variety of projects where the exclusively preemptive scheduling model it implements better fits the production process.

All the best,

John