Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Appearance settings
Discussion options

Context

I'm modelling a Flexible Job Shop Scheduling Problem (FJSSP) using @PlanningListVariable on Machine. The domain is:

  • Machine (@PlanningEntity): holds @PlanningListVariable List<Operation> assignedOperations
  • Operation (@PlanningEntity + @ValueRangeProvider): has startTime as a shadow variable
  • Job (@ProblemFact): fixed sequence of operations

The startTime of each operation depends on two independent sources:

  1. previousOperationOnMachine — the operation preceding it in the same machine's list (@PreviousElementShadowVariable)
  2. previousOperation — the preceding operation in the same job, which may be assigned to a completely different machine

Formally: startTime(op) = max(endTime(prevOnMachine), endTime(prevInJob))

Current implementation

I'm using a VariableListener that listens on both chosenMachine and previousOperationOnMachine, propagates iteratively along the machine chain, and handles the cross-machine job dependency:

@ShadowVariable(variableListenerClass = OperationChainListener.class, sourceVariableName = "chosenMachine")
@ShadowVariable(variableListenerClass = OperationChainListener.class, sourceVariableName = "previousOperationOnMachine")
private Integer startTime;

The listener propagates iteratively (not recursively) along assignedOperations:

private Integer computeStartTime(Operation op, Machine machine) {
    if (machine == null) return null;
    Integer endOnMachine = op.getPreviousOperationOnMachine() == null
        ? null : op.getPreviousOperationOnMachine().getEndTime();
    Integer endInJob = op.getPreviousOperation() == null
        ? null : op.getPreviousOperation().getEndTime();
    int start = 0;
    if (endOnMachine != null) start = Math.max(start, endOnMachine);
    if (endInJob     != null) start = Math.max(start, endInJob);
    return start;
}

This works correctly, but the problem is: when previousOperation.startTime changes (because that operation moved to a different machine), nothing triggers a recomputation on the downstream operation in the job chain.

The core issue

The cross-entity dependency is essentially: startTime of operation N depends on startTime of operation N-1, which lives in a different Machine's list. This makes it a dependency across two separate @PlanningListVariable lists.

I explored the possibility of also declaring startTime as a source of itself (to propagate along the job chain when it changes), but this would introduce a cycle in the shadow variable dependency graph, which Timefold would reject at initialization.

@CascadingUpdateShadowVariable seems to handle intra-list propagation well, but I don't see a clean way to also react to cross-list changes from a different entity's shadow variable.

Question

As VariableListener moves toward deprecation (and presumably removal in 2.0), what is the recommended approach to model this pattern?

Is there a planned primitive or API for shadow variables with cross-entity, cross-list dependencies? Or is @CascadingUpdateShadowVariable expected to cover this somehow in 2.0?

Happy to share more context if useful. Thanks!

You must be logged in to vote

Replies: 3 comments · 5 replies

Comment options

Declarative shadow variables should solve that problem; take a look at TestdataDependencyValue for cross-entity, cross-list dependencies:

@ShadowSources({ "dependencies[].endTime", "previousValue.endTime", "entity" })
public LocalDateTime calculateStartTime() {
LocalDateTime readyTime;
if (previousValue != null) {
readyTime = previousValue.endTime;
} else if (entity != null) {
readyTime = entity.startTime;
} else {
return null;
}
if (dependencies != null) {
for (var dependency : dependencies) {
if (dependency.endTime == null) {
return null;
}
readyTime = ObjectUtils.max(readyTime, dependency.endTime);
}
}
return readyTime;
}

You must be logged in to vote
3 replies
@electrosilvia
Comment options

Thank you Christoper for pointing me to the TestdataDependencyValue example — it was exactly what I needed to understand the intended pattern.

What I tried

Following the example, I replaced the VariableListener with the declarative @ShadowVariable(supplierName = ...) + @ShadowSources API. My domain has:

  • Machine (@PlanningEntity) with @PlanningListVariable List<Operation> assignedOperations
  • Operation (@PlanningEntity) with two shadow variables: startTime and endTime

