Introduce/extend manufacturing line quickstart with job dependencies

[triceo]

Discussed in TimefoldAI/timefold-solver#385

^{Originally posted by mcimbora October 31, 2023}
Let's say we've got a model similar to this:

ManufacturingLine
List<Job> jobs

Job
List<Job> predecessorJobs
List<Job> successorJobs

The jobs have dependencies between each other (Job can start only after the predecessors are finished). At the same time, the manufacturing line can process a single item at time only. This is a fairly common problem, that causes confusion (should I go for food packaging vs project job scheduling). Ideally the docs explain the differences.

Volunteer to implement this (not critical atm).

[kentbill]

Hello, @mcimbora
For this issue, I am working on a similar project, and the approach I am trying is based on the food packaging example. I added predecessor jobs to the job and added a planning variable - delay to the job. In the variableListener, the shadow variable startProductionDateTime of the job is taken as the later of "startProductionDateTime" or "predecessor job endDateTime". Then add a constraint to penalize those cases where the startProductionTime is earlier than the endDateTime of their predecessor jobs.

But this method resulted in a score corruption exception, and I think I know the cause for this exception.

For example, Job A is the predecessor job of Job B. In one of the solutions, Job B' startProductionDateTime is later than the endDateTime of Job A, there will be no penalty score. However, when there is a move, changes the endDatetime of Job A, causing it later than the startProductionDateTime of Job B, then a penalty score will be generated. But at this move, all planning variables of Job B never changed, a score correction appeared.
I'm not entirely certain if the actual reason is as such， do you have a better idea?

So far, I haven't been able to come up with any other ideas for this use case. Would you kindly share any other methods you may have?

[mcimbora]

@kentbill I've got a bit different idea to model these dependencies (see screenshot).

• Machine has a planning list variable "jobs".
• Jobs are executed on a machine and have optional dependencies (e.g. multiple components A1, A2 need to be assembled into A3)
• Jobs planned on a single machine are executed in order, i.e. B1 can start only after A2 has been finished for machine Y
• At the same time there are inter-job dependencies, see project A. Job A3 can only start after all its predecessors (A1, A2) are finished
• In case there is minimum start time for some of your tasks, that need to be taken into account too (by delaying the start time of the job). For example, if A3 has a minimum start date of 13:00, set the start time to 13:00. That creates a gap on machine X (11:15 - 13:00). The solver will try to fill it with other jobs.
• That means the start time of A3 is max(A1.endTime, A2.endTime, A3.minStartTime)
• All above needs to be calculated via a variable listener

[kentbill]

Hi @mcimbora
I'm sorry for being busy with other work these days, so today I finally tried the model you proposed. In the StartDateTimeUpdatingVariableListener, I added some logic about predecessor jobs when calculating startCleaningDateTime - the startCleaningDateTime of a job must not be earlier than the max end time of its predecessor jobs.
Following is my implementation.
In StartDateTimeUpdatingVariableListener, created a method to get the max end time of a job:

private LocalDateTime getMaxPredecessorEndTime(Job job) {
        // get the max predecessor end time
        if(job.getPredecessorJobs() != null && !job.getPredecessorJobs().isEmpty()) {
            LocalDateTime predecessorJobEndTime = LocalDateTime.MIN;
            for(Job predecessorJob : job.getPredecessorJobs()) {
                LocalDateTime currentEndTime = predecessorJob.getEndDateTime();
                if(currentEndTime != null && currentEndTime.isAfter(predecessorJobEndTime)) {
                    predecessorJobEndTime = currentEndTime;
                }
            }
            return predecessorJobEndTime;
        } else {
            return null;
        }
 }

In updateStartDateTime method, after getting startCleaningDateTime value, calls the method getMaxPredecessorEndTime, replaces the startCleaningDateTime value if the max predecessor end time is after startCleaningDateTime.
See below code with comment "FOR PREDECESSOR JOB"

 private void updateStartDateTime(ScoreDirector<PackagingSchedule> scoreDirector, Job job) {
        Line line = job.getLine();
        if (line == null) {
            if (job.getStartCleaningDateTime() != null) {
                scoreDirector.beforeVariableChanged(job, "startCleaningDateTime");
                job.setStartCleaningDateTime(null);
                scoreDirector.afterVariableChanged(job, "startCleaningDateTime");
                scoreDirector.beforeVariableChanged(job, "startProductionDateTime");
                job.setStartProductionDateTime(null);
                scoreDirector.afterVariableChanged(job, "startProductionDateTime");
                scoreDirector.beforeVariableChanged(job, "endDateTime");
                job.setEndDateTime(null);
                scoreDirector.afterVariableChanged(job, "endDateTime");
            }
            return;
        }

        Job previousJob = job.getPreviousJob();
        LocalDateTime startCleaningDateTime;
        LocalDateTime startProductionDateTime;
        if (previousJob == null) {
            startCleaningDateTime = line.getStartDateTime();
            startProductionDateTime = line.getStartDateTime();
        } else {
            startCleaningDateTime = previousJob.getEndDateTime();

            //FOR PREDECESSOR JOB： get the max end time of predecessor jobs, set the max end time as the startCleaningDateTime if the max end time is after original startCleaningDateTime
            LocalDateTime predecessorEndTime = this.getMaxPredecessorEndTime(job);
            if(predecessorEndTime != null && predecessorEndTime.isAfter(startCleaningDateTime)) {
                startCleaningDateTime = predecessorEndTime;
            }

            startProductionDateTime = startCleaningDateTime.plus(job.getProduct().getCleanupDuration(previousJob.getProduct()));

        }
        // An equal startCleaningDateTime does not guarantee an equal startProductionDateTime
        for (Job shadowJob = job;
                shadowJob != null && (!Objects.equals(shadowJob.getStartCleaningDateTime(), startCleaningDateTime)
                || !Objects.equals(shadowJob.getStartProductionDateTime(), startProductionDateTime));) {
            scoreDirector.beforeVariableChanged(shadowJob, "startCleaningDateTime");
            shadowJob.setStartCleaningDateTime(startCleaningDateTime);
            scoreDirector.afterVariableChanged(shadowJob, "startCleaningDateTime");

            scoreDirector.beforeVariableChanged(shadowJob, "startProductionDateTime");
            shadowJob.setStartProductionDateTime(startProductionDateTime);
            scoreDirector.afterVariableChanged(shadowJob, "startProductionDateTime");

            scoreDirector.beforeVariableChanged(shadowJob, "endDateTime");
            // TODO skip weekends and holidays according to WorkCalendar
            shadowJob.setEndDateTime(startProductionDateTime == null ? null : startProductionDateTime.plus(shadowJob.getDuration()));
            scoreDirector.afterVariableChanged(shadowJob, "endDateTime");

            LocalDateTime endDateTime = shadowJob.getEndDateTime();
            previousJob = shadowJob;
            shadowJob = shadowJob.getNextJob();
            if (shadowJob == null || endDateTime == null) {
                startCleaningDateTime = null;
                startProductionDateTime = null;
            } else {
                startCleaningDateTime = endDateTime;

                // FOR PREDECESSOR JOB： get the max end time of predecessor jobs, set the max end time as the startCleaningDateTime if the max end time is after original startCleaningDateTime
                LocalDateTime predecessorEndTime = this.getMaxPredecessorEndTime(job);
                if(predecessorEndTime != null && predecessorEndTime.isAfter(startCleaningDateTime)) {
                    startCleaningDateTime = predecessorEndTime;
                }

                startProductionDateTime = startCleaningDateTime.plus(shadowJob.getProduct().getCleanupDuration(previousJob.getProduct()));
                if (startProductionDateTime.isBefore(shadowJob.getReadyDateTime())) {
                    startProductionDateTime = shadowJob.getReadyDateTime();
                }
            }
        }
    }

