Jonas Erbe
Jonas Erbe

Reputation: 331

How to model dependencies in chained through time pattern?

TL;DR

How to model a process where the duration of one task depends on the finish time of its predecessor task in chained through time pattern. For more details please read the following description:

Planning Problem Description

First of all I want to describe my planning problem:

Constraints

Planning Goals

Examples of valid processes

The following picture illustrates two valid production processes. The Machines are on the right end of the process because the PlanningEntities are chained through time backwards starting with the target time.

enter image description here

Domain Model

I have modeled the problem with the chained through time pattern since the shortest duration of a production job is less than a minute. So I have to plan in seconds. Maybe this would be to fine grained for the time grain pattern. The following code is an excerpt from my domain model.The abstract class JobOrSlot is used to model the chain of jobs anchored by a slot.

@PlanningEntity
public abstract class JobOrSlot {

    @Id
    private UUID id = UUID.randomUUID();

    @InverseRelationShadowVariable(sourceVariableName = "previousJobOrSlot")
    
    protected Job nextJob;

    public abstract Integer getStartOffset();
}

@PlanningEntity
public class Job extends JobOrSlot {
    @PlanningVariable(valueRangeProviderRefs = { "slotRange", "jobRange" }, graphType = PlanningVariableGraphType.CHAINED)
    private JobOrSlot previousJobOrSlot;

    @AnchorShadowVariable(sourceVariableName = "previousJobOrSlot")
    private Slot slot;

    @ShadowVariable(variableListenerClass = EndTimeUpdatingVariableListener.class, sourceVariableName = "previousJobOrSlot")
    private Integer startOffset;

    @PiggybackShadowVariable(shadowVariableName = "startOffset")
    private Integer endOffset;

    // problem facts
    @Nullable
    private Job predecessor;

    @Nullable
    private Job successor;

    private Duration duration;
    private JobType type; // produce, hold

    // ... unecessary problemfacts and getter and setter omitted

}

The EndTimeUpdatingVariableListener.class iterates through the chains of jobs and calculates the start and end times of the jobs based on their duration and their position in the chain.

The Problem

The challenge is, that the duration of the cooling job is not known before the planning starts. The duration of the cooling job can only be calculated in the moment the production job is placed. It is targetTime - cookingJob.endTime. So placing a production job must change the duration of the cooling job and I can't find a good solution to model this in Optaplanner. I have evaluate two possible solutions but maybe you have a better idea to implement this.

  1. One solution would be to update the associated cooling job start and end times in the EndTimeUpdatingVariableListener every time its production job changes, but this could create effects which are hard to tackle. E.G. Placing another job between the production job and its cooling job like produce A -> someOtherJob -> cool A -> Slot would create an infinite update loop. This could be tackled by implementing a MoveFilter to forbid such invalid moves but its still pain.

  2. Another solution could be to implement CustomMoves that add or remove cooling jobs from the planning problem. Every time a cooling job is added it gets the current valid duration. Hence the duration of the Entity is fixed during planning.

Both implementation getting pretty complex. Is there a better way to model such a planning entity dependency in optaplanner?

Upvotes: 1

Views: 103

Answers (0)

Related Questions