The startTime of each operation depends on:

  1. previousOperationOnMachine.endTime — the preceding operation on the same machine
  2. previousOperationsInJob[].endTime — all preceding operations in the same job, potentially assigned to different machines

I declared both shadow variables and their suppliers as follows:

@ShadowVariable(supplierName = "calculateStartTime")
private Integer startTime;

@ShadowVariable(supplierName = "calculateEndTime")
private Integer endTime;

@ShadowSources({"previousOperationOnMachine.endTime",
                "previousOperationsInJob[].endTime",
                "chosenMachine"})
public Integer calculateStartTime() {
    if (chosenMachine == null) return null;
    Integer endOnMachine = previousOperationOnMachine == null
            ? null : previousOperationOnMachine.getEndTime();
    Integer endInJob = null;
    if (previousOperationsInJob != null) {
        for (Operation prev : previousOperationsInJob) {
            Integer prevEnd = prev.getEndTime();
            if (prevEnd != null) {
                endInJob = endInJob == null ? prevEnd : Math.max(endInJob, prevEnd);
            }
        }
    }
    int start = 0;
    if (endOnMachine != null) start = Math.max(start, endOnMachine);
    if (endInJob != null)     start = Math.max(start, endInJob);
    return start;
}

@ShadowSources({"startTime"})
public Integer calculateEndTime() {
    if (chosenMachine == null) return null;
    Integer duration = getDuration();
    if (duration == null) return null;
    return (startTime == null ? 0 : startTime) + duration;
}

The problem

The Construction Heuristic works correctly — shadow variables are computed in the right order and the initial solution is feasible.

However, during Local Search the score progressively degrades to 0hard/0soft. Investigation shows that endTime becomes null for all operations during LS, causing the makespan constraint (which filters on op.getEndTime() != null) to see an empty stream and produce a penalty of 0.

The issue appears to be an inconsistent update order between startTime and endTime during Local Search: when a move is applied, the two shadow variables seem to be updated in a sequence that leaves endTime as null before the score is computed, even when startTime is already correctly set.

We tried several approaches to work around the null propagation (using 0 as a fallback when startTime is null in calculateEndTime, adding null guards in constraints) but the behaviour persists.

Note on @ShadowSources path validation

We also found that using previousOperationOnMachine.endTime in @ShadowSources requires endTime to be a declared @ShadowVariable — referencing a plain getter method causes an IllegalArgumentException at startup:

The source path (previousOperationOnMachine.endTime) starting from root entity class (Operation)
does not end on a variable.

This means endTime cannot be a simple derived method and must be a full shadow variable, which is what introduces the update-order fragility described above.

Question

We are not sure whether the behaviour we observed is a bug in 1.32.0, a known limitation of the declarative API, or simply a mistake in how we declared the shadow variable chain. We may well be missing something in the way @ShadowSources is supposed to be used when a shadow variable (endTime) depends on another shadow variable (startTime) that is itself triggered by a cross-entity list path.

For the time being we have reverted to the VariableListener approach, which produces correct results. However, we would strongly prefer to migrate away from it — not only because it is deprecated, but also because staying on a deprecated API means we will not be able to upgrade to 2.0 when it stabilises without a significant rewrite.

Any guidance on what we might be doing wrong, or on the correct way to model this chained cross-entity dependency with the declarative API, would be greatly appreciated. If this is indeed a limitation that is being addressed in 2.0, even a pointer to the planned approach would help us plan the migration.

Thank you!

@electrosilvia
Comment options

Update

Following the TestdataDependencyValue example, we added @ShadowVariablesInconsistent to the Operation class:

@ShadowVariablesInconsistent
Boolean isInvalid;

The solver now produces correct results — the score corruption issue is resolved. However, we are observing a significant performance degradation compared to the VariableListener version. On our larger instance (20 machines, 100 jobs, 1422 operations) the move evaluation speed drops dramatically.

Is this expected when using @ShadowVariablesInconsistent, or is there something we can do to reduce the overhead?

Thank you!

@triceo
Comment options

@electrosilvia In some situations, the new shadow variable mechanism will be slower; that said, calling what you're observing a "performance degradation" is not entirely fair. You were having trouble implementing a feature, the new shadow variables gave you a way of implementing that feature, and you paid a price for it. A fairer comparison would be to compare variable listeners to the new shadow variables on the same feature set.

Note that the Enterprise Edition of the solver contains a faster implementation of the new shadow variable mechanism. It also includes other features which can significantly improve the performance of the solver.

Comment options

Hi everyone, sorry for the long silence — I'm re-opening this topic I started a while ago. Thanks to everyone who replied in the meantime.
I've put together a minimal self-contained reproducer (attached: Maven project, JDK 21, Timefold 2.0.0). The model is a tiny FJSP setup: Machine has a @PlanningListVariable, Operation has the usual machine-side shadow variables plus declarative startTime/endTime via @ShadowVariable + @Shadowsources. Job precedence is modelled as a problem-fact field previousOperationInJob on Operation, fixed before solving.
The issue is the @Shadowsources path previousOperationInJob.endTime (cross-entity dependency through a problem-fact reference to another operation's shadow variable): it doesn't propagate. After solving, every operation ends up with startTime/endTime = null. Run with mvn exec:java; the README lists the variants I already tried.
repro.zip

You must be logged in to vote
2 replies
@Christopher-Chianelli
Comment options

It seems you migrated against an older preview version of declarative shadow variables.
TL;DR: There was a prior preview version of declarative shadow where inconsistent entities were included in forEach. This was very annoying, since basically every constraint except one needed to filter out those entities. Now, inconsistent entities are not included in forEach; you need to use forEachUnfiltered instead. This constraint provider works and solves correctly:

package com.example;

import ai.timefold.solver.core.api.score.HardSoftScore;
import ai.timefold.solver.core.api.score.stream.Constraint;
import ai.timefold.solver.core.api.score.stream.ConstraintCollectors;
import ai.timefold.solver.core.api.score.stream.ConstraintFactory;
import ai.timefold.solver.core.api.score.stream.ConstraintProvider;

public class FJSConstraintProvider implements ConstraintProvider {

    @Override
    public Constraint[] defineConstraints(ConstraintFactory constraintFactory) {
        return new Constraint[] {
                inconsistentOperation(constraintFactory),
                minimizeMakespan(constraintFactory)
        };
    }

    /**
     * Hard constraint: every Operation assigned to a machine must have a non-null startTime.
     * This guards against the constraint silently ignoring operations with null shadow values.
     */
    private Constraint inconsistentOperation(ConstraintFactory constraintFactory) {
        return constraintFactory.forEachUnfiltered(Operation.class)
                .filter(Operation::isInconsistent)
                .penalize(HardSoftScore.ONE_HARD)
                .asConstraint("Inconsistent Operation");
    }

    /**
     * Minimize makespan. If endTime is null we replace it with a huge number so the
     * solver cannot 'cheat' by leaving shadow variables unpopulated.
     */
    private Constraint minimizeMakespan(ConstraintFactory constraintFactory) {
        return constraintFactory.forEach(Operation.class)
                .groupBy(ConstraintCollectors.max((Operation op) ->
                        op.getEndTime() == null ? Integer.MAX_VALUE / 2 : op.getEndTime().intValue()))
                .penalize(HardSoftScore.ONE_SOFT, makespan -> makespan)
                .asConstraint("Minimize makespan");
    }
}
@electrosilvia
Comment options

ok, this works, thank you, but it is very slowly.
I'd like to avoid inconsistent Operations before the constraint recalculation.

Comment options

You must be logged in to vote
0 replies
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
4 participants
Morty Proxy This is a proxified and sanitized view of the page, visit original site.