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

2015-04-13 フランス語

フランス語  フランス語を含むブックマーク

メール

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

2015-04-01 Repeated Planning

[]Repeated Planning Repeated Planningを含むブックマーク

ここ、ちょっと掘り下げます

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

長期的に Solver を回しっぱなしのときに、problem facts が変化したらどうするのか?3つのパターンが考えられる。

Backup planning

まず、バックアップ考慮に入れて制約を作っておく。スペア従業員、予備ベッドなど。

変化が起こった時(従業員病気になる)、problem facts / planning entities を変更(従業員delete, シフトを空ける)し、プランニングを再開する。このとき、その時点の solution から再開する。変化したので、スコアも変わったはず。construction heuristics は変化により発生したギャップシフトの空き)を埋める(スペア従業員で)。metaheuristics で更に改善する。

ポイント:この一連の動作をどのようなコードでやる? うーん、examples を見る限り(Nurse rostering で、Employee を GUI から delete したり、advance 1 day したり)、全部後述の ProblemFactChange でやってるように見える。

質問しました。

http://stackoverflow.com/questions/29410015/repeated-planning-without-problemfactchange

Continuous planning (windowed planning)

100年分のシフトプランしても仕方ないですね。一定期間(planning windows)、例えば4週間分だけプランし、それを継続的に(例えば1日ごとに)プランすればよい。過去分のプランの planning entities は変更不可能だが、スコア制約に使うかもしれない(「続けて5日働いては行けない」とか)ので、まだ Solution に入っている。

Immovable planning entities

SelectionFilter を使って、「期間外のMoveは動かさない」を実装します。@PlanningEntity(movableEntitySelectionFilter = ... ) で指定します。

Nonvolatile replanning (semi movable planning entities)

継続的プランニングでは「既存の状態からあんまり変えたくない」という要求もありえます。その場合、単純にスコア制約を追加すればいい。


Real-time planning

まず基本的な考えとしては、短い planning window で Continuous planning やるってこと。実装テクニックとして、以下がある。

ProblemFactChange

Solver が動いているときは、外部から problem fact を変更してはいけない。ProblemFactChange を使う。ProblemFactChange を実装して、solver.addProblemFactChange()で渡してやると、Solver が適切なタイミングで変更を反映してくれる。

コード例、Warning/Important/Note をよく読もう。problem fact list は自分で Shallow clone している。

実際は Solver は stop し、ProblemFactChange を実行し、restart する。よって、construction heuristic を再実行する。ただし、既存の solution から続けるため、遅くはならない。

Daemon: solve() does not return

Solver を daemon モードで走らせる。

org.optaplanner.examples.cloudbalancing.app.CloudBalancingDaemonTest が参考になるはず。

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

2015-03-19 HttpURLConnection

[]HttpURLConnection HttpURLConnectionを含むブックマーク

OpenJDK 1.7.0_75 で調べた。

http のとき URL.openConnection() で返って来るのは sun.net.www.protocol.http.HttpURLConnection。

HttpURLConnection.connect() で、sun.net.www.http.HttpClient を生成、保持する。Socket の管理は HttpClient の仕事connect()時点では OutputStream を作るが InputStream はまだ。例えば HttpURLConnection.getResponseCode() のとき、内部で HttpURLConnection.getInputStream() が呼ばれる。

Socket の生成

HttpURLConnection.connect() -> HttpClient.openServer() -> NetworkClient.doConnect() -> new java.net.Socket() : impl = java.net.SocksSocketImpl (extends PlainSocketImpl)

Socket のクローズ

HttpURLConnection を disconnect() し忘れた場合、AbstractPlainSocketImpl で、finalize 時に Socket をクローズしている。よってGC時にクローズされる。(disconnect() 時の keepalive キャッシュの条件がイマイチ分からない。。。)

InputStream を最後まで読まず、disconnect() すると サーバ側で ClientAbortException が起こる。disconnect() せずに connection を放棄すると、GC時に突然 ClientAbortException が起こる(かもしれない)。

    protected void finalize() throws IOException {
        close();
    }
    protected void close() throws IOException {
        synchronized(fdLock) {
            if (fd != null) {
                if (!stream) {
                    ResourceManager.afterUdpClose();
                }
                if (fdUseCount == 0) {
                    if (closePending) {
                        return;
                    }
                    closePending = true;
                    /*
                     * We close the FileDescriptor in two-steps - first the
                     * "pre-close" which closes the socket but doesn't
                     * release the underlying file descriptor. This operation
                     * may be lengthy due to untransmitted data and a long
                     * linger interval. Once the pre-close is done we do the
                     * actual socket to release the fd.
                     */
                    try {
                        socketPreClose();
                    } finally {
                        socketClose();
                    }
                    fd = null;
                    return;
                } else {
                    /*
                     * If a thread has acquired the fd and a close
                     * isn't pending then use a deferred close.
                     * Also decrement fdUseCount to signal the last
                     * thread that releases the fd to close it.
                     */
                    if (!closePending) {
                        closePending = true;
                        fdUseCount--;
                        socketPreClose();
                    }
                }
            }
        }
    }
