Combination Custom Moves

[Andrew O]

Hello community,

I have a conundrum which can be summarized by the attached picture and described situation below:

I have a certain amount of tasks to be planned (planning entity is the invidual task itself), with each of those tasks having different duration times and properties (labeled A,B,C).  I would like to ensure that tasks of same property are planned together an that only one unique employee works on tasks of a certain property type.  Therefore I created a custom move to change/swap blocks of tasks with the same property together. (a sort of subchain custom move)

After construction heuristics is finished, I get a solution similar to the image below.  In which tasks of property A were planned last and assigned to two different employees, because neither employee had enough availability to complete all of the tasks of type A (availability hard constraint).  The only way that I can find the solution that I want is for tasks with property A to be moved to employee A: such that employee A works only on type A tasks, employee B only on type B, and employee C only on type C.

However, I am not able to figure out a series of moves (or perhaps a rule) which would allow me to do that.  It seems some kind of CompositeMove on custom moves would be necessary here, but I am not sure how to do this.  Does anyone have any ideas on this topic or how to approach this issue?

Thank you!

[Jiří Locker]

In my opinion it's OK to get the result illustrated by the image after CH. It's a good initial solution despite the fact it's not feasible.

Explanation: CH's job is to initialize entities, 1 entity per step. Once a step is made and a variable is assigned a value, that variable can no longer be modified until CH ends and solver moves on to the LS phase. So it's not unusual that CH paints itself into the corner. It cannot look ahead and predict that assigning the first A task to Employee B move is destined to result in an infeasible solution because Employee B's capacity won't allow to process all A tasks. For example, if your secondary goal is to minimize the number of used Employees, then assigning the first A task to Employee B or C is a reasonable move because it avoids utilization of a third employee.

In addition to that, as I already said, CH initializes 1 entity in each step, so you have to give up thinking about a custom move that somehow assigns a bunch of tasks of the same property type to a single employee (someone correct me if this is not true, I'm not 100% sure). So you have to accept that CH may produce this type of imperfect solutions and come up with custom moves that will rectify the situation and move the fragmented task groups to a single employee in addition to the custom move that moves whole groups that you already have.

HTH,

Jiri

[Osamu Kuniyasu]

I agree to Jiri.

One Idea of a penalty rule that any two tasks assigned an employee has different types, count 1 penalty.

In the case of the image, 10 penalties with the employee B. and 7 penalties with the employee C.

a changeMove of an A task to the Employee A reduces 5 penalties....

How this rule(score) works is depends on your priorities of this and other rules, plus your LS algorithm.

The LA or SA may accept not good steps for future better solutions.

HTH,

Osamu Kuniyasu

 

2022年5月5日木曜日 0:03:04 UTC+9 jiri....@gmail.com:

[Andrew O]

Hello,

Thank you for your feedback Jiri and Osamu,

@Jiri: Just to clarify, I totally agree that his first CH solution is unavoidable due to the factors that you mentioned (specifically that a task can not be modified once it is placed in CH).  However, I am interested particularly in how to amend this initial solution in local search as you described in your last sentence.  i.e. how to realign the fragments to a single group....

To this end...i think the suggestion of Osamu can work.  To clarify, I am currently using LA, also with strategicOscillator set to True in the Forager.  I do not necessarily care about agent allocation "fairness".  But the algorithm should indeed repiece the blocks with similar properties together both in overconstrained and underconstrained cases.  So yes, I think the best solution here might be to implement a rule as Osamu suggested in which individual moves reduce penalties in such a way that an aggregate blocks are nautrally preferred in the end.

I will try it out today :)

Thanks!