APS开源源码解读: 排程工具 optaplanner

抽象条理非常好，广义优化工具。用于排产没有复杂的落地示例
move 真实的规划变量 -> trigger shadowvariable更新 -> StartTimeListener
  

• https://github.com/apache/incubator-kie-optaplanner/blob/main/optaplanner-examples/src/main/java/org/optaplanner/examples/projectjobscheduling/app/ProjectJobSchedulingApp.java
  
• https://github.com/eugenp/tutorials/tree/master/timefold-solver
  
• https://github.com/kisszhu/aps
  

安装

• java
  
• maven
  

设置

• xml设置
  
• solutionClass
  
• entityClass
  
• constraintProviderClass
  
  
  
  • 约束设置
    
  
  
• termination： 5min
  
• constructionHeuristic: FIRST_FIT
  
  
  
  • first fit
    
  
  
• localSearch:
  

也即是说，先定义对象“entityClass”， 转化为约束“constraintProviderClass”，然后运用 constructionHeuristic + localSearch的方式进行求解
其中，一个团体的使命叫做project, 资源有可再生，非可再生。
工序叫做Job，job跟着若干project。每个工序有自己的资源，ResourceRequirement. 执行模式Execution Mode. 分配allocation.

• resourceRequirement和allocation都要设置execution mode
  
• 每个工序JOb, 有自己的resourceRequirement, executation mode, allocation
  
• 
  

   最好先跑一个实例中的quick-start: https://docs.timefold.ai/timefold-solver/latest/quickstart/hello-world/hello-world-quickstart
  基本概念

   

• 最简单的宏观视角来说，构建一个solver = solverFactory.buildSolver()，构建一个题目建模solution=new PlanningSolution(machines, tasks)，solver.solve(solution)即可.
  
• 其中PlanningEntity, 约束位于solution之中; Planning Variable (可设置变化范围)位于PlanningEntity中，由于一些联动的关系，可以设置影子变量ShadowVariable，一个entity的变量改变了，其影子变量也跟着改变，例如下一道工序的开始时间；如果是双向的，及两个变量恣意个发生变化，另一个都跟着变化，则设置为InverseRelationShadowVariable
  计划相干：https://docs.timefold.ai/timefold-solver/latest/responding-to-change/responding-to-change#continuousPlanning
  

  

• PlanningSolution
  
  
  
  • 定义Problem，以及解
    
  
  
• planning entity
  
  
  
  • Allocation
    
  
  
• planing variable
  
  
  
  • executionMode
    
  • delay
    
  
  
• shadow variable
  
  
  
  • predecessorsDoneDate
    
  • https://www.optaplanner.org/docs/optaplanner/latest/shadow-variable/shadow-variable.html
    
  • ShadowVariable和VariableListener之间的关系紧密相干
    
  
  
• planning score
  
• 核心的优化算法
  

其他使命的domain 模子对怎样建模比力重要

Java基本概念

• 反射就是Java可以给我们在运行时获取类的信息，例如在类上加上@Component注解，Spring就帮你创建对象
  
• 
  

建模

建模非常关键，也就是想清晰一个计划或分配题目，真正分配的是什么，或者计划过程中，真正变化的什么。很多只是变化引起的
优化过程中，交换的是什么？
课程表

   安排课程，也就是将时间和教室分配给课程
  拿quick-start中的课程表为例，分配的资源是教室和时间，其中的约束为

• A room can have at most one lesson at the same time.
  
• A teacher can teach at most one lesson at the same time.
  
• A student can attend at most one lesson at the same time.
  
• A teacher prefers to teach all lessons in the same room.
  
• A teacher prefers to teach sequential lessons and dislikes gaps between lessons.
  
• A student dislikes sequential lessons on the same subject.
  

• 其中的planningvariable应该是多对一的，多个planning variable对应到一个其他entity，而不是一个planning variable对应到多个entity。使用到该planning variable的其他entity，是1，可以直接对应到多个planning entity中的planning variable。
  

车辆规划

   每一辆车分给一个使命队列，依次去这些地方

  排产-Project Job Scheduling

   排产也就是把使命分配给资源和时间.
  官方实例中分配资源也就是选择execution mode，目标是淘汰project delay. 其中真正分配和变化的是execution mode. 也就是选择差别的资源
排产-TaskAssigning

约束

比如排产中的工序依赖关系

1. import org.timefold.solver.core.api.score.buildin.hardsoft.HardSoftScore;
2. import org.timefold.solver.core.api.score.stream.ConstraintProvider;
3. import org.timefold.solver.core.api.score.stream.Constraint;
4. import org.timefold.solver.core.api.score.stream.ConstraintStream;
5. import org.timefold.solver.core.api.score.stream.Joiners;
7. public class JobShopConstraintProvider implements ConstraintProvider {
9.     @Override
10.     public Constraint[] defineConstraints(ConstraintFactory constraintFactory) {
11.         return new Constraint[] {
12.             // Ensure operations follow the sequence within each job
13.             constraintFactory.from(Operation.class)
14.                 .join(Operation.class, Joiners.filteringEach(otherOp ->
15.                     otherOp.getJob().equals(op.getJob()) &&
16.                     otherOp.getSequence() == op.getSequence() + 1
17.                 ))
18.                 .penalize("Operations must follow sequence",
19.                     HardSoftScore.ONE_HARD,
20.                     (op, otherOp) -> 1),
21.             
22.             // Ensure machine constraints are respected
23.             constraintFactory.from(Operation.class)
24.                 .join(Operation.class, Joiners.filteringEach((op1, op2) ->
25.                     op1.getMachine().equals(op2.getMachine()) &&
26.                     op1.getEndTime() > op2.getStartTime() &&
27.                     op1.getStartTime() < op2.getEndTime() &&
28.                     !op1.equals(op2))
29.                 )
30.                 .penalize("Machine cannot process two operations at once",
31.                     HardSoftScore.ONE_HARD,
32.                     (op1, op2) -> 1)
33.         };
34.     }
35. }

复制代码

官方示例

入口在APP的main

1. public static void main(String[] args) {
2.         prepareSwingEnvironment();
3.         new ProjectJobSchedulingApp().init();
4.     }

复制代码

init

1. public void init() {
2.         init(null, true);
3.     }
5.     public void init(Component centerForComponent, boolean exitOnClose) {
6.         solutionBusiness = createSolutionBusiness();
7.         solverAndPersistenceFrame = new SolverAndPersistenceFrame<>(solutionBusiness, createSolutionPanel(),
8.                 createExtraActions());
9.         solverAndPersistenceFrame
10.                 .setDefaultCloseOperation(exitOnClose ? WindowConstants.EXIT_ON_CLOSE : WindowConstants.DISPOSE_ON_CLOSE);
11.         solverAndPersistenceFrame.init(centerForComponent);
12.         solverAndPersistenceFrame.setVisible(true);
13.     }

复制代码

其中，solution business
- SolverFactory.createFromXmlResource建立了solver

1. public SolutionBusiness<Solution_, ?> createSolutionBusiness() {
2.         SolutionBusiness<Solution_, ?> solutionBusiness = new SolutionBusiness<>(this,
3.                 SolverFactory.createFromXmlResource(solverConfigResource));
4.         solutionBusiness.setDataDir(determineDataDir(dataDirName));
5.         solutionBusiness.setSolutionFileIO(createSolutionFileIO());
6.         solutionBusiness.setImporters(createSolutionImporters());
7.         solutionBusiness.setExporters(createSolutionExporters());
8.         solutionBusiness.updateDataDirs();
9.         return solutionBusiness;
10.     }

复制代码

在APP类继承的solution中，示例采用的是schedule，也就是planningsolution,作为题目和排产效果

1. package org.optaplanner.examples.projectjobscheduling.domain;
3. import java.util.List;
5. import org.optaplanner.core.api.domain.solution.PlanningEntityCollectionProperty;
6. import org.optaplanner.core.api.domain.solution.PlanningScore;
7. import org.optaplanner.core.api.domain.solution.PlanningSolution;
8. import org.optaplanner.core.api.domain.solution.ProblemFactCollectionProperty;
9. import org.optaplanner.core.api.score.buildin.hardmediumsoft.HardMediumSoftScore;
10. import org.optaplanner.examples.common.domain.AbstractPersistable;
11. import org.optaplanner.examples.projectjobscheduling.domain.resource.Resource;
13. @PlanningSolution
14. public class Schedule extends AbstractPersistable {
16.     private List<Project> projectList;
17.     private List<Job> jobList;
18.     private List<ExecutionMode> executionModeList;
19.     private List<Resource> resourceList;
20.     private List<ResourceRequirement> resourceRequirementList;
22.     private List<Allocation> allocationList;
24.     private HardMediumSoftScore score;
26.     public Schedule() {
27.     }
29.     public Schedule(long id) {
30.         super(id);
31.     }
33.     @ProblemFactCollectionProperty
34.     public List<Project> getProjectList() {
35.         return projectList;
36.     }
38.     public void setProjectList(List<Project> projectList) {
39.         this.projectList = projectList;
40.     }
42.     @ProblemFactCollectionProperty
43.     public List<Job> getJobList() {
44.         return jobList;
45.     }
47.     public void setJobList(List<Job> jobList) {
48.         this.jobList = jobList;
49.     }
51.     @ProblemFactCollectionProperty
52.     public List<ExecutionMode> getExecutionModeList() {
53.         return executionModeList;
54.     }
56.     public void setExecutionModeList(List<ExecutionMode> executionModeList) {
57.         this.executionModeList = executionModeList;
58.     }
60.     @ProblemFactCollectionProperty
61.     public List<Resource> getResourceList() {
62.         return resourceList;
63.     }
65.     public void setResourceList(List<Resource> resourceList) {
66.         this.resourceList = resourceList;
67.     }
69.     @ProblemFactCollectionProperty
70.     public List<ResourceRequirement> getResourceRequirementList() {
71.         return resourceRequirementList;
72.     }
74.     public void setResourceRequirementList(List<ResourceRequirement> resourceRequirementList) {
75.         this.resourceRequirementList = resourceRequirementList;
76.     }
78.     @PlanningEntityCollectionProperty
79.     public List<Allocation> getAllocationList() {
80.         return allocationList;
81.     }
83.     public void setAllocationList(List<Allocation> allocationList) {
84.         this.allocationList = allocationList;
85.     }
87.     @PlanningScore
88.     public HardMediumSoftScore getScore() {
89.         return score;
90.     }
92.     public void setScore(HardMediumSoftScore score) {
93.         this.score = score;
94.     }
96.     // ************************************************************************
97.     // Complex methods
98.     // ************************************************************************
100. }

复制代码

Timefold 示例

Solver job接受到problem，开始run

1. @Deprecated(forRemoval = true, since = "1.6.0")
2.     default SolverJob<Solution_, ProblemId_> solve(ProblemId_ problemId,
3.             Solution_ problem, Consumer<? super Solution_> finalBestSolutionConsumer,
4.             BiConsumer<? super ProblemId_, ? super Throwable> exceptionHandler) {
5.         SolverJobBuilder<Solution_, ProblemId_> builder = solveBuilder()
6.                 .withProblemId(problemId)
7.                 .withProblem(problem);
8.         if (finalBestSolutionConsumer != null) {
9.             builder.withFinalBestSolutionConsumer(finalBestSolutionConsumer);
10.         }
11.         if (exceptionHandler != null) {
12.             builder.withExceptionHandler(exceptionHandler);
13.         }
14.         return builder.run();
15.     }

复制代码

1. solverStatus = SolverStatus.SOLVING_ACTIVE;
2.             // Create the consumer thread pool only when this solver job is active.
3.             consumerSupport = new ConsumerSupport<>(getProblemId(), bestSolutionConsumer, finalBestSolutionConsumer,
4.                     firstInitializedSolutionConsumer, exceptionHandler, bestSolutionHolder);
6.             Solution_ problem = problemFinder.apply(problemId);
7.             // add a phase lifecycle listener that unlock the solver status lock when solving started
8.             solver.addPhaseLifecycleListener(new UnlockLockPhaseLifecycleListener());
9.             // add a phase lifecycle listener that consumes the first initialized solution
10.             solver.addPhaseLifecycleListener(new FirstInitializedSolutionPhaseLifecycleListener(consumerSupport));
11.             solver.addEventListener(this::onBestSolutionChangedEvent);
12.             final Solution_ finalBestSolution = solver.solve(problem);
13.             consumerSupport.consumeFinalBestSolution(finalBestSolution);
14.             return finalBestSolution;

复制代码

理解

• https://www.optaplanner.org/docs/optaplanner/latest/shadow-variable/shadow-variable.html
  
• build_solver/ default_solver_factory
  

1.     public Solver<Solution_> buildSolver(SolverConfigOverride<Solution_> configOverride) {
2.         Objects.requireNonNull(configOverride, "Invalid configOverride (null) given to SolverFactory.");
3.         var isDaemon = Objects.requireNonNullElse(solverConfig.getDaemon(), false);
5.         var solverScope = new SolverScope<Solution_>();
6.         var monitoringConfig = solverConfig.determineMetricConfig();
7.         solverScope.setMonitoringTags(Tags.empty());
8.         var metricsRequiringConstraintMatchSet = Collections.<SolverMetric> emptyList();
9.         if (!monitoringConfig.getSolverMetricList().isEmpty()) {
10.             solverScope.setSolverMetricSet(EnumSet.copyOf(monitoringConfig.getSolverMetricList()));
11.             metricsRequiringConstraintMatchSet = solverScope.getSolverMetricSet().stream()
12.                     .filter(SolverMetric::isMetricConstraintMatchBased)
13.                     .filter(solverScope::isMetricEnabled)
14.                     .toList();
15.         } else {
16.             solverScope.setSolverMetricSet(EnumSet.noneOf(SolverMetric.class));
17.         }
19.         var environmentMode = solverConfig.determineEnvironmentMode();
20.         var constraintMatchEnabled = !metricsRequiringConstraintMatchSet.isEmpty() || environmentMode.isAsserted();
21.         if (constraintMatchEnabled && !environmentMode.isAsserted()) {
22.             LOGGER.info(
23.                     "Enabling constraint matching as required by the enabled metrics ({}). This will impact solver performance.",
24.                     metricsRequiringConstraintMatchSet);
25.         }
27.         var innerScoreDirector = scoreDirectorFactory.buildScoreDirector(true, constraintMatchEnabled);
28.         solverScope.setScoreDirector(innerScoreDirector);
29.         solverScope.setProblemChangeDirector(new DefaultProblemChangeDirector<>(innerScoreDirector));
31.         var moveThreadCount = resolveMoveThreadCount(true);
32.         var bestSolutionRecaller = BestSolutionRecallerFactory.create().<Solution_> buildBestSolutionRecaller(environmentMode);
33.         var randomFactory = buildRandomFactory(environmentMode);
35.         var configPolicy = new HeuristicConfigPolicy.Builder<>(
36.                 environmentMode,
37.                 moveThreadCount,
38.                 solverConfig.getMoveThreadBufferSize(),
39.                 solverConfig.getThreadFactoryClass(),
40.                 solverConfig.getNearbyDistanceMeterClass(),
41.                 randomFactory.createRandom(),
42.                 scoreDirectorFactory.getInitializingScoreTrend(),
43.                 solutionDescriptor,
44.                 ClassInstanceCache.create()).build();
45.         var basicPlumbingTermination = new BasicPlumbingTermination<Solution_>(isDaemon);
46.         var termination = buildTerminationConfig(basicPlumbingTermination, configPolicy, configOverride);
47.         var phaseList = buildPhaseList(configPolicy, bestSolutionRecaller, termination);
49.         return new DefaultSolver<>(environmentMode, randomFactory, bestSolutionRecaller, basicPlumbingTermination,
50.                 termination, phaseList, solverScope,
51.                 moveThreadCount == null ? SolverConfig.MOVE_THREAD_COUNT_NONE : Integer.toString(moveThreadCount));
52.     }

复制代码

solver的主流程

1. @Override
2.     public final Solution_ solve(Solution_ problem) {
3.         if (problem == null) {
4.             throw new IllegalArgumentException("The problem (" + problem + ") must not be null.");
5.         }
7.         // No tags for these metrics; they are global
8.         LongTaskTimer solveLengthTimer = Metrics.more().longTaskTimer(SolverMetric.SOLVE_DURATION.getMeterId());
9.         Counter errorCounter = Metrics.counter(SolverMetric.ERROR_COUNT.getMeterId());
11.         solverScope.setBestSolution(problem);
12.         solverScope.setSolver(this);
13.         outerSolvingStarted(solverScope);
14.         boolean restartSolver = true;
15.         while (restartSolver) {
16.             LongTaskTimer.Sample sample = solveLengthTimer.start();
17.             try {
18.                 // solvingStarted will call registerSolverSpecificMetrics(), since
19.                 // the solverScope need to be fully initialized to calculate the
20.                 // problem's scale metrics
21.                 solvingStarted(solverScope);
22.                 runPhases(solverScope);
23.                 solvingEnded(solverScope);
24.             } catch (Exception e) {
25.                 errorCounter.increment();
26.                 solvingError(solverScope, e);
27.                 throw e;
28.             } finally {
29.                 sample.stop();
30.                 unregisterSolverSpecificMetrics();
31.             }
32.             restartSolver = checkProblemFactChanges();
33.         }
34.         outerSolvingEnded(solverScope);
35.         return solverScope.getBestSolution();
36.     }

复制代码

• run_phase /abstract_solver
  

1. protected void runPhases(SolverScope<Solution_> solverScope) {
2.         if (!solverScope.getSolutionDescriptor().hasMovableEntities(solverScope.getScoreDirector())) {
3.             logger.info("Skipped all phases ({}): out of {} planning entities, none are movable (non-pinned).",
4.                     phaseList.size(), solverScope.getWorkingEntityCount());
5.             return;
6.         }
7.         Iterator<Phase<Solution_>> it = phaseList.iterator();
8.         while (!solverTermination.isSolverTerminated(solverScope) && it.hasNext()) {
9.             Phase<Solution_> phase = it.next();
10.             phase.solve(solverScope);
11.             // If there is a next phase, it starts from the best solution, which might differ from the working solution.
12.             // If there isn't, no need to planning clone the best solution to the working solution.
13.             if (it.hasNext()) {
14.                 solverScope.setWorkingSolutionFromBestSolution();
15.             }
16.         }
17.     }

复制代码

• solver表面的phase, PhaseFactory
  
• dostep
  局部搜索在当前解上尝试多个移动，并选择最佳的被接受的移动作为这一步。A step is the winning Move。在每一步，它尝试全部选定的移动，除非是选定的step，否则它不会进一步研究谁人解。这就是局部搜索具有很高可扩展性的原因之一。
  

1. private void doStep(CustomStepScope<Solution_> stepScope, CustomPhaseCommand<Solution_> customPhaseCommand) {
2.         InnerScoreDirector<Solution_, ?> scoreDirector = stepScope.getScoreDirector();
3.         customPhaseCommand.changeWorkingSolution(scoreDirector);
4.         calculateWorkingStepScore(stepScope, customPhaseCommand);
5.         solver.getBestSolutionRecaller().processWorkingSolutionDuringStep(stepScope);
6.     }

复制代码

• 决定下一步
  
  
  
  • A MoveSelector which selects the possible moves of the current solution. See the chapter move and neighborhood selection.
    
  • An Acceptor which filters out unacceptable moves.
    
  • A Forager which gathers accepted moves and picks the next step from them.
    
  
  

1.   <localSearch>
2.     <unionMoveSelector>
3.       ...
4.     </unionMoveSelector>
5.     <acceptor>
6.       ...
7.     </acceptor>
8.     <forager>
9.       ...
10.     </forager>
11.   </localSearch>

复制代码

从底向上看，理解大概的move。如果是entity+value组合，或者是entity和entity进行新的组合。也许这就是叫做组合优化的原因?
chatgpt产生的一些简单代码

1. // File: pom.xml
2. <?xml version="1.0" encoding="UTF-8"?>
3. <project xmlns="http://maven.apache.org/POM/4.0.0"
4.          xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
5.          xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
6.     <modelVersion>4.0.0</modelVersion>
8.     <groupId>org.example</groupId>
9.     <artifactId>jobshop-scheduler</artifactId>
10.     <version>1.0-SNAPSHOT</version>
12.     <properties>
13.         <maven.compiler.source>17</maven.compiler.source>
14.         <maven.compiler.target>17</maven.compiler.target>
15.         <timefold.version>1.6.0</timefold.version>
16.     </properties>
18.     <dependencies>
19.         <dependency>
20.             <groupId>ai.timefold.solver</groupId>
21.             <artifactId>timefold-solver-core</artifactId>
22.             <version>${timefold.version}</version>
23.         </dependency>
24.         <dependency>
25.             <groupId>org.projectlombok</groupId>
26.             <artifactId>lombok</artifactId>
27.             <version>1.18.30</version>
28.             <scope>provided</scope>
29.         </dependency>
30.         <dependency>
31.             <groupId>ch.qos.logback</groupId>
32.             <artifactId>logback-classic</artifactId>
33.             <version>1.4.11</version>
34.         </dependency>
35.     </dependencies>
36. </project>
38. // File: src/main/resources/logback.xml
39. <?xml version="1.0" encoding="UTF-8"?>
40. <configuration>
41.     <appender name="STDOUT" class="ch.qos.logback.core.ConsoleAppender">
42.         <encoder>
43.             <pattern>%d{HH:mm:ss.SSS} [%thread] %-5level %logger{36} - %msg%n</pattern>
44.         </encoder>
45.     </appender>
47.     <logger name="ai.timefold.solver" level="info"/>
49.     <root level="warn">
50.         <appender-ref ref="STDOUT"/>
51.     </root>
52. </configuration>
54. // File: src/main/resources/solver-config.xml
55. <?xml version="1.0" encoding="UTF-8"?>
56. <solver xmlns="https://timefold.ai/xsd/solver" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
57.         xsi:schemaLocation="https://timefold.ai/xsd/solver https://timefold.ai/xsd/solver/solver.xsd">
58.     <solutionClass>org.example.jobshop.domain.JobShopSchedule</solutionClass>
59.     <entityClass>org.example.jobshop.domain.JobAllocation</entityClass>
61.     <scoreDirectorFactory>
62.         <constraintProviderClass>org.example.jobshop.solver.JobShopConstraintProvider</constraintProviderClass>
63.     </scoreDirectorFactory>
65.     <termination>
66.         <minutesSpentLimit>5</minutesSpentLimit>
67.     </termination>
69.     <constructionHeuristic>
70.         <constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType>
71.     </constructionHeuristic>
73.     <localSearch>
74.         <unionMoveSelector>
75.             <changeMoveSelector/>
76.             <swapMoveSelector/>
77.             <moveListFactory>
78.                 <moveListFactoryClass>org.example.jobshop.solver.JobAllocationMoveFactory</moveListFactoryClass>
79.             </moveListFactory>
80.         </unionMoveSelector>
81.         <acceptor>
82.             <lateAcceptanceSize>400</lateAcceptanceSize>
83.         </acceptor>
84.         <forager>
85.             <acceptedCountLimit>4</acceptedCountLimit>
86.         </forager>
87.     </localSearch>
88. </solver>
90. // File: src/main/java/org/example/jobshop/domain/Project.java
91. package org.example.jobshop.domain;
93. @lombok.Data
94. @lombok.NoArgsConstructor
95. @lombok.AllArgsConstructor
96. public class Project {
97.     private String id;
98.     private String name;
99.     private LocalDateTime releaseDate;
100.     private LocalDateTime dueDate;
101.     private List<Job> jobs;
102. }
104. // File: src/main/java/org/example/jobshop/domain/Job.java
105. package org.example.jobshop.domain;
107. @lombok.Data
108. @lombok.NoArgsConstructor
109. @lombok.AllArgsConstructor
110. public class Job {
111.     private String id;
112.     private String name;
113.     private Project project;
114.     private Duration processingTime;
115.     private List<Resource> compatibleResources;
116.     private Job previousJob;
117.     private Job nextJob;
118. }
120. // File: src/main/java/org/example/jobshop/domain/Resource.java
121. package org.example.jobshop.domain;
123. @lombok.Data
124. @lombok.NoArgsConstructor
125. @lombok.AllArgsConstructor
126. public class Resource {
127.     private String id;
128.     private String name;
129.     private ResourceType type;
130.     private LocalDateTime availableFrom;
131.     private double costPerHour;
132. }
134. // File: src/main/java/org/example/jobshop/domain/JobAllocation.java
135. package org.example.jobshop.domain;
137. @PlanningEntity
138. @lombok.Data
139. @lombok.NoArgsConstructor
140. @lombok.AllArgsConstructor
141. public class JobAllocation {
142.     private String id;
143.     private Job job;
144.    
145.     @PlanningVariable(valueRangeProvider = "resourceRange")
146.     private Resource resource;
147.    
148.     @PlanningVariable(valueRangeProvider = "allocationRange")
149.     private JobAllocation previousAllocation;
150.    
151.     @CustomShadowVariable(
152.         variableListenerClass = StartTimeUpdatingVariableListener.class,
153.         sources = {@PlanningVariableReference(variableName = "previousAllocation"),
154.                   @PlanningVariableReference(variableName = "resource")})
155.     private LocalDateTime startTime;
156.    
157.     private LocalDateTime endTime;
158.    
159.     // ... other methods from previous versions
160. }
162. // File: src/main/java/org/example/jobshop/solver/JobShopSolver.java
163. package org.example.jobshop.solver;
165. import ai.timefold.solver.core.api.solver.SolverFactory;
166. import ai.timefold.solver.core.config.solver.SolverConfig;
168. public class JobShopSolver {
169.     private final SolverFactory<JobShopSchedule> solverFactory;
171.     public JobShopSolver() {
172.         SolverConfig solverConfig = SolverConfig.createFromXmlResource(
173.                 "solver-config.xml");
174.         this.solverFactory = SolverFactory.create(solverConfig);
175.     }
177.     public JobShopSchedule solve(JobShopSchedule problem) {
178.         return solverFactory.buildSolver().solve(problem);
179.     }
180. }
182. // File: src/main/java/org/example/jobshop/Main.java
183. package org.example.jobshop;
185. public class Main {
186.     public static void main(String[] args) {
187.         // Create sample problem
188.         JobShopSchedule problem = createSampleProblem();
189.         
190.         // Create and run solver
191.         JobShopSolver solver = new JobShopSolver();
192.         JobShopSchedule solution = solver.solve(problem);
193.         
194.         // Print solution
195.         printSolution(solution);
196.     }
198.     private static JobShopSchedule createSampleProblem() {
199.         // Create resources
200.         List<Resource> resources = new ArrayList<>();
201.         resources.add(new Resource("R1", "Machine 1", ResourceType.MACHINE,
202.             LocalDateTime.now(), 100.0));
203.         resources.add(new Resource("R2", "Machine 2", ResourceType.MACHINE,
204.             LocalDateTime.now(), 150.0));
205.         
206.         // Create projects and jobs
207.         List<Project> projects = new ArrayList<>();
208.         List<JobAllocation> allocations = new ArrayList<>();
209.         
210.         Project project1 = new Project("P1", "Project 1",
211.             LocalDateTime.now(), LocalDateTime.now().plusDays(5), new ArrayList<>());
212.         
213.         // Create jobs for project 1
214.         Job job1 = new Job("J1", "Job 1", project1, Duration.ofHours(4),
215.             resources, null, null);
216.         Job job2 = new Job("J2", "Job 2", project1, Duration.ofHours(3),
217.             resources, job1, null);
218.         job1.setNextJob(job2);
219.         
220.         project1.setJobs(Arrays.asList(job1, job2));
221.         projects.add(project1);
222.         
223.         // Create allocations
224.         allocations.add(new JobAllocation("A1", job1, null, null, null, null));
225.         allocations.add(new JobAllocation("A2", job2, null, null, null, null));
226.         
227.         return new JobShopSchedule(projects, allocations, resources);
228.     }
230.     private static void printSolution(JobShopSchedule solution) {
231.         System.out.println("\nSolution found:");
232.         
233.         // Print by resource
234.         for (Resource resource : solution.getResources()) {
235.             System.out.println("\nResource: " + resource.getName());
236.             
237.             // Find all allocations for this resource and sort by start time
238.             List<JobAllocation> resourceAllocations = solution.getAllocations().stream()
239.                 .filter(a -> a.getResource() == resource)
240.                 .sorted(Comparator.comparing(JobAllocation::getStartTime))
241.                 .collect(Collectors.toList());
242.             
243.             for (JobAllocation allocation : resourceAllocations) {
244.                 System.out.printf("  %s: %s -> %s (%s)\n",
245.                     allocation.getJob().getName(),
246.                     allocation.getStartTime().format(DateTimeFormatter.ISO_LOCAL_TIME),
247.                     allocation.getEndTime().format(DateTimeFormatter.ISO_LOCAL_TIME),
248.                     allocation.getJob().getProject().getName());
249.             }
250.         }
251.         
252.         // Print by project
253.         for (Project project : solution.getProjects()) {
254.             System.out.println("\nProject: " + project.getName());
255.             
256.             List<JobAllocation> projectAllocations = solution.getAllocations().stream()
257.                 .filter(a -> a.getJob().getProject() == project)
258.                 .sorted(Comparator.comparing(JobAllocation::getStartTime))
259.                 .collect(Collectors.toList());
260.             
261.             for (JobAllocation allocation : projectAllocations) {
262.                 System.out.printf("  %s: %s on %s\n",
263.                     allocation.getJob().getName(),
264.                     allocation.getStartTime().format(DateTimeFormatter.ISO_LOCAL_TIME),
265.                     allocation.getResource().getName());
266.             }
267.         }
268.     }
269. }