トラックバック - http://d.hatena.ne.jp/tokobayashi/20150319

2015-03-18 スコアリングルールを書く

[]スコアリングルールを書く スコアリングルールを書くを含むブックマーク

http://d.hatena.ne.jp/tokobayashi/20150312 で、Cheap time scheduling には DRL が無いと書きましたが、それを追加するための JIRA がオープンされています

Add Drools score rules for example CheapTime Scheduling https://issues.jboss.org/browse/PLANNER-275

で、やってみました。これがなかなか大変でした!

準備

親切にも準備/手順を JIRA に書いてくれています

手順

  • cheapTimeScoreRules.drl を作成ます
  • cheapTimeSolverConfig.xml で、DRLを使うようにします
  • cheapTimeScoreRules.drl に制約を記述ます
  • CheapTimeApp を実行します
  • cheapTimeSolverConfig.xml で assertionScoreDirectorFactory を有効にし(CheapTimeEasyScoreCalculator)、environmentMode で FAST_ASSERT 及び FULL_ASSERT を設定して CheapTimeApp を実行します。Exception が出たら直します
  • environmentMode 無しで CheapTimeApp を5分間走らせ、average calculate count per second (ACC) を確認ますログ最後に出る)。

実際にやってみると。。。

  • まず新規クラス作成せずに全ての制約を書けるかがんばってみる -> 無理!
  • ルール効果確認するために小さいデータセットを作る(sample01.xml編集)。効果確認のため、ちょいちょい変更したりする(特定期間の powerPriceMicros をガッと上げるとか)。
  • 簡単にテストできるよう CheapTimeHelloWorld 作る。でもGUIもすごく役に立つ!
  • 期間単位評価する必要があるので MachinePeriodPart 導入
  • MachinePeriodPart の生成のために Period 導入
  • Idle vs Spin には2段階計算必要 -> IdleCost 導入
  • ShadowVariable を使うにはドメインモデル修正が入るので、今回はやめた。代わりに insertLogical を使う。
  • from collect / accumulate はかなり使う
  • できたっぽいよ!
  • FULL_ASSERT すると。。。Exception でた。 score corruption だって
    • assertionScoreDirectorFactory マジ素晴らしい。正しい CheapTimeEasyScoreCalculator と比較して、スコアが違うと怒ってくれる
    • 今回は CheapTimeEasyScoreCalculator が既にあったので比較できたけど、新規プロジェクトでも、先に EasyJava の ScoreCalculator を作っておくと、DRL や IncrementalJava の実装が楽になる。2人で並行して作って、相互チェックなんてのもアリだろう
    • エラーメッセージで、easyScoreCalculator は constraintMatchEnabled = false なので、analysis が出ないって言われるけど、analysis はそれほど重要ではないと思われる。 assertionScoreDirectorFactory を incrementalScoreCalculatorClass に差し替えれば analysis が出るけど、同じ粒度名前で制約を実装していないと、比較ができない
  • で、その score corruption だけど、scoreHolder.addHardConstraintMatch()をルールのRHS内で複数回呼んだせいで発生していた。
rule "resourceCapacity"
    when
        $machinePeriodPart : MachinePeriodPart()
    then
        for (int resourceAvailable : $machinePeriodPart.getResourceAvailableList()) {
            if (resourceAvailable < 0) {
                scoreHolder.addHardConstraintMatch(kcontext, resourceAvailable);
            }
        }
end

計算してから、一回だけ呼ぶようにすればいい

        long resourceAvailableTotal = 0;
        for (int resourceAvailable : $machinePeriodPart.getResourceAvailableList()) {
            if (resourceAvailable < 0) {
                resourceAvailableTotal += resourceAvailable;
            }
        }
        scoreHolder.addHardConstraintMatch(kcontext, resourceAvailableTotal);

