OptaPlanner examples その11

OptaPlanner

Exam timetabling


http://docs.jboss.org/optaplanner/release/latest/optaplanner-docs/html_single/index.html#examination

ここから "Difficult examples" です。どんだけ difficult なのかドキドキしますね。

試験を部屋と時間に割り当てる問題です。Course timetabling に似てますね。今回は生徒もモデル化されています。

The problem is defined by the International Timetabling Competition 2007 track 1 (http://www.cs.qub.ac.uk/itc2007/examtrack/exam_track_index.htm). Geoffrey De Smet finished 4th in that competition with a very early version of OptaPlanner. Many improvements have been made since then.

だそうですよ！

  • Examination : @PlanningSolution
  • LeadingExam : @PlanningEntity
    • Room : @PlanningVariable
    • Period : @PlanningVariable
    • Topic topic
  • FollowingExam : @PlanningEntity
    • Room : @PlanningVariable
    • Period : @CustomShadowVariable
    • LeadingExam leadingExam
    • Topic topic

@PlanningEntity であるところの Exam は abstract クラスです。実際にはその2つのサブクラス LeadingExam と FollowingExam が使われます。これは hard 制約の「指定の Exam は同じ Period に行わなければいけない(Coincidence)」が適用されるときに 一つを LeadingExam に、その他を FollowingExam とします。FollowingExam の period は LeadingExam の period から演繹できる(ていうか同値)ので @CustomShadowVariable です。

examinationSolverConfig.xml が difficult ですよ、コレ。

  <constructionHeuristic>
    <queuedEntityPlacer>
      <entitySelector id="placerEntitySelector">
        <entityClass>org.optaplanner.examples.examination.domain.Exam</entityClass>
        <cacheType>PHASE</cacheType>
        <selectionOrder>SORTED</selectionOrder>
        <sorterManner>DECREASING_DIFFICULTY</sorterManner>
      </entitySelector>
      <cartesianProductMoveSelector>
        <changeMoveSelector>
          <entitySelector mimicSelectorRef="placerEntitySelector"/>
          <valueSelector>
            <downcastEntityClass>org.optaplanner.examples.examination.domain.LeadingExam</downcastEntityClass>
            <variableName>period</variableName>
            <cacheType>PHASE</cacheType>
            <!--<selectionOrder>SORTED</selectionOrder>-->
            <!--<sorterManner>INCREASING_STRENGTH</sorterManner>-->
          </valueSelector>
        </changeMoveSelector>
        <changeMoveSelector>
          <entitySelector mimicSelectorRef="placerEntitySelector"/>
          <valueSelector>
            <variableName>room</variableName>
            <cacheType>PHASE</cacheType>
            <selectionOrder>SORTED</selectionOrder>
            <sorterManner>INCREASING_STRENGTH</sorterManner>
          </valueSelector>
        </changeMoveSelector>
      </cartesianProductMoveSelector>
    </queuedEntityPlacer>
  </constructionHeuristic>

いままでは built-in の ConstructionHeuristic を使ってきましたが、今回はカスタマイズを行います。ここ読んでおいた方がいいです http://docs.jboss.org/optaplanner/release/latest/optaplanner-docs/html_single/index.html#allocateEntityFromQueue

は普通に DECREASING_DIFFICULTY。

@PlanningVariable が2つあるので、それぞれに を設定し、 で囲む。period は LeadingExam にしかないので する。

このカスタマイズは @PlanningEntity が複数あるため必要になったようです。FIRST_FIT_DECREASING を指定するとどの Entity か分からないよって怒られた。

  <localSearch>
    <unionMoveSelector>
      <cartesianProductMoveSelector>
        <changeMoveSelector>
          <entitySelector id="cartesianProductEntitySelector">
            <entityClass>org.optaplanner.examples.examination.domain.Exam</entityClass>
          </entitySelector>
          <valueSelector>
            <variableName>room</variableName>
          </valueSelector>
        </changeMoveSelector>
        <changeMoveSelector>
          <entitySelector mimicSelectorRef="cartesianProductEntitySelector"/>
          <valueSelector>
            <downcastEntityClass>org.optaplanner.examples.examination.domain.LeadingExam</downcastEntityClass>
            <variableName>period</variableName>
          </valueSelector>
        </changeMoveSelector>
      </cartesianProductMoveSelector>
      <swapMoveSelector>
        <entitySelector>
          <entityClass>org.optaplanner.examples.examination.domain.LeadingExam</entityClass>
        </entitySelector>
      </swapMoveSelector>
    </unionMoveSelector>
    <acceptor>
      <entityTabuSize>10</entityTabuSize>
    </acceptor>
    <forager>
      <acceptedCountLimit>2000</acceptedCountLimit>
    </forager>
  </localSearch>

こちらもそれほど特別なことはやってないですね。 では LeadingExam だけを swap します。なぜなら FollowingExam は LeadingExam に合わせて period を変更するから。