How to model dependencies in chained through time pattern?

101 views Asked by At

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

  • A machine has x slots and can produce or cool different types of products in each of its slots.
  • A machine could not produces and cool at the same time, but it could produces first and than cool afterwards.
  • A machine can produce only one type of product at a time, but it can produce different types of products one after the other.
  • A machine could produces multiple products of the same type at the same time
  • A machine could cool different types of products at the same time
  • The products are consumed at a target time
  • Produced products must be cooled until target time

Planning Goals

  • Minimize production time
  • Determine the latest time at which the production must be started

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?

0

There are 0 answers