RHSで複数回 addHardConstraintMatch を呼ぶと、LongConstraintUndoListener.undo() のせいでスコアがおかしくなる。フォーラム確認して、仕様ならドキュメント化したほうがよさそう。 https://issues.jboss.org/browse/PLANNER-284 も関連してるかな。

    public void addHardConstraintMatch(RuleContext kcontext, final long weight) {
        hardScore += weight;
        registerLongConstraintMatch(kcontext, 0, weight, new LongConstraintUndoListener() {
            public void undo() {
                hardScore -= weight;
            }
        });
    }
  • ACC は。。。 sample01.xmlテスト。。。 ぐはあ、遅え! ACC=376
    • ちなみに CheapTimeEasyScoreCalculator : ACC = 5867
    • CheapTimeIncrementalScoreCalculator : ACC = 177142 (Unbelievable!)
  • さあ、ここからチューニング
    • まずは stepCountLimit=10000 のベンチマーク cheapTimeStepLimitBenchmarkConfig.xml を作る
    • ルールを全部コメントアウト
    • 一個ずつ有効にしながら、ACC の変化を見る
      • period : 5521
      • machinePeriodPart : 1916
      • maximumCapacity : 1376
      • calculateIdleCost : 996
      • startTimeLimitsFrom/startTimeLimitsTo : 1012
      • machinePowerCostActive : 793
      • machinePowerCostOffToActive/machinePowerCostIdleToActive : 750
      • firstBoot : 686
      • taskPowerCost : 427
      • startEarly : 414
    • うーん、machinePeriodPart が大きなボトルネックだけどこれはどうしようもなさそう。ひとつずつ丁寧に見ていくか。。。
      • enum だった STATUS を boolean に変更 : 426
      • LHS の順序を調整 : 442
      • memberOf やめて < > で比較 : 468
      • maximumCapacity に if 入れて不必要な addHard 止める : 462
      • MachinePeriodPart のフィールドから taskAssignmentList を削除 : 458
      • taskPowerCost の計算は MachinePeriodPart ではなく Period で : 600 (影響大!)
      • resourceInShortTotal を MachinePeriodPart 内で計算 : 620
      • CheapTimeApp で 5分計測 -> 670
トラックバック - http://d.hatena.ne.jp/tokobayashi/20150318

2015-03-12 OptaPlanner examples その14

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

Cheap time scheduling

f:id:tokobayashi:20150312155816p:image

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

遂にラスト

タスクマシンに割り当て、消費電力を最小化します。CloudBalance や MachineReassignment に似てます

  • CheapTimeSolution : @PlanningSolution
  • TaskAssignment : @PlanningEntity
    • Machine machine : @PlanningVariable
    • Integer startPeriod : @PlanningVariable
    • Task task

@PlanningVariable は2つ。モデリングシンプルなんだけど、制約の実装が意外と手強い。このサンプルにはDRLがまだ無く、CheapTimeEasyScoreCalculator と CheapTimeIncrementalScoreCalculator が実装されています理解するにはまず CheapTimeEasyScoreCalculator を見よう。

期間(Period)単位リソースの制約や消費電力コスト計算するので、MachinePeriodPart というクラスを導入します

        for (Machine machine : machineList) {
            List<MachinePeriodPart> machinePeriodList = new ArrayList<MachinePeriodPart>(globalPeriodRangeTo);
            for (int period = 0; period < globalPeriodRangeTo; period++) {
                machinePeriodList.add(new MachinePeriodPart(machine, period, resourceListSize));
            }
            machinePeriodListMap.put(machine, machinePeriodList);
        }

リソース計算は MachinePeriodPart 側でやります

        public void addTaskAssignment(TaskAssignment taskAssignment) {
            active = true;
            Task task = taskAssignment.getTask();
            for (int i = 0; i < resourceAvailableList.size(); i++) {
                int resourceAvailable = resourceAvailableList.get(i);
                TaskRequirement taskRequirement = task.getTaskRequirementList().get(i);
                resourceAvailableList.set(i, resourceAvailable - taskRequirement.getResourceUsage());
            }
        }

「休止中は、アイドル状態にしておくか停止/起動するか、安い方を選ぶ」はこのように実装されています

                    if (previousStatus != MachinePeriodStatus.OFF) {
                        idleCostMicros += CheapTimeCostCalculator.multiplyTwoMicros(machine.getPowerConsumptionMicros(),
                                periodPowerPrice.getPowerPriceMicros());
                        if (idleCostMicros > machine.getSpinUpDownCostMicros()) {
                            idleCostMicros = 0L;
                            previousStatus = MachinePeriodStatus.OFF;
                        } else {
                            previousStatus = MachinePeriodStatus.IDLE;
                        }
                    }

そんなに難しそうに見えない?これが CheapTimeIncrementalScoreCalculator ではエライことになります

https://github.com/droolsjbpm/optaplanner/blob/master/optaplanner-examples/src/main/java/org/optaplanner/examples/cheaptime/solver/score/CheapTimeIncrementalScoreCalculator.java

ここでは詳細に説明しませんが、insert と retract に応じたスコアメンテナンスがかなりハードです。

DRLで書けば少なからず楽になるはずです。さてそれは次回。。。