复制代码

1. // Domain classes
2. @PlanningEntity
3. public class Allocation {
4.     private Job job;
5.    
6.     @PlanningVariable(valueRangeProviderRefs = "resourceRange")
7.     private Resource resource;
8.    
9.     // This is the anchor planning variable
10.     @PlanningVariable(valueRangeProviderRefs = "allocationRange")
11.     private Allocation previousAllocation;
12.    
13.     // Shadow variables that get updated automatically
14.     @CustomShadowVariable(
15.         variableListenerClass = StartTimeUpdatingVariableListener.class,
16.         sources = {@PlanningVariableReference(variableName = "previousAllocation"),
17.                   @PlanningVariableReference(variableName = "resource")})
18.     private Integer startTime;
19.    
20.     @CustomShadowVariable(
21.         variableListenerClass = EndTimeUpdatingVariableListener.class,
22.         sources = {@PlanningVariableReference(variableName = "startTime")})
23.     private Integer endTime;
24. }
26. // Move implementation for changing resources
27. public class ResourceChangeMove extends AbstractMove<JobShopSchedule> {
28.     private final Allocation allocation;
29.     private final Resource toResource;
30.    
31.     @Override
32.     protected void doMoveOnGenuineVariables(ScoreDirector<JobShopSchedule> scoreDirector) {
33.         // Step 1: Change the resource
34.         scoreDirector.beforeVariableChanged(allocation, "resource");
35.         allocation.setResource(toResource);
36.         scoreDirector.afterVariableChanged(allocation, "resource");
37.         
38.         // Step 2: Update the chain
39.         // The allocation becomes the last in the new resource's chain
40.         Allocation lastInResource = findLastAllocationInResource(toResource);
41.         
42.         scoreDirector.beforeVariableChanged(allocation, "previousAllocation");
43.         allocation.setPreviousAllocation(lastInResource);
44.         scoreDirector.afterVariableChanged(allocation, "previousAllocation");
45.     }
46. }
48. // Move implementation for sequence changes
49. public class SequenceChangeMove extends AbstractMove<JobShopSchedule> {
50.     private final Allocation allocation;
51.     private final Allocation beforeAllocation;
52.    
53.     @Override
54.     protected void doMoveOnGenuineVariables(ScoreDirector<JobShopSchedule> scoreDirector) {
55.         // Step 1: Update the chain links
56.         Allocation oldNextAllocation = allocation.getNextAllocation();
57.         Allocation oldPreviousAllocation = allocation.getPreviousAllocation();
58.         
59.         // Connect old previous and next allocations
60.         if (oldNextAllocation != null) {
61.             scoreDirector.beforeVariableChanged(oldNextAllocation, "previousAllocation");
62.             oldNextAllocation.setPreviousAllocation(oldPreviousAllocation);
63.             scoreDirector.afterVariableChanged(oldNextAllocation, "previousAllocation");
64.         }
65.         
66.         // Step 2: Insert allocation in new position
67.         Allocation newNextAllocation = beforeAllocation.getNextAllocation();
68.         
69.         scoreDirector.beforeVariableChanged(allocation, "previousAllocation");
70.         allocation.setPreviousAllocation(beforeAllocation);
71.         scoreDirector.afterVariableChanged(allocation, "previousAllocation");
72.         
73.         if (newNextAllocation != null) {
74.             scoreDirector.beforeVariableChanged(newNextAllocation, "previousAllocation");
75.             newNextAllocation.setPreviousAllocation(allocation);
76.             scoreDirector.afterVariableChanged(newNextAllocation, "previousAllocation");
77.         }
78.     }
79. }
81. // Variable Listener for updating start times
82. public class StartTimeUpdatingVariableListener
83.     implements VariableListener<JobShopSchedule, Allocation> {
84.    
85.     @Override
86.     public void afterEntityAdded(ScoreDirector<JobShopSchedule> scoreDirector,
87.                                Allocation allocation) {
88.         updateStartTime(scoreDirector, allocation);
89.     }
90.    
91.     @Override
92.     public void afterVariableChanged(ScoreDirector<JobShopSchedule> scoreDirector,
93.                                    Allocation allocation) {
94.         updateStartTime(scoreDirector, allocation);
95.     }
96.    
97.     private void updateStartTime(ScoreDirector<JobShopSchedule> scoreDirector,
98.                                Allocation allocation) {
99.         Allocation previousAllocation = allocation.getPreviousAllocation();
100.         Integer newStartTime;
101.         
102.         if (previousAllocation == null) {
103.             // First in resource - can start at 0
104.             newStartTime = 0;
105.         } else {
106.             // Must wait for previous allocation to finish
107.             newStartTime = previousAllocation.getEndTime();
108.         }
109.         
110.         // Consider job dependencies (if this job must wait for other jobs)
111.         for (Job prerequisite : allocation.getJob().getPrerequisites()) {
112.             Allocation prerequisiteAllocation = findAllocationForJob(prerequisite);
113.             if (prerequisiteAllocation != null) {
114.                 newStartTime = Math.max(newStartTime,
115.                                       prerequisiteAllocation.getEndTime());
116.             }
117.         }
118.         
119.         scoreDirector.beforeVariableChanged(allocation, "startTime");
120.         allocation.setStartTime(newStartTime);
121.         scoreDirector.afterVariableChanged(allocation, "startTime");
122.     }
123. }

