任务计划卡住了 [英] Task scheduling gets stuck

问题描述

我目前正在尝试掌握OptaPlanner，因为它似乎是

I am currently trying to get my grip on OptaPlanner as it seems to be the perfect solution for a problem I have.

基本上项目作业计划

Basically the Project job scheduling example is what I am going for, but as I only know my Java basics this is way to complex to start with. So I am trying to start with a very limited example and work my way up from there:

我有一个任务，任务的持续时间和一个已定义的前任. 计划实体是每个任务开始的时间.

I have tasks with a duration and one defined predecessor. The planning entity is the time each task starts.

我的成绩很差，可以惩罚在其前身的启动时间+持续时间之前开始的任务.我还有一个软评分，试图缩小差距，使整个过程尽可能短.

I have a hard score that punishes tasks starting before starttime+duration of its predecessor. I also have a soft score that tries to reduce gaps, keeping the overall process as short as possible.

public HardSoftScore calculateScore(Schedule schedule) {
    int hardScore = 0;
    int softScore = 0;

    for (Task task : schedule.getTaskList()) {
        int endTime = task.getAllocation().getStartTime() + task.getDuration();
        softScore = -endTime;

        for (Task task2 : schedule.getTaskList()) {
            if(task.getId()!=task2.getId()){
                if( task2.getPredecessorId()==task.getId()) {
                    if (endTime > task2.getAllocation().getStartTime()) {
                        hardScore += task2.getAllocation().getStartTime() - endTime;
                    }
                }
            }
        }
    }

    return HardSoftScore.valueOf(hardScore, softScore);

}

这是求解器配置:

<?xml version="1.0" encoding="UTF-8"?>
<solver>
    <!--<environmentMode>FAST_ASSERT</environmentMode>-->

    <!-- Domain model configuration -->
    <solutionClass>com.foo.scheduler.domain.Schedule</solutionClass>
    <planningEntityClass>com.foo.scheduler.domain.Task</planningEntityClass>

    <!-- Score configuration -->
    <scoreDirectorFactory>
        <scoreDefinitionType>HARD_SOFT</scoreDefinitionType>
        <simpleScoreCalculatorClass>com.foo.scheduler.solver.score.SchedulingSimpleScoreCalculator</simpleScoreCalculatorClass>
    </scoreDirectorFactory>

    <!-- Optimization algorithms configuration -->
    <termination>
        <maximumSecondsSpend>100</maximumSecondsSpend>
    </termination>
    <constructionHeuristic>
        <constructionHeuristicType>FIRST_FIT</constructionHeuristicType>
    </constructionHeuristic>
    <localSearch>
        <acceptor>
            <entityTabuSize>7</entityTabuSize>
        </acceptor>
        <forager>
            <acceptedCountLimit>1000</acceptedCountLimit>
        </forager>
    </localSearch>
</solver>

问题是，只要我只有硬分，这就会很好用.但是，当然有差距.一旦添加软分数，一切都会在大约10个步骤后卡住.为什么?

[...]
2014-05-03 20:01:31,966 [main] DEBUG     Step index (10), time spend (495), score (-35hard/-66soft),     best score (-34hard/-68soft), accepted/selected move count (1000/19884) for picked step (com.foo.scheduler.domain.Task@35480096 => com.foo.scheduler.domain.Allocation@f9a4520).
2014-05-03 20:03:11,471 [main] DEBUG     Step index (11), time spend (100000), score (-35hard/-65soft),     best score (-34hard/-68soft), accepted/selected move count (0/105934687) for picked step (com.foo.scheduler.domain.Task@7050c91f => com.foo.scheduler.domain.Allocation@47c44bd4).

推荐答案

在步骤11中选择的移动计数105934687清楚地表明未接受任何移动.我不知道软分怎么会触发它.只有1种解释:

A selected move count of 105934687 at step 11 clearly indicates that no move is being accepted. I don't see how a soft score could trigger that though. There is only 1 explanation:

• EntityTabuAcceptor不接受任何举动，因为它们都是禁忌，这意味着每个举动的计划实体都在禁忌列表中.如果您的数据集非常小(14或更少的计划实体)，则可以这样做. 打开TRACE日志记录，日志将对此进行确认.

• The EntityTabuAcceptor doesn't accept any move, because they are all tabu, which means every move's planning entities are in the tabu list. This is possible if you have very small dataset (14 or less planning entities). Turn on TRACE logging and the log will confirm this.

这些变通办法中的每一个都应解决以下问题:

Each of these workaround should fix that:

• 使用后期验收

<acceptor>
  <lateAcceptanceSize>400</lateAcceptanceSize>
</acceptor>
<forager>
  <acceptedCountLimit>1</acceptedCountLimit>
</forager>

使用<entityTabuRatio>代替<entityTabuSize>

根据具有SolverFactory.getSolverConfig()的数据集大小，缺少<entityTabuSize>.不推荐！

Mess with the <entityTabuSize> based on the dataset size with SolverFactory.getSolverConfig(). Not recommended!

为什么计划实体少于14个?

Why less than 14 planning entities?

因为默认情况下，您会得到一个<changeMoveSelector>和一个<swapMoveSelector>. <swapMoveSelector>交换2个实体，如果赢得一个步骤，则两个都禁忌.禁忌列表的大小是步骤数，因此，如果连续有7个交换动作赢得了这些步骤，则禁忌列表中可能有14个实体.

Because by default you get a <changeMoveSelector> and a <swapMoveSelector>. The <swapMoveSelector> swaps 2 entities, making both tabu if it wins a step. The tabu list size is the number of steps, so if 7 swap moves win the steps in a row, there can be 14 entities in the tabu list.

这篇关于任务计划卡住了的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！