Problems regarding shadow variable and adding entities dynamically.

[Quân Hồ]

Hi, I’m a developer new to optaplanner & been working on a FJS problem. Here’s the simplified domain classes for information:

Activity (fact): step of a job. Activities of each jobs have a duration, and they have to be done in a specified sequence. Each activities require different skills to complete.

public class Activity {
Long id;
EnumSet<Skill> skills;
Duration duration;

//Other fields, getter setters
}

public class Job {
String name;
LocalDateTime due;
List<Activity> activities;

//Other fields, getter setters

}

Resources (fact): provide different skills & have a set of available timeslots.

public class Timeslot {
LocalDateTime start;
LocalDateTime end;
}

public class Resource {
EnumSet<Skill> skills;
}

public class ResourceTimeslot extends Timeslot {
Resource resource;
}

Allocation (entity): planning resource + occupied timeslot for each activities.

@PlanningEntity
public class Allocation {
@PlanningId
Long id;

Activity activity;

@PlanningVariable(valueRangeProviderRefs = "timeslotRange")
ResourceTimeslot resourceTimeslot;
//Other fields, getter setters
}

ScheduleTable (solution):

@PlanningSolution
public class ScheduleTable {
@ProblemFactCollectionProperty
@ValueRangeProvider(id = "jobRange")
List<Job> jobs;
@ProblemFactCollectionProperty
@ValueRangeProvider(id = "activityRange")
List<Activity> activities;

@ProblemFactCollectionProperty
@ValueRangeProvider(id = "timeslotRange")
List<ResourceTimeslot> resourceTimeslots;

@PlanningEntityCollectionProperty
List<Allocation> allocations;

@PlanningScore
private HardSoftScore score;

}

I need to allocate activities to resource timeslots. For this domain design I’ve solved the case where each activities have just one allocation: each activity is allocated to a resource timeslot. The number of allocation is known beforehand.

My problem is how to solve two more complex situations:

1. Multiple activites can occupy the same resource timeslot, as long as their duration fit into the timeslot. I need to dynamically calculate each activities starts/stops.

My first approach is to use shadow variable + a map to keep track their activity order since they can be deduced from current solution:

@PlanningEntity
public class Allocation {

private static Map<ResourceTimeslot, List<Timeslot>> allocatedTimeslots = new ConcurrentHashMap<>();
@PlanningId
Long id;

Activity activity;

@CustomShadowVariable(variableListenerClass = AllocationVariableListener.class, sources = {@PlanningVariableReference(variableName = "resourceTimeslot")})
ActivityTimeslot ActivityTimeslot;

@PlanningVariable(valueRangeProviderRefs = "timeslotRange")
ResourceTimeslot resourceTimeslot;
//Other fields, getter setters

}

Is the use of static variable acceptable in optaplanner?

2. One activity can have multiple allocations e.g activities can be split between multiple resources for parallel processing. The number of allocation therefore are not known beforehand. Is there a way to add/remove entities dynamically?

Regards,
Quan

[Jiří Locker]

> 1. Multiple activites can occupy the same resource timeslot, as long as their duration fit into the timeslot. I need to dynamically calculate each activities starts/stops.

The static field is definitely not the way to go. If activities on the same resource must happen in sequence and their order is important, for example to calculate their exact start and stop times, then you need to use the Chained Through Time pattern. Before you take that approach, ask yourself the question whether the activity sequence for a given resource timeslot should affect the score (depends on your business requirements). For example, if you only need to make sure the total duration of the sum of activities in a given resource timeslot doesn't exceed the timeslot size, you don't need Chained Through Time. In such case, you could calculate the total duration using Constraint Streams, optionally with the help of @InverseRelationShadowVariable on the timeslot.

> 2. One activity can have multiple allocations e.g activities can be split between multiple resources for parallel processing. The number of allocation therefore are not known beforehand. Is there a way to add/remove entities dynamically?

I think there is a way to add/remove entities during solving using a special type of move but I've never seen such use case nor have done that myself so I can't help with that. I would personally try to avoid that by looking for a compromise. For example, you could achieve some level of parallel processing by dividing each activity into fixed number of allocations, say two allocations per activity, and then, by means of your constraint design, demand that both allocations must be assigned either to the same resource timeslot (serial processing) or different resource timeslots in the same time period (parallel processing).

BR,

Jiri

[Osamu Kuniyasu]

Hi,

As Jiri said, I don't think it is good idea adding entity dynamically.

I'm referring the Project Job Scheduling example, as it looks similar to me.

You can allow multiple allocations same time in a resource by totalResourceRequirement <= resourceCapacity.

If one resource represents a single person, you will need to split activities that are too large for one person in preprocessing.

If the resource represents a group, i.e. multiple people, there is no need to split large activities, but post-processing will require "by name" assignment using other models.

Best Regards,

Osamu Kuniyasu

2021年9月3日金曜日 20:34:56 UTC+9 jiri....@gmail.com:

[Quân Hồ]

I solved (1) by spliting timeslots into individual timegrains. Calculating start + stop is now very easy (start = what optaplanner picks, stop = start + activity duration).

for (2) I think could be also be solved by also splitting activities into segment of equal lengths (activity duration / timegrain length) then you can allocate those segments to different resources. Though I haven't tested it.

The drawbacks are calculation speed and more complicated constraints.