The data are the same as in your example:
ProductA: JobA1, JobA2, JobA3. JobA3 has two predecessors - JobA1 and JobA2.
ProductB: JobB1, JobB2. JobB2 has a predecessor - JobB1.

But I got an UndoMove corruption.

23:46:06.515 [main        ] TRACE         Move index (3), score (-2init/0hard/0medium/-6008400soft), move (job-A3 {null -> lineY[1]}).
23:46:06.517 [main        ] DEBUG     CH step (2), time spent (115), score (-2init/0hard/0medium/-5576400soft), selected move count (4), picked move (job-A3 {null -> lineX[0]}).
23:46:06.521 [main        ] TRACE         Corruption detected. Diagnosing...
Exception in thread "main" ai.timefold.solver.core.impl.solver.exception.UndoScoreCorruptionException: UndoMove corruption (-480hard/-1920medium/-34527600soft): the beforeMoveScore (-2init/0hard/0medium/-5576400soft) is not the undoScore (-2init/-480hard/-1920medium/-40104000soft) which is the uncorruptedScore (-2init/-480hard/-1920medium/-40104000soft) of the workingSolution.
Variables that are different between before and undo:
  - Actual value (2024-01-04T17:00) of variable startCleaningDateTime on Job entity (job-A1) differs from expected (2024-01-01T20:00)
  - Actual value (2024-01-05T08:00) of variable endDateTime on Job entity (job-A1) differs from expected (2024-01-02T11:00)
  - Actual value (2024-01-04T17:00) of variable startProductionDateTime on Job entity (job-A1) differs from expected (2024-01-01T20:00)


1) Enable EnvironmentMode TRACKED_FULL_ASSERT
(if you haven't already) to fail-faster in case there's a score corruption or variable listener corruption.
2) Check the Move.createUndoMove(...) method of the moveClass (ListAssignMove).
The move (job-B1 {null -> lineX[0]}) might have a corrupted undoMove (job-B1 {lineX[0] -> null}).
3) Check your custom VariableListeners (if you have any)
for shadow variables that are used by score constraints that could cause
the scoreDifference (-480hard/-1920medium/-34527600soft).

	at ai.timefold.solver.core.impl.score.director.AbstractScoreDirector.assertExpectedUndoMoveScore(AbstractScoreDirector.java:717)
	at ai.timefold.solver.core.impl.constructionheuristic.decider.ConstructionHeuristicDecider.doMove(ConstructionHeuristicDecider.java:120)
	at ai.timefold.solver.core.impl.constructionheuristic.decider.ConstructionHeuristicDecider.decideNextStep(ConstructionHeuristicDecider.java:89)
	at ai.timefold.solver.core.impl.constructionheuristic.DefaultConstructionHeuristicPhase.solve(DefaultConstructionHeuristicPhase.java:52)
	at ai.timefold.solver.core.impl.solver.AbstractSolver.runPhases(AbstractSolver.java:82)
	at ai.timefold.solver.core.impl.solver.DefaultSolver.solve(DefaultSolver.java:195)
	at com.easyplan.Main.main(Main.java:41)

[kentbill]

@mcimbora I have some concerns about your model. Would you mind explaining it further? Perhaps I haven't fully understood it yet.
When updating the times of each job, do I need to update the successor jobs of the jobs on the same line（iterate by nextJob）? If necessary, it will be a rather complex process that will have an impact on other lines, just like the neutron bombardment of atomic nuclei, resulting in chain reactions and even infinite loops.

But if the successor jobs of these jobs are not updated, it is possible that there is a job that may start earlier than the end time of its predecessor job, because its predecessor job end time is moved back. Such as the following image: