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

抽象层次非常好，广义优化工具。用于排产没有复杂的落地示例

• 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

基本概念

• PlanningSolution
  • 定义Problem，以及解
• planning entity
  • Allocation
• planing variable
  • executionMode
  • delay
• shadow variable
  • predecessorsDoneDate
  • https://www.optaplanner.org/docs/optaplanner/latest/shadow-variable/shadow-variable.html
• planning score
• 核心的优化算法

约束

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

import org.timefold.solver.core.api.score.buildin.hardsoft.HardSoftScore;
import org.timefold.solver.core.api.score.stream.ConstraintProvider;
import org.timefold.solver.core.api.score.stream.Constraint;
import org.timefold.solver.core.api.score.stream.ConstraintStream;
import org.timefold.solver.core.api.score.stream.Joiners;public class JobShopConstraintProvider implements ConstraintProvider {@Overridepublic Constraint[] defineConstraints(ConstraintFactory constraintFactory) {return new Constraint[] {// Ensure operations follow the sequence within each jobconstraintFactory.from(Operation.class).join(Operation.class, Joiners.filteringEach(otherOp -> otherOp.getJob().equals(op.getJob()) && otherOp.getSequence() == op.getSequence() + 1)).penalize("Operations must follow sequence",HardSoftScore.ONE_HARD,(op, otherOp) -> 1),// Ensure machine constraints are respectedconstraintFactory.from(Operation.class).join(Operation.class, Joiners.filteringEach((op1, op2) ->op1.getMachine().equals(op2.getMachine()) &&op1.getEndTime() > op2.getStartTime() &&op1.getStartTime() < op2.getEndTime() &&!op1.equals(op2))).penalize("Machine cannot process two operations at once",HardSoftScore.ONE_HARD,(op1, op2) -> 1)};}
}

官方示例

入口在APP的main

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

init

public void init() {init(null, true);}public void init(Component centerForComponent, boolean exitOnClose) {solutionBusiness = createSolutionBusiness();solverAndPersistenceFrame = new SolverAndPersistenceFrame<>(solutionBusiness, createSolutionPanel(),createExtraActions());solverAndPersistenceFrame.setDefaultCloseOperation(exitOnClose ? WindowConstants.EXIT_ON_CLOSE : WindowConstants.DISPOSE_ON_CLOSE);solverAndPersistenceFrame.init(centerForComponent);solverAndPersistenceFrame.setVisible(true);}

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

public SolutionBusiness<Solution_, ?> createSolutionBusiness() {SolutionBusiness<Solution_, ?> solutionBusiness = new SolutionBusiness<>(this,SolverFactory.createFromXmlResource(solverConfigResource));solutionBusiness.setDataDir(determineDataDir(dataDirName));solutionBusiness.setSolutionFileIO(createSolutionFileIO());solutionBusiness.setImporters(createSolutionImporters());solutionBusiness.setExporters(createSolutionExporters());solutionBusiness.updateDataDirs();return solutionBusiness;}

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

package org.optaplanner.examples.projectjobscheduling.domain;import java.util.List;import org.optaplanner.core.api.domain.solution.PlanningEntityCollectionProperty;
import org.optaplanner.core.api.domain.solution.PlanningScore;
import org.optaplanner.core.api.domain.solution.PlanningSolution;
import org.optaplanner.core.api.domain.solution.ProblemFactCollectionProperty;
import org.optaplanner.core.api.score.buildin.hardmediumsoft.HardMediumSoftScore;
import org.optaplanner.examples.common.domain.AbstractPersistable;
import org.optaplanner.examples.projectjobscheduling.domain.resource.Resource;@PlanningSolution
public class Schedule extends AbstractPersistable {private List<Project> projectList;private List<Job> jobList;private List<ExecutionMode> executionModeList;private List<Resource> resourceList;private List<ResourceRequirement> resourceRequirementList;private List<Allocation> allocationList;private HardMediumSoftScore score;public Schedule() {}public Schedule(long id) {super(id);}@ProblemFactCollectionPropertypublic List<Project> getProjectList() {return projectList;}public void setProjectList(List<Project> projectList) {this.projectList = projectList;}@ProblemFactCollectionPropertypublic List<Job> getJobList() {return jobList;}public void setJobList(List<Job> jobList) {this.jobList = jobList;}@ProblemFactCollectionPropertypublic List<ExecutionMode> getExecutionModeList() {return executionModeList;}public void setExecutionModeList(List<ExecutionMode> executionModeList) {this.executionModeList = executionModeList;}@ProblemFactCollectionPropertypublic List<Resource> getResourceList() {return resourceList;}public void setResourceList(List<Resource> resourceList) {this.resourceList = resourceList;}@ProblemFactCollectionPropertypublic List<ResourceRequirement> getResourceRequirementList() {return resourceRequirementList;}public void setResourceRequirementList(List<ResourceRequirement> resourceRequirementList) {this.resourceRequirementList = resourceRequirementList;}@PlanningEntityCollectionPropertypublic List<Allocation> getAllocationList() {return allocationList;}public void setAllocationList(List<Allocation> allocationList) {this.allocationList = allocationList;}@PlanningScorepublic HardMediumSoftScore getScore() {return score;}public void setScore(HardMediumSoftScore score) {this.score = score;}// ************************************************************************// Complex methods// ************************************************************************}

Timefold 示例

Solver job接受到problem，开始run

@Deprecated(forRemoval = true, since = "1.6.0")default SolverJob<Solution_, ProblemId_> solve(ProblemId_ problemId,Solution_ problem, Consumer<? super Solution_> finalBestSolutionConsumer,BiConsumer<? super ProblemId_, ? super Throwable> exceptionHandler) {SolverJobBuilder<Solution_, ProblemId_> builder = solveBuilder().withProblemId(problemId).withProblem(problem);if (finalBestSolutionConsumer != null) {builder.withFinalBestSolutionConsumer(finalBestSolutionConsumer);}if (exceptionHandler != null) {builder.withExceptionHandler(exceptionHandler);}return builder.run();}

solverStatus = SolverStatus.SOLVING_ACTIVE;// Create the consumer thread pool only when this solver job is active.consumerSupport = new ConsumerSupport<>(getProblemId(), bestSolutionConsumer, finalBestSolutionConsumer,firstInitializedSolutionConsumer, exceptionHandler, bestSolutionHolder);Solution_ problem = problemFinder.apply(problemId);// add a phase lifecycle listener that unlock the solver status lock when solving startedsolver.addPhaseLifecycleListener(new UnlockLockPhaseLifecycleListener());// add a phase lifecycle listener that consumes the first initialized solutionsolver.addPhaseLifecycleListener(new FirstInitializedSolutionPhaseLifecycleListener(consumerSupport));solver.addEventListener(this::onBestSolutionChangedEvent);final Solution_ finalBestSolution = solver.solve(problem);consumerSupport.consumeFinalBestSolution(finalBestSolution);return finalBestSolution;

理解

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

• build_solver/ default_solver_factory

    public Solver<Solution_> buildSolver(SolverConfigOverride<Solution_> configOverride) {Objects.requireNonNull(configOverride, "Invalid configOverride (null) given to SolverFactory.");var isDaemon = Objects.requireNonNullElse(solverConfig.getDaemon(), false);var solverScope = new SolverScope<Solution_>();var monitoringConfig = solverConfig.determineMetricConfig();solverScope.setMonitoringTags(Tags.empty());var metricsRequiringConstraintMatchSet = Collections.<SolverMetric> emptyList();if (!monitoringConfig.getSolverMetricList().isEmpty()) {solverScope.setSolverMetricSet(EnumSet.copyOf(monitoringConfig.getSolverMetricList()));metricsRequiringConstraintMatchSet = solverScope.getSolverMetricSet().stream().filter(SolverMetric::isMetricConstraintMatchBased).filter(solverScope::isMetricEnabled).toList();} else {solverScope.setSolverMetricSet(EnumSet.noneOf(SolverMetric.class));}var environmentMode = solverConfig.determineEnvironmentMode();var constraintMatchEnabled = !metricsRequiringConstraintMatchSet.isEmpty() || environmentMode.isAsserted();if (constraintMatchEnabled && !environmentMode.isAsserted()) {LOGGER.info("Enabling constraint matching as required by the enabled metrics ({}). This will impact solver performance.",metricsRequiringConstraintMatchSet);}var innerScoreDirector = scoreDirectorFactory.buildScoreDirector(true, constraintMatchEnabled);solverScope.setScoreDirector(innerScoreDirector);solverScope.setProblemChangeDirector(new DefaultProblemChangeDirector<>(innerScoreDirector));var moveThreadCount = resolveMoveThreadCount(true);var bestSolutionRecaller = BestSolutionRecallerFactory.create().<Solution_> buildBestSolutionRecaller(environmentMode);var randomFactory = buildRandomFactory(environmentMode);var configPolicy = new HeuristicConfigPolicy.Builder<>(environmentMode,moveThreadCount,solverConfig.getMoveThreadBufferSize(),solverConfig.getThreadFactoryClass(),solverConfig.getNearbyDistanceMeterClass(),randomFactory.createRandom(),scoreDirectorFactory.getInitializingScoreTrend(),solutionDescriptor,ClassInstanceCache.create()).build();var basicPlumbingTermination = new BasicPlumbingTermination<Solution_>(isDaemon);var termination = buildTerminationConfig(basicPlumbingTermination, configPolicy, configOverride);var phaseList = buildPhaseList(configPolicy, bestSolutionRecaller, termination);return new DefaultSolver<>(environmentMode, randomFactory, bestSolutionRecaller, basicPlumbingTermination,termination, phaseList, solverScope,moveThreadCount == null ? SolverConfig.MOVE_THREAD_COUNT_NONE : Integer.toString(moveThreadCount));}

solver的主流程

@Overridepublic final Solution_ solve(Solution_ problem) {if (problem == null) {throw new IllegalArgumentException("The problem (" + problem + ") must not be null.");}// No tags for these metrics; they are globalLongTaskTimer solveLengthTimer = Metrics.more().longTaskTimer(SolverMetric.SOLVE_DURATION.getMeterId());Counter errorCounter = Metrics.counter(SolverMetric.ERROR_COUNT.getMeterId());solverScope.setBestSolution(problem);solverScope.setSolver(this);outerSolvingStarted(solverScope);boolean restartSolver = true;while (restartSolver) {LongTaskTimer.Sample sample = solveLengthTimer.start();try {// solvingStarted will call registerSolverSpecificMetrics(), since// the solverScope need to be fully initialized to calculate the// problem's scale metricssolvingStarted(solverScope);runPhases(solverScope);solvingEnded(solverScope);} catch (Exception e) {errorCounter.increment();solvingError(solverScope, e);throw e;} finally {sample.stop();unregisterSolverSpecificMetrics();}restartSolver = checkProblemFactChanges();}outerSolvingEnded(solverScope);return solverScope.getBestSolution();}

• run_phase /abstract_solver

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

• solver外面的phase, PhaseFactory

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

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

• 决定下一步
  • 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.

  <localSearch><unionMoveSelector>...</unionMoveSelector><acceptor>...</acceptor><forager>...</forager></localSearch>

从底向上看，理解可能的move。如果是entity+value组合，或者是entity和entity进行新的组合。也许这就是叫做组合优化的原因?