tokobayashiの日記 このページをアンテナに追加 RSSフィード

2015-03-05 予定管理

シュワンクマイエル  シュワンクマイエルを含むブックマーク

サヴァイヴィング ライフ

3/7(土)-3/13(金) 18:30~

シアター・イメージフォーラム

http://svank2015.jimdo.com/

シュヴァンクマイエル作品トリビュート展/プラハの憂鬱・ルドル二世へのレクイエム

第一期●2015年3月07日[土]〜4月13日[月]

第二期●2015年4月17日[金]〜5月11日[月]

■月〜金/13:00〜20:00 土日祝/12:00〜19:00

展覧会 会場:parabolica-bis[パラボリカ・ビス]

http://www.yaso-peyotl.com/archives/2015/01/1503jsm.html

ヒティロヴァ  ヒティロヴァを含むブックマーク

ひなぎく

シアター・イメージフォーラム

 2015年3月7日(土)〜20日(金)

 (レイトショー/ 連日21:15上映)

http://hinagiku2014.jimdo.com/

三原順  三原順を含むブックマーク

復活祭

■会場:米沢嘉博記念図書館1階展示コーナー

■期間:2015年2月6日(金)-5月31日(日)

 休館日:毎週火・水・木曜日祝日は開館)

◎第一期:2月6日(金)-3月2日(月)

 グレアムと「はみだしっ子特集

◎第二期:3月6日(金)-4月6日(月)

 アンジーと初期短編特集

◎第三期:4月10日(金)-4月29日(水・祝)

 サーニンと「ルーソロモン」「ムーン・ライティング」「Sons」

◎第四期:5月1日(金)-5月31日(日)

 マックスと「X Day」ほか後期作品特集

http://www.meiji.ac.jp/manga/yonezawa_lib/exh-miharajun.html

トラックバック - http://d.hatena.ne.jp/tokobayashi/20150305

2015-03-04 OptaPlanner examples その12

[]OptaPlanner examples その12 OptaPlanner examples その12を含むブックマーク

Employee rostering

f:id:tokobayashi:20150303224101p:image

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