复制代码

1. package org.example.jobshop.solver;
3. import ai.timefold.solver.core.api.score.director.ScoreDirector;
4. import ai.timefold.solver.core.impl.phase.custom.CustomPhaseCommand;
5. import java.util.*;
7. public class JobShopInitializer implements CustomPhaseCommand<JobShopSchedule> {
8.     @Override
9.     public void changeWorkingSolution(ScoreDirector<JobShopSchedule> scoreDirector) {
10.         JobShopSchedule schedule = scoreDirector.getWorkingSolution();
11.         
12.         // Step 1: Sort jobs by priority and dependencies
13.         List<JobAllocation> sortedAllocations = prioritizeAllocations(schedule);
14.         
15.         // Step 2: Initialize all allocations to unassigned
16.         for (JobAllocation allocation : schedule.getAllocations()) {
17.             scoreDirector.beforeVariableChanged(allocation, "resource");
18.             allocation.setResource(null);
19.             scoreDirector.afterVariableChanged(allocation, "resource");
20.             
21.             scoreDirector.beforeVariableChanged(allocation, "previousAllocation");
22.             allocation.setPreviousAllocation(null);
23.             scoreDirector.afterVariableChanged(allocation, "previousAllocation");
24.         }
26.         // Step 3: Assign jobs considering both resource and sequence constraints
27.         Map<Resource, JobAllocation> lastAllocationByResource = new HashMap<>();
28.         Map<Job, LocalDateTime> jobEndTimes = new HashMap<>();
30.         for (JobAllocation allocation : sortedAllocations) {
31.             // Find best resource and position
32.             ResourceAssignment bestAssignment = findBestAssignment(
33.                 allocation,
34.                 schedule.getResources(),
35.                 lastAllocationByResource,
36.                 jobEndTimes,
37.                 schedule);
39.             // Apply the assignment
40.             if (bestAssignment != null) {
41.                 // Assign resource
42.                 scoreDirector.beforeVariableChanged(allocation, "resource");
43.                 allocation.setResource(bestAssignment.resource);
44.                 scoreDirector.afterVariableChanged(allocation, "resource");
46.                 // Assign previous allocation
47.                 scoreDirector.beforeVariableChanged(allocation, "previousAllocation");
48.                 allocation.setPreviousAllocation(bestAssignment.previousAllocation);
49.                 scoreDirector.afterVariableChanged(allocation, "previousAllocation");
51.                 // Update tracking maps
52.                 lastAllocationByResource.put(bestAssignment.resource, allocation);
53.                 jobEndTimes.put(allocation.getJob(), bestAssignment.endTime);
54.             }
55.         }
56.     }
58.     private List<JobAllocation> prioritizeAllocations(JobShopSchedule schedule) {
59.         List<JobAllocation> sortedAllocations = new ArrayList<>(schedule.getAllocations());
60.         
61.         // Create job dependency graph
62.         Map<Job, Set<Job>> dependencies = new HashMap<>();
63.         Map<Job, Integer> inDegree = new HashMap<>();
64.         
65.         for (Project project : schedule.getProjects()) {
66.             for (Job job : project.getJobs()) {
67.                 dependencies.putIfAbsent(job, new HashSet<>());
68.                 inDegree.putIfAbsent(job, 0);
69.                
70.                 if (job.getNextJob() != null) {
71.                     dependencies.get(job).add(job.getNextJob());
72.                     inDegree.merge(job.getNextJob(), 1, Integer::sum);
73.                 }
74.             }
75.         }
77.         // Topological sort with additional priority factors
78.         sortedAllocations.sort((a1, a2) -> {
79.             Job job1 = a1.getJob();
80.             Job job2 = a2.getJob();
81.             
82.             // First priority: dependency order
83.             int dep1 = inDegree.getOrDefault(job1, 0);
84.             int dep2 = inDegree.getOrDefault(job2, 0);
85.             if (dep1 != dep2) return dep1 - dep2;
86.             
87.             // Second priority: project due date
88.             int dueDate = job1.getProject().getDueDate()
89.                 .compareTo(job2.getProject().getDueDate());
90.             if (dueDate != 0) return dueDate;
91.             
92.             // Third priority: processing time (longer first)
93.             return job2.getProcessingTime().compareTo(job1.getProcessingTime());
94.         });
95.         
96.         return sortedAllocations;
97.     }
99.     @lombok.Data
100.     @lombok.AllArgsConstructor
101.     private static class ResourceAssignment {
102.         private Resource resource;
103.         private JobAllocation previousAllocation;
104.         private LocalDateTime startTime;
105.         private LocalDateTime endTime;
106.         private double score;
107.     }
109.     private ResourceAssignment findBestAssignment(
110.             JobAllocation allocation,
111.             List<Resource> resources,
112.             Map<Resource, JobAllocation> lastAllocationByResource,
113.             Map<Job, LocalDateTime> jobEndTimes,
114.             JobShopSchedule schedule) {
115.         
116.         ResourceAssignment bestAssignment = null;
117.         double bestScore = Double.NEGATIVE_INFINITY;
119.         Job job = allocation.getJob();
120.         
121.         // Get earliest start time based on job dependencies
122.         LocalDateTime earliestStart = job.getPreviousJob() != null ?
123.             jobEndTimes.getOrDefault(job.getPreviousJob(), LocalDateTime.MIN) :
124.             LocalDateTime.now();
126.         // Try each compatible resource
127.         for (Resource resource : job.getCompatibleResources()) {
128.             JobAllocation lastAllocation = lastAllocationByResource.get(resource);
129.             
130.             // Calculate possible start time
131.             LocalDateTime startTime = calculateStartTime(
132.                 earliestStart,
133.                 lastAllocation,
134.                 resource);
135.             
136.             LocalDateTime endTime = startTime.plus(job.getProcessingTime());
137.             
138.             // Calculate assignment score
139.             double score = calculateAssignmentScore(
140.                 resource,
141.                 startTime,
142.                 endTime,
143.                 job,
144.                 schedule);
146.             if (score > bestScore) {
147.                 bestScore = score;
148.                 bestAssignment = new ResourceAssignment(
149.                     resource, lastAllocation, startTime, endTime, score);
150.             }
151.         }
153.         return bestAssignment;
154.     }
156.     private LocalDateTime calculateStartTime(
157.             LocalDateTime earliestStart,
158.             JobAllocation lastAllocation,
159.             Resource resource) {
160.         
161.         LocalDateTime resourceAvailable = lastAllocation != null ?
162.             lastAllocation.getEndTime() :
163.             resource.getAvailableFrom();
164.             
165.         return earliestStart.isAfter(resourceAvailable) ?
166.             earliestStart : resourceAvailable;
167.     }
169.     private double calculateAssignmentScore(
170.             Resource resource,
171.             LocalDateTime startTime,
172.             LocalDateTime endTime,
173.             Job job,
174.             JobShopSchedule schedule) {
175.         
176.         double score = 0.0;
177.         
178.         // Factor 1: Resource utilization balance
179.         score -= getResourceUtilization(resource, schedule) * 2;
180.         
181.         // Factor 2: Start time (earlier is better)
182.         score -= startTime.until(job.getProject().getDueDate(), ChronoUnit.HOURS);
183.         
184.         // Factor 3: Resource cost
185.         score -= resource.getCostPerHour() *
186.             job.getProcessingTime().toHours();
187.         
188.         // Factor 4: Project critical path consideration
189.         if (isOnCriticalPath(job)) {
190.             score += 1000;  // Prioritize critical path jobs
191.         }
192.         
193.         return score;
194.     }
196.     private double getResourceUtilization(Resource resource, JobShopSchedule schedule) {
197.         return schedule.getAllocations().stream()
198.             .filter(a -> a.getResource() == resource)
199.             .mapToDouble(a -> a.getJob().getProcessingTime().toHours())
200.             .sum();
201.     }
203.     private boolean isOnCriticalPath(Job job) {
204.         // Simple critical path detection
205.         Job current = job;
206.         while (current.getNextJob() != null) {
207.             current = current.getNextJob();
208.         }
209.         return current.getProject().getDueDate()
210.             .minusHours(calculatePathDuration(job))
211.             .isBefore(LocalDateTime.now());
212.     }
214.     private long calculatePathDuration(Job startJob) {
215.         long duration = 0;
216.         Job current = startJob;
217.         while (current != null) {
218.             duration += current.getProcessingTime().toHours();
219.             current = current.getNextJob();
220.         }
221.         return duration;
222.     }
223. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。