Timefold: How to create a constraint for equipment capacity in jobs that are scheduled to employees?

Question

I am attempting to create a model that has an equipment capacity check. My model consists of Jobs, Employees, and Equipment, where Employees are the anchor for the Job entities which are implemented as chained planning variables. An employee and equipment are assigned to each job. I've made my model such that each equipment has a capacity to it, which represents the number of that equipment we have (i.e. a pen with a capacity with 2 means we have 2 pens). However, I am stuck on implementing a capacity check for the equipment, since the capacity can change at any point in time for any job, because we are using a chained-through-time pattern.

I started with a naive method to count the number of overlapping jobs that also have the equipment, but this isn't correct, as the overlapping jobs themselves might not be overlapping with each other, giving me an incorrect count and penalizing when it shouldn't be.

Therefore, I tried a different method (seen below), where I get a pair of jobs with the same equipment and overlapping times, and then check every other job to see if this third job is overlapping with and has the same equipment as the pair. I then group this TriConstraintStream by Employee, so jobs from the same employee that are overlapping don't double-count. This gives me a UniConstraintStream of Employees, who have a job overlapping with this pair, but since I need the count of jobs, I call another groupBy that groups all employees together and creates a BiConstraintStream with the count.

return factory.forEachUniquePair(Job.class, Joiners.overlapping(Job::getStartDateTime, Job::getEndDateTime))
        .filter(((job1, job2) ->
                !Collections.disjoint(job1.getEquipment(), job2.getEquipment())))
        .join(factory.forEach(Job.class).filter(job -> !job.getEquipment().isEmpty()))
        .filter(((job1, job2, job3) ->
                job3 != job1 && job3 != job2
                // The overlap between jobs 1 and 2 is determined by the later start date and earlier end date.
                // job 3 is overlapping if its start is before the overlap's end time...
                && job3.getStartDateTime().isBefore(
                        (job1.getEndDateTime().isBefore(job2.getEndDateTime()))
                                ? job1.getEndDateTime()
                                : job2.getEndDateTime())
                // and the overlap's start time is before the job's end time.
                && ((job1.getStartDateTime().isAfter(job2.getStartDateTime()))
                        ? job1.getStartDateTime()
                        : job2.getStartDateTime())
                        .isBefore(job3.getEndDateTime())
                // now check if job3 has equipment that is within both job 1 and 2
                && !Collections.disjoint(job1.getEquipment(), job3.getEquipment())
                && !Collections.disjoint(job2.getEquipment(), job3.getEquipment())))
        // group by job3's employee, so employees won't be double-counted
        .groupBy(((job1, job2, job3) -> job3.getEmployee()))
        // group the employees by their service, and since all employees have a null service, this gives me the count.
        .groupBy(Employee::getService, count())
        // TODO: equipment capacity is needed so we can determine if it's above capacity or not.
        .penalizeLong(HardMediumSoftLongScore.ONE_HARD, (((service, integer) -> (long) (Math.max(0, integer - 2))))) 
        .asConstraint("Equipment capacity check");

My first question is: how do I incorporate the equipment into this constraint so I can get its capacity for the penalty?

My second question is: This constraint only works when the capacity is greater than or equal to 3, since I check three jobs at a time. Is there a way that is less cumbersome that allows me to check the capacity without checking three different jobs?

Answer 1

I would use the experimental consecutive interval collector for this task (you would need to copy the experimental package into your project files):

return factory.forEach(Job.class)
        // Change Job to (Job, Equipment) tuples
        .expand(Job::getEquipment())
        .flattenLast(equipment -> equipment)
        // Group consecutive intervals by equipment
        .groupBy((job, equipment) -> equipment,
                 ExperimentalConstraintCollectors.consecutiveTemporalInterval(
                     (job, equipment) -> job,
                     Job::getStartDateTime,
                     Job::getEndDateTime)
        )
        .flattenLast(ConsecutiveIntervalInfo::getIntervalClusters)
        // Only include interval clusters that have overlap
        .filter((equipment, cluster) -> cluster.hasOverlap())
        .expand((equipment, cluster) -> getMaximumOverlap(cluster))
        .filter((equipment, cluster, maxOverlapCount) -> maxOverlapCount > equipment.getCapacity())
        .penalizeLong(HardMediumSoftLongScore.ONE_HARD,
                     (equipment, cluster, maxOverlapCount) -> maxOverlapCount - equipment.getCapacity())
        .asConstraint("Equipment capacity check");

getMaximumOverlap is a function that keep tracks of the maximum number of open intervals; cluster can be iterated:

record JobEvent(LocalDateTime moment, int change) implements Comparable<JobEvent> {
    public int compareTo(JobEvent other) {
         return moment.compareTo(other.moment);
    }
}

int getMaximumOverlap(IntervalCluster<Job, LocalDateTime> cluster) {
     List<JobEvent> eventList = new ArrayList<>(2 * cluster.size());
     for (var job : cluster) {
         eventList.add(new JobEvent(job.getStartDateTime(), 1));
         eventList.add(new JobEvent(job.getEndDateTime(), -1));
     }
     eventList.sort(Comparator.naturalOrder());
     int sum = 0;
     int maxSum = 0;
     for (var event : eventList) {
         sum += event.change();
         if (sum > maxSum) {
             maxSum = sum;
         }
     }
     return maxSum;
}