従業員シフト最適化です。"Nurse Rostering Competition" ていう競技があって (http://www.kuleuven-kulak.be/nrpcompetition)、その問題実装しています

  • NurseRoster : @PlanningSolution
  • ShiftAssignment : @PlanningEntity
    • Employee : @PlanningVariable
    • Shift shift
    • int indexInShift

@PlanningEntity、@PlanningVariable がひとつずつなので比較シンプルです。Skill や Contract など Employee に関する属性はいろいろあって、制約に使われますSoft制約がかなりたくさんある。。。けど特筆するものは無いかな。

<localSearch> では <moveListFactory> が使われています

  <localSearch>
    <unionMoveSelector>
      <moveListFactory>
        <cacheType>PHASE</cacheType>
        <moveListFactoryClass>org.optaplanner.examples.nurserostering.solver.move.factory.EmployeeChangeMoveFactory</moveListFactoryClass>
      </moveListFactory>
      <moveListFactory>
        <cacheType>PHASE</cacheType>
        <moveListFactoryClass>org.optaplanner.examples.nurserostering.solver.move.factory.ShiftAssignmentSwapMoveFactory</moveListFactoryClass>
      </moveListFactory>
      <moveListFactory>
        <cacheType>STEP</cacheType>
        <moveListFactoryClass>org.optaplanner.examples.nurserostering.solver.move.factory.ShiftAssignmentPillarPartSwapMoveFactory</moveListFactoryClass>
      </moveListFactory>
      <!--<moveListFactory>-->
        <!--<cacheType>STEP</cacheType>-->
        <!--<moveListFactoryClass>org.optaplanner.examples.nurserostering.solver.move.factory.ShiftAssignmentSequenceSwitchLength2MoveFactory</moveListFactoryClass>-->
      <!--</moveListFactory>-->
      <!--<moveListFactory>-->
        <!--<cacheType>STEP</cacheType>-->
        <!--<moveListFactoryClass>org.optaplanner.examples.nurserostering.solver.move.factory.ShiftAssignmentSequenceSwitchLength3MoveFactory</moveListFactoryClass>-->
      <!--</moveListFactory>-->
    </unionMoveSelector>
    <acceptor>
      <entityTabuSize>7</entityTabuSize>
    </acceptor>
    <forager>
      <acceptedCountLimit>800</acceptedCountLimit>
    </forager>
  </localSearch>

<moveListFactory> は単純に <moveListFactoryClass> で指定したクラスMove の List を返させます

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

指定された EmployeeChangeMoveFactory, ShiftAssignmentSwapMoveFactory, ShiftAssignmentPillarPartSwapMoveFactory は基本的に MovableShiftAssignmentSelectionFilter を使って isInPlanningWindow、つまり現在プランニング対象の期間のシフトだけ、Move対象にしています

あと、ShiftAssignmentPillarPartSwapMoveFactory は複雑です。。。ぐぬぬ、自信が無いが、同じ Employee のシフトをまとめて動かして CompositeMove にしているようです。

トラックバック - http://d.hatena.ne.jp/tokobayashi/20150304

2015-03-03 OptaPlanner examples その11

[]OptaPlanner examples その11 OptaPlanner examples その11を含むブックマーク

Exam timetabling

f:id:tokobayashi:20150302192324p:image

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

<entitySelector> は普通に DECREASING_DIFFICULTY。

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

このカスタマイズは @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>

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

トラックバック - http://d.hatena.ne.jp/tokobayashi/20150303

2015-03-02 OptaPlanner examples その10

[]OptaPlanner examples その10 OptaPlanner examples その10を含むブックマーク

Hospital bed planning

f:id:tokobayashi:20150301172845p:image

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

患者を病室のベッドに割り当てます患者によっては特別設備必要だったり、別性の患者は同じ部屋には割り当てない、など。ディナーパーティーexampleに似てますね。

  • PatientAdmissionSchedule : @PlanningSolution
  • BedDesignation : @PlanningEntity
    • Bed bed : @PlanningVariable(nullable = true)
    • AdmissionPart admissionPart

AdmissionPart は患者(Patient)と滞在日程(firstNight,lastNight)と専門分野(Specialism)をラップしたもの。Specialism は Patient の属性じゃないの?と思ったけど、「この期間は外科でこの期間はリハビリ科」みたいな感じかな。AdmissionPart は 固定なので、PlanningVariable は Bed だけ。

今回の新ネタは overconstrained.

http://d.hatena.ne.jp/tokobayashi/20150113ちょっと書いたけど、「制約が厳しすぎて解が得られない」ような問題場合、PlanningVariable が null になるのを許容する。@PlanningVariable(nullable = true) とする。

"4.3.4.2. Nullable planning variable" http://docs.jboss.org/optaplanner/release/latest/optaplanner-docs/html_single/index.html#planningVariable

PlanningVariable である Bed が null でもよい。つまり、患者が路頭に迷ってもいいということですね。他の病院たらい回しでもするのだろう。いちおう Medium scoreスコアはしておきます

rule "assignEveryPatientToABed"
    when
        $bedDesignation : BedDesignation(bed == null)
    then
        scoreHolder.addMediumConstraintMatch(kcontext, - $bedDesignation.getAdmissionPartNightCount());
end

サンプルでは overconstrained01.xml で動作を確認できます。Unassigned な患者がいっぱいいますけど、病院ベストを尽くすのです。

トラックバック - http://d.hatena.ne.jp/tokobayashi/20150302

2015-03-01 OptaPlanner examples その9

[]OptaPlanner examples その9 OptaPlanner examples その9を含むブックマーク

Project job scheduling

f:id:tokobayashi:20150301001650p:image

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

プロジェクトWBSガントチャートにし、依存関係/リソース考慮して最適な順序に並べる。あー、むかし人力でやってたなー。 MISTA 2013 challenge の課題だそうです http://allserv.kahosl.be/mista2013challenge/

  • Schedule : @PlanningSolution
  • Allocation : @PlanningEntity
    • ExecutionMode executionMode : @PlanningVariable
    • Integer delay : @PlanningVariable

またちょっと語彙が分かりにくい。Project を分割したのが Job で、その Job を何日間実行するか(duration)、をラップしたのが ExecutionMode (Modeって感じじゃないよなー)。開始までの日にち(delay)と ExecutionMode の組み合わせ(共にPlanningVariable)を保持するのが Allocation です。Allocation は他に predecessorAllocationList (先行配置リスト)、successorAllocationList(後行配置リスト)、sourceAllocation(開始配置)、sinkAllocation(終了配置)を持っています。これらは静的な条件から得られるので PlanningVariable ではないです。

今回は <scoreDirectorFactory> で新ネタがあります

  <scoreDirectorFactory>
    <scoreDefinitionType>BENDABLE</scoreDefinitionType>
    <bendableHardLevelsSize>1</bendableHardLevelsSize>
    <bendableSoftLevelsSize>2</bendableSoftLevelsSize>
    <incrementalScoreCalculatorClass>org.optaplanner.examples.projectjobscheduling.solver.score.ProjectJobSchedulingIncrementalScoreCalculator</incrementalScoreCalculatorClass>
    <!--<scoreDrl>org/optaplanner/examples/projectjobscheduling/solver/projectJobSchedulingScoreRules.drl</scoreDrl>-->
  </scoreDirectorFactory>

BENDABLE を指定すると、Hard / Soft score をそれぞれ複数レベル(=種類)持つことができます。この場合は2レベル(=種類)の Soft score を持ち、個別スコアadd できますhttp://docs.jboss.org/optaplanner/release/latest/optaplanner-docs/html_single/index.html#bendableScore

DRLの例:第二引数の '1' がレベルを表しますスコア比較時は、レベルが小さい方が優先されます。つまり、HardMediumSoft の3段階よりさらに柔軟に設定できるということです。

scoreHolder.addSoftConstraintMatch(kcontext, 1, -$maxProjectEndDate.intValue());

また、今回のサンプルはデフォルトで DRL ではなく、incrementalScoreCalculatorClass を使っています。ProjectJobSchedulingIncrementalScoreCalculator を見ればよいのですが、コメントアウトされている projectJobSchedulingScoreRules.drl と見比べると。。。やっぱり DRL のほうが分かりやすいですね。ワーキングメモリ内のエンティティを変化させながらベストスコアを狙う LocalSearch の考え方が Droolsマッチしてるんだなあと思うのでした。incrementalScoreCalculatorClass では、そのステートフルな動作を自前のコード保証しないといけない。

トラックバック - http://d.hatena.ne.jp/tokobayashi/20150301